Týden 8¶
(instrukce k domácímu procvičování)
- Úloha 1 [A-B]
- Sbírka, cvičení 29.
- Úloha 2 [B]
- Sbírka, cvičení 32.
- Úloha 3 [A-B]
- Ověřte si, že si pamatujete (a/nebo umíte odůvodnit) uzávěrové vlastnosti rekurzivních a rekurzivně spočetných množin. (Třeba si je vypište a pak zkontrolujte podle učebnice.)
- Úloha 4 [C]
- Sbírka, cvičení 33. Toto je velká úloha na procvičení práce s množinami, vypracujte ji prosím pořádně.
- Úloha 5 [B]
- Nastudujte teorii na příští cvičení: všechny tři Riceovy věty. Doporučení: Zkuste si třeba sami nejprve napsat jejich přesné znění, pak si ho zkontrolujte podle učebnice. Taky je užitečné formulovat vlastními slovy, co tyto věty říkají na intuitivní úrovni - jak byste je třeba stručně vysvětlili kamarádovi, který tento předmět (ještě) neabsolvoval.
- Úloha 6 [B-C]
- Sbírka, cvičení 34a.
- Bonus: Úloha 7 [A-C]
- Sbírka, cvičení 27.
- Bonus: Úloha 8 [A-B]
- Zkuste si sami dokázat první Riceovu větu. Pokud je to pro vás těžké, pomoci může přečtení článku o intuici za Riceovou větou v Pythonu.
- Bonus: Úloha 9 [A-B]
- Dokažte samostatně 2. a 3. Riceovu větu.
- Bonus: Úloha 10 [A-C]
- Dokažte nerekurzivnost množiny z cvičení 34a bez využití Riceovy věty (pomocí redukce).