čeština

Studenti získají základní znalosti z teorie grafů a grafových algoritmů. Budou tak schopni modelovat pomocí grafů různé problémy z praxe a ty pak řešit pomocí osvojených algoritmů.

Ke studiu teorie grafů postačují základní znalosti z teorie množin, kombinatoriky a operačního výzkumu.

Metody vyučování závisejí na způsobu výuky a jsou popsány článkem 7 Studijního a zkušebního řádu VUT.

Podmínkou pro zápočet je implementace netriviálního grafového algoritmu na počítači
v prostředí Delphi, C++ nebo jiném programu.
Zkouška má písemnou formu. Studenti v ní prokazují znalosti pojmů a základních algoritmů.

Cílem předmětu je seznámit studenty s teorií grafů a jejími algoritmy, které rozšiřují znalosti získané v předmětech se zaměřením na umělou inteligenci, operační výzkum, projektové řízení a počítačové sítě, a mají aplikace v technických i jiných oblastech.

Protože cvičení jsou povinná, bude na nich vyučující pravidelně kontrolovat účast. V případě omluvené nepřítomnosti student obdrží příklady k samostatnému vypracování tak, aby mohl zameškanou látku zvládnout.

Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C.: Introduction to Algorithms. MIT Press, 2001.
Gross, J.L. and Yellen, J.: Graph Theory and Its Applications. CRC Press, Boca Raton, 1998.
Gross, J.L. and Yellen, J.: Handbook of Graph Theory. CRC Press, Boca Raton, 2004.
Hochbaum, D.: Graph Algorithms and Network Flows. Lecture Notes, University of California at Berkeley, 1997, 84 pp.
Chartrand, G. and Oellermann, O.R. : Applied Algorithmic Graph Theory. McGraw Hill, New York, 1993.
Michaels, J.G. and Rosen, K.H.: Applications of Discrete Mathematics. McGraw Hill, New York, 1991.
Sedgewick, R.: Algorithms in Java, Part 5: Graph Algorithms. Addison Wesley, New York, 2002.

Demel, J.: Grafy a jejich aplikace. ACADEMIA, Praha, 2002.
Kolář, J.: Theoretical Computer Science. ČVUT FEL, Praha, 1998.