4. Státní závěrečná zkouška

Studium je zakončeno státní závěrečnou zkouškou. Ta má dvě části, jimiž jsou obhajoba diplomové práce a ústní část. K oběma částem státní závěrečné zkoušky se posluchač poprvé přihlašuje najednou. Studium je úspěšně zakončeno po úspěšném absolvování obou těchto částí.

Podmínky pro přihlášení ke státní závěrečné zkoušce

– získání alespoň 120 kreditů

– splnění všech povinných předmětů zvoleného oboru

– splnění povinně volitelných předmětů zvoleného oboru ve stanoveném rozsahu

– odevzdání vypracované diplomové práce ve stanoveném termínu.

Předmět lze splnit jeho úspěšným absolvováním nebo uznáním z předchozího studia.

Téma diplomové práce si posluchač vybere v zimním semestru předposledního roku studia v termínu stanoveném harmonogramem akademického roku. Může si vybrat téma z nabídky garantujícího pracoviště zvoleného studijního oboru nebo může garantujícímu pracovišti předložit vlastní návrh tématu. Všechna témata vypisovaných diplomových prací podléhají schválení odpovědným učitelem příslušného oboru.

Po zadání diplomové práce si každý posluchač postupně zapíše povinné předměty společné pro všechny obory:

Zápočty z povinných předmětů NSZZ023 Diplomová práce I, NSZZ024 Diplomová práce II, NSZZ025 Diplomová práce III uděluje vedoucí diplomové práce jako doklad o úspěšné práci posluchače na stanoveném diplomovém úkolu. Předmět Diplomová práce I si posluchač zapíše zpravidla v letním semestru předposledního roku studia, předměty Diplomová práce II a Diplomová práce III pak návazně v zimním a v letním semestru posledního roku svého studia. V případě potřeby lze zvolit i jiné uspořádání, každý z těchto předmětů je možné zapsat v zimním nebo v letním semestru.

Ústní část státní závěrečné zkoušky má na všech oborech I1 – I4 studijního programu Informatika stejnou strukturu. Každý posluchač je zkoušen ze znalostí dvou nebo tří povinných zkušebních okruhů pokrývajících teoretický základ informatiky (složitost, vyčíslitelnost, datové struktury), a dále ze tří volitelných zkušebních okruhů. Ty jsou specifické pro každý studijní obor, v rámci oboru mohou být ještě rozděleny podle studijních plánů. Volitelné zkušební okruhy si posluchač sám vybere z nabídky zkušebních okruhů pro studovaný obor a svou volbu oznámí při přihlašování se ke státní závěrečné zkoušce. Vybírá si přitom nejméně dva zkušební okruhy z toho studijního plánu, v němž zakončuje studium, třetí zkušební okruh si může zvolit buď ze stejného, nebo z jiného studijního plánu téhož oboru. V odůvodněných případech může odpovědný učitel oboru povolit jinou skladbu volitelných zkušebních okruhů (např. zvolit jeden zkušební okruh z jiného oboru studia).

Státní závěrečná zkouška na oboru I5 má stejnou podobu jako státní závěrečná zkouška některého z oborů I1 – I4 podle vlastní volby posluchače, ústní část státní závěrečné zkoušky je však doplněna o další povinný zkušební okruh Informatika a didaktika informatiky. Podrobnosti jsou uvedeny v odstavci věnovaném oboru I5.

Povinné zkušební okruhy společné pro obory I1 a I4

1. Složitost
Věty o zrychlení a o mezerách, věty o hierarchii tříd složitosti, konstruovatelné funkce, vztahy mezi časovými a prostorovými mírami a determinismem a nedeterminismem, Savitchova věta. Úplné problémy pro třídy NP, PSPACE, polynomiální hierarchie, pseudopolynomiální algoritmy. Dolní odhady pro uspořádání (rozhodovací stromy). Aproximační algoritmy a schémata. Metody tvorby algoritmů: rozděl a panuj, dynamické programování, hladový algoritmus. Pravděpodobnostní algoritmy.

2. Vyčíslitelnost
Algoritmicky vyčíslitelné funkce, jejich vlastnosti, ekvivalence jejich různých matematických definic. Primitivně a částečně rekurzivní funkce. Rekurzivní a rekurzivně spočetné množiny a jejich vlastnosti. Algoritmicky nerozhodnutelné problémy. Věty o rekurzi a jejich aplikace. Gödelovy věty.

3. Datové struktury
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í. Možnosti dynamizace jednotlivých datových struktur. Mapování datových struktur do stránek vnější paměti počítače, časová složitost algoritmů vyjádřená v počtu I/O operací. Třídění ve vnitřní a vnější paměti.

Povinné zkušební okruhy společné pro obory I2 a I3

1. Složitost a vyčíslitelnost
Metody tvorby algoritmů: rozděl a panuj, dynamické programování, hladový algoritmus. Dolní odhady pro složitost třídění (rozhodovací stromy). Amortizovaná složitost. Ú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. Rekurzivní a rekurzivně spočetné množiny a jejich vlastnosti. Algoritmicky nerozhodnutelné problémy (halting problem). Věty o rekurzi a jejich aplikace: příklady, Riceova věta.

2. Datové struktury
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í. Možnosti dynamizace jednotlivých datových struktur. Mapování datových struktur do stránek vnější paměti počítače, časová složitost algoritmů vyjádřená v počtu I/O operací. Třídění ve vnitřní a vnější paměti.