Týden 13¶

(instrukce k domácímu procvičování)

Úloha 1 [B]

Sbírka, cvičení 81.

Úloha 2 [B]

Sbírka, cvičení 83.

Úloha 3 [C]

Sbírka, cvičení 82.

Bonus: Úloha 4 [A-C]

Sbírka, cvičení 85.

Bonus: Úloha 5 [A-C]

Sbírka, cvičení 89.

Bonus: Úloha 6 [A-C]

Projděte si celou složitost a napište si stručné shrnutí (pár bodů, myšlenková mapa, obrázek, cokoliv). Zaměřte se na to, co nového jste se naučili o světě, ve kterém žijeme a čím vás třeba teorie složitosti překvapila. Pokud narazíte na nějaké nejasnosti, otázky nebo byste chtěli něco sdílet se spolužáky, neváhejte použít diskuzní fórum.

Bonus: Úloha 7 [A-C]

Vytvořte si přípravy k relevantním státnicovým otázkám. Pro většinu to bude nejspíš otázka č. 15 Složitost (Složitost algoritmu versus složitost problému. Složitostní třídy (P, NP, PSPACE) a vztahy mezi nimi, příklady problémů z jednotlivých tříd. Těžkost a úplnost problému v dané třídě, polynomiální redukce problémů, NP-úplné úlohy.) a část otázky 14 Korektnost a složitost algoritmu (konkrétně Asymptotická složitost, O-notace.).