Jureczki formalne i złożoność obliczeniowa

• Lista 1 (8 punktów): zad. 1, zad. 2, zad. 3, zad. 4 (2pkt.), zad. 5, zad. 7, zad. 9. (print friendly)
• Lista 2 (9 punktów): zad. 11, zad. 12, zad. 13, zad. A1, zad. A2, zad. A9, zad. A10, zad. 22 (2pkt.). (print friendly)
• Lista 3 (8 punktów): zad. 14, zad. 15, zad. 16, zad. 17, zad. 20, zad. 24, zad. 25, zad. 27. (print friendly)
• Lista 4 (11 punktów): zad. 28, zad. 29, zad. 30, zad. 31, zad. 32, zad. 39, zad. 40, zad. 41, zad. 42, zad. 43 (2pkt.). (print friendly)
• Lista 5 (13 punktów): zad. A6, zad. A7, zad. A8, zad. 33, zad. 34, zad. 35 (3pkt.), zad. 44, zad. 45, zad. 46, zad. 47, zad. 48. (print friendly)
• Lista 6 (12 punktów): zad. 49, zad. 50, zad. 51, zad. 52, zad. 53 (2pkt.), zad. 54, zad. 55, zad. 56, zad. 57, zad. 65, zad. 66. (print friendly)
• Lista 7 (12 punktów): zad. 60, zad. 61 (2pkt.), zad. 62, zad. 63, zad. 64, zad. 68 (2pkt.), zad. 69, zad. 70, zad. 71, zad. 72. (print friendly)
• Lista 8 (10 punktów): zad. 73, zad. 74 (2pkt.), zad. 75, zad. 78, zad. 79, zad. 80 (2pkt.), zad. 81 (2pkt.). (print friendly)
• Lista 9 (14 punktów): zad. 82 (2pkt.), zad. 83 (2pkt.), zad. A17, zad. A18, zad. 88, zad. 89 (2pkt.), zad. 91 (2pkt.), zad. 92 (2pkt.), zad. 93. (print friendly)
• Lista 10 (10 punktów, na 16 maja): zad. 85, zad. 86, zad. 87, zad. 90 (2 pkt.), zad. 98, zad. 99, zad. 108, zad. 111, zad. 112. (print friendly)
• Lista 11 (11 punktów): zad. 94 (2 pkt.), zad. 95, zad. 96 (2 pkt.), zad. 97, zad. 100 (2 pkt.), zad. 101, zad. 102, zad. 104. (print friendly)
• Lista 12 (10 punktów): zad. 116, zad. 120 (2 pkt.), zad. 121, zad. 123, zad. 124, zad. 131, zad. 133, zad. 134, zad. 135. (print friendly)
• Lista 13 (11 punktów): zad. 122 (3 pkt.), zad. 127 (2 pkt.), zad. 128, zad. 129 (2 pkt.), zad. 130 (3 pkt.). (print friendly)
• Lista 14 (8 punktów): zad. 105, zad. 106, zad. 107, zad. 109, zad. 113, zad. 117, zad. 118, zad. 119. (print friendly)
• Lista 15 (8 punktów): zad. A22, zad. A23, zad. A24, zad. A25, zad. A26, zad. A27, zad. A32 (2 pkt.). (print friendly)

Maksymalna liczba punktów do zdobycia: 155.

Progi:

gdzie a,b,c,d,e\in \{-2,-1,0,1,2\}

# -*- 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\}” zamiast 'a' czasami jest też 'b', 'c', …

• Lista 1: zad. 1, zad. 2, zad. 5. (języki regularne, DFA) (print friendly)
• Lista 2: zad. 3, zad. 4, zad. 6, zad. 18, zad. 19, zad. 20, zad. 24. (języki regularne, NFA) (print friendly)
• Lista 3: zad. 10, zad. 11, zad. 12, zad. 13, zad. 15, zad. 16, zad. 17, zad. 21, zad. 22, zad. 23. (języki regularne, wyrażenia regularne) (print friendly)
• Lista 4: zad. 25, zad. 27, zad. 28, zad. 29, zad. 31, zad. 32, zad. 33, zad. 35, zad. 40. (języki bezkontekstowe) (print friendly)
• Lista 5: zad. 36, zad. 37, zad. 38, zad. 42, zad. 43, zad. 44, zad. 45, zad. 46, zad. 47, zad. 48, zad. 49. (automaty ze stosem, jeżyki rekurencyjne i rekurencyjnie przeliczalne) (print friendly)
• Lista 6 (15 puntów): zad. 50, zad. 51, zad. 52, zad. 53, zad. 54, zad. 55, zad. 56, zad. 57, zad. 58, zad. 60, zad. 61, zad. 65, zad. 66
• Lista 7 (10 punktów): zad. 68, zad. 69, zad. 70, zad. 78, zad. 79, zad. 80, zad. 81
• Lista 8 (10 punktów): zad. 71, zad. 72, zad. 73, zad. 74, zad. 75, zad. 76, zad. 77, zad. 82,
• Lista 9 (10 punktów): zad. 83, zad. 85, zad. 86, zad. 87, zad. 88, zad. 89, zad. 90 (print friendly)
• Lista 10: zad. 91, zad. 92, zad. 93, zad. 94, zad. 95, zad. 105, zad. 106, zad. 107 (print friendly)
• Lista 11: zad. 96, zad. 97, zad. 98, zad. 99, zad. 100, zad. 104, zad. 114 (print friendly)
• Lista 12: zad. 110, zad. 111, zad. 112, zad. 113, zad. 117, zad. 118, zad. 119, zad. 120 (print friendly)
• Lista 13: zad. 109, zad. 121, zad. 123, zad. 124, zad. 126, zad. 133, zad. 135 (print friendly)
• Lista 14 (9 puntów): zad. 101, zad. 102, zad. 108, zad. 122, zad. 125, zad. 134 (print friendly)
• Lista 15 (9 puntów): zad. 127, zad. 128, zad. 129, zad. 130, zad. 131 (print friendly)

Maksymalna liczba punktów do zdobycia: 143.

• Jeżyki regularne
• Jeżyki bezkontekstowe (CFL)

• Jeżyki rekurencyjne (rozstrzygalne, obliczalne)
• Jeżyki rekurencyjnie przeliczalne (RE)

• 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
  • 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 (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

• Aneks do zbioru (2011)
• Zbiór zadań (2009)
• Zbiór zadań (2008)
• Zbiór zadań (2007)
• Rozwiązania
• Egzaminy

• Jeżyki formalne i automaty Marcina Kubicy (mimuw)
• Rozwiązania niektórych zadań Arkadiusza Janickiego
• Notatki Mietka Bąka z 2008 roku
• Skrypt AKO

• Michael Sipser - Introduction to the Theory of Computation (Wstęp do teorii obliczeń)
• Hopcroft, Ullman - Wprowadzenie do teorii automatów języków i obliczeń.