Algoritmy a datové struktury I

Přednáška z algoritmů a datových struktur I [NTIN060] se koná v LS 2008/2009 v úterky od 14:00 v S5.

datum co se přednášelo
24. 2. Euklidův algoritmus a jeho analýza. Pokus o definici algoritmu, časové a paměťové složitosti. Srovnání růstu funkcí (obrázky).
3. 3. Výpočetní model RAM a opravdová definice složitosti (jednotkové nebo logaritmické ceny instrukcí). Asymptotická notace (O, Ω, Θ). Úvod do grafových algoritmů.
10. 3. Prohledávání grafů do šířky (BFS) a do hloubky (DFS). Reprezentace grafů a jejich vliv na složitost. Souvislost BFS s nejkratšími cestami. DFS stromy a klasifikace hran (stromové, zpětné, dopředné, příčné).
17. 3. Aplikace prohledávání do hloubky: topologické uspořádání grafu (a jeho využití pro hledání nejdelších cest a kritických vrcholů v acyklických grafech), rozklad na silně souvislé komponenty, hledání mostů.
24. 3. Hledání nejkratší cesty v ohodnoceném grafu: obecný "průzkumnický" algoritmus, Bellmanův-Fordův a Dijkstrův algoritmus (odvození pomocí podrozdělování hran i obecný důkaz).
31. 3. Nejkratší cesty: graf předchůdců a jeho vlastnosti. Implementace Dijkstrova algoritmu pomocí různých hald (slidy). 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.
7. 4. Hledání minimální kostry hladově (Kruskalův algoritmus). Udržování komponent souvislosti a Union-Find problem. Metoda Rozděl a panuj: třídění sléváním (Mergesort), násobení n-ciferných čísel v čase O(nlog23).
14. 4. 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.
21. 4. Ještě jednou k-tý nejmenší prvek, tentokrát lineárně i bez náhody (trik s pěticemi). Quicksort: princip, analýza průměrné složitosti, implementace. Dolní odhad složitosti třidění pomocí porovnávání.
28. 4. Přihrádkové třídění (záznamy s klíči z malého universa, k-tice čísel, třídění po číslicích). Mapa třídicích algoritmů. Binární vyhledávací stromy a operace s nimi.
5. 5. Vyvažování vyhledávacích stromů: AVL stromy, (a,b)-stromy.
12. 5. Červeno-černé stromy (left-leaning varianta) a jejich odvození z (2,4)-stromů. Datové struktury pro celá čísla: číslicové stromy (trie), hashování. Přehlídka hashovacích funkcí, analýza průměrného zaplnění přihrádky.
19. 5. Lineárně-algebraické algoritmy: Strassenovo násobení matic (vzorce). Inverze trojúhelníkové matice. Permutacní matice. LUP dekompozice. Aplikace v teorii grafů: dosažitelnost, Floydův-Warshallův algoritmus na nejkratší cesty. Aplikace v LA: determinanty, inverze matice, řešení soustav lineárních rovnic.

Cvičení

Cvičení najdete v rozvrhu (k této paralelce patří cvičení lidí z KAMu a KSVI).

Stránky mého cvičení

Zápisky

K přednášce průběžně vznikají elektronické zápisky inspirované těmi z mé předloňské přednášky. Velice děkuji Martinovi Kouteckému, Markétě Popelové a Petrovi Jankovskému za péči, jíž jim věnovali, a také předloňským zapisovatelům, z jejichž textů vycházíme.

Aktuální stav zápisků s datem poslední změny:

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 :)

Nezkouším Strassenovy vzorce a detaily algoritmu na LUP dekompozici matic.

Můžete se podívat na otázky z minulých termínů.

Termíny v září: 11. 9. a 18. 9., pak už budu do konce září pryč.

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)

Programátorská kuchařka KSP (nepříliš formální textíky o různých algoritmech):

Ostatní zajímavé knihy:

Sbírky příkladů:

Různé:

Stránku spravuje Martin Mareš