Detail předmětu
Grafy a algoritmy
FSI-SGA-A Ak. rok: 2023/2024 Zimní semestr
V kurzu budou studenti seznámeni se základy teorie grafů a s některými algoritmy, které jsou na této teorii založeny. Po zavedení základních pojmů budou diskutovány klasické problémy jako Eulerův tah, Hamiltonova kružnice, vybarvování uzlů, planarita apod. Budou také studovány stromy a algoritmy pro hledání minimální kostry. Studenti budou seznámeni s bipartitními grafy, s problémem párování a hledání nejkratší cesty. Pozornost bude věnována rovněž orientovaným grafům včetně algoritmů pro hledání kritické cesty. Nakonec bude pojednáno o sítích a tocích v nich. Výklad bude veden se zřetelem na aplikace teorie grafů, které zasahují do mnoha oblastí života společnosti. Důraz bude přitom kladen na aplikace v informatice, optimalizaci, teorii řízení a operačním výzkumu.
Jazyk výuky
angličtina
Počet kreditů
5
Garant předmětu
Zajišťuje ústav
Vstupní znalosti
Vyžadovány jsou pouze středoškolské znalosti teorie množin a kombinatoriky.
Pravidla hodnocení a ukončení předmětu
Podmínkou pro zápočet je aktivní účast ve cvičeních a prokázání znalostí při písemných testech, které budou průběžně konány. V písemné části zkoušky je třeba prokázat schopnost řešit zadaný problém na základě získaných vědomostí, v její ústní části pan zvládnutí probrané teorie.
Účast na cvičeních je povinná a vyučující ji bude pravidelně kontrolovat. V případě omluvené nepřítomnosti student obdrží příklady k samostatnému vypracování tak, aby mohl zameškanou látku zvládnout.
Učební cíle
Cílem kurzu je seznámit studenty s teorií grafů a na ní založenými
algoritmy, které jsou často používány k řešení problémů v technických i mnoha jiných oborech.
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ů.
Použití předmětu ve studijních plánech
Program N-MAI-A: Mathematical Engineering, magisterský navazující, povinný
Program N-AIM-A: Applied and Interdisciplinary Mathematics, magisterský navazující, povinný
Program N-MAI-P: Matematické inženýrství, magisterský navazující, povinný
Typ (způsob) výuky
Přednáška
26 hod., nepovinná
Vyučující / Lektor
Osnova
- Základní pojmy
- Tahy, cesty a kružnice
- Stromy a kostry
- Vybarvování uzlů
- Planarita
- Třídicí algoritmy
- Hledání nejkratší cesty
- Vybarvování hran
- Bipartitní grafy
- Párování
- Orientované grafy
- Problém kritické cesty
- Toky a sítě
Cvičení
13 hod., povinná
Vyučující / Lektor
Osnova
Cvičení budou probíhat v těsné návaznosti na přednášky.