Počkejte prosím...
Data pro 2018/2019

Algoritmy a grafy 1

Kredity 6
Rozsah 2 / 2 / 0
Examinace Z+Zk
Jazyk výuky čeština
Úroveň bakalářský předmět
Garant prof. Ing. Pavel Tvrdík, CSc.

Anotace

Předmět pokrývá to nejzákladnější z efektivních algoritmů, datových struktur a teorie grafů, které by měl znát každý informatik. Spolupracuje se souběžně vyučovaným předmětem BI-ZDM, ve kterém studenti získají znalosti a dovednosti nezbytné pro vyhodnocování operační a paměťové složitosti algoritmů a naučí se prakticky používat asymptotickou matematiku.

Sylabus

Osnovy přednášek:
1. Motivace a úvod do teorie grafů
2. Základní definice a pojmy teorie grafů I 3. Základní definice a pojmy teorie grafů II
4. Řadící algoritmy O(n^2). Binární haldy a HeapSort.
5. Nafukovací pole, amortizovaná složitost, binomiální haldy
6. Vyhledávací stromy a jejich vyvažování
7. Pravděpodobnostní algoritmy a jejich složitost. QuickSort.
8. Rekurzivní algoritmy a metoda Rozděl a panuj. Lineární řazení
9. Rozptylování (hešování) a vyhledávací tabulky
10. Dynamické programování
11. Minimální kostry grafu
12. Nejkratší cesty v grafech
13. Rezerva

Osnovy cvičení:
1. Motivace a úvod do teorie grafů
2. Základní definice a pojmy teorie grafů I 3. Základní definice a pojmy teorie grafů II
4. Řadící algoritmy O(n^2). Binární haldy a HeapSort.
5. Nafukovací pole, amortizovaná složitost, binomiální haldy
6. Vyhledávací stromy a jejich vyvažování
7. Pravděpodobnostní algoritmy a jejich složitost. QuickSort.
8. Rekurzivní algoritmy a metoda Rozděl a panuj. Lineární řazení
9. Rozptylování (hešování) a vyhledávací tabulky
10. Dynamické programování
11. Minimální kostry grafu
12. Nejkratší cesty v grafech
13. Rezerva

Literatura

Z:Cormen, T. H., Leiserson, C. E., Rivest, R. L. Introduction to Algorithms. The MIT Press, 2001. ISBN 0262032937.
Z:Handbook of Graph Theory, 2nd Edition (Discrete Mathematics and Its Applications). Chapman and Hall/CRC, 2013. ISBN 978-1439880180.

VŠCHT Praha
Technická 5
166 28 Praha 6 – Dejvice
IČO: 60461373
DIČ: CZ60461373

Datová schránka: sp4j9ch

Copyright VŠCHT Praha 2014
Za informace odpovídá Oddělení komunikace, technický správce Výpočetní centrum
zobrazit plnou verzi