{{template>template:przedmiot|tytul=Jeżyki formalne i złożoność obliczeniowa|prowadzacy=Jerzy Marcinkowski|www=http://www.ii.uni.wroc.pl/~jma/kurs|ects=9|typ=obowiązkowy.O3 (obowiązkowy)|}}
 
====== Jureczki formalne i złożoność obliczeniowa ======

===== Ćwiczenia (2011) =====
  * Lista 1 (8 punktów): [[jfizo:zadanie09.001|zad. 1]], [[jfizo:zadanie09.002|zad. 2]], [[jfizo:zadanie09.003|zad. 3]], [[jfizo:zadanie09.004|zad. 4 (2pkt.)]], [[jfizo:zadanie09.005|zad. 5]], [[jfizo:zadanie09.007|zad. 7]], [[jfizo:zadanie09.009|zad. 9]]. ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista1|print friendly]])
  * Lista 2 (9 punktów): [[jfizo:zadanie09.011|zad. 11]], [[jfizo:zadanie09.012|zad. 12]], [[jfizo:zadanie09.013|zad. 13]], [[jfizo:zadanie11.001|zad. A1]], [[jfizo:zadanie11.002|zad. A2]], [[jfizo:zadanie11.009|zad. A9]], [[jfizo:zadanie11.010|zad. A10]], [[jfizo:zadanie09.022|zad. 22 (2pkt.)]]. ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista2|print friendly]])
  * Lista 3 (8 punktów): [[jfizo:zadanie09.014|zad. 14]], [[jfizo:zadanie09.015|zad. 15]], [[jfizo:zadanie09.016|zad. 16]], [[jfizo:zadanie09.017|zad. 17]], [[jfizo:zadanie09.020|zad. 20]], [[jfizo:zadanie09.024|zad. 24]], [[jfizo:zadanie09.025|zad. 25]], [[jfizo:zadanie09.027|zad. 27]]. ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista3|print friendly]])
  * Lista 4 (11 punktów): [[jfizo:zadanie09.028|zad. 28]], [[jfizo:zadanie09.029|zad. 29]], [[jfizo:zadanie09.030|zad. 30]], [[jfizo:zadanie09.031|zad. 31]], [[jfizo:zadanie09.032|zad. 32]], [[jfizo:zadanie09.39|zad. 39]], [[jfizo:zadanie09.040|zad. 40]], [[jfizo:zadanie09.041|zad. 41]], [[jfizo:zadanie09.042|zad. 42]], [[jfizo:zadanie09.043|zad. 43 (2pkt.)]]. ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista4|print friendly]])
  * Lista 5 (13 punktów): [[jfizo:zadanie11.006|zad. A6]], [[jfizo:zadanie11.007|zad. A7]], [[jfizo:zadanie11.008|zad. A8]], [[jfizo:zadanie09.033|zad. 33]], [[jfizo:zadanie09.034|zad. 34]], [[jfizo:zadanie09.035|zad. 35 (3pkt.)]], [[jfizo:zadanie09.044|zad. 44]], [[jfizo:zadanie09.045|zad. 45]], [[jfizo:zadanie09.046|zad. 46]], [[jfizo:zadanie09.047|zad. 47]], [[jfizo:zadanie09.048|zad. 48]]. ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista5|print friendly]])
  * Lista 6 (12 punktów): [[jfizo:zadanie09.049|zad. 49]], [[jfizo:zadanie09.050|zad. 50]], [[jfizo:zadanie09.051|zad. 51]], [[jfizo:zadanie09.052|zad. 52]], [[jfizo:zadanie09.053|zad. 53 (2pkt.)]], [[jfizo:zadanie09.054|zad. 54]], [[jfizo:zadanie09.055|zad. 55]], [[jfizo:zadanie09.056|zad. 56]], [[jfizo:zadanie09.057|zad. 57]], [[jfizo:zadanie09.065|zad. 65]], [[jfizo:zadanie09.066|zad. 66]]. ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista6|print friendly]])
  * Lista 7 (12 punktów): [[jfizo:zadanie09.060|zad. 60]], [[jfizo:zadanie09.061|zad. 61 (2pkt.)]], [[jfizo:zadanie09.062|zad. 62]], [[jfizo:zadanie09.063|zad. 63]], [[jfizo:zadanie09.064|zad. 64]], [[jfizo:zadanie09.068|zad. 68 (2pkt.)]], [[jfizo:zadanie09.069|zad. 69]], [[jfizo:zadanie09.070|zad. 70]], [[jfizo:zadanie09.071|zad. 71]], [[jfizo:zadanie09.072|zad. 72]]. ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista7|print friendly]])
  * Lista 8 (10 punktów): [[jfizo:zadanie09.073|zad. 73]], [[jfizo:zadanie09.074|zad. 74 (2pkt.)]], [[jfizo:zadanie09.075|zad. 75]], [[jfizo:zadanie09.078|zad. 78]], [[jfizo:zadanie09.079|zad. 79]], [[jfizo:zadanie09.080|zad. 80 (2pkt.)]], [[jfizo:zadanie09.081|zad. 81 (2pkt.)]]. ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista8|print friendly]])
  * Lista 9 (14 punktów): [[jfizo:zadanie09.082|zad. 82 (2pkt.)]], [[jfizo:zadanie09.083|zad. 83 (2pkt.)]], [[jfizo:zadanie11.017|zad. A17]], [[jfizo:zadanie11.018|zad. A18]], [[jfizo:zadanie09.088|zad. 88]], [[jfizo:zadanie09.089|zad. 89 (2pkt.)]], [[jfizo:zadanie09.091|zad. 91 (2pkt.)]], [[jfizo:zadanie09.092|zad. 92 (2pkt.)]], [[jfizo:zadanie09.093|zad. 93]]. ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista9|print friendly]])
  * Lista 10 (10 punktów, na 16 maja): [[jfizo:zadanie09.085|zad. 85]], [[jfizo:zadanie09.086|zad. 86]], [[jfizo:zadanie09.086|zad. 87]], [[jfizo:zadanie09.090|zad. 90 (2 pkt.)]], [[jfizo:zadanie09.098|zad. 98]], [[jfizo:zadanie09.099|zad. 99]], [[jfizo:zadanie09.108|zad. 108]], [[jfizo:zadanie09.111|zad. 111]], [[jfizo:zadanie09.112|zad. 112]]. ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista10|print friendly]])
  * Lista 11 (11 punktów): [[jfizo:zadanie09.094|zad. 94 (2 pkt.)]], [[jfizo:zadanie09.095|zad. 95]], [[jfizo:zadanie09.096|zad. 96 (2 pkt.)]], [[jfizo:zadanie09.097|zad. 97]], [[jfizo:zadanie09.100|zad. 100 (2 pkt.)]], [[jfizo:zadanie09.101|zad. 101]], [[jfizo:zadanie09.102|zad. 102]], [[jfizo:zadanie09.104|zad. 104]]. ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista11|print friendly]])
  * Lista 12 (10 punktów): [[jfizo:zadanie09.116|zad. 116]], [[jfizo:zadanie09.120|zad. 120 (2 pkt.)]], [[jfizo:zadanie09.121|zad. 121]], [[jfizo:zadanie09.123|zad. 123]], [[jfizo:zadanie09.124|zad. 124]], [[jfizo:zadanie09.131|zad. 131]], [[jfizo:zadanie09.133|zad. 133]], [[jfizo:zadanie09.134|zad. 134]], [[jfizo:zadanie09.135|zad. 135]]. ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista12|print friendly]])
  * Lista 13 (11 punktów): [[jfizo:zadanie09.122|zad. 122 (3 pkt.)]], [[jfizo:zadanie09.127|zad. 127 (2 pkt.)]], [[jfizo:zadanie09.128|zad. 128]], [[jfizo:zadanie09.129|zad. 129 (2 pkt.)]], [[jfizo:zadanie09.130|zad. 130 (3 pkt.)]]. ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista13|print friendly]])
  * Lista 14 (8 punktów): [[jfizo:zadanie09.105|zad. 105]], [[jfizo:zadanie09.106|zad. 106]], [[jfizo:zadanie09.107|zad. 107]], [[jfizo:zadanie09.109|zad. 109]], [[jfizo:zadanie09.113|zad. 113]], [[jfizo:zadanie09.117|zad. 117]], [[jfizo:zadanie09.118|zad. 118]], [[jfizo:zadanie09.119|zad. 119]]. ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista14|print friendly]])
  * Lista 15 (8 punktów): [[jfizo:zadanie11.022|zad. A22]], [[jfizo:zadanie11.023|zad. A23]], [[jfizo:zadanie11.024|zad. A24]], [[jfizo:zadanie11.025|zad. A25]], [[jfizo:zadanie11.026|zad. A26]], [[jfizo:zadanie11.027|zad. A27]], [[jfizo:zadanie11.032|zad. A32 (2 pkt.)]]. ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista15|print friendly]])

==== Prognozowane progi ====
Maksymalna liczba punktów do zdobycia: **155**.

Progi:
| dst | a+ 52.70 pkt. |
| dst+| a+ 65.10 pkt. |
| db  | a+ 77.50 pkt. |
| db+ | a+ 89.90 pkt. |
| bdb | a+102.30 pkt. |
gdzie $a,b,c,d,e\in \{-2,-1,0,1,2\}$

==== Kod generujący tą cholerną tabelkę (dostępny w "edytuj")====
# -*- coding: utf-8 -*-
import sys
x = int(sys.argv[1])
m = ["dst ", "dst+", "db  ", "db+ ", "bdb "]
r = [0.34, 0.42, 0.5, 0.58, 0.66]

print "==== Prognozowane progi ===="
print "Maksymalna liczba punktów do zdobycia: **%d**." % x
print
print "Progi:"
for i in xrange(5):
    print "| %s| a+%6.2f pkt. |" % (m[i], x * r[i])
print "gdzie $a,b,c,d,e\in \{-2,-1,0,1,2\}$"
TODO zamiast 'a' czasami jest też 'b', 'c', ...

===== Ćwiczenia (2010) =====
  * Lista 1: [[jfizo:zadanie09.001|zad. 1]], [[jfizo:zadanie09.002|zad. 2]], [[jfizo:zadanie09.005|zad. 5]]. (języki regularne, DFA) ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista1|print friendly]])
  * Lista 2: [[jfizo:zadanie09.003|zad. 3]], [[jfizo:zadanie09.004|zad. 4]], [[jfizo:zadanie09.006|zad. 6]], [[jfizo:zadanie09.018|zad. 18]], [[jfizo:zadanie09.019|zad. 19]], [[jfizo:zadanie09.020|zad. 20]], [[jfizo:zadanie09.024|zad. 24]]. (języki regularne, NFA) ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista2|print friendly]])
  * Lista 3: [[jfizo:zadanie09.010|zad. 10]], [[jfizo:zadanie09.011|zad. 11]], [[jfizo:zadanie09.012|zad. 12]], [[jfizo:zadanie09.013|zad. 13]], [[jfizo:zadanie09.015|zad. 15]], [[jfizo:zadanie09.016|zad. 16]], [[jfizo:zadanie09.017|zad. 17]], [[jfizo:zadanie09.021|zad. 21]], [[jfizo:zadanie09.022|zad. 22]], [[jfizo:zadanie09.023|zad. 23]]. (języki regularne, wyrażenia regularne) ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista3|print friendly]])
  * Lista 4: [[jfizo:zadanie09.025|zad. 25]], [[jfizo:zadanie09.027|zad. 27]], [[jfizo:zadanie09.028|zad. 28]], [[jfizo:zadanie09.029|zad. 29]], [[jfizo:zadanie09.031|zad. 31]], [[jfizo:zadanie09.032|zad. 32]], [[jfizo:zadanie09.033|zad. 33]], [[jfizo:zadanie09.035|zad. 35]], [[jfizo:zadanie09.040|zad. 40]]. (języki bezkontekstowe) ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista4|print friendly]])
  * Lista 5: [[jfizo:zadanie09.036|zad. 36]], [[jfizo:zadanie09.037|zad. 37]], [[jfizo:zadanie09.038|zad. 38]], [[jfizo:zadanie09.042|zad. 42]], [[jfizo:zadanie09.043|zad. 43]], [[jfizo:zadanie09.044|zad. 44]], [[jfizo:zadanie09.045|zad. 45]], [[jfizo:zadanie09.046|zad. 46]], [[jfizo:zadanie09.047|zad. 47]], [[jfizo:zadanie09.048|zad. 48]], [[jfizo:zadanie09.049|zad. 49]]. (automaty ze stosem, jeżyki rekurencyjne i rekurencyjnie przeliczalne) ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista5|print friendly]])
  * Lista 6 (15 puntów): [[jfizo:zadanie09.050|zad. 50]], [[jfizo:zadanie09.051|zad. 51]], [[jfizo:zadanie09.052|zad. 52]], [[jfizo:zadanie09.053|zad. 53]], [[jfizo:zadanie09.054|zad. 54]], [[jfizo:zadanie09.055|zad. 55]], [[jfizo:zadanie09.056|zad. 56]], [[jfizo:zadanie09.057|zad. 57]], [[jfizo:zadanie09.058|zad. 58]], [[jfizo:zadanie09.060|zad. 60]], [[jfizo:zadanie09.061|zad. 61]], [[jfizo:zadanie09.065|zad. 65]], [[jfizo:zadanie09.066|zad. 66]]
  * Lista 7 (10 punktów): [[jfizo:zadanie09.068|zad. 68]], [[jfizo:zadanie09.069|zad. 69]], [[jfizo:zadanie09.070|zad. 70]], [[jfizo:zadanie09.078|zad. 78]], [[jfizo:zadanie09.079|zad. 79]], [[jfizo:zadanie09.080|zad. 80]], [[jfizo:zadanie09.081|zad. 81]] 
  * Lista 8 (10 punktów): [[jfizo:zadanie09.071|zad. 71]], [[jfizo:zadanie09.072|zad. 72]], [[jfizo:zadanie09.073|zad. 73]], [[jfizo:zadanie09.074|zad. 74]], [[jfizo:zadanie09.075|zad. 75]], [[jfizo:zadanie09.076|zad. 76]], [[jfizo:zadanie09.077|zad. 77]], [[jfizo:zadanie09.082|zad. 82]], 
  * Lista 9 (10 punktów): [[jfizo:zadanie09.083|zad. 83]], [[jfizo:zadanie09.085|zad. 85]], [[jfizo:zadanie09.086|zad. 86]], [[jfizo:zadanie09.087|zad. 87]], [[jfizo:zadanie09.088|zad. 88]], [[jfizo:zadanie09.089|zad. 89]], [[jfizo:zadanie09.090|zad. 90]] ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista9|print friendly]])
  * Lista 10: [[jfizo:zadanie09.091|zad. 91]], [[jfizo:zadanie09.092|zad. 92]], [[jfizo:zadanie09.093|zad. 93]], [[jfizo:zadanie09.094|zad. 94]], [[jfizo:zadanie09.095|zad. 95]], [[jfizo:zadanie09.105|zad. 105]], [[jfizo:zadanie09.106|zad. 106]], [[jfizo:zadanie09.107|zad. 107]] ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista10|print friendly]])
  * Lista 11: [[jfizo:zadanie09.096|zad. 96]], [[jfizo:zadanie09.097|zad. 97]], [[jfizo:zadanie09.098|zad. 98]], [[jfizo:zadanie09.099|zad. 99]], [[jfizo:zadanie09.100|zad. 100]], [[jfizo:zadanie09.104|zad. 104]], [[jfizo:zadanie09.114|zad. 114]] ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista11|print friendly]])
  * Lista 12: [[jfizo:zadanie09.110|zad. 110]], [[jfizo:zadanie09.111|zad. 111]], [[jfizo:zadanie09.112|zad. 112]], [[jfizo:zadanie09.113|zad. 113]], [[jfizo:zadanie09.117|zad. 117]], [[jfizo:zadanie09.118|zad. 118]], [[jfizo:zadanie09.119|zad. 119]], [[jfizo:zadanie09.120|zad. 120]] ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista12|print friendly]])
  * Lista 13: [[jfizo:zadanie09.109|zad. 109]], [[jfizo:zadanie09.121|zad. 121]], [[jfizo:zadanie09.123|zad. 123]], [[jfizo:zadanie09.124|zad. 124]], [[jfizo:zadanie09.126|zad. 126]], [[jfizo:zadanie09.133|zad. 133]], [[jfizo:zadanie09.135|zad. 135]] ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista13|print friendly]])
  * Lista 14 (9 puntów): [[jfizo:zadanie09.101|zad. 101]], [[jfizo:zadanie09.102|zad. 102]], [[jfizo:zadanie09.108|zad. 108]], [[jfizo:zadanie09.122|zad. 122]], [[jfizo:zadanie09.125|zad. 125]], [[jfizo:zadanie09.134|zad. 134]] ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista14|print friendly]])
  * Lista 15 (9 puntów): [[jfizo:zadanie09.127|zad. 127]], [[jfizo:zadanie09.128|zad. 128]], [[jfizo:zadanie09.129|zad. 129]], [[jfizo:zadanie09.130|zad. 130]], [[jfizo:zadanie09.131|zad. 131]] ([[jezyki_formalne_i_zlozonosc_obliczeniowa:lista15|print friendly]])

==== Progi ====
Maksymalna liczba punktów do zdobycia: **143**.

| dst | 49 (+2) pkt |
| dst+ | 61 (-2) pkt |
| db | 72 (-1) pkt |
| db+ | 83 (0) pkt |
| bdb | 95 (0) pkt |

===== Teoria języków formalnych (rozdzialy 1, 2, 3, 4) =====
  * Jeżyki regularne
  * Jeżyki bezkontekstowe (CFL)
===== Rozstrzygalność i nierozstrzygalność (rozdzialy 5, 6, 7) =====
  * Jeżyki rekurencyjne (rozstrzygalne, obliczalne)
  * Jeżyki rekurencyjnie przeliczalne (RE)
===== Złożoność obliczeniowa (rozdzialy 8, 9, 10, 11) =====
  * PTIME
    * HORNSAT
  * NP (co-NP etc.). Lista problemow NP-Complete:
    * $CLIQUE_{n/2}$ - czy w grafie nieskierowanym o $n$ wierzcholkach istnieje clique o $>=n/2$ wierzcholkach.
    * $3SAT$ - czy formula w postaci $3CNF$ jest spelnialna (rowniez $nSAT$, $n >= 3$)
    * $3COL$ - czy graf jest trojkolorowalny
    * [[http://cs482.elliottback.com/lecture-25-hamiltonian-cycle-problem/|Hamiltonian Cycle]] - czy w grafie istnieje Cykl Hamiltona
    * Travelling Salesman - given the costs and a number x, decide whether there is a round-trip route cheaper than x
    * set cover
    * node cover
    * idependent set - problem znalezienia najwiekszego podzbioru grafu o tej wlasciwosci, ze zadne dwa wierzcholki znalezionego podgrafu ze soba nie sasiaduja
    * pokrycie niezaleznymi podzbiorami
  * PSPACE
    * $TQBF$ - czy formula w postaci Qualified Boolean Formula jest prawdziwa
    * $TOTRE$ - czy wyrazenie regularne jest rowne $\Sigma^*$
  * EXPTIME
  * Jeżyki nieelementarne

  * Relacje:
    * $SPACE(f(n)) = coSPACE(f(n))$ - wystarczy zanegowac wynik algorytmu
      * $PSPACE = coPSPACE$
    * $NSPACE(f(n)) \subseteq SPACE( (f(n))^2) \; \mathrm{dla} \; f(n) \geq \log n$ ([[http://en.wikipedia.org/wiki/Savitch%27s_theorem|twierdzenie Savitcha]])
      * $PSPACE = NPSPACE$
      * $NL \subseteq L^2$
    * $TIME(f(n)) \subseteq SPACE(f(n))$, $NTIME(f(n)) \subseteq NSPACE(f(n))$
      * $P \subseteq PSPACE$
      * $NP \subseteq PSPACE$
      * $coNP \subseteq PSPACE$
    * $SPACE(f(n)) \subseteq TIME(f(n)\cdot 2^{O(f(n))})$
      * $PSPACE \subseteq EXPTIME$
      * $L \subseteq P$
    * $P \not= EXPTIME$

===== Listy zadań i egzaminy =====
  * {{:jfizo:aneks-11.pdf|Aneks do zbioru}} (2011)
  * {{jfizo:zbior-09.pdf|Zbiór zadań}} (2009)
  * {{jfizo:zbior2008.pdf|Zbiór zadań}} (2008)
  * {{jfizo:zbior-07.ps|Zbiór zadań}} (2007)
  * [[jfizo:zbior_zadan|Rozwiązania]]
  * [[jfizo:egzaminy|Egzaminy]]

===== Materiały =====
  * {{:jfizo:jfa.pdf|Jeżyki formalne i automaty Marcina Kubicy (mimuw)}}
  * {{:jfizo:jfizo-rozwiazania.pdf|Rozwiązania niektórych zadań Arkadiusza Janickiego}}
  * {{:jfizo:jfizo-notatki-desp.pdf|Notatki Mietka Bąka z 2008 roku}}
  * {{:jfizo:jf-skrypt-ako.pdf|Skrypt AKO}}
===== Literatura =====
  * Michael Sipser - Introduction to the Theory of Computation (Wstęp do teorii obliczeń)
  * [[http://peb.pl/nauka-i-technika/189892-rapidshare-wprowadzenie-do-teorii-automatow-jezykow.html|Hopcroft, Ullman - Wprowadzenie do teorii automatów języków i obliczeń]].

{{tag>przedmioty_obowiazkowe lato_2010}} 
{{tag>przedmioty_obowiazkowe lato_2011}}