M8160 Grafové algoritmy

Přírodovědecká fakulta
podzim 2004
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
Út 15:00–16:50 A107
  • Rozvrh seminárních/paralelních skupin:
M8160/01: Út 17:00–17:50 A107, 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
  • 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 E. 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 2003.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/sci/podzim2004/M8160