1. Opakování intuitivních pojmů algoritmické vyčíslitelnosti, rozhodnutelnosti a částečné rozhodnutelnosti. Exaktní formalizace těchto pojmů. Deterministické Turingovy stroje (DTM), příklady. Univerzální Turingův stroj.
2. Problém zastavení a jeho nerozhodnutelnost. Další nerozhodnutelné problémy, převoditelnost problémů. Churchova teze. Důkazy nerozhodnutelnosti. Enumerace Turingových strojů. Riceova věta.
3. Algoritmy a jejich složitost. Třídy časové a prostorové složitosti. Problémy a jejich složitost. Složitost algoritmu jako horní odhad složitosti problému. Třídy časové složitosti. Strukturální složitost. Příklady výpočtů složitosti problémů.
4. Nedeterministické Turingovy stroje (NDTM), příklady NDTM. Jazyk akceptovatelný NDTM. Změna časové a prostorové složitosti pří přechodu od NDTM k DTM. Třída P (=PTIME) a třída NP (=NPTIME) a jejich robustnost vůči výpočetním modelům. Příklady NP problémů. Polynomiální redukovatelnost problémů (jazyků).
5. NP-úplné problémy. Otevřená otázka, zda P=NP. Problém SAT a jeho náležení k třídě NP. Idea důkazu NP-úplnosti problému splnitelnosti booleovských formulí (Cookova věta).
6. Využití polynomiální redukovatelnosti k důkazu NP-úplnosti dalších problémů: 3CNF, k-vrcholové pokrytí, H-batoh, Partition, SubsetSum.
7. Další třídy časové i prostorové složitosti a jejich vzájemné vztahy. Třídy PSPACE, EXPTIME, EXPSPACE. Idea rovnosti PSPACE=NPSPACE (Savitchova věta). Příklady PSPACE-úplných problémů.
8. Primitivně rekurzivní funkce. Částečné rekurzivní funkce. Konstrukce konkrétních funkcí.
9. PL-vyčíslitelné funkce. Model RAM. Důkaz ekvivalence s Turingovými stroji. Věta o rekurzi.
doc. RNDr. PaedDr. Hashim Habiballa, PhD. et Ph.D.
- Učitel: Hashim Habiballa