Informatika - Teoretická informatika

Tato stránka vychází z podkladů pro tištěné studijní plány (tzv. Karolinku).

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

kódPředmětKredityZSLS
NTIN090Základy složitosti a vyčíslitelnosti 42/1 Z+Zk
NTIN066Datové struktury 1 62/2 Z+Zk
NTIN022Pravděpodobnostní techniky 52/2 Z+Zk
NTIN063Složitost 42/1 Z+Zk
NTIN100Základy přenosu a zpracování informace 42/1 Z+Zk
NSZZ023Diplomová práce I 60/4 Z
NSZZ024Diplomová práce II 90/6 Z
NSZZ025Diplomová práce III 150/10 Z

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ň 35 kreditů. Posluchači, kteří zahájili studium před rokem 2022, musí získat alespoň 47 kreditů.

kódPředmětKredityZSLS
NAIL021Booleovské funkce a jejich aplikace 32/0 Zk
NTIN096Pseudo-Booleovská optimalizace 32/0 Zk
NAIL094Rozhodovací procedury a SAT/SMT řešiče 52/2 Z+Zk
NDMI010Grafové algoritmy 32/0 Zk
NDMI018Aproximační a online algoritmy 52/2 Z+Zk
NDMI025Pravděpodobnostní algoritmy 52/2 Z+Zk
NSWI072Algoritmy komprese dat 32/0 Zk
NTIN067Datové struktury 2 32/0 Zk
NDMI074Algoritmy a jejich implementace 52/2 Z+Zk
NTIN081Výpočetní složitost a interaktivni protokoly 32/0 Zk
NTIN082Neuniformní výpočetní modely 32/0 Zk
NTIN087Textové algoritmy 32/0 Zk
NTIN097Struktury v hyperkrychlích 32/0 Zk
NTIN099Algoritmy pro reprezentaci znalostí 32/0 Zk
NTIN103Introduction to Parameterized Algorithms 52/2 Z+Zk
NOPT034Matematické programování a polyedrální kombinatorika 42/1 Z+Zk
NTIN104Foundations of theoretical cryptography 42/1 Z+Zk
NDMI067Toky, cesty a řezy 32/0 Zk
NDMI077Algoritmy pro specifické třídy grafů 32/0 Zk
NDMI088Grafové algoritmy 2 32/0 Zk
NMAG536Důkazová složitost a P vs. NP problém 32/0 Zk
NMAI067Logika v informatice 32/0 Zk
NTIN017Paralelní algoritmy 32/0 Zk
NTIN023Dynamické grafové datové struktury 32/0 Zk
NTIN064Vyčíslitelnost 32/0 Zk
NTIN073Rekurze 32/0 Zk
NTIN084Bioinformatické algoritmy 52/2 Z+Zk
NTIN085Vybrané kapitoly z výpočetní složitosti I 42/1 Z+Zk
NTIN086Vybrané kapitoly z výpočetní složitosti II 42/1 Z+Zk
NTIN101Selected Topics in Algorithms 32/0 Zk
NTIN111Selected Topics in Algorithms II 32/0 Zk
NTIN110Vybrané kapitoly z datových struktur 32/0 Zk
NTIN088Algoritmická náhodnost 32/0 Zk
NTIN102Seminář z teoretické informatiky 30/2 Z0/2 Z
NDMI093Seminář z algoritmů a datových struktur 30/2 Z
NTIN106Implementace algoritmů a datových struktur 30/2 Z
NOPT059Optimalizace velkých problémů: přesné metody 52/2 Z+Zk
NOPT061Optimalizace velkých problémů: metaheuristiky 52/2 Z+Zk

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.

kódPředmětKredityZSLS
NDMI007Kombinatorické algoritmy 52/2 Z+Zk
NAIL116Sociální sítě a jejich analýza 52/2 Z+Zk
NOPT042Programování s omezujícími podmínkami 52/2 Z+Zk
NAIL076Logické programování 1 32/0 Zk

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

kódPředmětKredityZSLS
NTIN063Složitost 42/1 Z+Zk
NTIN081Výpočetní složitost a interaktivni protokoly 32/0 Zk
NTIN082Neuniformní výpočetní modely 32/0 Zk
NTIN104Foundations of theoretical cryptography 42/1 Z+Zk

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

kódPředmětKredityZSLS
NTIN099Algoritmy pro reprezentaci znalostí 32/0 Zk
NAIL094Rozhodovací procedury a SAT/SMT řešiče 52/2 Z+Zk
NTIN097Struktury v hyperkrychlích 32/0 Zk
NAIL021Booleovské funkce a jejich aplikace 32/0 Zk

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

kódPředmětKredityZSLS
NDMI010Grafové algoritmy 32/0 Zk
NDMI018Aproximační a online algoritmy 52/2 Z+Zk
NDMI025Pravděpodobnostní algoritmy 52/2 Z+Zk
NTIN103Introduction to Parameterized Algorithms 52/2 Z+Zk

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

kódPředmětKredityZSLS
NTIN100Základy přenosu a zpracování informace 42/1 Z+Zk
NTIN067Datové struktury 2 32/0 Zk
NTIN087Textové algoritmy 32/0 Zk
NDMI010Grafové algoritmy 32/0 Zk
NSWI072Algoritmy komprese dat 32/0 Zk