Algoritmy a datové struktury 1

Přednáška z Algoritmů a datových struktur 1 [NTIN060] se koná v LS 2024/2025 ve čtvrtky od 12:20 v N1.

Kdybyste čemukoliv nerozuměli, rád si s vámi domluvím konzultaci. Ozvěte se mi prosím na adresu mares+ads@kam.mff.cuni.cz.

Přednášky 20.3., 27.3., 1.5., 8.5. odpadají. Místo toho se bude konat 17.3. a 18.4. náhradní přednáška od 17:20 v N1. Náhradní přednášky budu nahrávat.

Co se přednášelo

datum téma video
20. 2. Pokus o definici algoritmu. Výpočetní model RAM: paměť, aritmetické a řídicí instrukce. Čas a prostor konkrétního výpočtu (různé varianty: jednotková cena, logaritmická cena, omezený rozsah čísel), časová a prostorová složitost algoritmu. Programování na RAMu a počítání složitosti: příklad s bublinkovým tříděním. Připomenutí asymptotické notace (O, Ω, Θ). Pokud vám nefungují videa, vypněte si AdBlock. Jedno z jeho pravidel zakazuje všechna URL s podřetězcem /ads1/ :D video
27. 2. Prohledávání grafu do hloubky (DFS). Klasifikace hran v DFS (stromové, zpětné, dopředné, příčné). Hledání mostů. video
6. 3. Aplikace DFS: Detekce cyklů a topologické uspořádání. Algoritmy pro acyklické grafy (počet cest). Komponenty silné souvislosti. video
13. 3. Nejkratší cesty v ohodnocených grafech: trojúhelníková nerovnost pro vzdálenosti, nejkratší cesta versus nejkratší sled, problémy se zápornými cykly. Odvození Dijkstrova algoritmu z BFS pomocí podrozdělování hran a „budíků“. Dijkstrův algoritmus, implementace pomocí haldy (binární a zmínka o ostatních). video
17. 3.
17:20		 Plán: Nejkratší cesty: Obecný relaxační algoritmus, důkaz korektnosti Dijkstrova algoritmu pro obecné délky hran, Bellmanův-Fordův algoritmus.
20. 3. Přednáška odpadá.
27. 3. Přednáška odpadá.

Cvičení

Existuje dvě české paralelky přednášky, ale budeme je udržovat synchronní. Můžete si tedy vybrat libovolné cvičení.

Literatura

Ostatní zajímavé knihy:

Sbírky příkladů:

Různé:

Stránku spravuje Martin Mareš