Vyčíslitelnost a složitost 1 (Vyčíslitelnost a složitost) – VYSL1, XVYS1, 7VYS1
Vyčíslitelnost a složitost 2 (Vyčíslitelnost a složitost 2) – VYSL2, XVYS2
Základní opora Vyčíslitelnost a složitost
Balíček dodatkových materiálů pro VYSL1 nebo http://web.osu.cz/~Habiballa/opory/vysl1pack.zip
Záznamy přednášek v systému Mediasite
Balíček dodatkových materiálů pro VYSL2 nebo http://web.osu.cz/~Habiballa/opory/vysl2pack.zip
| Požadavky na studenta |
| V prezenčním studiu 2 testy za celkem 60 bodů a aktivity na cvičení za 40 bodů na konci semestru. V kombinovaném a distančním studiu 4 korespondenční úkoly za celkem 100 bodů. |
| Přehled probírané látky |
| 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. |
| Literatura |
| Základní: Habiballa, H. Vyčíslitelnost a složitost, OU Ostrava, 2013.. Základní: Habiballa, H. Úvod do informatiky, OU Ostrava, 2013.. Rozšiřující: U. Manber. Introduction to Algorithms, Addison-Wesley.. Rozšiřující: Aho, A., Hopcroft, J., Ullman, J. The design and analysis of computer algorithms, Addison-Wesley, 1974.. Doporučená: Jančar P. JANČAR, PETR Teoretická informatika. VŠB TU Ostrava http://www.cs.vsb.cz/jancar/TEORET-INF/teoret-inf.htm Doporučená: Černá, I. Úvod do teorie složitosti, FI MUNI, 1993. |