Detail předmětu

Grafy a algoritmy

FSI-SGA-A Ak. rok: 2024/2025 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. 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.

Garant předmětu

prof. RNDr. Josef Šlapal, CSc.

Zajišťuje ústav

Ústav matematiky

Výsledky učení předmětu

Prerekvizity

Plánované vzdělávací činnosti a výukové metody

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

Jazyk výuky

angličtina

Cíl

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

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

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

Program N-LAN-A: Logistics Analytics, magisterský navazující
obor ---: bez specializace, 4 kredity, povinný

Program N-MAI-A: Mathematical Engineering, magisterský navazující
obor ---: bez specializace, 4 kredity, povinný

Program N-MAI-P: Matematické inženýrství, magisterský navazující
obor ---: bez specializace, 4 kredity, povinný

Program N-AIM-A: Applied and Interdisciplinary Mathematics, magisterský navazující
obor ---: bez specializace, 4 kredity, povinný

Program C-AKR-P: Akreditované předměty v CŽV, celoživotní vzdělávání v akr. stud. programu
obor CZS: Předměty zimního semestru, 4 kredity, volitelný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

Michael Joseph Lieberman, Ph.D.

Osnova


  1. Základní pojmy

  2. Tahy, cesty a kružnice

  3. Stromy a kostry

  4. Vybarvování uzlů

  5. Planarita

  6. Třídicí algoritmy

  7. Hledání nejkratší cesty

  8. Vybarvování hran

  9. Bipartitní grafy

  10. Párování

  11. Orientované grafy

  12. Problém kritické cesty

  13. Toky a sítě

Cvičení

13 hod., povinná

Vyučující / Lektor

Michael Joseph Lieberman, Ph.D.

Osnova

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