ÚVOD / Studijní obory / Sylaby / Základy návrhu a optimalizace algoritmů

Základy návrhu a optimalizace algoritmů

Cílem předmětu je naučit studenty využívat nejznámější typy algoritmů při řešení implementačních úloh. Při výuce je představena reprezentace čísel a obecný pohled na programování s některými abstrakcemi jako rekurze či dynamické programování. Je proveden úvod do jazyků a gramatik a jsou probírány jednotlivé automaty až po zavedení Turingova stroje. V tomto okamžiku je formálně zavedena výpočetní složitost. Dále jsou představeny základní datové struktury a metody vyhledávání a třídění. Kromě teoretického základu si studenti všechny techniky vyzkouší na modelovém příkladu. Smyslem je, aby studenti pochopili význam a důležitost znalostí týkajících se datových struktur a algoritmů třídění a vyhledávání pro praxi. Důraz je kladen na pochopení základních principů, praktické procvičení a současně také na zvládnutí teoretických (matematických) základů.

Sylabus předmětu

  1. Výpočetní složitost - Časová, prostorová složitost, asymptotická složitost.
  2. Turingův stroj - Zavedení turingova stroje, jeho použití pro výpočetní složitost.
  3. Datové struktury - Práce se seznamy, poli, zásobníky, frontami.
  4. Hashování a asociativní pole - Principy hashování a odpovídající datové struktury.
  5. Třídění I - Základní principy třídění (stabilita, složitost, atd.), jednoduché třídící metody (selection sort, insertion sort, bubble sort, atd.).
  6. Třídění II - Pokročilejší metody třídění (merge sort, quicksort), složitost problému třídění.
  7. Vyhledávání I - Vyhledávací struktura, vyhledávací operace nad seznamem a polem (včetně binárního a interpolačního vyhledávání), binární vyhledávací strom, AVL strom a jeho vlastnosti.
  8. Vyhledávání II - BB(α) strom, B-strom, vyhledávání v textu Boyer-Mooreovým algoritmem.
  9. Reprezentace čísel v počítači - Reprezentace čísel v počítači a jeho problémy a úskalí.
  10. Jazyky a gramatiky - Jazyky a gramatiky a souvislost se složitostí a algoritmizací.
  11. Rekurze a dynamické programování - Rekurze a odpovídající konstrukce algoritmů, dynamické programování a vliv na složitost.

Organizace výuky

Prezenční forma

Výuka probíhá v 6 přednáškách a 12 seminářích po 1,5 hod.

Kombinovaná forma

Výuka probíhá ve 3 tutoriálech po 3 hodinách.

Doporučená literatura

Základní učební texty a pomůcky

  • Učební texty k předmětu Základy návrhu a optimalizace algoritmů (intranetová učební pomůcka), Unicorn College
  • WRÓBLEWSKI, P.: Algoritmy - Datové struktury a programovací techniky, Computer Press, 2004
  • CORMEN, T., LEISERSON, Ch., RIVEST, R., STEIN, C.: Introduction To Algorithms, The MIT Press, 2009

Doplňující a rozšiřující učební texty

  • VIRIUS, M.: Základy algoritmizace, ČVUT, 1997
  • KEOGH, J., DAVIDSON, K.: Datové struktury bez předchozích znalostí, Computer Press, 2006