Algoritmy a datové struktury II

Přednáška z algoritmů a datových struktur II [NTIN061] se koná v ZS 2011/2012 v pátky od 9:00 v S3.

datum co se přednášelo
7. 10. Vyhledávání v textu: naivní algoritmy, algoritmus KMP (Knuth, Morris, Pratt) a jeho analýza.
14. 10. Vyhledávaní v textu: algoritmus Aho-Corasicková pro hledání více řetězců. Přístup pomocí hashování à la Rabin-Karp. Úvod do toků v sítích.
21. 10. Toky: Fordův-Fulkersonův a Dinicův algoritmus. Celočíselné sítě a celočíselné toky.
28. 10. Státní narozeniny. Přednáška se nekoná.
4. 11. Dokončení analýzy Dinicova algoritmu. Aplikace toků na hledání největšího párování v bipartitním grafu. Goldbergův algoritmus, jeho analýza a animace průběhu výpočtu.
11. 11. Dokončení analýzy Goldbergova algoritmu. Stručně o hradlových sítích.
18. 11. Paralelní programování pomocí hradlových sítí: sčítání přirozených čísel booleovským obvodem, bitonické třídění komparátorovou sítí.
25. 11. Bitonické třídění: lemma o separátorech, dolní odhad složitosti. Geometrické algoritmy v rovině: konvexní obaly, průsečíky úseček zametáním roviny, lokalizace bodu pomocí persistentních datových struktur.
2. 12. Konstrukce persistentních stromů s logaritmickým prostorem na verzi. Opakování operací s komplexními čísly z mateřské školky (slidy). Násobení polynomů a rychlá Fourierova transformace (algoritmus FFT).
9. 12. Inverzní Fourierova transformace. Rozhodovací problémy a převody mezi nimi: SAT a 3-SAT
16. 12. Převody problémů: 3,3-SAT, nezávislá množina a klika v grafu, 3D-párování.
6. 1. Třídy P a NP, NP-těžké a NP-úplné problémy a jejich základní vlastnosti. Cookova věta o NP-úplnosti SATu a její důkaz: booleovské obvody pro problémy z P (to jsme jen nastínili), důkaz NP-úplnosti obvodového SATu, převod obvodového SATu na CNF-SAT. Zoo klasických NP-úplných problémů.
13. 1. První pomoc při setkání s těžkým problémem. Řešení speciálních případů: barvení intervalových grafů, pseudopolynomiální algoritmus pro problém batohu. Aproximační algoritmy: obchodní cestující v metrickém prostoru (2-aproximace), aproximační schéma pro problém batohu.

Učební texty

Postupně přetvářím zápisy z minulých let na učební texty k jednotlivým přednaškám. Většina textů už je hotová, ale ještě neprošly důkladnými korekturami. Pokud tedy narazíte na jakoukoliv chybu, nepřesnost nebo těžko pochopitelné místo, dejte mi prosím vědět.

Cvičení

K přednášce existuje několik cvičení a jelikož letos existuje jediná paralelka, všechna cvičení by měla být ekvivalentní. Zápočet je nutný ke zkoušce a podmínky k jeho udělení určuje cvičící.

Stránka mého cvičení (St 9:00 v S10)

Studentům kombinovaného studia doporučuji vybrat si libovolného cvičícího a domluvit se s ním na získání zápočtu za domácí úkoly. Účast na cvičení není nutná, ale hodí se alespoň občas se tam stavit, abyste měli přehled, co se dělá.

Zkoušky

Termíny jsou vypsány v SISu, zapisujte se, prosím, tam.

Ke zkoušce je potřeba:

Předtermíny: čtvrtek 22. 12. od 17:20 a pátek 13. 1. od 14:00. Můžete přijít i bez zápočtu (v takovém případě známku zapíši, až budete zápočet mít). Zkouším vše, ještě nepřednesenou látku si můžete nastudovat z učebních textů.

Můzete se pro inspiraci podívat na otázky z minulých zkouškových termínů a z let 2007 a 2009.

Literatura

Knížku v češtině, která by pokrývala celou přednášku, bohužel dosud nikdo nenapsal (ale pracujeme na ní). Zatím mohu doporučit:

(tituly označené "kň" jsou k dispozici v knihovně MFF)

Animovaný výklad algoritmů v Algovision kolegy Kučery.

Sbírky příkladů:

Ostatní:

Stránku spravuje Martin Mareš