Co nás zajímá na algoritmech.

Téma 1 -- řadící algoritmy
Co potřebujete vědět o logaritmech.
Notace velké O, v průvodci je na str. 47 tabulka 2.2 pro vybrané velikosti vstupu a vybrané časové složitosti, na str. 48 pak tabulka 2.3 doby běhu takových algoritmů na současném hardwaru.
Časovou složitost binárního vyhledávání najdete v řešení úlohy 29-Z1-6 z KSP.
repl na řadící algoritmy,
repl na algoritmy na vyhledávání prvku.

Animace řadících algoritmů (dle výkladu studenta Ondřeje Svárovského při zkoušení): Merge sort, Quick sort.

Prezentace k témetům 1 i 2 (Merge sort, DFS, LIFO)

Téma 2 -- prohledávání grafu do šířky (BFS) a do hloubky (DFS)
Základní pojmy teorie grafů.
Typická úloha na použití BFS je hledání nejkratší cesty v grafu s neohodnocenými hranami (tedy hrany mají stejnou délku). Úlohu ilustrujeme na šachovnici -- hledáme nejkratší cestu koněm mezi dvěma poli: repl.
Videa na DFS: část 1 (začátek), část 2 (závěr). Ve videích není zmínka o zásobníku: do zásobníku vkládáme objevené hrany (ve videu nazývané discovered) a ze zásobníku odebíráme tyto hrany při backtrackingu (termín používaný i v češtině).
pseudokód DFS, BFS
Videa od vašeho spolužáka: DFS, BFS.

Téma 3 -- algoritmy na nejkratší cestu v grafu
Popis problému, pseudokód.
Pseudokód v průvodci, kapitola o nejkratších cestách, strany 147, 150.
Dijkstrův algoritmus repl.
prezentace na Dijkstrův algoritmus
prezentace na Bellman-Fordův algoritmus (použití BFS) OPRAVENÁ BARVA JEDNÉ Z HRAN
prezentace k pojmům, otevřený, uzavřený vrchol, relaxace vrcholu, BELLMAN-FORDŮV ALGORITMUS JE V PREZENTACI VYLOŽEN CELÝ

Téma 4 -- algoritmy na minimální kostru grafu
Jarníkův algoritmus: pseudokód Jarníkova algoritmu, důkaz správnosti včetně řezového lemmatu najdete na stranách 167 až 170 v průvodci. Na stranách 171, 172 implementaci Jarníkova algoritmu pomocí haldy.
Ilustrace elementárního řezu a řezového lemmatu,
ilustrace k důkazu řezového lemmatu.
pseudokód Jarníkova algoritmu s haldou/listem, časová složitost (PŘIDALA JSEM VYSVĚTLENÍ TABULKY S ČASOVOU SLOŽITOSTÍ)

K tématům 3, 4
Datová struktura halda (binární): halda před videem, video o haldě, halda po videu.