Algoritmy a datové struktury I

Přednáška z Algoritmů a datových struktur I [NTIN060] se koná v LS 2010/2011 ve čtvrtky od 14:00 v S3.

Druhou paralelku přednáší Jan Hric.

Co se přednášelo

datum téma zápis
24. 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, časová a paměťová složitost. 2011-05-31
3. 3. Programování na RAMu a počítání složitosti. Srovnání růstu funkcí (obrázky). Asymptotická notace (O, Ω, Θ). Grafové algoritmy: Prohledávání do šířky (BFS), souvislost s nejkratšími cestami. 2011-05-23
10. 3. 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é). Použití DFS na detekci cyklů a topologické uspořádání. 2011-05-24
17. 3. Algoritmy pro acyklické grafy (hledání nejdelších cest a kritických hran). Další aplikace DFS: hledaní mostů, rozklad na komponenty silné souvislosti. 2011-06-21
24. 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. Bellmanův-Fordův algoritmus. Obecný průzkumnický algoritmus a jeho vlastnosti. 2011-07-31
31. 3. Přednáška se nekoná (je místo ní Matematická analýza II Roberta Šámala; naopak v pátek 27. 5. bude ADS1 místo analýzy). —
7. 4. Nejkratší cesty: Dijkstrův algoritmus a dva důkazy jeho správnosti (přes průzkumnický algoritmus a pomocí podrozdělování a "budíků"). Implementace pomocí různých hald (binárních a k-regulárních). Floydův-Warshallův algoritmus pro výpočet matice vzdáleností. 2011-05-24
(nehotové)
14. 4. 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 hladový algoritmus, udržování komponent souvislosti a Union-Find problem. 2011-05-24
21. 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. 2011-05-23
28. 4. Vyvažování AVL stromů pomocí rotací. (a,b)-stromy: definice, odhad hloubky, operace. 2011-05-23
5. 5. Pozor! Přednáška odpadá. Místo ní bude Programování 2 kolegy Töpfera, naopak 12. 5. bude místo P2 další přednáška z ADS1. —
12. 5. 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). Hashování: princip, volba hashovací funkce, c-universální systémy funkcí, dynamické rozšiřování tabulky, 1-universální systém založený na skalárním součinu. 2011-05-30
(část)
19. 5. Metoda Rozděl a panuj: třídění sléváním (Mergesort), násobení n-ciferných čísel v čase O(nlog23). Věta o časové složitosti rekurzivních algoritmů (kuchařka alias Master theorem). Knížka
26. 5. Hledání k-tého nejmenšího prvku a různé způsoby volby pivota. Randomizace a průměrná časová složitost. 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. Knížka
27. 5. Implementace QuickSortu (slidy). Dolní odhad složitosti třidění pomocí porovnávání. 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ů. Strassenovo násobení matic (vzorce), aplikace na dosažitelnost v grafech. 2011-07-31

Cvičení

Stránka mého cvičení (Čt 9:00 v S7)

Další cvičení k této paralelce vedou Honza Bulánek, Zdeněk Dvořák, Vladan Majerech, Milan Straka, Tomáš Valla.

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: pátky 20. 5. a 27. 5. od 13:00. 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).

Pár zkouškových termínů vypíši i v září, viz SIS.

Otázky z minulých zkoušek

Zápisky

K přednáškám průběžně vznikají zápisky – viz odkazy u jednotlivých přednášek, případně všechny zápisky v jednom souboru: verze 2011-07-31.

Kde chybí, zkuste nahlédnout do zápisků z let 2009 a 2007.

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

Velice děkuji Karlovi Královi, Janu Moskytovi Matějkovi, Pavlu Tauferovi a Pavolovi Rohárovi za péči, jíž jim věnovali, a také zapisovatelům z minulých let, z jejichž textů vycházíme.

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 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š