Detail předmětu

Grafy a algoritmy

FSI-SGA-A Ak. rok: 2020/2021 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 Eulerova cesta, Hamiltonova kružnice, vybarvování uzlů, apod. Pak budou studovány stromy a na nich založené algoritmy. Pozornost bude rovněž věnována problému hledání nejkratší cesty v grafu. Studenti budou také seznámeni s bipartitními grafy a s problémem párování. Nakonec bude pojednáno o orientovaných grafech, zejména pak o sítích a tocích v nich a o algoritmech pro hledání kritické cesty. Výklad bude veden se zřetelem na alplikace teorie grafů, které zasahují do mnoha oblastí života společnosti. Důraz bude přitom kladen na aplikace v informatice, optimalizaci a teorii řízení a v operačním výzkumu.

Jazyk výuky

angličtina

Počet kreditů

4

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

Vyžadovány jsou pouze středoškolské znalosti teorie množin a kombinatoriky.

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 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.

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
jiných oborech.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

Úč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.

Použití předmětu ve studijních plánech

Program M2A-A: Aplikované vědy v inženýrství, magisterský navazující
obor M-MAI: Matematické inženýrství, povinný

Program M2A-P: Aplikované vědy v inženýrství, magisterský navazující
obor M-MAI: Matematické inženýrství, povinný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

Osnova

1. Základní pojmy
2. Cesty a kružnice
3. Vybarvování uzlů
4. Stromy
5. Třídící algoritmy
6. Kostry
7. Problém nejkratší cesty
8. Bipartitní grafy
9.Vybarvování hran
10.Párování
11.Orientované grafy
12.Problém kritické cesty
13.Toky v sítích

Cvičení

13 hod., povinná

Vyučující / Lektor

Osnova

Cvičení budou probíhat v těsné návaznosti na přednášky.