Státnice - Povinné zkušební okruhy oborů I2 a I3

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, návod. -- Tuetschek 11:41, 22 Sep 2010 (CEST)

Základy složitosti a vyčíslitelnosti

• Metody tvorby algoritmů (rozděl a panuj, dynamické programování, hladový algoritmus)
• NP-úplnost (úplné problémy pro třídu NP, Cook-Levinova věta, pseudopolynomiální algoritmy, silná NP-úplnost)
• Aproximační algoritmy a schémata
• Algoritmicky vyčíslitelné funkce, jejich vlastnosti, ekvivalence jejich různých matematických definic, částečně rekurzivní funkce
• Algoritmicky nerozhodnutelné problémy (halting problem)
• Věty o rekurzi a jejich aplikace: příklady, Riceova věta

Datové struktury

K dispozici je souhrn i detailnější popis otázek:

• Stromové vyhledávací struktury (binární stromy a jejich vyvažování, haldy, trie, B-stromy a jejich varianty)
• Hašování (řešení kolizí, univerzální hašování, perfektní hašování)
• Třídění ve vnitřní a vnější paměti.