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).
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