Sylabus
-
1. Turingovy stroje a jejich varianty. Churchova-Turingova teze -
2. Halting problém a další nerozhodnutelné problémy -
3. RAM a jeho ekvivalence s Turingovými stroji. Algoritmicky vyčíslitelné funkce -
4. Rozhodnutelné a částečně rozhodnutelné jazyky a jejich vlastnosti -
5. m-převoditelnost a m-úplné jazyky -
6. Riceova věta -
7. Nedeterministické Turingovy stroje, základní třídy složitosti, třídy P, NP, PSPACE, EXP -
8. Savičova věta -
9. Věty o deterministické prostorové a časové hierarchii -
10. Polynomiální převoditelnost problémů, pojmy NP-těžkosti a NP-úplnosti -
11. Cook-Levinova věta, příklady NP-úplných problémů, důkazy NP-úplnosti -
12. Třídy co-NP a #P -
13. Parametrizované algoritmy, třída FPT -
14. Hypotézy o exponenciálním čase (ETH, SETH) a podmíněné dolní odhady. -
15. Složitost a kryptografie
Anotace
Přednáška seznamující se základy teorie algoritmů, efektivní vyčíslitelnosti a teorie složitosti. První část přednášky je věnována základům vyčíslitelnosti: Turingovy stroje. RAM. Rekurzivní a rekurzivně spočetné jazyky a množiny.
Algoritmicky nerozhodnutelné problémy. Druhá část přednášky je věnována studiu tříd časové a prostorové složitosti: Ekvivalence PSPACE a NPSPACE. Věty o hierarchiích. Třída NP. Polynomiální převoditelnost problémů.
Důkazy NP-úplnosti. Aproximační algoritmy a schémata.