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.
• Sbírka příkladů pro cvičení
• Slajdy z přednášek (slajdy využívejte jako podklad k vlastním poznámkám z přednášek, nejsou samostatnou studijní literaturou)

Pro představu také zveřejňujeme vzorová zadání implementační části a znalostní části zkoušky.

Prerekvizity

IB001 Úvod do prog. skrze C || IB111 Úvod do prog. (Python) || IB999 Vstupní test z programování

Předpokládá se, že posluchači mají znalosti v rozsahu předmětů IB001 Úvod do programování skrze C anebo IB111 Úvod do programování skrze Python a v rozsahu předmětu IB000 Matematické základy informatiky. Studenti by měli být schopni používat základní programátorské konstrukce (např. podmínky, cykly, funkce, základní datové typy) a znát několik základních algoritmů. Kromě toho se předpokládá znalost základních matematických konstruktů v rozsahu IB000. Součástí hodnocení předmětu je závěrečný praktický test realizovaný v jazyce Python.