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

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

kódPředmětKredityZSLS
NTIN090Základy složitosti a vyčíslitelnosti 52/1 Z+Zk
NTIN066Datové struktury I 52/1 Z+Zk
NTIN022Pravděpodobnostní techniky 62/2 Z+Zk
NTIN063Složitost 52/1 Z+Zk
NTIN100Základy přenosu a zpracování informace 52/1 Z+Zk
NSZZ023Diplomová práce I 60/4 Z0/4 Z
NSZZ024Diplomová práce II 90/6 Z0/6 Z
NSZZ025Diplomová práce III 150/10 Z0/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ň 45 kreditů:

kódPředmětKredityZSLS
NAIL021Booleovské funkce a jejich aplikace 32/0 Zk
NAIL031Reprezentace booleovských funkcí 32/0 Zk
NAIL094Rozhodovací procedury a verifikace 62/2 Z+Zk
NMAG563Úvod do složitosti CSP 32/0 Zk
NDMI010Grafové algoritmy 32/0 Zk
NDMI013Kombinatorická a výpočetní geometrie II 62/2 Z+Zk
NDMI018Aproximační a online algoritmy 62/2 Z+Zk
NDMI025Pravděpodobnostní algoritmy 62/2 Z+Zk
NDMI067Toky, cesty a řezy 32/0 Zk
NDMI074Algoritmy a jejich implementace 62/2 Z+Zk
NDMI077Algoritmy pro specifické třídy grafů 32/0 Zk
NDMI088Grafové algoritmy II 32/0 Zk
NMAG446Logika a složitost 32/0 Zk
NMAG536Důkazová složitost a P vs. NP problém 32/0 Zk
NMAI067Logika v informatice 32/0 Zk
NOPT034Matematické programování a polyedrální kombinatorika 52/1 Z+Zk
NSWI072Algoritmy komprese dat 32/0 Zk
NTIN017Paralelní algoritmy 32/0 Zk
NTIN018Pravděpodobnostní analýza algoritmů 32/0 Zk
NTIN033Experimentální analýza algoritmů 62/2 Z+Zk
NTIN064Vyčíslitelnost 32/0 Zk
NTIN067Datové struktury II 32/0 Zk
NTIN073Rekurze 32/0 Zk
NTIN081Strukturální složitost 32/0 Zk
NTIN082Výpočetní složitost 32/0 Zk
NTIN084Bioinformatické algoritmy 62/2 Z+Zk
NTIN085Vybrané kapitoly z výpočetní složitosti I 52/1 Z+Zk
NTIN086Vybrané kapitoly z výpočetní složitosti II 52/1 Z+Zk
NTIN087Textové algoritmy 32/0 Zk
NTIN088Algoritmická náhodnost 32/0 Zk
NTIN096Pseudo-Booleovská optimalizace 32/0 Zk
NTIN097Struktury v hyperkrychlích 32/0 Zk
NTIN098Pokročilé datové struktury 32/0 Zk
NTIN099Algoritmy pro reprezentaci znalostí 32/0 Zk
NTIN104Foundations of theoretical cryptography 52/1 Z+Zk
NTIN103Introduction to Parameterized Algorithms 62/2 Z+Zk

Doporučené volitelné předměty

kódPředmětKredityZSLS
NOPT016Celočíselné programování 62/2 Z+Zk
NOPT042Programování s omezujícími podmínkami 62/2 Z+Zk
NTIN023Dynamické grafové datové struktury 32/0 Zk

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

kódPředmětKredityZSLS
NTIN063Složitost 52/1 Z+Zk
NTIN081Strukturální složitost 32/0 Zk
NTIN082Výpočetní složitost 32/0 Zk
NMAG536Důkazová složitost a P vs. NP problém 32/0 Zk
NTIN064Vyčíslitelnost 32/0 Zk
NTIN100Základy přenosu a zpracování informace 52/1 Z+Zk

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

kódPředmětKredityZSLS
NTIN099Algoritmy pro reprezentaci znalostí 32/0 Zk
NAIL094Rozhodovací procedury a verifikace 62/2 Z+Zk
NTIN097Struktury v hyperkrychlích 32/0 Zk
NAIL021Booleovské funkce a jejich aplikace 32/0 Zk
NAIL031Reprezentace booleovských funkcí 32/0 Zk

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

kódPředmětKredityZSLS
NDMI010Grafové algoritmy 32/0 Zk
NDMI018Aproximační a online algoritmy 62/2 Z+Zk
NDMI025Pravděpodobnostní algoritmy 62/2 Z+Zk
NTIN017Paralelní algoritmy 32/0 Zk
NTIN087Textové algoritmy 32/0 Zk

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

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

Univerzita Karlova, Matematicko-fyzikální fakulta
Ke Karlovu 3, 121 16 Praha 2
IČ: 00216208, DIČ: CZ00216208