Detail předmětu
Teorie grafů a grafové algoritmy
FSI-VTG-K Ak. rok: 2019/2020 Zimní semestr
Předmět je úvodem do teorie grafů a seznamuje studenty s jeho základními pojmy. Zabývá se následujícími tématy: Reprezentace grafu v počítači. Časová složitost algoritmů.
Datové struktury pro grafové algoritmy binární halda, disjunktní množiny, ...).
Eulerovské tahy, hamiltonovské cesty. Prohledávání grafů (do šířky, do hloubky), backtracking, metoda větví a mezí. Souvislost a dosažitelnost. Nejkratší cesty.
Síťové grafy. Stromy a kostry. Steinerovy stromy. Základy počítačové geometrie, Voronoiovy diagramy a Delaunayho triangulace. Toky v sítích. Barvení grafů. Párování v grafech.
Jazyk výuky
čeština
Počet kreditů
5
Garant předmětu
Zajišťuje ústav
Výsledky učení předmětu
Studenti získají základní znalosti z teorie grafů a grafových algoritmů. Budou tak schopni modelovat pomocí grafů různé problémy z praxe a ty pak řešit pomocí osvojených algoritmů.
Prerekvizity
Ke studiu teorie grafů postačují základní znalosti z teorie množin, kombinatoriky a operačního výzkumu.
Plánované vzdělávací činnosti a výukové metody
Předmět je vyučován formou přednášek, které mají charakter výkladu základních principů a teorie dané disciplíny. Cvičení je zaměřeno na praktické zvládnutí látky probrané na přednáškách.
Způsob a kritéria hodnocení
Podmínkou pro zápočet je implementace netriviálního grafového algoritmu na počítači ve vyšším programovacím jazyku (např. C++, Java, Python, ...)
Zkouška má písemnou formu. Studenti v ní prokazují znalosti pojmů a základních algoritmů.
Učební cíle
Cílem předmětu je seznámit studenty s teorií grafů a jejími algoritmy, které rozšiřují znalosti získané v předmětech se zaměřením na umělou inteligenci, operační výzkum, projektové řízení a počítačové sítě, a mají aplikace v technických i jiných oblastech.
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky
Protože cvičení jsou povinná, bude na nich vyučující pravidelně kontrolovat účast. V případě omluvené nepřítomnosti student obdrží příklady k samostatnému vypracování tak, aby mohl zameškanou látku zvládnout.
Použití předmětu ve studijních plánech
Program M2I-K: Strojní inženýrství, magisterský navazující
obor M-AIŘ: Aplikovaná informatika a řízení, povinný
Typ (způsob) výuky
Konzultace v kombinovaném studiu
17 hod., nepovinná
Vyučující / Lektor
Osnova
1. Definice grafu a základní pojmy.
2. Reprezentace grafu v počítači.
3. Časová a paměťová složitost algoritmů.
4. Prohledávání grafů, backtracking, metoda větví a mezí.
5. Aplikace úloh o cestách, nejkratší cesty, síťové grafy.
6. Eulerovské tahy, hamiltonovské cesty a kružnice.
7. Komponenty souvislosti, stromy a kostry.
8. Steinerovy stromy.
9. Voronoiovy diagramy, Delaunayho triangulace.
10. Barvení grafů, kliky.
11.-12. Toky v sítích.
13. Párování grafech.