PB165 Grafy a sítě

Fakulta informatiky
podzim 2023

Předmět se v období podzim 2023 nevypisuje.

Rozsah
2/0/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í)
Mgr. Stanislav Murín (pomocník)
RNDr. Lukáš Ručka (pomocník)
Garance
doc. RNDr. Eva Hladká, Ph.D.
Katedra počítačových systémů a komunikací – Fakulta informatiky
Dodavatelské pracoviště: Katedra počítačových systémů a komunikací – Fakulta informatiky
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.
Výstupy z učení
Absolvent bude schopen vysvětlit řadu grafových algoritmů a jejich použití v počítačových systémech a sítích.
Absolvent bude rovněž schopen analyzovat konkrétní problém a převést jej do grafové reprezentace.
Absolvent bude dále schopen analyzovat a vyřešit jednoduché problémy z oblasti plánování.
Absolvent bude schopen vyřešit jednodušší grafové problémy.
Absolvent bude schopen interpretovat chování počítačové sítě v pojmech teorie grafů.
Osnova
  • Pojem grafu a počítačové sítě, stromy, kořenové a binární stromy.
  • Prohledávání v grafu. Algoritmy nalezení kostry grafu. Hledání nejkratších cest.
  • Problém plánování a jeho grafové reprezentace.
  • Plánování projektu a metoda kritické cesty.
  • Barvení grafu.
  • Plánování datových přenosů.
  • Plánování seznamem, heuristiky mapování, shlukovací heuristiky.
  • Rozložení zátěže.
  • Algoritmy směrování a přepínání, planování GSM sítí, peer to peer sítě.
  • P2P sítě a algoritmy pro přidávání, ubírání uzlů a směrování.
  • Grafy pro modelování a simulace sítí typu Internet
  • Síťové kódování.
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
Výukové metody
Standardní přednáška, bez cvičení a domácích úkolů. Přednášky zahrnují příklady na procvičení.
Metody hodnocení
V polovině semestru je písemná zkouška z probraného učiva, jejíž výsledek se započítává 20% do výsledné známky.
Závěrečná písemná zkouška se započítává 70% procenty do výsledné známky, tato písemná zkouška se skládá z 9 otázek, je možné za ni získat 100 bodů.
Během semestru je možné získat bonusové body za aktivní účast (cca 12 bodů dle počtu přednášek), které se započítávají 10% do výsledné známky. Každý student může získat 1 bonusový bod za aktivitu na jedné přednášce (např. reakce na více jednoduchých dotazů nebo dotazy studentky/a na vyjasnění látky, reakce na jeden složitější dotaz).
Hodnocení předmětu je následující A 100%-80%, B 79%-70%, C 69%-60%, D 59%-50%, E 49%-45%.
Další komentáře
Předmět je vyučován každoročně.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019.