# **NTIN090** Základy složitosti a vyčíslitelnosti

<{Box(infobox)}>
|-----|-----|
| **Učitel:** | [RNDr. Petr Kučera, Ph.D.](http://ktiml.mff.cuni.cz/~kucerap/) |
| **Odkaz do SISu:** | [NMAI054](https://is.cuni.cz/studium/predmety/index.php?do=predmet&kod=NTIN090) |
| **Diskuze:** | [Discord kanál]() |
<{/Box}>


## Zdroje
- [Stránka předmětu](http://ktiml.mff.cuni.cz/%7Ekucerap/NTIN090/)
- [Skripta](NTIN090/skripta.pdf)
- [Zpracované otázky od Petrosauruse](/NTIN090/otazky2025.pdf) (ZS 2025)
- [Poznámky z cvičení](http://forum.matfyz.info/download/file.php?id=546)
- [Parameterized Algorithms](https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf) - hlubší vysvětlení parametrizovaných Vertex cover metod
- [Emulátor primitivně rekurzivních funkcí](http://forum.matfyz.info/download/file.php?id=553)
- [Johančiny pohádky z vyčíslitelnosti](http://web.archive.org/web/20100626015101/http://atrey.karlin.mff.cuni.cz/%7Ejohanka/vyuka/pohadky_vycislitelnost.html)


## 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

<<ZapocetList()>>


## 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.

<<ExamList()>>


## 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í.