Základy složitosti a vyčíslitelnosti

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.