Teorie grafů
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
611Y1TG | KZ | 2 | 2P+0C | česky |
- Garant předmětu:
- Přednášející:
- Cvičící:
- Předmět zajišťuje:
- pracoviště Děčín
- Anotace:
-
Základní grafové pojmy, formalizace popisu grafů, způsoby reprezentace grafu. Úlohy teorie grafů, instance, zadání. Prohledávání grafu, minimální kostra grafu, stromy, nejkratší dráha, Eulerovské tahy, párování v bipartitních grafech, toky v sítích, cirkulace, kritická cesta, úloha obchodního cestujícího. Algoritmy řešení existenčních a optimalizačních úloh. Výpočetní složitost, přístup k řešení NP-těžkých úloh, heuristické postupy.
- Požadavky:
-
Znalost základních pojmů z teorie grafů.
- Osnova přednášek:
- Osnova cvičení:
- Cíle studia:
-
Student prohloubí své znalosti z teorie grafů. Seznámí se se základními pojmy a problémy z oblasti algoritmizace úloh. Setká se s klasickými úlohami teorie grafů a algoritmy pro jejich řešení. Nahlédne do problematiky časové náročnosti a efektivity algoritmů.
- Studijní materiály:
-
Demel, J: Grafy a jejich aplikace, Praha, Academia, 2002
Matoušek, J., Nešetřil, J.: Kapitoly z diskrétní matematiky, Praha, Karolinum, 2009
- Poznámka:
- Další informace:
- Pro tento předmět se rozvrh nepřipravuje
- Předmět je součástí následujících studijních plánů:
-
- PRE bak. studium oboru DOS rozřazení od 15-16 (povinně volitelný předmět)
- PRE bak. studium oboru MED rozřazení od 15-16 (povinně volitelný předmět)
- PRE bak. studium oboru MED rozřazení od 15-16, od 3.ročníku obor MED v KOMBI formě (povinně volitelný předmět)
- PRE bak. studium oboru DOS rozřazení v 16-17 (povinně volitelný předmět)
- PRE bak. studium oboru LOG rozřazení v 16-17 (povinně volitelný předmět)
- PRE oboru DOS rozřazení od 16-17 (skok z 1. r.) (povinně volitelný předmět)
- PRE bak. studium oboru DOS rozřazení v 17-18 - v 1.sem. si NEZAPSALI 614DB (povinně volitelný předmět)
- PRE bak. studium oboru DOS rozřazení v 17-18 - v 1.sem. si ZAPSALI 14DB. (povinně volitelný předmět)
- PRE bak. studium od 17-18 obor DOS uznané předměty (povinně volitelný předmět)
- PRE bak. studium od 17-18 obor DOS - s FYZ (povinně volitelný předmět)
- PRE bak. studium oboru DOS rozřazení v 18-19 (povinně volitelný předmět)
- PRE bak. studium oboru LOG rozřazení v 18-19 (povinně volitelný předmět)
- PRE bak. studium oboru DOS rozřazení v 18-19 (skok z 1. r.) (povinně volitelný předmět)
- PRE bak. studium oboru DOS rozřazení v 19-20 (povinně volitelný předmět)
- PRE bak. studium oboru LOG rozřazení v 19-20 (povinně volitelný předmět)
- PRE bak. studium oboru DOS rozřazení v 19-20 (skok z 1. r.) (povinně volitelný předmět)
- PRE bak. studium oboru DOS rozřazení v 20-21 (povinně volitelný předmět)
- PRE bak. studium oboru LOG rozřazení v 20-21 (povinně volitelný předmět)
- PRE bak. studium oboru DOS rozřazení v 20-21 (skok z 1. r.) (povinně volitelný předmět)
- PRE bak. studium oboru DOS rozřazení v 21-22 (povinně volitelný předmět)
- PRE bak. studium oboru DOS rozřazení v 21-22 (skok z 1. r.) (povinně volitelný předmět)
- PRE bak. studium oboru DOS rozřazení v 21-22 (skok z 1. r.) (povinně volitelný předmět)
- PRE bak. studium od 22-23 (skok do 3. r. oboru DOS) - program B3710 (povinně volitelný předmět)