Algoritmy a datové strukury I (NTIN060)
Konzultace po dohodě emailem (nejlépe ve středu nebo pátek na MS, 3. patro). Do subjektu emailů pište "ADS2019".
- Přednáška: St 12:20, S3
- Cvičení:
Odpřednesená látka
- 20. února
- Co to je algoritmus. Definice výpočetního modelu RAM. Časová a prostorová složitost. O notace.
- 28. února
- Prohledávání do šířky: algoritmus, korektnost, rozdělení grafu do vrstev a časová šložitost. Reprezentace grafu v paměti. Algoritmus prohledávání do hloubky.
- 6. března
- Klasifikace DFS hran, hledání mostů v neorientovaném grafu, cykly v orientovaných grafech a acyklické grafy (DAGy). Rozpoznávání DAGu pomocí DFS a toplogické třídění.
- 13. března
- Hledání nejkratších a nejdelších cest v acyklickém grafu. Rozpoznávání komponent silné souvislosti. Úvod do hledání nejkratších cest v ohodnoceném grafu.
- 20. března
- Dijkstrův a Belmanův-Fordův algoritmus. (Suploval Matěj Konečný)
- 28. března
- Floyd-Washallův algoritmus. Algoritmy pro hledání minimálních koster: Jarník-Prim a Kruskalův.
- 3. dubna
- Datové struktury: množiny, uspořádané množiny. Binární vyhledávací stromy. AVL stromy s operací insert.
- 10. dubna
- Delete v AVL stromu. (a,b)-stromy s insertem a náznakem delete. LLRB stromy s operací insert. Úvod do rozděl a panuj.
- 17. dubna
- Rozděl a panuj: merge sort, Karacubův algoritmus na násobení čisel, kuchařková věta (master theorem), Strassenův algoritmus (pozor, na konci hodiny jsem chybně napsal, že pro dosazení do master theoremu je b=4. Má být b=2).
- 24. dubna
- Quicksort: analýza průměrného příkladu. Dolní odhad složitosti porovnávacích třídicích algoritmů.
- 15. května
- Přihrádkové třídění. Radix sort. Písmenkový strom.
Hašování se spojovým seznamem na řešení kolizí: očekávaný čas operací find, insert a delete s náhodnou hešovací funkcí. Univerzální hešování.
- 22. května
- Hašování s otevřenou adresací: očekáváný čas neúspěšného hledání. Euklidův algoritmus. LUP dekompozice (nebude u zkoušky)
Cvičení
- 22. února
- Programujeme RAM: hledání prvočísel jednoduše i pomocí Erastetonova síta. Časová složitost O(n log log n).
příklady
- 1. března
- Prohledávání do hloubky a šířky.
příklady a domácí úkol
- 8. března
- Aplikace prohledávání do hloubky a šířky.
příklady a domácí úkol
- 15. března
- Dijsktrův algoritmus.
příklady a domácí úkol
- 22. března
- Nejkratší cesty v ohodnocených grafech podruhé.
příklady
- 30. března
- Kostry grafu.
příklady a domácí úkol
- 5. dubna
- AVL stromy.
příklady a domácí úkol
- 12. dubna
- LLRB stromy.
příklady
- 26. dubna
- Rozděl a panuj.
příklady a domácí úkol
- 17. května
- Hešování a třídění v lineárním čase.
příklady a domácí úkol
- 24. května
- Zkouškové příklady.
příklady
Odkazy