Algoritmy a datové struktury I

Přednáška z algoritmů a datových struktur I [NTIN060] se koná v LS 2006/2007 v pondělky od 15:40 v S3.

datum co se přednášelo zápis
19. 2. Eukleidův algoritmus a jeho analýza. Pokus o definici algoritmu, časové a paměťové složitosti. Srovnání růstu funkcí (obrázky). 24.5.
26. 2. Asymptotická notace (O, Ω, Θ). Metoda Rozděl a panuj a analýza rekurzivních algoritmů. Násobení čísel v lepším než kvadratickém čase. Řešení rekurentních rovnic a Master theorem alias kuchařková věta. 24.5.
5. 3. Strassenův algoritmus na násobení matic a jeho obrázkový důkaz. Hledání k-tého nejmenšího prvku rekurzivně, různé způsoby výběru pivota (pevně, randomizovaně, rekurzivně přes pětice). 24.5.
12. 3. Průměrná časová složitost algoritmů, jak vzhledem ke vstupům, tak při použití náhodných čísel. Rychlokurs teorie pravděpodobnosti: elementární a složené jevy, náhodné veličiny, střední hodnoty. Analýza průměrné složitosti hledání k-tého nejmenšího prvku při náhodné volbě pivota, ekvivalence s případem, kdy pivot je pevný a vstup náhodný. Hříčka s mícháním karet. 26.4.
19. 3. QuickSort, jeho složitost v průměrném případě a pár slov o implementaci. Rozhodovací stromy, dolní odhad na třídění pomocí porovnávání. 2.9.
26. 3. Přihrádkové třídění čísel a k-tic čísel v lineárním čase. Binární vyhledávací stromy a jejich vyvažování. AVL stromy: definice a důkaz logaritmické hloubky. 12.11.
2. 4. Vyvažování vyhledávacích stromů pomocí rotací. Insert a Delete v AVL stromech. (a,b)-stromy: definice, operace Insert a Delete pomocí štěpení a slučování vrcholů. 7.12.
16. 4. Základní grafové algoritmy: prohledávání do hloubky (DFS) a do šířky (BFS). Rozklad grafu na komponenty souvislosti. Hledání mostů a artikulací pomocí DFS. Charakterizace hran při DFS (stromové, zpětné, příčné a dopředné). 30.5.
23. 4. Další aplikace DFS: topologické třídění acyklických orientovaných grafů a jeho využití k hledání kritických cest; hledání silně souvislých komponent orientovaných grafů. 14.6.
30. 4. Hledání nejkratších cest: prohledávání do šířky, odvození Dijkstrova algoritmu podrozdělováním hran a jeho zrychlování haldou (obyčejnou a k-regulární). Dosažitelnost v grafu pomocí násobení matic. 28.5.
7. 5. Opět nejkratší cesty: důkaz Dijkstrova algoritmu pro libovolné kladné délky hran, Bellman-Fordův a Floyd-Warshallův algoritmus a jejich analýza. 30.9. (část)
14. 5. Problém minimální kostry: Jarníkův, Borůvkův a Kruskalův algoritmus. Lemma o řezech, jednoznačnost minimální kostry a její určenost uspořádáním hran. Problém udržování komponent souvislosti, řešení v čase O(log n) pomocí stromů. Červeno-černé stromy: definice, odhad hloubky, operace Insert. 23.5.
21. 5. Hashování se separovanými řetězci a jeho rozbor. Nafukovací hashovací tabulky. Příklady hashovacích funkcí: modulo, násobení iracionálním číslem, polynomy, výběr náhodné funkce z vhodné množiny (universální hashování). 10.9.

Cvičení

Cvičení najdete v rozvrhu (k této paralelce patří cvičení lidí z KAMu), čtvrteční (od 10:40 v S10) je v lichých týdnech anglicky, v sudých cvičím já ekvivalentní v češtině.

Stránky mého cvičení

Zápisky

Zápočet můžete také získat za sepsání zápisu z jedné přednášky (každou přednášku max. 3 lidé, nejlépe společně). Zápis byste mi měli 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.

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.

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

V posledních dvou čtvrtcích semestru budou předtermíny (opět viz SIS), na nich nezkouším poslední přednášku a zápočet můžete získat dodatečně.

Také si můžete přečíst zadání písemek z minulých termínů: 17. 5., 24. 5., 30. 5., 7. 6., 14. 6., 21. 6., 28. 6., 12. 9., 19. 9..

Již se v SISu objevil jeden srpnový termín a dva v září. Pokud vám ani jeden nevyhovuje, pak mi, prosím, napište. Varování: Poslední týden v září budu pryč.

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.

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

Ostatní zajímavé knihy:

Sbírky příkladů:

Stránku spravuje Martin Mareš