Vyčíslitelnost a složitost

Přednášky:

Uvod ke kursu. Slozitost algoritmu. Model RAM.

Odhady slozitosti. Nejhorsí vs. prumerný pripad. Analyza vybranych algoritmu.
Metoda `rozdel a panuj'.

Analyza dalsich algoritmu. `Greedy' algoritmy. Metoda dynamickeho programovani.


Problemy, tridy slozitosti problemu, horni a dolní odhady. Turinguv stroj.

Turingovy stroje a dalsi vypocetni modely; jejich vzajemna `polynomialni'
simulace.

Trida P (=PTIME) jako aproximace tridy prakticky zvladnutelných problemu. Trida
NP (=NPTIME). Polynomialni preveditelnost. NP-uplnost.

NP-uplne problemy. Otevrena otazka, zda P=NP.

Dalsi tridy casove i prostorove slozitosti a jejich vzajemne vztahy.
Dokazatelne nezvladnutelne problemy.

Church-Turingova teze. Rozhodnutelnost a castecna rozhodnutelnost problemu.

Univerzalni Turinguv stroj. Rekurzivni a rekurzivne spocetne mnoziny (jazyky).
Rekurzivni a castecne rekurzivni funkce. Metoda diagonalizace.

Nerozhodnutelnost problemu zastaveni. Dalsi nerozhodnutelne problemy. Riceova
věta.


Dalsi temata teorie algoritmu.