Přístupnostní navigace
E-přihláška
Vyhledávání Vyhledat Zavřít
Detail předmětu
FSI-SGA-AAk. rok: 2024/2025
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. Dále budou studenti seznámeni s bipartitními grafy, s problémy 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, které teorie grafů nachází především v technických vědách. Důraz bude kladen na aplikace v informatice, optimalizaci, teorii řízení a operačním výzkumu.
Jazyk výuky
Počet kreditů
Garant předmětu
Zajišťuje ústav
Vstupní znalosti
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 pak 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ýmialgoritmy, 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ů.
Studijní opory
Studenti mají k dispozici studijní opory předmětu, které jsou umístěny na webových stránkách Ústavu matematiky jako soubory ke stažení poskytnuté garantem předmětu.
Základní literatura
Doporučení literatura
Zařazení předmětu ve studijních plánech
specializace CZS , 1 ročník, zimní semestr, volitelný
Přednáška
Vyučující / Lektor
Osnova
Cvičení