BI-EFA – Efektivní algoritmy

Cíl předmětu

Studenti získají důkladný přehled efektivních algoritmů pro řešení standardních problémů. Umějí pracovat s asymptotickou notací používanou při vyjadřování složitosti. Rozumějí algoritmům pro řazení o složitosti O(n.log n), pro speciální řazení s lineární složitostí a pro řazení ve vnějších pamětech, algoritmům asociativního a adresního vyhledávání (vyhledávací stromy, rozptýlené tabulky, vícerozměrné vyhledávací stromy). Znají a umějí používat pokročilé datové struktury. Ovládají metody používané pro analýzu paměťové a operační složitosti algoritmů.

Program přednášek

  1. Matematické základy teorie složitosti algoritmů.
  2. Algoritmy řazení se složitostí n.log n, analýza QuickSortu.
  3. Řazení v lineárním čase, řazení v externích pamětech.
  4. Rekurze, analýza složitosti rekurzivních algoritmů, transformace na iterační algoritmy.
  5. Binární haldy, prioritní fronty, binomiální a Fibonnaciho haldy.
  6. Dynamické programování.
  7. Vyhledávací problém, jednorozměrné adresní vyhledávání, mapovací funkce.
  8. Rozptýlené tabulky, otevřené a řetězené adresování, rozptylovací funkce.
  9. Asociativní vyhledávání, vyhledávací a binární vyhledávací stromy, vyhledávání vzoru v textu.
  10. Vícerozměrné vyhledávání, vícerozměrné vyhledávací stromy.
  11. Vyvažování vyhledávacích stromů.

Program cvičení

  1. Procvičování a opakováni diskrétní a asymptotické matematiky.
  2. [2] Implementace, stabilizace, analýza složitosti algoritmů řazení.
  3. Implementace a analýza složitosti algoritmů externího řazení.
  4. Srovnání rekurzivních a iteračních algoritmů, převody.
  5. Použití pokročilých hald.
  6. Použití metod dynamického programování.
  7. Adresní vyhledávání, návrh mapovacích funkcí.
  8. Používání rozptýlených tabulek, otevřené a řetězené adresování.
  9. Vyhledávací a binární vyhledávací stromy, hledání vzoru v textu.
  10. Vyhledávací stromy pro vícerozměrné vyhledávání, vyhledávání nejbližšího souseda.
  11. Vyvažování vyhledávacích stromů.



Poslední změna: 22.4.2009, 21:01