Algoritmy a datové struktury II

Přednáška z Algoritmů a datových struktur II [NTIN061] se koná v ZS 2021/2022 v pondělky od 15:40 v N1.

Kdybyste čemukoliv nerozuměli, rád si s vámi domluvím konzultaci. Ozvěte se mi prosím na adresu mares+ads2@kam.mff.cuni.cz.

datum co se přednášelo záznam
4. 10. Vyhledávání v textu: značení okolo řetězců, naivní algoritmy, algoritmus KMP (Knuth, Morris, Pratt) a jeho analýza. Jak hledat více řetězců? Pokud vám nefungují videa, vypněte si AdBlock. Jedno z jeho pravidel zakazuje všechna URL s podřetězcem /ads2/ :D video
11. 10. Vyhledávaní v textu: algoritmus Aho-Corasicková pro hledání více řetězců. Přístup pomocí hešování à la Rabin-Karp. Lemmata o polynomech a důsledky pro hešování řetězců. video
18. 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ů. Ekvivalentní definice: čisté toky. Celočíselné sítě a celočíselné toky. Převod párování v bipartitním grafu na celočíselný tok. video
25. 10. Toky: Dinicův algoritmus a jeho analýza. Základní myšlenky Goldbergova algoritmu. video
1. 11. Toky: Goldbergův algoritmus, jeho analýza a animace průběhu výpočtu. video
8. 11. Goldbergův algoritmus s výběrem nejvyššího vrcholu. Násobení polynomů: reprezentace polynomu grafem, nástin rekurzivního algoritmu. Opakování operací s komplexními čísly z mateřské školky (slidy). video
15. 11. Násobení polynomů: rychlá Fourierova transformace (algoritmus FFT) a její inverze. Obvod pro FFT a nerekurzivní FFT. Poznámky k FFT (slajdy): spektrální analýza, zpracování signálu, algebraická interpretace. video
22. 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í. video
29. 11. Komparátorové sítě: konstrukce separátoru. Geometrické algoritmy v rovině: konvexní obal, průsečíky úseček zametáním roviny. video
6. 12. Plán: Voroného diagramy a lokalizace bodu pomocí persistentních datových struktur. Rozhodovací problémy a převody mezi nimi. Převody problémů: SAT, 3-SAT, nezávislá množina a klika v grafu.

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í. Podmínky k udělení zápočtu určuje cvičící.

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.

Zdroje

Ostatní zajímavé knihy:

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

Sbírky příkladů:

Stránku spravuje Martin Mareš