Algoritmy a datové struktury I

Přednáška z Algoritmů a datových struktur I [NTIN060] se koná v LS 2012/2013 ve středy od 15:40 v S5.

Co se přednášelo

datum téma
20. 2. Úvodní příklad s reportáží (nejdelší rostoucí podposloupnost) a přehlídka způsobů, jak ho vyřešit. Pokus o definici algoritmu. Výpočetní model RAM.
27. 2. Časová a paměťová složitost. Programování na RAMu a počítání složitosti. Srovnání růstu funkcí (obrázky). Asymptotická notace (O, Ω, Θ). Úvod do grafových algoritmů.
6. 3. Grafové algoritmy: Prohledávání do šířky (BFS), souvislost s nejkratšími cestami. Reprezentace grafů a její vliv na časovou složitost BFS. Prohledávání do hloubky (DFS). Klasifikace hran v DFS (stromové, zpětné, dopředné, příčné).
13. 3. Použití DFS na detekci cyklů a topologické uspořádání. Algoritmy pro acyklické grafy (hledání nejdelších cest a kritických hran). Další aplikace DFS: hledaní mostů, rozklad na komponenty silné souvislosti.
18. 3. Nejkratší cesty v ohodnocených grafech: trojúhelníková nerovnost pro vzdálenosti (neplatí v grafech se zápornými cykly), nejkratší cesta versus nejkratší sled. Algoritmus pro nejkratší sledy dané délky. Princip relaxace a Bellmanův-Fordův algoritmus. Přednáška výjimečně v pondělí od 15:40 v S5.
27. 3. Nejkratší cesty: Dijkstrův algoritmus a dva důkazy jeho správnosti (z relaxačního algoritmu a pomocí podrozdělování a "budíků"). Implementace pomocí různých hald (binárních a k-regulárních). Úvod do minimálních koster: lemma o řezech.
3. 4. Problém minimální kostry: Jarníkův a Borůvkův algoritmus. Jednoznačnost minimální kostry a její určenost uspořádáním hran. Kruskalův algoritmus, udržování komponent souvislosti a Union-Find problem.
10. 4. Datové struktury: obecný úvod, problém reprezentace slovníku a množiny. Binární vyhledávací stromy a operace s nimi. Dokonale vyvážené stromy a dolní odhad složitosti operací. Hloubkově vyvážené (AVL) stromy: definice, důkaz jejich logaritmické hloubky.
Příští dvě přednášky budou o 45 minut delší (na oslavu květnových státních svátků :)).
17. 4. Vyvažování AVL stromů pomocí rotací. (a,b)-stromy: definice, odhad hloubky, operace. Vkládání do (a,b)-stromu štěpením shora dolů. Červeno-černé stromy: definice, isomorfismus s (2,4)-stromy, operace Insert.
24. 4. Reprezentace řetězců pomocí písmenkových stromů (trie), použití pro čísla. Hešování: princip, volba hešovací funkce, c-universální systémy funkcí, 1-universální systém založený na skalárním součinu, dynamické rozšiřování tabulky. Metoda Rozděl a panuj: třídění sléváním (Mergesort), násobení n-ciferných čísel v čase O(nlog23).
15. 5. Věta o časové složitosti rekurzivních algoritmů (kuchařka alias Master theorem). Hledání k-tého nejmenšího prvku a různé způsoby volby pivota. Randomizace a průměrná časová složitost.
22. 5. Lineární algoritmus na výběr k-tého nejmenšího prvku (trik s pěticemi). QuickSort: princip, analýza průměrné složitosti. Dolní odhad složitosti třidění pomocí porovnávání. Strassenovo násobení matic (vzorce), aplikace na dosažitelnost v grafech.

Cvičení

Cvičení k této paralelce vedou:

Studentům kombinovaného studia doporučuji přečíst si úvodní informace, 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á.

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.

Otázky z minulých zkoušek

Literatura

Knížku v češtině, která by pokrývala celou přednášku, bohužel dosud nikdo nenapsal (ale pracujeme na tom). Zatím mohu doporučit:

(tituly označené "kň" jsou k dispozici v knihovně MFF)

Ostatní zajímavé knihy:

Sbírky příkladů:

Různé:

Stránku spravuje Martin Mareš