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.

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

Odkazy