Algoritmy a datové struktury II

Přednáška z algoritmů a datových struktur II [NTIN061] se koná v ZS 2009/2010 v pátky od 10:40 v S3.

datum co se přednášelo zápisky
2. 10. Problém maximálního toku v síti. Definice sítí, toků a řezů. Minimaxová věta o tocích a řezech. Fordův-Fulkersonův algoritmus. Převod párování v bipartitním grafu na tok. 2010-02-09
9. 10. Toky: Dinicův algoritmus a jeho analýza. 2010-02-09
16. 10. Toky: Goldbergův algoritmus, jeho analýza a animace průběhu výpočtu. 2010-02-09
23. 10. Podrobnější analýza Goldbergova algoritmu. Booleovské obvody coby model paralelního počítače. 2010-01-15
30. 10. Paralelní sčítání a násobení booleovským obvodem. Komparátorové sítě a bitonické třídění. 2011-01-28
6. 11. Vyhledávání v textu: naivní algoritmy, algoritmus KMP (Knuth, Morris, Pratt) a jeho analýza. Přístup pomocí hashování à la Rabin-Karp. 2010-02-09
13. 11. Vyhledávání v textu: algoritmus Aho-Corasicková pro hledání více řetězců najednou (zápis viz minulá přednáška). Úvod do geometrických algoritmů: medvědi, ryby a konvexní obaly. 2010-02-09
20. 11. Geometrické algoritmy v rovině: průsečíky úseček, Voroného diagramy (jen definice a základní vlastnosti), lokalizace bodu pomocí persistentních datových struktur. Persistentní stromy s prostorem O(log n) na verzi. 2010-02-09
27. 11. Násobení polynomů, diskrétní Fourierova transformace a algoritmus FFT. Opakování operací s komplexními čísly z mateřské školky (slidy). 2010-02-12
4. 12. Rozhodovací problémy a převody mezi nimi: SAT, 3-SAT, 3,3-SAT, nezávislá množina a klika v grafu. 2010-02-09
11. 12. 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. Zoo klasických NP-úplných problémů. Převod 3,3-SAT → 3D-párování. 2010-02-12
18. 12. Důkaz Cookovy věty: booleovské obvody pro problémy z P, přímý důkaz NP-úplnosti obvodového SATu, převod obvodového SATu na CNF-SAT. První pomoc při setkání s těžkým problémem. Řešení speciálních případů: maximální nezávislá množina ve stromu, pseudopolynomiální algoritmus pro problém batohu. viz ↑ a ↓
8. 1. Aproximační algoritmy: obchodní cestující v grafu s trojúhelníkovou nerovností (2-aproximace), neaproximovatelnost obchodního cestujícího bez trojúhelníkové nerovnosti, aproximační schéma pro problém batohu. 2010-02-12
15. 1. Algoritmy okolo teorie čísel. Multiplikativní grupa modulo n a její základní vlastnosti. Řešení lineárních kongruencí pomocí rozšířeného Euklidova algoritmu. Invertibilní prvky. Fermatova a Eulerova věta. Čínská věta o zbytcích. Testování prvočíselnosti: Fermatův test a Carmichaelova čísla. Šifrovací algoritmus RSA. skriptíčka

Cvičení

K přednášce existuje několik cvičení, vyberte si pokud možno takové, které patří k této paralelce (přednáška z druhé paralelky je sice podobná obsahem, leč nikoliv pořadím látky).

Zápočet je nutný ke zkoušce a podmínky k jeho udělení určuje cvičící. Obvykle se uděluje za vypracování zápočtové práce – ta by měla obsahovat implementaci některého zajímavého a netriviálního algoritmu, ať už z přednášky nebo odjinud, a krátký popis toho, jak algoritmus funguje, proč funguje a jakou má časovou a paměťovou složitost. Každopádně se předem domluvte s cvičícím na konkrétním algoritmu.

Pro inspiraci pár námětů na zápočtové práce.

Zkoušky

Termíny jsou vypsány v SISu, zapisujte se, prosím, tam. Ke zkoušce je potřeba zápočet, znalost toho, co bylo odpředneseno (definice, algoritmy a jejich rozbor, věty a jejich důkazy) a schopnost tyto znalosti aplikovat (řešit algoritmické problémy podobné těm, co se dělaly na cvičení); doporučena jest čistá mysl a dobrá nálada :)

Můzete se pro inspiraci podívat na otázky z minulých zkouškových termínů a z předloňských zkoušek.

Pokud jste zkoušku nestihli v zimním zkouškovém, dejte mi vědět, ještě chci vypsat nějaký termín v letním semestru a letním zkouškovém.

Zápisky

K přednáškám průběžně vznikají zápisky (viz odkazy u jednotlivých přednášek), inspirované těmi z předloňska.

Také si můžete stáhnout všechny zápisky v jednom souboru: verze 2011-01-28.

Zdrojové texty zápisků v TeXu bydlí (včetně kompletní historie) v Gitové repository na git://git.ucw.cz/ads2.git.

Velice děkuji Pavlovi Klavíkovi, Michalovi Kozákovi, Petrovi Jankovskému, Markétě Popelové a Vojtovi Tůmovi za péči, jíž jim věnovali, a také předloňským zapisovatelům, z jejichž textů vycházíme.

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š