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.
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.