Otázky N-TEI Teoretická informatika

Společný základ programu

  1. Logika: Syntaxe, sémantika a odvozovací systémy pro výrokovou a predikátovou logiku, jejich korektnost a úplnost. Věta o kompaktnosti. Algoritmická rozhodnutelnost a složitost problému splnitelnosti pro výrokovou a predikátovou logiku. Gödelovy věty o neúplnosti. Rezoluční princip ve výrokové a predikátové logice. (MA007)
  2. Pravděpodobnost: Definice pravděpodobnostního prostoru. Náhodná proměnná, definice a její použití, Markovova a Čebyševova nerovnost. Náhodné procesy, Markovovy řetězce, invariantní distribuce, ergodická věta. Teorie informace (entropie, vzájemná informace), teorie kódování (Kraftova a McMillanova věta, Huffmanovo kódování, věta o kapacitě chybových kanálů). (IV111)
  3. Složitost: Časová a prostorová výpočetní složitost, základní složitostní třídy. Vztah deterministických a nedeterministických tříd, Savitchova věta. Pravděpodobnostní složitostní třídy. Alternování a polynomiální hierarchie. (IA012)
  4. Sémantiky programovacích jazyků: Operační, denotační a axiomatická sémantika. Úplná částečná uspořádání, věta o pevném bodě. Denotační sémantika while cyklu. Tvrzení o částečné korektnosti programů, nejslabší vstupní podmínka, invariant cyklu, Hoareův odvozovací systém, jeho korektnost a úplnost. Principy automatizované deduktivní verifikace. (IA011)
  5. Návrh algoritmů: Amortizovaná složitost, příklady využití. Techniky návrhu algoritmů: rozděl a panuj, dynamické programování, hladové algoritmy. Problém nejkratší cesty v grafu (Bellman-Ford, Floyd-Warshall, Dijkstra). (IV003)

Specializace – Diskrétní algoritmy a modely

  1. Algoritmika pro těžké problémy: Aproximační algoritmy; návrh aproximačních algoritmů; aproximační schémata. Parametrizované algoritmy; pseudopolynomiální algoritmy. Typy pravděpodobnostních algoritmů; derandomizace. (IA101)
  2. Teorie grafů: Eulerova věta. Oreho věta. Vlastnosti stromů. Rovinné grafy; Eulerova formule; věta o pěti barvách; charakterizace rovinných grafů. Vrcholová a hranová barevnost; Brooksova věta; Vizingova věta. Vrcholová a hranová souvislost; Mengerovy věty; Königova věta; Hallova věta. Ramseyova věta. (MA010)
  3. Algoritmická teorie her: Hry v normální formě; čisté a smíšené strategie; dominované strategie; iterovaná eliminace ostře dominovaných strategií. Nashovo ekvilibrium; support enumeration; von Neumannova věta (minimax). Extenzivní forma her; subgame-perfect equilibrium; zpětná indukce. Opakované hry; grim trigger; folk theorems. Kombinatorické aukce; Bayesovské hry; Bayesovské Nashovo ekvilibrium. (IA168)
  4. Optimalizace (povinné pro studium dle kontrolní šablony 2022/2023): Optimalizace bez omezení (Nelder-Meadova metoda, metoda největšího spádu, Newtonovské metody). Lineární programování (simplexová metoda) a celočíselné programování. (PV027)
  5. Grafové algoritmy (povinné pro studium dle kontrolní šablony 2023/2024 nebo novější): Problém minimální kostry (hladové algoritmy, Fredman-Tarjan, Karger-Klein-Tarjan). Toky v sítích (Ford-Fulkerson, Edmonds-Karp, Dinitz, redukce problémů na toky); párování v bipartitních grafech. Edmondsův algoritmus pro maximální párování. Stromová šířka. Problém grafového izomorfismu (heuristiky, izomorfismus stromů). (MA015)

Specializace – Formální analýza počítačových systémů

  1. Ověřování modelu (model checking): Ověřování modelu pro logiky lineárního a větvícího se času, enumerativní a symbolický přístup, bounded model checking, k-indukce. Abstrakce přechodových systémů, metoda CEGAR. Dosažitelnost řízená vlastností (Property Directed Reachability). (IA169)
  2. Statická analýza programů: Analýza ukazatelů a dynamicky-alokované paměti (shape analysis). Prořezávání programů (slicing). Symbolická exekuce. Automatické generování testů (grey-box, white-box testing). Verifikace pomocí automatů, symbolické exekuce a interpolace. Konfigurovatelná analýza programů. (IA159)
  3. Splnitelnost a automatické usuzování: Rozhodování splnitelnosti formulí výrokové logiky (DPLL, CDCL). Predikátová logika a teorie v predikátové logice (lineární aritmetika celých a reálných čísel, teorie polí). Rozhodování splnitelnosti predikátových formulí vzhledem k teoriím, jejich kombinacím (CDCL(T)) a techniky pro kvantifikované formule. (IA085)
  4. Algoritmy pro kvantitativní verifikaci: Časované systémy, časované automaty, regionová konstrukce pro časované automaty. Pravděpodobnostní systémy, Markovovy řetězce (DTMC, CTMC), Markovovy rozhodovací procesy. Dosažitelnost v pravděpodobnostních systémech. Odměny v pravděpodobnostních systémech. Specifikace a ověřování vlastností časovaných a pravděpodobnostních systémů. (IA175)

Specializace – Kvantové a jiné neklasické výpočetní modely

  1. Náhodnostní algoritmy: Principy a metody tvorby náhodnostních algoritmů. Pravděpodobnostní složitostní třídy a jejich vztah k deterministickým složitostním třídám. Náhodné procházky, Markovovy řetězce a jejich aplikace. Náhodnostní metody v kryptografii. (IA062)
  2. Základy kvantového zpracování informace: Kvantový bit a jeho stav, princip superpozice, měření, evoluce kvantového stavu. Složené systémy, stavový prostor, zobecněné Bornovo pravidlo, kvantově provázané stavy, hradla, husté kódování a teleportace. Reversibilní výpočty Booleovských funkcí, kvantový parelelismus. Základy kvantové kryptografie (protokol BB84), Shorův and Groverův algoritmus. (IA066)
  3. Algoritmika pro těžké problémy: Aproximační algoritmy; návrh aproximačních algoritmů; aproximační schémata. Parametrizované algoritmy; pseudopolynomiální algoritmy. Typy pravděpodobnostních algoritmů; derandomizace. (IA101)
  4. Kryptografie: Symetrické šifrování (proudové a blokové šifry, módy blokových šifer). Kryptografické hashovací funkce, MACy, autentizované šifrování. Asymetrické šifrování: RSA, kryptografie založená na diskrétním logaritmu, protokol Diffie-Hellman. Eliptické křivky a kryptografie s jejich využitím. Digitální podpisy. Zero-knowledge protokoly. Bezpečnostní definice (sémantická bezpečnost, CPA a CCA bezpečnost, existenční podvrh) (IA174)

Specializace – Principy programovacích jazyků

  1. Lambda kalkul: Syntaxe, sémantika: alfa a beta konverze, pořadí vyhodnocení výrazů. Rekurze a kombinátory pevného bodu. Kódovaní datových typů. Aplikované lambda kalkuly. Typovaná rozšíření - jednoduše typovaný lambda kalkul, system Hindley-Milner, System F. Typové odvození. (IA081 nebo IA038)
  2. Moderní koncepty funkcionálního programování: Typové třídy a jejich implementace, konstruktorové třídy, funkční závislosti. Funktory, monády, jejich význam a aplikace. Monadické tranformátory. Typová rozšíření - generalizované algebraické typy (GADT), závislé typy. (IA014)
  3. Překladače: Deterministické bezkontextové jazyky a jejich syntaktická analýza. Třídy LL(k), SLL(k), LR(k) a jejich analyzátory. Sémantická analýza. Analýza jmen a rozsahů, tabulka symbolů. Typová kontrola a typová konverze.Techniky generování kódu, optimalizace. (PA008, IA006)
  4. Kryptografie: Symetrické šifrování (proudové a blokové šifry, módy blokových šifer). Kryptografické hashovací funkce, MACy, autentizované šifrování. Asymetrické šifrování: RSA, kryptografie založená na diskrétním logaritmu, protokol Diffie-Hellman. Eliptické křivky a kryptografie s jejich využitím. Digitální podpisy. Zero-knowledge protokoly. Bezpečnostní definice (sémantická bezpečnost, CPA a CCA bezpečnost, existenční podvrh) (IA174)

Specializace – Fundamenty umělé inteligence

  1. Algoritmická teorie her: Hry v normální formě; čisté a smíšené strategie; dominované strategie; iterovaná eliminace ostře dominovaných strategií. Nashovo ekvilibrium; support enumeration; von Neumannova věta (minimax). Extenzivní forma her; subgame-perfect equilibrium; zpětná indukce. Opakované hry; grim trigger; folk theorems. Kombinatorické aukce; Bayesovské hry; Bayesovské Nashovo ekvilibrium. (IA168)
  2. Neuronové sítě: Vícevrstvé sítě a jejich výrazové schopnosti. Učení neuronových sítí: Gradientní sestup, zpětná propagace, praktické otázky učení (příprava dat, inicializace vah, volba a adaptace hyperparametrů). Regularizace. Konvoluční sítě. Rekurentní sítě. (PV021)
  3. Reinforcement Learning: Markovovy rozhodovací procesy, formulace RL úlohy. Hlavní typy RL algoritmů, včetně příkladů: Monte Carlo vs. temporal difference metody, on-policy vs. off-policy metody, policy evaluation vs. control úlohy. Deep Q-networks. Policy gradient metody, metody typu Actor-Critic, algoritmus PPO. Multi-armed bandit úlohy. Model-based RL, offline RL. (PA230)
  4. Bayes networks: TBA (IA178)