pozadavky

Podrobnější požadavky pro státnice (verze pro LS 2022/2023)

1. Matematika pro informační technologie

Složitost:  Výpočetní modely, algoritmická rozhodnutelnost, základní složitostní třídy, regulární jazyky. Související předmět: NMMB415 Automaty a výpočetní složitost.

Definice Turingova stroje. Výpočtový problém jako funkce nebo jazyk. Nerozhodnutelné problémy (nerozhodnutelnost HALTING).
Časová a prostorová složitost výpočtu. Savitchova věta. Koncept přijímání jazyka nedeterministickým strojem.
NP-úplnost a Cook-Levinova věta. Definice třídy NP pomocí nedeterministického stroje a pomocí svědecké relace, jejich ekvivalence.
Popis problému P vs. NP.  Definice konečného automatu, vztah konečného automatu a Turingova stroje bez pracovní pásky. Regulární jazyky - definice a příklady.

Konvexní optimalizace: Základní metody konvexní optimalizace. Související předmět: NMMB409 Konvexní optimalizace.

Definice a základní vlastnosti konvexních množin a funkcí, kužely. Základní typy úloh konvexní optimalizace (lineární, kvadratické, semidefinitní a kuželové programy).
Vektorová a vícekriteriální optimalizace a skalarizace. Lagrangián a Lagrangeova duální funkce. Silná a slabá dualita, Slaterovo kritérium. KKT podmínky a jejich význam.
Algoritmy pro řešení úloh konvexní optimalizace (gradientní metoda, Newtonova metoda pro minimalizaci bez omezujících podmínek, metoda vnitřního bodu).

Algoritmy na polynomech: Groebnerovy báze a  Buchbergerův algoritmus. Související předmět NMMB413 Algoritmy na polynomech.

Monočleny, přípustná uspořádání, definice Groebnerovy báze. Přepisování a redukovaná forma polynomu. S-polynomy a Buchbergerovo kritérium. Buchbergerův algoritmus
a důkaz jeho korektnosti. Redukovaná Groebnerova báze - existence a jednoznačnost.

Algoritmy na mřížích: Mříže a algoritmus LLL, související předmět NMMB411 Algoritmy na mřížích.

Definice mříže, základní výpočetní problémy na mřížích (SVP,CVP a jejich aproximační verze).
LLL redukovaná báze a její vlastnosti. LLL algoritmus a zdůvodnění jeho korektnosti (důkaz, že jde o polynomiální algoritmus není součástí zkoušky, bylo by ale dobré vědět, co vše by bylo třeba pro takový důkaz ověřit).

Tématický okruh 2: Student z témat 2A - 2E zvolí dvě, ke každému pak dostane jednu otázku. 

2A Algebraické a číselné algoritmy:  Související předměty NMMB413 Algoritmy na polynomech a NMMB402 Číselné algoritmy

Rozklady polynomů: Berlekampův algoritmus pro faktorizaci polynomů jedné neurčité nad konečným tělesy (včetně důkazu korektnosti), Henselovo zdvihání (včetně důkazu Henselova lemmatu), Berlekampův-Henselův algoritmus pro faktorizaci primitivních celočíselných polynomů (popis jednotlivých částí algoritmu).

Groebnerovy báze - aplikace: Algoritmy pro řešení problému náležení do ideálu či radikálu v oboru polynomů více neurčitých nad algebraicky uzavřeným tělesem, algoritmus pro nalezení průniku ideálů. Eliminační lemma a jeho využití. Příklady využití těchto algoritmů při řešení problémů z planimetrie.V rámci otázky je možné též zkoušet témata uvedená v otázce 1.

Číselné algoritmy: Algoritmy pro faktorizaci složených čísel: Pollard rho (princip metody, Floydova metoda hledání cyklů), Pollardova (p-1)-metoda (B hladká a B-mocná čísla, popis základní verze algoritmu, dvoufázová varianta není předmětem zkoušky), ECM (popis algoritmu, odvození vzorců pro algoritmus, odhad složitosti není předmětem zkoušky). CFRAC a kvadratické síto (u obou algoritmů popis Dixonova faktorizačního schématu - relace, hladké relace, lineární fáze, parciální relace; u CFRAC pak algoritmus pro řetězový rozvoj odmocniny ze kterého algoritmus generuje relace a omezení velikosti pravé strany
těchto relací; u kvadratického síta pak princip prosívání a Tonelliho-Shanksův algoritmus; odhad složitosti a technika malého koeficientu nejsou předmětem zkoušky).
Algoritmy pro diskrétní logaritmus: Přehled generických algoritmů pro diskrétní logaritmus (Pollard rho, Pohlig-Hellman, Baby steps - Giant steps).
Faktorizace pomocí diskrétního logaritmu - algoritmus, který pomocí orakula pro řešení zobecněného problému diskrétního logaritmu v multiplikativní grupě okruhu Z_N provede efektivně faktorizaci N.

2B Algoritmy pro lineární algebru a optimalizaci  související předměty NMNV411 Algoritmy maticových a iteračních metod, NMNV533 Řídké matice v numerické matematice a  NMNV503 Numerické metody optimalizace 1

Řídký Choleského a LU rozklad, řídký QR rozklad. Krylovovské iterační metody pro řešení soustav lineárních algebraických rovnic a lineárních aproximačních problémů, včetně konstrukce algebraických předpodmínění. Metody pro řešení nelineárních algebraických rovnic a jejich soustav, metody pro minimalizaci funkcionálu bez omezení, lokální a globální konvergence metod.

2C Kryptologie (předměty NMMB331 Booleovské funkce, NMMB404 Kryptanalýza, NMMB411 Algoritmy na mřířích, NMMB432 Náhodnost a výpočty)

Základy Booleovských funkcí (ohnuté funkce, APN a AB funkce, ekvivalence, S-boxy, Walshova transformace a LAT, diferenční uniformita a DDT). Posloupnosti dané posuvnými registry. Základní kryptoanalytické útoky na blokové šifry (diferenciální a lineární kryptoanalýza, útoky vyšších řádů, meet-in-the-middle) a proudové šifry (korelace, algebraické útoky), útoky postranním kanálem. Součástí otázky z kryptologie může být konkrétní příklad (provést kryptoanalýzu daného schématu a pod).

Aplikace mříží: NTRU (popis základní verze NTRU, korektnost, mřížový útok na NTRU), aplikace LLL (např. útok na RSA s malým veřejným exponentem - princip Coppersmithovy metody hledání malých kořenů polynomiální kongruence).

Pravděpodobnostní složitostní třídy, pseudonáhodné generátory:Intraktivní protokoly. Simulace jako základní myšlenka důkazu IP=PSPACE. Pojem pseudonáhodného generátoru.  Derandomizace.

2D Počítačové vidění a robotika (předměty NMMB440 Geometrie počítačového vidění, NMMB442 Geometrické problémy v robotice)

Matematický model perspektivní kamery.Výpočet pohybu kalibrované kamery z obrazů neznámé scény. 3D rekonstrukce ze dvou obrazů neznámé scény. Geometrie tří kalibrovaných kamer. Denavit-Hartenbergův popis kinematiky manipulátoru. Inverzní kinematická úloha pro šestistupňový sériový manipulátor – formulace a řešení. Kalibrace parametrů manipulátoru – formulace a řešení.

Podrobnější rozpis požadavků pro předmět Geometrie počítačového vidění:

1) Matematický model perspektivní kamery. Projekční a kalibrační matice kamery a jejich výpočet z průmětů prostorových bodů do obrazu.

2) Výpočet polohy kalibrované kamery z průmětu tří prostorových bodů do obrazu.

3) Epipolární gemetrie dvou nekalibrovaných kamer. Vlastnosti a výpočet fundamentální matice.

4) Epipolární gemetrie dvou kalibrovaných kamer. Vlastnosti a výpočet esenciální matice.

5) Výpočet pohybu kalibrované kamery z esenciální matice a 3D rekonstrukce ze dvou obrazů neznámé scény.

2E Zpracování obrazu a počítačová grafika (předměty NPGR013 Speciální funkce a transformace ve zpracování obrazu, NPGR029 Variační metody ve zpracování obrazu, NMMB433 Geometrie pro počítačovou grafiku, NMNV531 Inverzní metody a regularizace)

Modelování inverzních problémů, regularizační metody, digitalizace obrazu, zaostřování a odšumování obrazu, detekce hran, obrazová registrace, komprese, syntéza obrazu, metody compressed sensing.

Analytická, kinematická a diferenciální geometrie: Shodná, afinní a projektivní zobrazení v rovině, jejich aplikace na řešení úloh, panoramatické lepení fotografií a animaci pohybu v rovině.
Kvaterniony a popis rotací v prostoru s jejich pomocí, LERP, SLERP. Diferenciální geometrie křivek, křivost a torze, animace pohybu podél křivky, pohyb s minimální rotací.