Polynomiální algoritmy pro standardní grafové úlohy. Kombinatorické a číselně-teoretické algoritmy, izomorfizmus, prvočísla. Vyhledávací stromy a jejich využití. Vyhledávání v textu založené na konečných automatech.

Notace asymptotické složitosti algoritmů. Základní notace grafových problémů - stupeň, cesta, cyklus. Reprezentace grafů pomocí matic sousednosti, vzdálenosti, Laplaceovy matice a matice incidence. Reprezentace seznamem sousednosti.
Algoritmy pro minimální kostru grafu (Prim-Jarník, Kruskal, Borůvka), silně souvislé komponenty (Kosaraju-Sharir, Tarjan), Eulerovská stopa. Problém Union-find. Izomorfismus grafů, izomorfismus stromů.
Generování a enumerace kombinatorických objektů – podmnožiny, k-prvkové podmnožiny, permutace. Grayovy kódy. Prvočísla, Eratosthenovo síto. Vlastnosti pseudonáhodných čísel. Lineární kongruenční generátor.
Vyhledávací stromy – datové struktury, operace a jejich složitosti. Binární strom, AVL strom, red-black strom (RB-strom), B-strom a B+ strom, splay strom, k-d strom. Hledání nejbližšího souseda v k-d stromech. Skip list.
Konečné automaty, regulární výrazy, operace nad regulárními jazyky. Bitová reprezentace nedeterministických konečných automatů. Algoritmy pro vyhledávání v textu - přesné vyhledávání vzorů, přibližné vyhledávání vzorů (Hammingova a Levenshteinova vzdálenost), slovníkové automaty.

Trace: • a4m33pal