NI-ICC: Úvod do výpočetní složitosti
Zápočet je dosažitelný, větší riziko je ústní zkouška. Témata zatím nejsou zveřejněná a budeš muset rozumět teorii, ne jen počítat. Ke cvičením navíc nejsou řešení, proto je kapitoly níže obsahují. Začni první kapitolou, test je od 23. 11.
Kapitoly
Uč se v tomto pořadí. Před testem zvládni kapitoly 1 až 3, pak jdi na redukce a nácvičné testy.
| Kapitola | K čemu je | Čas |
|---|---|---|
| Návrh Turingova stroje | úloha 1, 6 b | 40 min |
| Self-redukce | úloha 2, 6 b | 25 min |
| Modelování jako ILP a SAT | úloha 3, 6 b | 30 min |
| Důkaz NP-úplnosti redukcí | úloha 4, 12 b a ústní | 55 min |
| Nácvičné testy | formát testu | 2× 60 min |
| Teorie k ústní zkoušce | ústní | 60 min |
Jak se z toho učit
- U příkladu si nejdřív zkus odpověď a teprve pak rozklikni nápovědu a řešení.
- Stroje si projdi v krokovači.
- Kvíz dělej bez dívání do textu. Tlačítkem Zkusit znovu ho opakuj.
- Na konci zaškrtni Kapitolu mám prostudovanou. Přehled ti ji pak nabídne k zopakování po 2, 7 a 21 dnech.
- Čemu nerozumíš, označ a přidej poznámku. Stáhneš je na stránce Poznámky a dáš je Claude Code.
Podmínky
- Zápočet: aspoň 10 z 30 bodů v zápočtovém testu. Test se píše mimo výuku mezi 23. 11. a 4. 12.
- Zkouška: ústní, seznam témat bude zveřejněn.
Není jasné, jak se test promítá do výsledné známky. Zeptej se na cvičení.
Cesta k cíli
| Úloha v testu | Body | Plán |
|---|---|---|
| Návrh Turingova stroje | 6 | umět |
| Self-redukce | 6 | umět |
| Formulace jako ILP nebo SAT | 6 | umět |
| Důkaz NP-těžkosti redukcí | 12 | rezerva, kolik půjde |
Turingův stroj a self-redukce dají dohromady 12 bodů, takže na zápočet stačí i bez redukce.
Co vypustit při nedostatku času
Nic. ICC má v plánu přednost. Když bude tlak, oberou se body jinde.
Chybí
- témata zkoušky po zveřejnění
- přednášky od 7. a cvičení od 5.