Předmět Grafové algoritmy (FSI-9GRA)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu FSI-9GRA - Grafové algoritmy, Fakulta strojního inženýrství, Vysoké učení technické v Brně (VUT).

Materiál	Typ	Datum	Počet stažení

Cíl

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.

Osnova

1. Definice grafu a základní pojmy. 2. Reprezentace grafu v počítači. 3. Časová a paměťová složitost algoritmů. 4. Prohledávání grafů, backtracking, metoda větví a mezí. 5. Aplikace úloh o cestách, nejkratší cesty, síťové grafy. 6. Eulerovské tahy, hamiltonovské cesty a kružnice. 7. Komponenty souvislosti, stromy a kostry. 8. Steinerovy stromy. 9. Voronoiovy diagramy, Delaunayho triangulace.10. Barvení grafů, kliky.11.-12. Toky v sítích.13. Párování grafech.

Literatura

Chartrand, G. and Oellermann, O.R.: Applied Algorithmic Graph Theory. McGraw Hill, New York, 1993.Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C.: Introduction to Algorithms. MIT Press, 2001.Gross, J.L. and Yellen, J.: Handbook of Graph Theory. CRC Press, Boca Raton, 2004.Gross, J.L. and Yellen, J.: Graph Theory and Its Applications. CRC Press, Boca Raton, 1998.Hochbaum, D.: Graph Algorithms and Network Flows. Lecture Notes, University of California at Berkeley, 1997, 84 pp.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.

Požadavky

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

Garant

prof. RNDr. Ing. Miloš Šeda, Ph.D.

Vyučující

prof. RNDr. Ing. Miloš Šeda, Ph.D.