Algoritmy a datové strukury I (NTIN060)

Jan Hubička, hubicka@kam.mff.cuni.cz

Konzultace po dohodě emailem (nejlépe ve středu nebo pátek na MS, 2. patro). Do subjektu emailů pište "ADS2026".

Odpřednesená látka

17. února
Co to je algoritmus. Definice výpočetního modelu RAM. Časová a prostorová složitost. O notace. Video
24. února
Prohledávání grafů do hloubky a klasifikace hran. Aplikace pro hledání mostů Video
3. března
Aplikace DFS, topologické třídění, topologická indukce, silně souvislé komponenty Video
10. března
Dokončení silně souvislých komponent. Nejkratší cesty: Disktrův algoritmus Video z technických důvodů bohužel chybí. Video Martina Mareše z loňka (na konci jsou KSS) Video Martina Mareše z loňka (na konci jsou KSS)
17. března
Nekratší cesty II: Důkaz správnosti a časová složitost Dijsktrova algoritmu. Bellmanův-Fordův algoritmus. Floydův-Warshallův algoritmus. Video z technických důvodů bohužel chybí. Video Martina Mareše z loňka
24. března
Minimální kostry Video
31. března
Úvod do datových struktur pro množiny a uspořádané množiny. Binární vyhledávací stromy Video Martina Mareše z loňka
7. dubna
Insert a delete v AVL stromu
14. dubna
(a,b)-stromy (insert, delete), RB stromy (jen převod z (2,4)-stromu), krátký úvod do Hašován (separované řetezce a otevřená adresace). Pokračování bue po třídicích algoritmech
21. dubna
Rozděl a panuj (merge sort, Karatsuba, kuchařková věta), Strassenůva algoritmus
28. dubna
Rozděl a panuj dokončení. Hledání k-teho nejmenšího prvku pomoci QuickSelect: různé metody volby pivota, randomizace a průměrná časová složitost. Složitost QuickSortu jako zobecnění QuickSelectu. Opakování dolního odhadu časové složitosti třídění a přihrádkové třídění. Lineární algoritmus pro výběr k-tého nejmenšího prvku.
5. května
Hašování (řešení kolizí, univerzální hešování)
6. května
Dynamické programování (nejdelší rostoucí podposloupnost, editační vzdálenost)
19. května
Přednáška zrušena (látka byla dokončena minulou přednášku).

Odkazy