Otázky N-TEI Teoretická informatika

Pro studenty dle kontrolní šablony 2022/2023 nebo novější:

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: Diskrétní a spojitý pravděpodobnostní prostor. Náhodná proměnná a její použití. Střední hodnota, rozptyl. Náhodné procesy, Markovovy řetězce. Teorie informace (entropie, vzájemná informace), teorie kódování (Huffmanovo kódování, kapacita 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, metoda konjugovaných gradientů, metody s omezeným krokem, úloha nejmenších čtverců). Lineární programování 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ů

(povinné pro studium dle kontrolní šablony 2022/2023)

  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. Abstrakce přechodových systémů, metoda CEGAR. (IA159, IA169)
  2. Metody testování: Mise a strategie testování, problém orákula, metody pro testování produktu bez znalosti kódu (black-box testing) a se znalostí kódu (white-box testing). Pokrytí kódu. Symbolická exekuce jako metoda pro detekci chyb a generování testů. (IA169)
  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. Spojité a hybridní systémy: Spojité a hybridní systémy: Definice systému, objekt, model, systém. Dynamický systém, přechodová funkce, rozměr systému, stavové rovnice. Spojitý, diskrétní, hybridní systém. Lineární a nelineární systémy, linearizace. Stabilita a charakterizace stability. Identifikovatelnost systému, estimace parametrů. Dosažitelnost v hybridním systému. Základní pojmy teorie řízení: řiditelnost, pozorovatelnost. (IV120)

(povinné pro studium dle kontrolní šablony 2023/2024 nebo novější)

  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: Bellmanovy rovnice pro pravděpodobnostní systémy. Algoritmy pro analýzu vlastností temporálních i na odměnách založených, iterace hodnot, iterace strategií, lineární a kvadratické programování, zpětnovazebné učení. Regionová konstrukce pro časované systémy. (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, kvantové zdroje náhodnosti, kvantová interference a princip superpozice. Kvantová bezpečnost a princip neurčitosti. Schrodingerova rovnice a kvantová hradla. Kvantové provázání a teleportace. Shorův and Groverův algoritmus. Základní principy kvantové kryptografie (one-time pad systém, protokol BB84). Typy kvantových měření. (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)

Pro studenty dle kontrolní šablony 2021/2022 nebo starší:

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.
  2. Pravděpodobnost. Diskrétní a spojitý pravděpodobnostní prostor. Náhodná proměnná a její použití. Střední hodnota, rozptyl. Náhodné procesy, Markovovy řetězce. Teorie informace (entropie, vzájemná informace), teorie kódování (Huffmanovo kódování, kapacita chybových kanálů).
  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.
  4. 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ě (LSTM).
  5. 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.

Specializace - Algoritmy výpočetních modelů

  1. Náhodnostní algoritmy. Principy a metody tvorby nahodnostních algoritmů. Pravděpodobnostní složitostní třídy a jejich vztah k deterministickým složitostním třídam. Náhodné procházky, Markovovy řetězce a jejich aplikace. Náhodnostní metody v kryptografii.
  2. Základy kvantového zpracování informace. Kvantový bit, kvantové zdroje náhodnosti, kvantová interference a princip superpozice. Kvantová bezpečnost a princip neurčitosti. Schrodingerova rovnice a kvantová hradla. Kvantové provázání a teleportace. Shorův and Groverův algoritmus. Základní principy kvantové kryptografie (one-time pad systém, protokol BB84). Typy kvantových měření.
  3. Numerické metody. Chybová analýza, absolutní a relativní chyba. Iterativní metody řešení systémů nelineárních rovnic, metody Jacobi a Gauss-Seidel. Řešení systému nelineárních rovnic, Newtonova metoda. Interpolace a aproximace. Numerická derivace a integrace.
  4. Algoritmika pro těžké problémy. Algoritmické techniky pro řešení těžkých problémů: pseudopolynomiální a parametrizované algoritmy. Aproximativní algoritmy. Heuristiky lokálního vyhledávání a genetické algoritmy.

Specializace - Formální verifikace a analýza programů

  1. Pojem kvality ve vývoji software. Softwarové metriky. Principy Clean Code & SOLID přístupů. Testování kódu ve vývojovém cyklu. Testování jednotek, integrační testování, systémové a akceptační testování. Testování a optimalizace výpočetní výkonnosti. Vývojové metody založené na testování. Řídící procesy týkající se zajištění kvality software. (PV260)
  2. Metody testování. Mise a strategie testování, problém orákula, metody pro testování produktu bez znalosti kódu (black-box testing) a se znalostí kódu (white-box testing). Pokrytí kódu. Symbolická exekuce jako metoda pro detekci chyb a generování testů. (IA169)
  3. Model checking. Ověřování modelu (model checking) pro logiky lineárního a větvícího se času, enumerativní a symbolický přístup, bounded model checking. Abstrakce přechodových systémů, metoda CEGAR. (IA169, IA159)
  4. Games in the strategic form: Dominant strategies, iterative elimination of strictly dominated strategies, Nash equilibria in pure and mixed strategies. Computing Nash equilibria: Support enumeration, linear programming for zero-sum games, computational complexity. Extensive form games: Perfect and imperfect information, mixed and behavioral strategies, subgame-perfect equilibria, backward induction, repeated games (Folk theorems). Incomplete information games: Strict incomplete information games, dominant strategies, ex-post Nash equilibria; Bayesian games, Bayesian Nash equilibria, auctions.

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í.
  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.
  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.
  4. Real time systémy. Pojmy "soft" a "hard" systémů reálného času. Plánování řízené hodinami (clock-driven) a událostmi (event-driven). Periodické úlohy: Algoritmy EDF, RM a DM, optimalita, testy naplánovatelnosti pomocí utilizace (utilization) a analýzy časových požadavků (time-demand analysis). Aperiodické úlohy: Polling server, deferrable server, sporadic server, test naplánovatelnosti pomocí analýzy časových požadavků. Sporadické úlohy: Akceptační test (acceptance test). Plánování se zdroji: Inverze priorit, deadlock. Protokoly priority inheritance, priority ceiling. Základní znalosti plánování pro více procesorů (časové anomálie, migrace úloh, maximální utilizace, globální vs dělené (partitioned) plánování, Dhallův efekt).

Specializace - Diskrétní algoritmy a modely

  1. Games in the strategic form: Dominant strategies, iterative elimination of strictly dominated strategies, Nash equilibria in pure and mixed strategies. Computing Nash equilibria: Support enumeration, linear programming for zero-sum games, computational complexity. Extensive form games: Perfect and imperfect information, mixed and behavioral strategies, subgame-perfect equilibria, backward induction, repeated games (Folk theorems). Incomplete information games: Strict incomplete information games, dominant strategies, ex-post Nash equilibria; Bayesian games, Bayesian Nash equilibria, auctions.
  2. Eulerova 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.
  3. Optimalizace bez omezení (Nelder-Meadova metoda, metoda největšího spádu, newtonovské metody, sdružený gradient, metody s omezeným krokem, úloha nejmenších čtverců). Lineární programování a celočíselné programování. Globální optimalizace (simulované žíhání, genetické algoritmy).
  4. Algoritmika pro těžké problémy. Algoritmické techniky pro řešení těžkých problémů: pseudopolynomiální a parametrizované algoritmy. Aproximativní algoritmy. Heuristiky lokálního vyhledávání a genetické algoritmy.