Sylabus
1) Turingovy stroje a jejich varianty. Churchova-Turingova teze
2) Halting problém.
3) RAM a jeho ekvivalence s Turingovými stroji. Algoritmicky vyčíslitelné funkce.
4) Rekurzivní a rekurzivně spočetné jazyky a množiny a jejich vlastnosti.
5) 1-převoditelnost a m-převoditelnost, 1-úplné a m-úplné množiny.
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 - ekvivalence tříd PSPACE a NPSPACE.
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) Pseudopolynomiální algoritmy a silná NP-úplnost.
13) Aproximace NP-těžkých optimalizačních úloh. Aproximační algoritmy a schémata.
14) Třídy co-NP a #P.
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.