Grafy a algoritmy (FSI-SGA-A)

Akademický rok 2012/2013
Garant: prof. RNDr. Josef Šlapal, CSc.  
Garantující pracoviště: ÚM všechny předměty garantované tímto pracovištěm
Jazyk výuky: angličtina
Cíle předmětu:
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.
Výstupy studia a kompetence:
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.
Obsah předmětu (anotace):
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.
Metody vyučování:
Metody vyučování závisejí na způsobu výuky a jsou popsány článkem 7 Studijního a zkušebního řádu VUT.
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.
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.
Typ (způsob) výuky:
    Přednáška  13 × 2 hod.
    Cvičení  13 × 1 hod.
Osnova:
    Přednáška 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í Cvičení budou probíhat v těsné návaznosti na přednášky.
Literatura - základní:
1. Biggs, N.L.: Discrete Mathematics, Oxford Science Publications 1999
2. Wallis, W.D.: A Beginner's Guide to Graph Theory, Birkhäuser Boston 2000
3. Balakrishnan, V.K.: Introductory Discrete Mathematics, Dover Publications, Inc., New York 1996
4. Piff, M.: Discrete Mathematics, An Introduction for Software Engineers, Cambridge University Press 1991
5. Plesník, J.: Grafové algoritmy, Veda, Bratislava 1983
6. Willson, J.R., Watkins, J.J.: Graphs: An Introductory Approach, Wiley 1990
Literatura - doporučená:
1. Plesník, J.: Grafové algoritmy, Veda, Bratislava 1983
2. Willson, J.R., Watkins, J.J.: Graphs: An Introductory Approach, Wiley 1990
Zařazení předmětu ve studijních programech:
Program Forma Obor Spec. Typ ukončení   Kredity     Povinnost     St.     Roč.     Semestr  
M2A-P prezenční studium M-MAI Matematické inženýrství -- zá,zk 4 Povinný 2 1 Z