Algoritmy a datové struktury II

Přednáška z algoritmů a datových struktur II [NTIN061] se koná v ZS 2013/2014 v pondělky od 12:20 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. Přístup pomocí hashování à la Rabin-Karp.
14. 10. Vyhledávaní v textu: algoritmus Aho-Corasicková pro hledání více řetězců. Úvod do toků v sítích.
21. 10. Toky: Fordův-Fulkersonův algoritmus a důkaz jeho správnosti pomocí řezů. Celočíselné sítě a celočíselné toky. Dinicův algoritmus.
28. 10. Přednáška se nekoná, slavíme státní narozeniny. Dokončení rozboru Dinicova algoritmu se prosím naučte ze skriptíček.
4. 11. Toky: Goldbergův algoritmus, jeho analýza a animace průběhu výpočtu.
11. 11. Paralelní programování pomocí hradlových sítí: sčítání přirozených čísel booleovským obvodem. Úvod do komparátorových sítí.
18. 11. Bitonické třídění komparátorovou sítí. Geometrické algoritmy v rovině: konvexní obaly, průsečíky úseček zametáním roviny.
25. 11. Dokončení algoritmu na průsečíky úseček. Zmínka o lokalizaci bodu pomocí persistentních datových struktur. Úvod k násobení polynomů. Opakování operací s komplexními čísly z mateřské školky (slidy).
2. 12. Násobení polynomů, rychlá Fourierova transformace (algoritmus FFT) a její inverze. Rozhodovací problémy a převody mezi nimi.
9. 12. Převody problémů: SAT, 3-SAT, nezávislá množina a klika v grafu.
16. 12. Převody problémů: 3,3-SAT a 3D-párování. 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.
6. 1. První pomoc při setkání s těžkým problémem. Řešení speciálních případů: nezávislá množina ve stromech, 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.

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í.

Cvičení vedou:

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: pondělky 16. 12. a 6. 1. 2013, obojí od 14:00 a 16: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, 2009 a 2011.

Pokud jste zkoušku nestihli v zimním zkouškovém, budou termíny i v letním zkouškovém a v září.

Literatura

Postupně k přednáškám z ADS1+2 sepisujeme učební texty. Jednou z nich třeba bude knížka.

Co se existujících knížek týče, mohu doporučit:

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

Sbírky příkladů:

Ostatní:

Stránku spravuje Martin Mareš