Základy složitosti a vyčíslitelnosti

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.