{{Sources|''Chcete-li otázky výrazně upravovat a dopracovávat, nebo získat pěkné PDF pro tisk, přečtěte si, prosím, [[Help:Státnice|návod]].'' -- [[User:Tuetschek|Tuetschek]] 11:41, 22 Sep 2010 (CEST)}}
=== Základy složitosti a vyčíslitelnosti ===
Existuje i ještě stručnější výcuc pro I2 a I3, sloučený s otázkami na ZSV: [[Řešené_otázky_NTIN090]]
* [[Státnice - Informatika - Složitost (obory Matematická lingvistika a Softwarové systémy)|Složitost]]:
** [[Státnice - Metody tvorby algoritmů|Metody tvorby algoritmů]] (rozděl a panuj, dynamické programování, hladový algoritmus)
** [[Státnice - Odhady složitosti|Odhady složitosti]] (dolní odhady pro složitost třídění (rozhodovací stromy), amortizovaná složitost)
** [[Státnice - NP-úplnost|NP-úplnost]] (úplné problémy pro třídu NP, Cook-Levinova věta, pseudopolynomiální algoritmy, silná NP-úplnost)
** [[Státnice - Aproximační algoritmy a schémata|Aproximační algoritmy a schémata]]
* [[Státnice - Informatika - Vyčíslitelnost|Vyčíslitelnost]]:
** [[Státnice - Algoritmicky vyčíslitelné funkce|Algoritmicky vyčíslitelné funkce]], jejich vlastnosti, ekvivalence jejich různých matematických definic, částečně rekurzivní funkce
** [[Státnice - Rekurzivní a rekurzivně spočetné množiny|Rekurzivní a rekurzivně spočetné množiny]] a jejich vlastnosti
** [[Státnice - Algoritmicky nerozhodnutelné problémy|Algoritmicky nerozhodnutelné problémy]] (halting problem)
** [[Státnice - Věty o rekurzi|Věty o rekurzi]] a jejich aplikace: příklady, Riceova věta
=== Datové struktury ===
K dispozici je [[Státnice - Informatika - Datové struktury|souhrn]] i detailnější popis otázek:
* [[Státnice - Stromové vyhledávací struktury_I2|Stromové vyhledávací struktury]] (binární stromy a jejich vyvažování, haldy, trie, B-stromy a jejich varianty)
* [[Státnice - Hašování_I2|Hašování]] (řešení kolizí, univerzální hašování, perfektní hašování)
* [[Státnice - Třídění_I2|Třídění]] ve vnitřní a vnější paměti.
