Sylabus přednášky

• Základy analýzy algoritmů 
  • Korektnost algoritmu, vstupní a výstupní podmínky, parciální korektnost, konvergence, verifikace
  • Délka výpočtu, složitost algoritmu, složitost problému. Asymptotická analýza časové a prostorové složitosti, růst funkcí
• Techniky návrhů algoritmů
  • Iterativní algoritmy
  • Rekurzivní algoritmy (rozděl a panuj)
• Řadící algoritmy
  • Řazení rozdělováním
  • Řazení slučováním
  • Řazení haldou
  • Dolní odhad složitosti
• Fundamentální datové struktury
  • Seznamy, fronty
  • Binární halda
  • Binární vyhledávací stromy, vyvážené stromy
  • Červeno-černé stromy
  • B-stromy
  • Modifikace datových struktur
  • Hašování
• Základní grafové algoritmy
  • Reprezentace grafů
  • Procházení grafu do hloubky, zúplnění uspořádání, silně souvislé komponenty
  • Procházení grafu do šířky
  • Nejkratší cesty v grafu, Dijkstrův algoritmus, Bellmanův - Fordův algoritmus

Literatura

• Povinná
  • T. H. Cormen, C. E. Leiserson,  R. L. Rivest, and C. Stein. Introduction to Algorithms (Third Edition). The MIT Press, 2009.
• Doporučená
  • J. Bentley. Programming Pearls (Second Edition). ACM Press 2000.
  • G. Brassard, and P. Bratley. Fundamentals of Algorithmics. Prentice Hall, 1996.
  • T.H. Cormen. Algorithms Unlocked. The MIT Press, 2013.
  • A. Levitin, Introduction to the Design and Analysis of Algorithms. Addison-Wesley, 2003.
  • S. Dasgupta, Ch. Papadimitriou, U. Vazirani: Algorithms. McGraw Hill, 2007.
• Doplňková
• J. Kleinberg, and E. Tardos: Algorithm Design. Addison-Wesley, 2006.

Studijní materiály

• Slajdy z přednášky
• Sbírka příkladů pro cvičení
• Užitečné rady k programovacím úkolům

Prerekvizity

IB111 Základy programování a IB000 Matematické základy informatiky
Kromě nutnosti absolvování předmětu IB111 se předpokládá, že posluchači mají znalosti v rozsahu  předmětu IB000 Matematické základy informatiky, speciálně důkazové postupy pro algoritmy, rekurze a strukturální indukce, pojem grafu.