Algoritmy a datové struktury II

Přednáška z Algoritmů a datových struktur II [NTIN061] se koná v ZS 2025/2026 ve čtvrtky od 15:40 v N1.

Můžete sledovat přímý přenos z přednášek.

Kdybyste chtěli cokoliv konzultovat, rád si s vámi popovídám. Ozvěte se mi prosím na adresu mares+ads2@kam.mff.cuni.cz.

datum co se přednášelo záznam
2. 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
9. 10. Vyhledávaní v textu: algoritmus Aho-Corasicková pro hledání více řetězců. Přístup pomocí hešování à la Rabin-Karp. Lemma o kořenech polynomů a důsledky pro hešování řetězců. video
17. 10. Toky v sítích: Definice a základní tvrzení o tocích. Fordův-Fulkersonův algoritmus a důkaz jeho správnosti pomocí řezů. video
23. 10. Toky: Celočíselné sítě a celočíselné toky. Převod párování v bipartitním grafu na celočíselný tok. Reformulace pomocí průtoků. Síť rezerv a skládání toků. Dinicův algoritmus a jeho analýza. video
30. 10. Toky: Goldbergův algoritmus a jeho analýza. Vylepšená verze s výběrem nejvyššího vrcholu. Animace průběhu výpočtu. video
6. 11. Násobení polynomů: reprezentace polynomu grafem, nástin rekurzivního algoritmu. Opakování operací s komplexními čísly (slidy). Rychlá Fourierova transformace (algoritmus FFT) a její inverze. video
13. 11. Poznámky k FFT (slidy): nerekurzivní verze, spektrální analýza, zpracování signálu. Paralelní programování pomocí hradlových sítí: sčítání přirozených čísel booleovským obvodem. video
20. 11. Hradlová síť pro násobení čísel. Komparátorové sítě pro třídění založené na bitonických posloupnostech. Geometrické algoritmy v rovině: konvexní obal. video
27. 11. Přednáška se nekoná: otevíráme dveře.
4. 12. Geometrické algoritmy v rovině: průsečíky úseček zametáním roviny, zmínka o Voroného diagramech, lokalizace bodu pomocí persistentních datových struktur. Zamyšlení nad tím, kdy je algoritmus efektivní. video
11. 12. Plán: Rozhodovací problémy a převody mezi nimi: SAT, 3-SAT, nezávislá množina a klika v grafu, 3,3-SAT.
18. 12. Plán: Převod 3,3-SATu na 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 SAT pro CNF. Zoo klasických NP-úplných problémů.
8. 1. Plán: Jak si poradit s NP-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). Obchodní cestující: neaproximovatelnost verze bez trojúhelníkové nerovnosti. Aproximační schéma pro problém batohu.

Cvičení

K přednášce existuje několik cvičení a jelikož letos existuje jediná česká paralelka, všechna cvičení by měla být ekvivalentní. Podmínky k udělení zápočtu určuje cvičící.

Zkoušky

Předtermín bude v pátek 19. 12. od 14:00 v posluchárně S5 na Malé Straně. Přihlaste se prosím v SISu.

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

Zkouška bude ústní s písemnou přípravou: Na začátku zadám otázky. Vy si odpovědi rozmyslíte (času bude dost) a sepíšete. Pak si o nich spolu popovídáme a na základě toho dostanete buďto známku, nebo nápovědu k další práci. Cílem je, aby každý vyřešil všechno, a známka se bude odvíjet od toho, jak moc jsem vám musel napovídat :)

Ke zkoušce je potřeba:

Otázky z minulých zkoušek

Pokud byste z nějakého důvodu zkoušku nestihli složit, mohu vás vyzkoušet i později – během letního zkouškového, během semestru, případně i o prázdninách. Na to už obvykle termíny nevypisuji, vše je na individuální domluvě. Tuto možnost nicméně doporučuji využít spíš v nouzi, než si tak rovnou zkoušku plánovat.

Zdroje

Ostatní zajímavé knihy:

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

Sbírky příkladů:

Stránku spravuje Martin Mareš