Vyčíslitelnost a složitost

Aktuální informace k předmětu, zápočtům, výukové materiály atd. najdete zde.

Seznam cvičení

  1. Turingův stroj (TS) a příklady TS
    • Navrhněte TS, který ze zadaného slova nad abecedou {a,b} umaže od začátku i od konce nejdelší možné stejně dlouhé úseky znaků a(kde umazání samozřejmě znamená přepsání znaky 2). Tedy např. k vstupnímu slovu aaababaastroj nechá jako výstup slovo abab, kdežto vstupní slovo aaabab nezmění; ze slova aaa zbude ε. Řešení na str. 194 v [JAN-TI].
    • Domácí úkol: Navrhněte TS, který přijímá jazyk {w#w | w∈{a,b}*}.
  2. Simulace variant TS
    • Dokažte, že k-páskový TS jde simulovat pomocí (standardního) jednopáskového TS. Idea řešení na str. 177 v Introduction to the Theory of Computation od M. Sipsera (3. edice).
    • Domácí úkol: dokažte, že TS s dvoudimenzionální páskou lze simulovat pomocí (standardního) jednopáskového TS.
  3. Nerozhodnutelnost problému zastavení

    • Problém DHP je varianta problému zastavení, kde vstup je kód TS M, tedy <M> a otázkou je, zda se M zastaví pro vstup <M> svého vlastního kódu.

      Dokažte, že problém DHP je nerozhodnutelný. Pomocí něj pak dokažte, že je nerozhodnutelný i HP (klasický problém zastavení). Řešení na str. 211 v [JAN-TI].

    • Domácí úkol: nechť k-PDA je zásobníkový automat s k zásobníky, kde k-PDA definujeme jako P=(Q,Σ,Γ,δ,q0,​Z0​,F), s přechodovou funkcí δ: Q × (Σ ∪ {ε}) × Γk → 2Q × (Γ*)k. Takže 0-PDA je vlastně NFA, 1-PDA je klasický PDA jak jej známe.

      Dokažte, že 2-PDA dovede simulovat TS, a tedy je silnější model, než 1-PDA (není třeba psát celou konstrukci, jde hlavně o ideu). Má smysl uvažovat 3-PDA?

  4. Částečně rozhodnutelné jazyky a převoditelnost
    • Dokažte, že {<A> | A je takový DFA, že L(A)=∅} je rozhodnutelný. Řešení najdete na str. 196 v Introduction to the Theory of Computation od M. Sipsera (3. edice).
    • Dokažte, že jazyk {<M> | M je takový TS, že ε∈L(M)} je rekurzivně spočetný a zároveň není rozhodnutelný. Nerozhodnutelnost je popsána v teorému 5.8.2 zde.

    • Domácí úkol: dokažte, že jazyk {<M> | M je takový TS, že L(M) je regulární} není rozhodnutelný.

  5. Riceova věta (měl profesor Jančar)
  6. Státní svátek
  7. První zápočtový test
  8. Časová složitost algoritmu
    • Porovnání průběhu funkcí (první úkol z 2. ukázkového testu zde).

    • Domácí úkol: dokažte, že rozhodání každého bezkontextového jazyka (reprezentovaného pomocí CFG), patří do PTIME.

  9. Polynomiální redukce
    • Popište polynomiální redukci problému IS ≤p SAT, tj. IS (independent set problem) na SAT. Řešení zde.
    • Popište obě polynomiální redukce mezi problémy HC (Hamiltonovský cyklus) a HK (Hamiltonovská kružnice). Řešení redukce HC ≤p HK zde.

    • Domácí úkol: navrhněte rekudci SAT ≤p DOUBLE-SAT, kde DOUBLE-SAT = {φ | φ má nejméně dvě splnitelné ohodnocení}.

  10. Problém obchodního cestujícího
    • Navrhněte nedeterministický polynomiální algoritmus pro rozhodovací problém obchodního cestujícího TSPdec.
    • Předpokládejme, že máme k dispozici polynomiální algoritmus pro TSPdec a ukažte, že pomocí něj lze v polynomiálním čase vyřešit i optimalizační verzi problému TSP.

    • Domácí úkol: ukažte, například návrhem algoritmu, že třída NP je uzavřená na Kleeneho uzávěr.

  11. TBA
  12. Druhý zápočtový tes (9.12.)
  13. Opravné zápočtové testy (16.12.)
    • 15:00-15:10 Nahlédnutí do 2. testů
    • 15:10-16:10 Oprava 1. testu
    • 16:10-16:20 Přestávka
    • 16:20-17:20 Oprava 2. testu