Předměty

Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (01.02.2018)

Prostředky pro popis složitosti algoritmů a operací nad datovými strukturami:

měření velikosti dat, počet kroků algoritmu jako funkce velikosti dat

asymptotická notace

Stromové datové struktury:

binární vyhledávací stromy

AVL stromy

červeno-černé stromy

volitelně B-stromy

Hašování:

popis jednoduchých strategií řešení kolizí

analýza časové složitosti vyhledávání v průměrném případě

Třídění:

analýza průměrného případu pro Quicksort, randomizovaný Quicksort

dolní odhad složitosti porovnávacích třídících algoritmů (rozhodovací stromy)

třídění v lineárním čase na základě adresování pomocí klíčů (víceprůchodové pro znakové klíče)

Základní grafové algoritmy:

prohledávání do hloubky a do šířky na neorientovaném grafu

detekce souvislých a silně souvislých komponent

prohledávání do hloubky na orientovaném grafu, tranzitivní uzávěr, topologické číslování

Extremální cesty v grafech:

extremální cesty v acyklickém orientovaném grafu, metoda kritické cesty

Dijkstrův algoritmus (zopakování binární haldy, srovnání implementace polem a binární haldou)

Bellman-Fordův algoritmus (hledání záporných cyklů)

volitelně Floyd-Warshallův algoritmus

Minimální kostra grafu:

algoritmus Borůvka-Kruskal

algoritmus Jarník-Prim

volitelně popis pomocí vážených matroidů

Algoritmy rozděl a panuj:

obecné schéma algoritmů typu rozděl a panuj, souvislost jejich složitosti s rekurentními rovnicemi

substituční metoda řešení rekurentních rovnic a "master theorem (kuchařka)"

jednoduché aplikace: binární vyhledávání a mergersort

složitější aplikace: Strassenovo násobení matic, volitelně hledání mediánu v lin. čase v nejhorším případě

Algoritmy lineární algebry:

Euklidův algoritmus

LUP dekompozice matic a její využití

volitelně vlastní čísla a vektory - numerický výpočet, aplikace (Google PageRank, minimální řez grafu)

Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (01.02.2018)

Asymptotic notation.

Tree structures, binary search trees, AVL trees, Red-black trees.

Hashing, solving of collisions, analysis of average case.

Sorting. Analysis of average case for quicksort, randomization. Lower bound for sorting (decision trees), linear-time sorting based on indexing by keys.

Graph algorithms, depth-first search, breadth-first search, strongly connected components, transitive closure, topological sorting.

Extreme paths in graphs. Method of critical path - PERT. Dijkstra alg., Bellman-Ford alg. (searching of negative cycles), Floyd-Warshall alg. for all paths.

Minimal spanning tree. Kruskal alg., Prim-Jarnik alg.

Method Divide and conquer. General schema, solving of recurrent equations. Master theorem. Applications: binary searching, mergesort, Strassen alg.

Eucleid alg., LUP decomposition.