zktal04062015.pdf - je tam vše, na co jsem si vzpomněl, kdo tam byl, tak třeba má ofocené zadání. Dřív jsem se k tomu bohužel nedostal

Poznámka k příkladům ze tříd: Konkrétně např. otázka č. 4, zde platí, že co-NP je podmnožinou R, proto stačí vzít jakoukoliv NPC úlohu. Ta je v R a není v co-NP. Důležité je u těchto úloh si představit Velký knedlík jazyků.

Poznámka k příkladu 5), správnost algoritmu. V zadání bylo, zda algoritmus vrátí maximální počet hranově disjunktních cest z bodu u do bodu v. Uvedený algoritmus není správný. Problém je v řádku c., pokud existuje hrana. Jelikož není specifikováno, jaká cesta, může to být cesta o maximálním počtu hran. Viz uvedený obrázek z bodu 1 do bodu 4. Existují maximálně dvě hranově disjunktní cesty (1,3,4) a (1,2,4). Pokud jako první se vybere (1,2,3,4), algoritmus vrátí 1, což je špatně.