Teorie grafů (FSI-VTG)

Akademický rok 1999/2000
Garant: prof. RNDr. Ing. Miloš Šeda, Ph.D.  
Garantující pracoviště: ÚAI všechny předměty garantované tímto pracovištěm
Jazyk výuky: čeština
Cíle předmětu:
Seznámení s algoritmy, které rozšířují znalosti získané v předmětech
se zaměřením na umělou inteligenci, operační výzkum, projektové řízení
a počítačové sítě.
Osvojení specifických oblastí teorie grafů s důrazem na praktické
aplikace.
Výstupy studia a kompetence:
Viz cíle a úkoly kursu
Prerekvizity:
 
Obsah předmětu (anotace):
Základní pojmy teorie grafů. Aplikace úloh o cestách. Síťové grafy. Prohledávání grafů, backtracking., metoda větví a mezí. Souvislost a dosažitelnost. Nejkratší cesty. Stromy a kostry. Toky v sítích. Párování. Barevnost grafů. Fuzzy grafy.
Metody vyučování:
 
Způsob a kritéria hodnocení:
Implementace netriviálního grafového algoritmu na počítači
s odpovídající úrovní prezentace (např. Borland Delphi, C++).
Studium zahraniční literatury z teorie grafů (Internet, knihy,
časopisy).
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky:
 
Typ (způsob) výuky:
    Přednáška  11 × 2 hod. nepovinná                  
    Cvičení na počítači  11 × 2 hod. povinná                  
Osnova:
    Přednáška 1. Definice grafu a základní pojmy.
2. Prohledávání grafů
3. Backtracking, metoda větví a mezí
4. Aplikace úloh o cestách, nejkratší cesty
5. Síťové grafy
6. Eulerovské tahy.
7. Hamiltonovské cesty a kružnice.
8. Komponenty souvislosti, stromy a kostry.
9. Steinerovy stromy.
10. Reprezentace grafu v počítači.
11. Barvení grafů, nezávislost, kliky.
12. Toky v sítích.
13. Párování.
14. Fuzzy grafy
    Cvičení na počítači Implementace algoritmů na počítači.
Vyhledávání a testování softwaru ze studované oblasti na Internetu.
Literatura - základní:
1. Chartrand, G. and Oellermann, O.R. : Applied Algorithmic Graph Theory. McGraw Hill, New York, 1993.
5. Hochbaum, D.: Graph Algorithms and Network Flows. Lecture Notes, University of California at Berkeley, 1997, 84 pp.
6. Michaels, J.G. and Rosen, K.H.: Applications of Discrete Mathematics. McGraw Hill, New York, 1991.
Literatura - doporučená:
1. Demel, J.: Grafy a jejich aplikace. ACADEMIA, Praha, 2002.
2. Kolář, J.: Theoretical Computer Science. ČVUT FEL, Praha, 1998.
Zařazení předmětu ve studijních programech:
Program Forma Obor Spec. Typ ukončení   Kredity     Povinnost     St.     Roč.     Semestr  
M2301-5 prezenční studium Inženýrská informatika a automatizace 01 Inženýrská informatika a automatizace informatika zá,zk 5 Volitelný 2 2 Z