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

<{Box(infobox)}>
|K    |V    |
|-----|-----|
| **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 (OUTDATED!)
- **2011**
  - [Zápočet 10.1.2011](/NTIN090/Zápočet 10.1.2011)
- **2010**
  - [Zápočet 13.1.2010](/NTIN090/Zápočet 13.1.2010) 
  - [Zápočet 27.1.2010](/NTIN090/Zápočet 27.1.2010) 
  - [Zápočet 28.1.2010](/NTIN090/Zápočet 28.1.2010)
  - [Zápočet 4.2.2010](/NTIN090/Zápočet 4.2.2010)
  - [Zápočet 8.2.2010](/NTIN090/Zápočet 8.2.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.

- 2023
  - [Zkouška Kučera 12.01. 2023](/NTIN090/Zkouška Kučera 12.01. 2023)
- 2020
  - [Zkouška Kučera 14.09. 2020](/NTIN090/Zkouška Kučera 14.09. 2020)
- 2018
  - [Zkouška Kučera 07.02. 2018](/NTIN090/Zkouška Kučera 07.02. 2018)
  - [Zkouška Kučera 31.01. 2018](/NTIN090/Zkouška Kučera 31.01. 2018)
  - [Zkouška Kučera 18.01. 2018](/NTIN090/Zkouška Kučera 18.01. 2018)
  - [Zkouška Kučera 16.01. 2018](/NTIN090/Zkouška Kučera 16.01. 2018)
  
- 2017
  - [Zkouška Kučera 03.02. 2017](/NTIN090/Zkouška Kučera 03.02. 2017)
  - [Zkouška Kučera 23.01. 2017](/NTIN090/Zkouška Kučera 23.01. 2017)
  - [Zkouška Kučera 19.01. 2017](/NTIN090/Zkouška Kučera 19.01. 2017)
  - [Zkouška Kučera 17.01. 2017](/NTIN090/Zkouška Kučera 17.01. 2017)
  - [Zkouška Kučera 17.01. 2017 (lefty)](/NTIN090/Zkouška Kučera 17.01. 2017 (lefty))

- 2016
  - [Zkouška Kučera 17.02. 2016](/NTIN090/Zkouška Kučera 17.02. 2016)
  - [Zkouška Kučera 27.01. 2016](/NTIN090/Zkouška Kučera 27.01. 2016)
  - [Zkouška Kučera 20.01. 2016](/NTIN090/Zkouška Kučera 20.01. 2016)

- 2015
- [Zkouška Kučera 04.02. 2015](/NTIN090/Zkouška Kučera 04.02. 2015)

- 2014
  - [Zkouška Kučera 04.02. 2014](/NTIN090/Zkouška Kučera 04.02. 2014)
  - [Zkouška Kučera 29.01. 2014](/NTIN090/Zkouška Kučera 29.01. 2014)
  - [Zkouška Kučera 23.01. 2014](/NTIN090/Zkouška Kučera 23.01. 2014)
  - [Zkouška Kučera 21.01. 2014](/NTIN090/Zkouška Kučera 21.01. 2014)
  - [Zkouška Kučera 15.01. 2014](/NTIN090/Zkouška Kučera 15.01. 2014)

- 2013
  - [Zkouška Kučera 13.02. 2013](/NTIN090/Zkouška Kučera 13.02. 2013)
  - [Zkouška Kučera 06.02. 2013](/NTIN090/Zkouška Kučera 06.02. 2013)
  - [Zkouška Kučera 04.02. 2013](/NTIN090/Zkouška Kučera 04.02. 2013)
  - [Zkouška Kučera 23.01. 2013](/NTIN090/Zkouška Kučera 23.01. 2013)

- 2012
  - [Zkouška Kučera 13.02. 2012](/NTIN090/Zkouška Kučera 13.02. 2012)
  - [Zkouška Kučera 02.02. 2012](/NTIN090/Zkouška Kučera 02.02. 2012)
  - [Zkouška Kučera 01.02. 2012](/NTIN090/Zkouška Kučera 01.02. 2012)
  - [Zkouška Kučera 20.01. 2012](/NTIN090/Zkouška Kučera 20.01. 2012)

- 2011
  - [Zkouška Kučera 20.06. 2011](/NTIN090/Zkouška Kučera 20.06. 2011)
  - [Zkouška Kučera 08.06. 2011](/NTIN090/Zkouška Kučera 08.06. 2011)
  - [Zkouška Kučera 04.02. 2011](/NTIN090/Zkouška Kučera 04.02. 2011)
  - [Zkouška Kučera 01.02. 2011](/NTIN090/Zkouška Kučera 01.02. 2011)
  - [Zkouška Kučera 27.01. 2011](/NTIN090/Zkouška Kučera 27.01. 2011)
  - [Zkouška Kučera 20.01. 2011](/NTIN090/Zkouška Kučera 20.01. 2011)

- 2010
  - [Zkouška Kučera 15.02. 2010](/NTIN090/Zkouška Kučera 15.02. 2010)
  - [Zkouška Kučera 08.02. 2010](/NTIN090/Zkouška Kučera 08.02. 2010)
  - [Zkouška Kučera 04.02. 2010](/NTIN090/Zkouška Kučera 04.02. 2010)
  - [Zkouška Kučera 03.02. 2010](/NTIN090/Zkouška Kučera 03.02. 2010)
  - [Zkouška Kučera 01.02. 2010](/NTIN090/Zkouška Kučera 01.02. 2010)
  - [Zkouška Kučera 28.01. 2010](/NTIN090/Zkouška Kučera 28.01. 2010)
  - [Zkouška Kučera 27.01. 2010](/NTIN090/Zkouška Kučera 27.01. 2010)
  - [Zkouška Kučera 18.01. 2010](/NTIN090/Zkouška Kučera 18.01. 2010)


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