Vyčíslitelnost a složitost

Kurs seznamuje se zakladnimi pojmy, vysledky a metodami teorie
algoritmu, specialne teorie vycislitelnosti a slozitosti.
Nejprve jsou rekapitulovany obecne metody navrhu algoritmu a
je analyzovana (casova, pametova) slozitost konkretnich algoritmu;
referencnim abstraktnim modelem pocitace je pritom RAM (random
access machine). Pote je diskutovana slozitost problemu
a jsou zavedeny tridy slozitosti. Specialni pozornost je venovana tridam
PTIME a NPTIME; je vysvetlena jejich dulezitost jak z teoretickeho,
tak praktickeho hlediska.
Dale je objasnen pojem algoritmicke nerozhodnutelnosti.
Kurs je pak doplnen strucnou ilustraci aproximacnich,
pravdepodobnostnich a take paralelnich a distribuovanych algoritmu.