Požadavky ke zkoušce z ADS1
Seznam všech definic, algoritmů, vět a důležitých příkladů z přednášky, které požaduji u zkoušky. K algoritmu vždy patří rozbor korektnosti a časové a prostorové složitosti. K větám patří důkaz.
Definice algoritmu
Výpočetní model RAM
Čas a prostor konkrétního výpočtu
Časová a prostorová složitost
Asymptotická notace: O, Ω, Θ
Základní grafové algoritmy
Prohledávání do šířky (BFS)
Prohledávání do hloubky (DFS)
Klasifikace hran v DFS
Hledání mostů
Algoritmy pro orientované grafy
Detekce cyklů pomocí DFS
Acyklický orientovaný graf (DAG), zdroj, stok
Topologické uspořádání DAGu
Konstrukce topologického uspořádání
Princip indukce podle topologického uspořádání
Počet cest mezi dvěma vrcholy v DAGu
Silná souvislost, její komponenty, graf komponent
Rozklad grafu na komponenty silné souvislosti
Nejkratší cesty
Vzdálenost v grafu
Trojúhelníková nerovnost pro vzdálenost
Dijkstrův algoritmus
Implementace Dijkstrova algoritmu pomocí haldy
Obecný relaxační algoritmus
Bellmanův-Fordův algoritmus
Minimální kostry
Jarníkův algoritmus
Lemma o řezech
Jednoznačnost minimální kostry
Borůvkův algoritmus
Kruskalův algoritmus
Union-Find
Vyhledávací stromy
Rozhraní slovníku, množiny a jejich uspořádaných verzí
Binární vyhledávací strom (BVS)
Operace Find, Insert a Delete v BVS
Dokonale vyvážený strom
Dolní odhad složitosti pro dokonale vyvážené stromy
AVL strom
Odhad hloubky AVL stromu
Operace Insert a Delete v AVL stromech
(a,b)-stromy
Vícecestný vyhledávací strom a (a,b)-strom
Odhad hloubky (a,b)-stromu
Operace Insert a Delete v (a,b)-stromech
Volba parametrů (a,b)-stromu
Červeno-černý strom (LLRB strom)
Isomorfismus LLRB stromů s (2,4)-stromy
Operace Insert v LLRB stromu
Písmenkové stromy (trie)
Definice trie
Operace Find, Insert a Delete v trii
Použití trie k reprezentaci čísel
Hešování
Hešování s řetězci v přihrádkach
Operace Find, Insert a Delete v hešování s řetězci
Dynamické rozšiřování tabulky
c-univerzální systém funkcí
Konstrukce 1-univerzálního systému pomocí skalárního součinu
Průměrná složitost operací při náhodné volbě hešovací funkce z c-univerzálního systému
Hešování s otevřenou adresací
Operace Find, Insert a Delete v hešování s otevřenou adresací
Složitost otevřené adresace pro plně náhodné vyhledávací posloupnosti
Rozděl a panuj
Třídění sléváním (Mergesort)
Násobení n-ciferných čísel v čase O(nlog23)
Kuchařková věta (Master theorem)
Strassenův algoritmus na násobení matic (vzorce nezkouším)
Quickselect – hledání k-tého nejmenšího prvku
Průměrná časová složitost Quickselectu při náhodné volbě pivota
k-tý nejmenší prvek v lineárním čase (algoritmus s pěticemi)
Quicksort
Průměrná časová složitost Quicksortu při náhodné volbě pivota
Lemma o harmonických číslech
Dynamické programování
Nejdelší rostoucí podposloupnost
Editační vzdálenost řetězců
Konstrukce optimálního BVS
Floydův-Warshallův algoritmus na výpočet vzdáleností v grafu
Princip dynamického programování
Grafová interpretace dynamického programování