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

AVL strom

Odhad hloubky AVL stromu

Rotace hrany 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

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

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)

Třídění a vyhledávání

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

Dynamické programování

Nejdelší rostoucí podposloupnost

Editační vzdálenost řetězců

Floydův-Warshallův algoritmus na výpočet vzdáleností v grafu

Princip dynamického programování

Grafová interpretace dynamického programování

Stránku spravuje Martin Mareš