Matfyz Wiki
NTIN090 Základy složitosti a vyčíslitelnosti
Zdroje
Zpracované otázky od Petrosauruse (ZS 2025)
Parameterized Algorithms - hlubší vysvětlení parametrizovaných Vertex cover metod
Zápočet
Po každém cvičení jsou zadány sady domácích úkolů, za něž lze celkem získat 30 bodů.
K získání zápočtu je potřeba získat 100 bodů.
Pro odevzdání řešení se použije odkaz u daného cvičení v Moodle.
Termín pro odevzdání každého úkolu je před začátkem příslušného cvičení.
Termín pro odevzdání je možné po dohodě prodloužit, je však nutné o tom informovat před jeho uplynutím.
Pokud je odevzdáno řešení, ve kterém jsou při opravování nalezeny chyby, nebo je z jiných důvodů shledáno nedostatečným, jsou k dispozici další dva týdny na opravu či doplnění řešení. Tento postup se může opakovat podle potřeby.
Pokud během semestru není získán dostatek bodů, je možné si je doplnit řešením dodatečných úkolů. Tímto způsobem lze získat nejvýše 40 bodů, proto se doporučuje nepodceňovat řešení úkolů během semestru.
V případě potřeby nápovědy či rady k některému příkladu, případně nejasností v jeho zadání, je vhodné dát včas vědět.
K řešení příkladů se nepoužívají žádné nástroje využívající umělou inteligenci; cílem je osvojit si látku samostatným přemýšlením. V případě nejasností je možné požádat o radu či nápovědu.
Řešení se neposílají e-mailem; místo toho je možné požádat o prodloužení termínu odevzdání.
Zápočet není nutný k připuštění ke zkoušce, je však vyžadován pro úspěšné absolvování kurzu na konci školního roku.
Minulé zápočtové testy (OUTDATED!)
2011
2010
Zkouška
Zkouška je pouze ústní; vždy jsou zadávány dvě otázky, jak je uvedeno i v seznamu otázek.
Při přihlašování na termín je v SISu přidělen čas, kdy je nutné se ke zkoušce dostavit; tento čas je třeba respektovat.
Časy jsou obvykle přidělovány v půlhodinových intervalech vždy dvojici studentů, což omezuje počet osob současně přítomných v místnosti.
Typicky jsou vyhlašovány jeden nebo dva zkouškové termíny i během letního zkouškového období.
Zápočet není nutnou podmínkou k připuštění ke zkoušce, je však nutnou podmínkou pro úspěšné absolvování kurzu na konci akademického roku.
všechny příklady na převody bere Kučera z doporučené literatury, konkrétně - Garey, Johnson: Computers and intractability - a guide to the theory of NPcompleteness, W.H. Freeman 1978. Bere pouze ty jednodušší ze začatku. Není problém zapůjčit tuto knihu v knihovně, je tam prý v několika výtiscích.
Další informace
Všeobecně platí, že tvrzení, která byla dokazována na přednášce, je nutné umět dokázat i u zkoušky. Pokud je součástí zkoušky tvrzení či věta, k jejichž důkazu bylo nejprve potřeba prokázat nějaké pomocné tvrzení, je nutné umět doložit i toto pomocné tvrzení. Důležitější je přitom princip důkazu než technické detaily.
Řada pojmů probíraných na přednášce má v literatuře definice, které se mohou v některých detailech lišit. V závislosti na tom se může lišit i to, jaké předpoklady je třeba uvést u tvrzení o těchto pojmech. Pokud je při zkoušce použita odlišná definice daného pojmu, je nutné zachovat konzistenci a odpovídajícím způsobem upravit tvrzení i jejich důkazy. Předpoklady tvrzení lze obvykle dovodit zpětně z důkazu, v němž se ukáže, co je potřeba k jeho dokončení.