Informatika - Teoretická informatika

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

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

Cílem tohoto studijního programu je poskytnout studentům široké vzdělání v teoretických základech informatiky. Program předpokládá dobré matematické základy a rozvíjí schopnosti přesného myšlení. Absolventi a absolventky získají přehled a porozumění v mnoha oblastech současné teoretické informatiky - od kryptografie a limitů výpočetních systémů po pokročilé algoritmické techniky. Zároveň se dostanou v oblastech svého zájmu ke hranicím současného poznání. Součástí studia tak může být práce v mezinárodních týmech vedených předními odborníky například při řešení diplomové práce. Absolventi a absolventky jsou vyhledáváni firmami vyvíjející technologie pro budoucnost založené na nynějším výzkumu. Zároveň je studijní program znamenitě připraví pro doktorské studium na kterékoliv světové univerzitě.

Část výuky může probíhat v anglickém jazyce.

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ň 47 kreditů:

Některé předměty jsou vyučovány pouze jednou za dva roky.

Doporučené volitelné předměty

Uvedený seznam volitelných předmětů obsahuje předměty, které přímo navazují a rozšiřují látku relevantní pro tento studijní program. Student má dále možnost vybrat si další předměty volitelně ze široké nabídky informatických předmětů nabízených MFF UK.

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

Student si zvolí tři okruhy z následující nabídky, z nichž dostane po jedné otázce. Otázky k jednotlivým okruhům vychází z látky probrané v rámci povinných předmětů a předmětů doporučených k jednotlivým okruhům. Celkem tedy každý student dostane tři otázky.

Zkušební okruhy

1. Složitost a kryptografie

2. Reprezentace znalostí v binární doméně

3. Algoritmy

4. Datové struktury

Zkušební požadavky

1. Složitost a kryptografie
Výpočty s orákuly a relativizované výpočetní třídy. Polynomiální hierarchie. Pravděpodobnostní výpočetní třídy. Neuniformní modely výpočtu. Interaktivní protokoly. Komunikační složitost. Vztahy a separace různých tříd složitosti. Kryptografie založená na předpokladech výpočetní obtížnosti. Jednosměrné funkce a hard-core predikáty. Pseudonáhodné generátory. Integrita dat (message authentication codes). Kryptografické hašovací funkce. Schémata pro commitment. Zero-knowledge důkazové systémy.

Doporučené předměty

2. Reprezentace znalostí v binární doméně
Rezoluce a její úplnost. Dualizace. Třídy booleovských funkcí a formulí se speciálními vlastnostmi. Exponenciální algoritmy pro k-SAT a obecný SAT. Parametrizované algoritmy pro SAT. Algoritmy pro MAXSAT. Reprezentace znalostí založené na NNF. Řešiče pro SAT založené na DPLL a CDCL a jejich využití pro SMT. Parciální krychle a mediánové grafy. Grayovy kódy. Isoperimetrické nerovnosti a lineární rozvržení. Turánovské problémy. Obvody, třída P/poly a její vlastnosti. QBF a jejich vlastnosti vzhledem k polynomiální hierarchii a třídě PSPACE. Algoritmy pro rozhodování QBF. Samo-opravné kódy.

Doporučené předměty

3. Algoritmy
Pokročilé grafové algoritmy, toky v síti. Lineární a semidefinitní programování, polynomiální algoritmy pro ně, použití v grafových a aproximačních algoritmech. Kombinatorické aproximační algoritmy a schémata. Pseudopolynomiální algoritmy, silná NP-úplnost. Parametrizované algoritmy - FPT, parametrizované dolní odhady, parametrizované aproximační algoritmy. 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.

Doporučené předměty

4. Datové struktury
Výpočetní modely (RAM a jeho varianty). Entropie a informace. Samoopravné kódy. Komprese dat. Vyhledávací stromy. Hešování. Pokročilé haldy. Datové struktury pro práci s celými čísly. Vícerozměrné datové struktury. Datové struktury pro práci s řetězci. Textové algoritmy. Struktury pro práci s grafy. Dynamizace a persistence. Práce s paměťovou hierarchií. Data-streamové problémy.

Doporučené předměty