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, 3. patro). Do subjektu emailů pište "ADS2019".

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). Floyd-Washallův algoritmus. Algoritmy pro hledání minimálních koster: Jarník-Prim a Kruskalův.

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

Odkazy