FI:PB165 Grafy a sítě - Informace o předmětu
PB165 Grafy a sítě
Fakulta informatikypodzim 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
- předmět má 56 mateřských oborů, zobrazit
- 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.
- Statistika zápisu (podzim 2023, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/podzim2023/PB165