M8160 Grafové algoritmy

Přírodovědecká fakulta
podzim 2003
Rozsah
2/1/0. 3 kr. (příf plus uk plus > 4). Ukončení: zk.
Vyučující
doc. RNDr. Libor Polák, CSc. (přednášející)
Garance
doc. RNDr. Libor Polák, CSc.
Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Kontaktní osoba: doc. RNDr. Libor Polák, CSc.
Rozvrh seminárních/paralelních skupin
M8160/01: Rozvrh nebyl do ISu vložen. L. Polák
Předpoklady
M5140 Teorie grafů
Základy teorie grafů.
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
  • Matematika (program PřF, M-MA, směr Diskrétní matematika)
  • Matematika (program PřF, N-MA, směr Diskrétní matematika)
Cíle předmětu
Diskutují se základní grafové algoritmy. Vždy se dokazuje jejich korektnost a odhaduje se složitost. Studenti samostatně navrhují další algoritmy.
Osnova
  • Elementární grafové algoritmy (reprezentace grafů, prohledávání do šířky, prohledávání do hloubky, topologické uspořádání, silně souvislé komponenty). Minimální kostry (růst minimální kostry, algoritmy Kruskala a Prima). Nejkratší cesty z jediného vrcholu (nejkratší cesty a relaxace, Dijkstrův algoritmus, Bellman- Fordův algoritmus, nejkratší cesty v orientovaných acyklických grafech). Nejkratší cesty mezi všemi dvojicemi vrcholů (nejkratší cesty a násobení matic, Floyd- Warshallův algoritmus, Johnsonův algoritmus pro řídké grafy). Maximální toky v sítích (sítě, Ford- Fulkersonova metoda, maximální párování v bipartitních grafech). Datové struktury pro grafové algoritmy (binární haldy, prioritní fronty, binomiální haldy, Fibonacciho haldy, datové struktury pro systémy disjunktních
Literatura
  • CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1990, xi, 1028. ISBN 0262031418. info
Metody hodnocení
Standardní přednáška, ve cvičení referují studenti řešení předem zadaných úloh.
Informace učitele
http://www.math.muni.cz/~polak
Další komentáře
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích jaro 2000, jaro 2001, jaro 2002, jaro 2003, podzim 2004.