====== 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. ======

[[https://fel.cvut.cz/cz/education/bk/predmety/46/85/p4685106.html|BE4M33PAL]] [[https://cw.fel.cvut.cz/b201/courses/be4m33pal/start|Webové stránky předmětu]]

  * **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.