PB165 Grafy a sítě

Fakulta informatiky
podzim 2007
Rozsah
2/0. 2 kr. (plus ukončení). Ukončení: zk.
Vyučující
prof. RNDr. Luděk Matyska, CSc. (přednášející)
doc. RNDr. Eva Hladká, Ph.D. (přednášející)
doc. Mgr. Hana Rudová, Ph.D. (přednášející)
RNDr. David Antoš, Ph.D. (pomocník)
RNDr. Igor Peterlík, Ph.D. (pomocník)
Garance
prof. RNDr. Václav Matyáš, M.Sc., Ph.D.
Katedra počítačových systémů a komunikací – Fakulta informatiky
Rozvrh
Po 14:00–15:50 A107
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
Cíle předmětu
Předmět zpřístupní základní informace o grafech a grafových algoritmech, používaných v prostředí počítačových sítí (směrování, přepínání). Speciální důraz je věnován plánování a rozvrhování, které jsou prezentovány jako specifické grafové problémy, obdobně jako problém rozložení zátěže v distribuovaných systémech.
Osnova
  • Pojem grafu, orientovaný a neorientovaný graf, hranově a vrcholově ohodnocené grafy. Vzdálenost v grafu.
  • Podgrafy, isomorfismus.
  • Stromy, kostra grafu. Toky v sítích.
  • Prohledávání v grafu. Hledání nejkratší cesty (Dijkstrův algoritmus). Algoritmy nalezení kostry grafu. Nalezení maximálního toku.
  • Plánování, reprezentace projektu, metoda kritické cesty.
  • Multi-operační rozvrhování, disjunktivní grafová reprezentace, posun kritického místa.
  • Problém barvení grafu a rozvrhování, heuristiky barvení grafu.
  • Rozložení zátěže, grafová reprezentace, heuristiky mapování.
  • Algoritmy směrování a přepínání, planování GSM sítí, peer to peer sítě.
Literatura
  • Kocay, William. Graphs, algorithms, and optimization. Chapman \& Hall/CRC Press, 2005.
  • GIBBONS, Alan. Algorithmic graph theory. Cambridge: Cambridge University Press, 1994, ix, 259. ISBN 0521288819. info
  • PLESNÍK, Ján. Grafové algoritmy. 1. vyd. Bratislava: Veda, 1983, 343 s. info
  • PINEDO, Michael. Planning and Scheduling in Manufacturing and Services. Springer, 2005. Springer Series in Operations Research. info
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019.