Algoritmy a datové struktury II

Přednáška z algoritmů a datových struktur II [NTIN061] se koná v ZS 2007/2008 v úterky od 14:00 v S5.

datum co se přednášelo zápis
2. 10. Booleovské obvody coby jednoduchý model paralelního počítače – formální definice, časová (počet hladin) a prostorová (počet hradel) složitost výpočtu. Obvod pro paralelní sčítání dvou n-bitových čísel. 20.1.
9. 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. 8.2.
16. 10. Dinicův algoritmus na hledání maximálního toku a jeho analýza. Převod maximálního párování v bipartitním grafu na maximální (celočíselný) tok. 20.1.
23. 10. Goldbergův algoritmus na hledání maximálního toku a jeho analýza. 8.1.
30. 10. Animace průběhu Goldbergova algoritmu a dokončení jeho analýzy. Třídící sítě a bitonické třídění. 20.1.
6. 11. Vyhledávání v textu: naivní algoritmy, algoritmus KMP (Knuth, Morris, Pratt) a jeho analýza. Přistup pomocí hashování à la Rabin-Karp. 20.1.
13. 11. Vyhledávání v textu: algoritmus AC (Aho, Corasicková) pro hledání více řetězců najednou. Násobení a vyhodnocování polynomů, náznak použití metody Rozděl a panuj. 20.1.
20. 11. Opakování operací s komplexními čísly z mateřské školky (slidy). Diskrétní Fourierova transformace a její inverze. Algoritmus FFT a jeho aplikace.
(zapsali Marek Polák, Karel Jakubec a Gábor Ocsovszký) 		18.2.
27. 11. Geometrické algoritmy: Konvexní obal a Voroného diagramy (Fortunův algoritmus). Obrázky z přednášky (nejdůležitější okamžiky v průběhu Fortunova algoritmu). Můžete si vyzkoušet animaci Fortunova algoritmu v Javě, případně totéž v Algovision.
(zapsali Michal Staša, Jan Návrat a Bohdan Maslowski) 		18.2.
4. 12. Rozhodovací problémy a převody mezi nimi: SAT, 3-SAT, 3,3-SAT, nezávislá množina a klika v grafu, 3D párování.
(zapsali Martin Chytil a Vladimír Kudelas) 		21.1.
11. 12. NP-úplnost: definice, Cookova věta (SAT je NP-úplný) a náčrt jejího důkazu. Zoo NP-úplných problémů. Převod obvodového SATu na obyčejný SAT. Převod 3,3-SATu na 3D párování (dokončení z minula).
(zapsali Radoslav Krivák, František Kačmárik a Daniel Remiš) 		21.1.
18. 12. Co dělat, když potkáme NP-úplný problém. Řešení speciálních případů: maximální nezávislá množina ve stromu (hladově), problém batohu s malými celými čísly (dynamickým programováním). Aproximační algoritmy: problém obchodního cestujícího s trojúhelníkovou nerovností (pomocí minimální kostry), problém batohu (kvantování).
Pozor: aproximaci problému batohu jsem na přednášce řekl špatně, podívejte se, prosím, do zápisků, tam je opravena.
(zapsali František Haško a Jozef Menda) 		15.1.
8. 1. Algoritmy okolo teorie čísel. Algebraické základy (grupy, multiplikativní grupa modulo n, invertibilní prvky, Eulerova funkce, Malá Fermatova a Eulerova věta). Řešení lineárních kongruencí pomocí Euklidova algoritmu. Pravděpodobnostní testování prvočíselnosti: Fermatův a Rabinův-Millerův test.
(zapsali Ondrej Hofferek, Jakub Brecka a Lucia Banáková)
Viz též můj textík o algoritmech s čísly. 		23.6.

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, a schopnost tyto znalosti aplikovat; doporučena jest čistá mysl a dobrá nálada :)

Pokud budete potřebovat vyzkoušet během letního semestru, ozvěte se mi.

Nezkouším důkaz Cookovy věty a důkaz nejpodrobnější verze lemmatu o nenasycených převedeních v analýze Goldbergova algoritmu.

Také si můžete přečíst otázky z minulých zkoušek.

Cvičení

K přednášce existuje několik více méně ekvivalentních cvičení. Pokud chcete chodit s jinou skupinou, než do které oficiálně patříte (nebo pokud jste na kombinovaném studiu), domluvte se, prosím, s cvičícími – jediné omezení je místo v posluchárnách.

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

Zde je pár úloh pro inspiraci.

Zápisky

Zápočet můžete mimo cvičení získat také za sepsání zápisu z jedné přednášky (každou přednášku max. 3 lidé, nejlépe společně). Zápis je třeba poslat do čtyř týdnů od přednášky a ideální bude, když jej napíšete v TeXu. Inspirovat se můžete stávajícími zápisky, v případě jakýchkoliv problémů rád pomohu. Na kreslení obrázků se může hodit Vrr.

Pokud chcete zápis psát, přihlašte se mi, prosím, na začátku přednášky. A také si přečtěte návod (viz níže).

Ke stažení:

Pozor: Ne všechny zápisky jsem už stihl detailně zkontrolovat, takže je možné, že se v nich tu a tam vyskytují drobné chyby. Pokud narazíte na něco podezřelého, pak si to buďto rozmyslete sami, nebo se mi ozvěte, ale rozhodně to, prosím, nepapouškujte u zkoušky.

Literatura

Knížku v češtině, která by pokrývala celou přednášku, bohužel dosud nikdo nenapsal (ale třeba se nějaká časem vyklube z vašich zápisků). 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í:

Viz též literatura k ADS 1.

Stránku spravuje Martin Mareš