Title: Státnice / Obecná informatika / Pokročilé algoritmy a datové struktury

Dynamické programování: princip dynamického programování (řešení podproblémů od nejmenších k největším)

Dynamické programování: aplikace: nejdelší rostoucí podposloupnost

Dynamické programování: aplikace: editační vzdálenost

Grafové algoritmy: komponenty silné souvislosti orientovaných grafů

Grafové algoritmy: toky v sítích: Dinicův algoritmus

Grafové algoritmy: toky v sítích: Goldbergův algoritmus

Q: Grafové algoritmy: toky v celočíselně ohodnocených grafech, aplikace na párování v bipartitních grafech
A: plus existuje celá teorie s těmi celočíselnými toky, ale na tu aplikaci na párování by mělo stačit tohle, tak nevím, co všechno je potřeba umět

Q: Algoritmy vyhledávání v textu: Knuth-Morris-Pratt
A: automaty:(

Algoritmy vyhledávání v textu: Aho-Corasicková

Q: Algebraické algoritmy: diskrétní Fourierova transformace a její aplikace
A: Později přejdeme do komplexních čísel a zavedeme DFT:
O FFT později v Anki, o inverzi kdyžtak dočtěte v průvodci.
Aplikace: spektrální rozklad (na frekvence), počítání konvoluce, přečtěte si v průvodci

Algebraické algoritmy: výpočet Fourierovy transformace algoritmem FFT

Q: RSA: šifrování, dešifrování a generování klíčů
A: Stanovský:
Bezoutova rovnost, rozšířený Euklidův algoritmus:
Eulerova funkce, malá Fermatova věta:
Multiplikativní invers:
Kryptosystém RSA (šifrování, dešifrování):
Medvěd:
Generování klíčů:

Aproximační algoritmy: aproximační poměr a relativní chyba

Aproximační algoritmy: aproximační schémata

Q: Aproximační algoritmy: příklady: obchodní cestující, batoh
A: Obchodní cestující:
(důkaz klasicky vynecháváme)
Batoh:
(důkaz přeskočen)

Paralelní třidění pomocí komparátorových sítí