Algoritmy a datové struktury II

Přednáška z Algoritmů a datových struktur II [NTIN061] se koná v ZS 2015/2016 ve středy od 14:00 v S3.

datum co se přednášelo
7. 10. Vyhledávání v textu: značení okolo řetězců, 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í hešování à la Rabin-Karp.
21. 10. Toky v sítích: Opakování definic a základních tvrzení o tocích. Fordův-Fulkersonův algoritmus a důkaz jeho správnosti pomocí řezů. Celočíselné sítě a celočíselné toky. Převod párování v bipartitním grafu na celočíselný tok.
28. 10. Přednáška se nekoná, slavíme státní narozeniny.
4. 11. Toky: Dinicův algoritmus a jeho analýza.
11. 11. Toky: Goldbergův algoritmus, jeho analýza a animace průběhu výpočtu.
18. 11. Dokončení analýzy Goldbergova algoritmu. Paralelní programování pomocí hradlových sítí: sčítání přirozených čísel booleovským obvodem.
25. 11. Paralelní algoritmy: Bitonické třídění komparátorovou sítí. Geometrické algoritmy v rovině: konvexní obal,.
2. 12. Průsečíky úseček zametáním roviny. Voroného diagramy a lokalizace bodu pomocí persistentních datových struktur. Úvod k násobení polynomů.
9. 12. Opakování operací s komplexními čísly z mateřské školky (slidy). Násobení polynomů, rychlá Fourierova transformace (algoritmus FFT) a její inverze.
16. 12. Rozhodovací problémy a převody mezi nimi. Převody problémů: SAT, 3-SAT, nezávislá množina a klika v grafu.
6. 1. 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 s náznakem důkazu: booleovské obvody pro problémy z P, důkaz NP-úplnosti obvodového SATu, převod obvodového SATu na CNF-SAT.
13. 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), zmínka o aproximačním schématu 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á. Za mnou samozřejmě můžete přijít na konsultaci, domluvte se e-mailem.

Zkoušky

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

Ke zkoušce je potřeba:

Předtermíny: Můžete přijít bez zápočtu (v takovém případě známku zapíši, až budete zápočet mít). Pozor, zkouším i dosud nepřednesenou látku; měla by nicméně být pokryta doporučenou literaturou.

Zdroje

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š