teaching:ads11920_prednaska
Toto je starší verze dokumentu!
Přednáška z Algoritmů a datových struktur I 2019/20
Přednáším Diskrétní matematiku (NTIN060) každé úterý v 10:40 v učebně S11.
Pokud se mnou chcete cokoliv probrat, jste vítáni v mé pracovně S326 na Malé Straně. Případně napište e-mail na adresu koutecky+ads1@iuuk.mff.cuni.cz
a/nebo uveďte v předmětu text [ADS1]
.
V druhé paralelce přednáší Jan Hric, přednášku se budeme snažit udržovat synchronní.
datum | co se přednášelo [zdroj] |
---|---|
18. 2. | Hledání nejbohatšího úseku. Snaha o definici algoritmu. Von Neumannův výpočetní model, Ǒčková notace ($\mathcal{O}, \mathcal{o}, \Omega, \omega$), výpočetní model RAM [L 1.1, 2] |
25. 2. | Základní grafové algoritmy: prohledávání do šířky (BFS), prohledávání do hloubky (DFS) na neorientovaném grafu, detekce mostů, DFS na orientovaném grafu [L 5.1-5.6] |
3. 3. | Pokračování DFS: topologické číslování; detekce komponent silné souvislosti v lineárním čase; úvod do nejkratších cest [L 5.7-6.1] |
10. 3. | Nejkratší cesty: Dijkstrův algoritmus pořádně; obecný relaxační algoritmus; Bellman-Ford umí detekovat záporný cyklus; Floyd-Warshall umí spočítat matici vzdáleností [L 6.1-6.4] |
17. 3. | Minimální kostry: Jarníkův (Primův, Dijkstrův) algoritmus, Borůvkův algoritmus, Kruskalův algoritmus, keříková struktura Union-Find [L 7.1-7.4], video přednášky, "zápis" z přednášky |
24. 3. | Plán: stromové datové struktury: binární vyhledávací stromy, AVL-stromy [L 8] video přednášky, zápis z přednášky (OneNote) |
31. 3. | $(a,b)$-stromy, červeno-černé stromy [L 8]video přednášky, zápis z přednášky (OneNote) |
7. 4. | rekapitulace LLRB, amortizace, úvod do hešování [L 9.1-9.2; 11.3] video přednášky, zápis z přednášky (OneNote) |
14. 4. | Plán: Hešování s otevřenou adresací, univerzální hešování [L 11.3-11.4], video přednášky, zápis z přednášky (OneNote) |
21. 4. | Rozděl a panuj - úvod [L 10], video z přednášky zápis z přednášky (OneNote) |
28. 4. | Plán: Rozděl a panuj - hledání medánu v lineárním čase [L 10.6-10.9] |
Užitečné zdroje
- Mareš, Valla: Průvodce labyrintem algoritmů [L]
teaching/ads11920_prednaska.1587548902.txt.gz · Poslední úprava: 2020/04/22 11:48 autor: Martin Koutecky