M015 Grafové algoritmy

Fakulta informatiky
jaro 2002
Rozsah
2/1. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.
Vyučující
doc. RNDr. Libor Polák, CSc. (přednášející)
Mgr. Michal Marciniszyn (cvičící)
Garance
doc. RNDr. Jiří Kaďourek, CSc.
Ústavy – Přírodovědecká fakulta
Kontaktní osoba: doc. RNDr. Libor Polák, CSc.
Rozvrh
St 12:00–12:50 B007, St 13:00–13:50 B007
  • Rozvrh seminárních/paralelních skupin:
M015/01: Rozvrh nebyl do ISu vložen. L. Polák
M015/02: Rozvrh nebyl do ISu vložen. M. Marciniszyn
M015/03: Rozvrh nebyl do ISu vložen. M. Marciniszyn
Předpoklady
Doporučeno je absolvovat M010 Kombinatorika a 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
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, datové struktury pro systémy disjunktních množin).
Literatura
  • CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1990, xi, 1028. ISBN 0262031418. info
Další komentáře
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích léto 1996, léto 1997, léto 1998, jaro 1999, jaro 2000, jaro 2001.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/fi/jaro2002/M015