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. | 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. | 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, kuchařková věta, násobení dlouhých čísel [L 10], video z přednášky zápis z přednášky (OneNote) |
| 28. 4. | Rozděl a panuj - hledání medánu v lineárním čase; úvod do dynamického programování [L 10.6-10.9, L 12.1-12.2] video z přednášky, zápis z přednášky (OneNote) |
| 5. 5. | Dynamické programování - Editační vzdálenost; dolní odhady na třídění; quicksort v průměrném případě video z přednášky, zápis z přednášky (OneNote) [L 12.3, 3.3, 11.2] |
Užitečné zdroje
- Mareš, Valla: Průvodce labyrintem algoritmů [L]
Zkouška ADS 1 / 2020
Na zkoušce budou zadány
- Dva příklady na algoritmy či datové struktury z přednášky
- Dvě úlohy podobné těm ze cvičení
Hodnocení
Na 3 stačí znát definice a algoritmy a nechat se dostrkat k řešení aspoň jedné úlohy (nebo ji vyřešit neefektivně).
Na 2 je potřeba umět řešit úlohy s nápovědou, případně na ně najít méně efektivní algoritmus. Pokud jsme na přednášce o algoritmech vyslovovali nějaká tvrzení, je třeba znát aspoň zhruba jejich znění.
Na 1 je potřeba i rozbor algoritmů (správnost a složitost včetně důkazů tvrzení) a umět řešit úlohy víceméně samostatně (ale nápověda typu “tady se hodí použít vyhledávací strom” je na jedničku stále v pořádku).
Okruhy
Pozor, okruhy níže nepředstavují konkrétní příklady na algoritmy či datové struktury. Je zřejmé, že některé okruhy níže jsou širší a některé užší. Pokud ale budete mít přehled o všech tématech níže, nic na zkoušce by vás nemělo zaskočit.
- BFS, DFS a jejich klasifikace hran
- Aplikace DFS: topologické třídění, detekce SSK
- Dijkstrův algoritmus
- Bellman-Fordův algoritmus
- Floyd-Warshallův algoritmus — půltéma
- Jarníkův algoritmus
- Borůvkův algoritmus
- Kruskalův algoritmus + Union-Find pomocí keříků
- BVS obecně
- AVL stromy
- $(a,b)$-stromy
- Červeno-černé stromy
- Hešování s přihrádkami
- Hešování s otevřenou adresací
- Univerzální hešování
- Kuchařková věta, rozbor algoritmu rozděl a panuj pomocí stromu rekurze
- Násobení dlouhých čísel pomocí rozděl a panuj; Strassenův algoritmus (idea)
- LinearSelect
- QuickSort v průměrném případě
- Editační vzdálenost
- Dolní odhady: binární vyhledávání, třídění v srovnávacím modelu