Týden 10¶
(instrukce k domácímu procvičování)
- Úloha 1 [B]
- Sbírka, cvičení 36.
- Úloha 2 [B]
- Sbírka, cvičení 37, pomocí diagonalizace.
- Úloha 3 [B]
- Sbírka, cvičení 37, pomocí redukce. (Podíváme se na to na příštím cviku, ale doporučuji to fakt aspoň zkusit.)
- Úloha 4 [B]
- Sbírka, cvičení 24. (Taky doporučuji aspoň chvilku se nad tím zamyslet, ale je v pohodě, pokud to nevyřešíte, nebo třeba napíšete jen hlavní nápad.)
- Úloha 5 [B]
- Nastudujte teorii na příští cvičení: časová složitost, asymptotické chování funkcí – “Big O notation” (definice \(\mathcal{O}, \mathcal{o}, \Omega, \omega, \Theta\)).
- Úloha 6 [B]
- Sbírka, cvičení 101.
- Bonus: Úloha 7 [C]
- Pokud chcete zpětnou vazbu ke kompletnímu důkazu využívajícího Ricových vět, sepište podrobný formální důkaz libovolného podpříkladu ze cvičení 24 nebo 29.
- Bonus: Úloha 8 [A-C]
- Sbírka, cvičení 25. (Nápověda: Využijte výsledku ze cvičení 24.)
- Bonus: Úloha 9 [A-C]
- Projděte si celou vyčíslitelnost a napište si shrnutí, např. formou myšlenkové mapy nebo přípravy k státnicové otázce. (Pro většinu to bude nejspíš otázka č. 13, Vyčíslitelnost: Turingův stroj. Problém zastavení. Rozhodnutelnost a částečná rozhodnutelnost, nerozhodnutelnost. Metoda redukce, diagonalizace.) Zkuste formulovat, co jste se nového naučili o světě, ve kterém žijeme, čím vás třeba teorie vyčíslitelnosti 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 10 [A-C]
- Sbírka, cvičení 26.
- Bonus: Úloha 11 [A-C]
- Sbírka, cvičení 38.