Algoritmy a datové struktury I

Přednáška z Algoritmů a datových struktur I [NTIN060] se koná v LS 2014/2015 v pondělky od 12:20 v S3.

Z přednášek se pořizují videozáznamy.

Co se přednášelo

datum téma
16. 2. Úvodní příklad s nejdelší rostoucí podposloupností a přehlídka způsobů, jak ho vyřešit. Pokus o definici algoritmu.
23. 2. Výpočetní model RAM. Čas a prostor konkrétního výpočtu (různé varianty: jednotková cena, logaritmická cena, omezený rozsah čísel), časová a paměťová složitost algoritmu. Programování na RAMu a počítání složitosti: příklad s tříděním výběrem. Asymptotická notace (O, Ω, Θ).
2. 3. Grafové algoritmy: Prohledávání do šířky (BFS), souvislost s nejkratšími cestami. Reprezentace grafů a její vliv na časovou složitost BFS.
9. 3. Prohledávání do hloubky (DFS). Klasifikace hran v DFS (stromové, zpětné, dopředné, příčné). Hledání mostů. Použití DFS na detekci cyklů a topologické uspořádání.
16. 3. Algoritmy pro acyklické grafy (hledání nejdelších cest). Rozklad na komponenty silné souvislosti. 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.
23. 3. Nejkratší cesty: Dijkstrův algoritmus a jeho odvození z BFS pomocí podrozdělování hran a "budíků"). Implementace pomocí různých hald (binárních a k-regulárních). Princip relaxace a důkaz korektnosti Dijkstrova algoritmu.
30. 3. Nejkratší cesty: Bellmanův-Fordův algoritmus. Problém minimální kostry: Jarníkův a Borůvkův algoritmus, lemma o řezech. 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.
6. 4. Ēostre, Paasfees, Великден, Ülestõusmispühad, Πάσχα, Páskar, 復活祭, Pace.
13. 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í.
20. 4. Hloubkově vyvážené (AVL) stromy: definice, důkaz jejich logaritmické hloubky. Vyvažování AVL stromů pomocí rotací. (a,b)-stromy: definice, odhad hloubky, operace Insert.
27. 4. Vkládání do (a,b)-stromu štěpením shora dolů. Červeno-černé stromy: definice, isomorfismus s (2,4)-stromy, operace Insert. Reprezentace řetězců pomocí písmenkových stromů (trie), použití pro čísla. Hešování: přihrádky s řetězci prvků, volba hešovací funkce, dynamické rozšiřování tabulky a jeho amortizace.
4. 5. Hešování: c-universální systémy funkcí a jejich použití při hešováni; konstrukce 1-universálního systému pomocí skalárního součinu. Metoda Rozděl a panuj: třídění sléváním (Mergesort), násobení n-ciferných čísel v čase O(nlog23).
11. 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.
18. 5. Strassenovo násobení matic (vzorce). 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í.
Domácí úkol: přihrádkové třídění (záznamy s klíči z malého universa, k-tice čísel, třídění po číslicích).

Cvičení

Cvičení k této paralelce vedou:

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.

Zkoušky

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

Ke zkoušce je potřeba:

Pár zkouškových termínů vypíši i v září, objeví se v SISu.

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š