Teoretická informatika

1. Pravděpodobnost. Základní pojmy a vlastnosti pravděpodobnosti; náhodná proměnná a její charakteristiky (střední hodnota, rozptyl, momenty, ....) a jejich použití; binomická, geometrická a další distribuce a jejich charakteristiky. Markovova a Čebyševova nerovnost a jejich použití; Černoffovy odhady a jejich použití; náhodné, zejména Markovovy, procesy a jejich vlastnosti; entropie a informace a jejich vlastnosti; aplikace v informatice.
   IV111, IA062
2. Algebra. Lineární algebra; vektorový a maticový počet; grupy, okruhy a pole a jejich základní vlastnosti; svazy a jejich základní vlastnosti; distributivní, modulární a Booleovy svazy; univerzální algebry (základní pojmy, homomorfismy, kongruence a faktorové algebry), variety, Birkhoffova věta.
   MA009
3. Grafy a grafové algoritmy. Základní pojmy a způsoby reprezentace a prohledávání; stromy a jejich reprezentace a prohledávání; planární grafy a jejich vlastnosti, algoritmy pro konstrukci minimální kostry, pro hledání nejkratší cesty; pro optimální párování; pro maximální toky atd.; datové struktury pro grafové algoritmy; náhodné grafy a jejich použití; náhodnostní grafové algoritmy.
   MA015, MA010

Zaměření Algoritmy

1. Automaty. Konečné deterministické, nedeterministické a pravděpodobnostní automaty a jejich vlastnosti (minimalizace, ekvivalence, rozhodovací problémy); regulární jazyky a jejich vlastnosti; pumping lemma, zásobníkové automaty a jejich vlastnosti; bezkontextové jazyky a jejich vlastnosti; Chomského gramatiky a jejich normální formy a vztah k modelům automatů. Syntaktická analýza nejpoužívanějších modelů bezkontextových gramatik; konečné automaty nad nekonečnými slovy; Turingovy stroje a jejich vlastnosti (rekurzivní a rekurzivně spočetné množiny, univerzalita a halting problem).
2. Výpočetní, komunikační a Kolmogorovova složitost. Časové a paměťové složitosti a jejich vlastnosti; Třídy složitosti pro deterministické, nedeterministické a náhodnostní výpočty a vztahy mezi nimi; úplné, zejména NP-úplné, problémy; důkazy NP-úplnosti; P-NP problém a jeho implikace; aproximační řešení NP-problémů; aproximační třídy složitosti; interaktivní dokazovací systémy a zero-knowledge dokazovací systémy; komunikační složitost a její aplikace; metody dokazování dolních odhadů komunikační složitosti; třídy komunikační složitosti, základní pojmy a vlastnosti Kolmogorovovy složitosti.
   IA012, IA062
3. Algoritmy pro řešení výpočetně náročných problémů. Náhodnostní algoritmy Monte Carlo a Las Vegas; náhodné procházky; aproximační algoritmy a jejich potenciál; genetické algoritmy; kvantové algoritmy (Shorův faktorizační a Groverův vyhledávací algoritmus).
   IA101, IA062
4. Kódování, kryptografie a kryptografické protokoly. Lineární kódy (definice, vlastnosti, kódování a dekódování, důležité příklady lineárních kódů; cyklické kódy (definice, algebraická charakterizace, kódování a dekódování, důležité příklady cyklických kódů); turbo kódy a low-density kódy; kryptosystémy s privátním klíčem; DES a AES kryptosystémy; kryptosystémy s veřejným klíčem; RSA kryptosystém a jeho vlastnosti; kryptografické systémy založené na eliptických křivkách; schémata pro digitální podpisy; autentizační protokoly; protokoly pro coin tossing, bit commitment a oblivious transfer; steganografie a vodotisk; kryptografické stroje a jejich historie; kvantová kryptografie (generování náhodných tajných klasických klíčů, kvantová teleportace).
   IV054
5. Matematická analýza. Systémy lineárních diferenciálních rovnic a metody jejich řešení; křivkový integrál.
   MA002

Zaměření Logika

1. Matematická logika a vyčíslitelnost. Výroková logika (výrokové formule, pravdivost, dokazatelnost, věta o úplnosti); predikátová logika (axiomy, sémantika, dokazatelnost); věty o korektnosti, úplnosti, dedukci a kompaktnosti; teorie a modely; Löwenheimova-Skolemova věta; Gödelovy věty o úplnosti a neúplnosti.
2. Riceovy věty; kreativní a imunní množiny; primitivní, totálně a částečně rekurzivní množiny a funkce. Aritmetické množiny a funkce; Gödelova a Rosserova věta o neúplnosti; druhá Gödelova věta o neúplnosti.
   MA007, IA038, IA046
3. Sémantiky programovacích jazyků. Základní přístupy k sémantice programovacích jazyků (operační, denotační a axiomatický); strukturální operační sémantika a její varianty; ekvivalence sémantik; základní pojmy a metody denotační sémantiky (pojem CPO, spojité funkce mezi CPO, věta o pevném bodu, sémantika rekurze); ekvivalence denotační a operační sémantiky.
   IA011
4. Petriho sítě. Základní vlastnosti Petriho sítí (ohraničenost, pokrytelnost, Karp-Millerův strom, slabý Petriho počítač, dosažitelnost a životnost); (ne)rozhodnutelnost sémantických ekvivalencí a temporálních logik pro Petriho sítě; S-systémy a S-varianty, T-systémy a T-varianty; Petriho sítě s volným výběrem; modelování pomocí Petriho sítí.
   IA023
5. Formální verifikační metody. Hlavní verifikační metody a jejich porovnání; problém stavové exploze; theorem proving jako deduktivní verifikační metoda; LTL-model checking pro konečně a nekonečně stavové systémy; ohraničený (bounded) model checking; symbolická exekuce; statická analýza; abstraktní interpretace; verifikační prostředky.
   IV113, IA159
6. Teorie, specifikace a logiky procesů. Procesy a přechodové systémy s návěštími a jejich specifikace; operační sémantika; hierarchie procesů; základní sémantické ekvivalence procesů na přechodových systémech a jejich vzájemné vztahy; možnosti algoritmické verifikovatelnosti sémantických ekvivalencí na nekonečně stavových procesech. Modální logiky (výroková modální logika, modální mu-calculus); temporální logiky (temporální operátory, výroková temporální logika, lineární a větvící se čas); procesy a jejich vlastnosti; verifikace temporálních vlastností; model checking; automatizovaná verifikace.
   IA040, IA041
7. Lambda calculus. Prvky lambda-kalkulu; transformace a redukce; lambda-kalkul a výpočty (kódování, rekurzivní definice, lambda-vyčíslitelnost, nerozhodnutelné problémy); typovaný lambda-kalkul (vlastnosti a aplikace); domény a jejich konstrukce; doménové modely.
   IA081