Kdy a kde:

• I/2-X/36 : Po 12:20 v M6

Za co je zapocet:

• Zapoctovy program (v libovolnem primerenem programovacim jazyce; primerenost posuzuji ja) -- tema vcetne specifikace, v niz shrnete, co ma vami vytvoreny program umet, byste mi meli oznamit do 15.12.2005. Program by mel implementovat netrivialni variantu nektereho z algoritmu popsanych na prednasce. Soucasti zapoctaku je dokumentace v primerenem rozsahu: Uzivatelska na takove urovni, abych byl schopen program vyzkouset. Programatorska by mela poskytovat spis hruby prehled o tom, kde je co implementovano a pripadne jak jsou realizovany datove struktury (samotny algoritmus neni potreba do detailu popisovat, staci odkaz na prednasku ci literaturu). Nejake napady na zapoctaky, nicmene pokud vas napada nejake jine tema, muzeme se dohodnout.
• Ucast na cviceni neni povinna; na druhou stranu, pokud po me bude chtit zapocet nekdo, koho jsem na cviceni nikdy nevidel, asi bude mit problem.

Obsah cviceni:

• (3.10.) Dynamicke programovani -- vzdalenost retezcu, batoh, pocet neredundantnich uzavorkovani vyrazu, pocet maximalnich nezavislych mnozin stromu.
• (10.10.) Vyhledavani v textu -- Knutt, Morris & Pratt; Boyer & Moore; Rabin & Karp; Aho&Corasick, suffixove pole a stromy.
• (17.10.) Odpadlo.
• (24.10.) Diskretni Fourierova transformace -- aplikace na rychle nasobeni polynomu, FFT nad telesem ruznym od komplexnich cisel, obraz sinusovky a exponenciely v DFT.
• (31.10.) Hradlove site -- zbytek po deleni. Povidani o tocich v sitich, aplikace na urceni souvislosti grafu a na hledani perfektniho parovani.
• (7.11.) Odpadlo.
• (14.11.) Opakovani a doplneni DFT, povidani o hradlovych sitich.
• (21.11.) Geometricke algoritmy -- vlastnosti Voroneho diagramu, Delaunayova triangulace, konstrukce VD metodou rozdel a panuj, dvojice nejblizsich a nejvzdalenejsich bodu v zadane mnozine (v rovine), slozitost nalezeni konvexniho obalu, lokalizace bodu v rovine.
• (28.11.) Toky v sitich -- hledani max. toku s omezenimi na minima na hranach. Slozitost Dinitzova algoritmu pro 1-omezene site.
• (5.12.) Aplikace toku. Zaokrouhlovani hodnot v matici. Tarjanuv algoritmus pro toky v ridkych sitich.
• (12.12.) NP-uplnost. Definice, prevody k-barveni na (k+1)-barveni, SATu na 3-SAT. Polynomialni reseni kliky pro fixni velikost a 2-SATu.
• (19.12.) Hornovske formule. SAT s omezenim poctu vyskytu promennych. Hamiltonovske cesty a kruznice. Nejkratsi a nejdelsi cesty v grafech.
• (2.1.) Aproximacni a online algoritmy -- lyzar, strankovani, volba manzelky. Aproximace 3-SATu a maximalniho rezu.
• (9.1.) RSA. Generovani klicu pro RSA, inverze v Z_k. Prumerny plat, deleni lupu (algoritmy odolne proti podvodum). Zakladni fakta o poctu prvocisel a prvociselnych delitelu.