Vyučující: Ondřej Čepek (
web se slajdy)
Předmět má za cíl «naučit základy z teorie složitosti algoritmů, včetně NP-úplnosti a převoditelnosti». Jedná se o přednášku se cvičeními ob týden.
Cvičení jsou od druhého týdne.
Staré (kompletní) slajdy na webu se neshodují se současným sylabem a budou průběžně aktualizované. Při zobrazení v OpenOffice.org jsou navíc poměrně velké části některých současných slajdů prázdné, přednášející slíbíl, že tam umístí i PDF. Update: V OOo 3.1.1 už je to v pořádku, jen je třeba mít správný (resp. špatný) font Symbol (takový co odpovídá Microsoftímu), aby se Vám zobrazily všechny symboly. Tak pozor na to.
Jestli máte občas trochu zmatek, jak přesně vypadá zadání které z běžných NP-úplných úloh, popletete jednu s druhou nebo nemáte spojené české a anglické názvy, pomůže vám tento přehled (používám v něm stejné legrační zkratky jako Čepek):
Pozor: Je to jen velmi orientační. Míchám optimalizační verze a rozhodovací verze a bylo by dobré pro úplnost popsat přesně vše a doplnit další souvislosti a vlastnosti problémů (asi v tabulce). Klidně se toho můžete někdo zhostit:).