Teoretická informatika

2. Teoretická informatika

Garantující pracoviště: Katedra teoretické informatiky a matematické logiky, Informatický ústav Univerzity Karlovy
Oborový garant: Doc. Mgr. Michal Koucký, Ph.D.

Obor se nedělí na zaměření

Absolvent důkladně rozumí teoretickým základům výpočetních systémů a zároveň má přehled o praktických výpočetních metodách a postupech. Rozumí tak různým modelům výpočtů a jejich vzájemným vztahům, zná možnosti a limity efektivních výpočtů, disponuje širokým spektrem algoritmických technik a technik konstrukce datových struktur. Má důkladné znalosti v oblasti pravděpodobnosti a jejího využití při návrhu a analýze algoritmů a výpočetních systémů.

Povinné předměty

Povinně volitelné předměty

Je požadováno splnění povinně volitelných předmětů z následujícího seznamu v rozsahu alespoň 45 kreditů:

Doporučené volitelné předměty

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

Ke dvěma povinným okruhům společným pro všechny obory si student vybere dva další okruhy z následující nabídky. Jako poslední okruh si student může zvolit buď také okruh z následující nabídky, nebo libovolný okruh oboru Diskrétní modely a algoritmy, libovolný okruh zaměření Inteligentní agenti nebo Strojové učení oboru Umělá inteligence, nebo libovolný okruh zaměření Počítačová grafika oboru Počítačová grafika a vývoj počítačových her. Celkem tedy každý student dostane pět otázek.

Zkušební okruhy

1. Složitost a vyčíslitelnost

2. Booleovské funkce

3. Algoritmy

4. Pokročilé datové struktury

Zkušební požadavky

1. Složitost a vyčíslitelnost
Výpočty s orákuly a relativizované výpočetní třídy. Polynomiální hierarchie. Neuniformní modely výpočtu. Pravděpodobnostní výpočetní třídy. Interaktivní protokoly, PCP věta. Jednosměrné funkce a pseudonáhodné generátory. Komunikační složitost. Důkazová složitost. Vztahy a separace různých tříd složitosti. Věty o rekurzi a jejich použití. Efektivně neoddělitelné množiny. Relativní vyčíslitelnost a operace skoku. Aritmetická hierarchie.

Doporučené předměty

2. Booleovské funkce
Rezoluce a její úplnost. Třídy booleovských funkcí se speciálními vlastnostmi. Algoritmy pro SAT a MAXSAT. Reprezentace booleovských funkcí pomocí BDD a OBDD. Řešiče pro SAT a jejich využití pro SMT. Parametrizovaná složitost. Hyperkrychlové grafy.

Doporučené předměty

3. Algoritmy
Pokročilé grafové algoritmy, toky v síti, algoritmy pro rovinné grafy. Lineární a semidefinitní programování, polynomiální algoritmy, použití v grafových a aproximačních algoritmech. Kombinatorické aproximační algoritmy a schémata. Pravděpodobnostní algoritmy, přibližné počítání, hašování a jeho aplikace. Interaktivní protokoly a verifikace, PCP věta a její aplikace. Paralelní výpočetní modely a třídy, techniky a příklady paralelních algoritmů. Textové algoritmy, posloupnosti, podřetězce, regulární výrazy a vyhledávání.

Doporučené předměty

4. Pokročilé datové struktury
Entropie a informace. Samoopravné kódy. Komprese dat. Datové struktury pro práci s řetězci. Dynamické datové struktury pro reprezentaci grafů. Slovníkové datové struktury. Pravděpodobnostní vyhledávací struktury. Pokročilé haldy. Datové struktury pro práci s celými čísly. Persistentní datové struktury. Samoupravující se datové struktury. Cache oblivious analýza a optimální algoritmy. Data-streamové problémy.

Doporučené předměty