Teorie grafů
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
11Y1TG | KZ | 2 | 2P+0C | česky |
- Garant předmětu:
- Přednášející:
- Cvičící:
- Předmět zajišťuje:
- ústav aplikované matematiky
- 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ů:
-
- 2.bl.bak.prez.DS 09/10začátek (povinně volitelný předmět)
- 2.bl.bak.prez.ME 09/10začátek (povinně volitelný předmět)
- 2.bl.bak.prez.AI 09/10začátek (povinně volitelný předmět)
- 2.bl.bak.prez.LD 09/10 (povinně volitelný předmět)
- 2.bl.bak.prez.DS 05/06 začátek (povinně volitelný předmět)
- 2.bl.bak.prez.ME 05/06 začátek (povinně volitelný předmět)
- 2.bl.bak.prez.AI 05/06 začátek (povinně volitelný předmět)
- 2.bl.bak.prez.LD 05/06začátek (povinně volitelný předmět)
- 2.bl.bak.prez.DS 06/07 začátek (povinně volitelný předmět)
- 2.bl.bak.prez.ME 06/07 začátek (povinně volitelný předmět)
- 2.bl.bak.prez.AI 06/07 začátek (povinně volitelný předmět)
- 2.bl.bak.prez.LD 06/07 začátek (povinně volitelný předmět)
- 2.bl.bak.prez.DS 07/08začátek (povinně volitelný předmět)
- 2.bl.bak.prez.AI 07/08začátek (povinně volitelný předmět)
- 2.bl.bak.prez.ME 07/08začátek (povinně volitelný předmět)
- 2.bl.bak.prez.LD 07/08začátek (povinně volitelný předmět)
- 2.bl.bak.prez.DS 08/09začátek (povinně volitelný předmět)
- 2.bl.bak.prez.AI 08/09začátek (povinně volitelný předmět)
- 2.bl.bak.prez.LD 08/09začátek (povinně volitelný předmět)
- 2.bl.bak.prez.ME 08/09začátek (povinně volitelný předmět)
- 2.bl.bak.prez.DS 10/11začátek (povinně volitelný předmět)
- 2.bl.bak.prez.ME 10/11začátek (povinně volitelný předmět)
- 2.bl.bak.prez.AI 10/11začátek (povinně volitelný předmět)
- 2.bl.bak.prez.LD 10/11 (povinně volitelný předmět)
- 2.bl.bak.pres.DS (povinně volitelný předmět)
- 2.bl.bak.prez.AI (povinně volitelný předmět)
- 2.bl.bak.prez.LD (povinně volitelný předmět)
- 2.bl.bak.prez.ME (povinně volitelný předmět)
- AUT bak.prez.11/12 (povinně volitelný předmět)
- DOS bak.prez.11/12 (povinně volitelný předmět)
- ITS bak.prez.11/12 (povinně volitelný předmět)
- LED bak.prez.11/12 (povinně volitelný předmět)
- MED bak.prez.11/12 (povinně volitelný předmět)
- AUT bak. prez.12/13 (povinně volitelný předmět)
- DOS bak.prez.12/13 (povinně volitelný předmět)
- MED bak.prez.12/13 (povinně volitelný předmět)
- ITS bak.prez.12/13 (povinně volitelný předmět)
- LED bak.prez.12/13 (povinně volitelný předmět)
- AUT bak.prez.13/14 (povinně volitelný předmět)
- DOS bak.prez.13/14 (povinně volitelný předmět)
- ITS bak.prez.13/14 (povinně volitelný předmět)
- LED bak.prez.13/14 (povinně volitelný předmět)
- MED bak.prez.13/14 (povinně volitelný předmět)
- DOS bak.prez.13/14 (SKOK) (povinně volitelný předmět)
- LED bak.prez.13/14 (SKOK) (povinně volitelný předmět)
- MED bak.prez.13/14 (SKOK) (povinně volitelný předmět)
- DOS bak.prez.14/15 (povinně volitelný předmět)
- MED bak.prez.14/15 (povinně volitelný předmět)
- AUT bak.prez.14/15 (povinně volitelný předmět)
- ITS bak.prez.14/15 (povinně volitelný předmět)
- LED bak.prez.14/15 (povinně volitelný předmět)
- DOS bak.prez.15/16 (povinně volitelný předmět)
- MED bak.prez.15/16 (povinně volitelný předmět)
- AUT bak.prez.15/16 (povinně volitelný předmět)
- ITS bak.prez.15/16 (povinně volitelný předmět)
- LED bak.prez.15/16 (povinně volitelný předmět)
- BEZ bak.prez.15/16 (povinně volitelný předmět)
- DOS bak.prez.16/17 (povinně volitelný předmět)
- LOG bak.prez.16/17 (povinně volitelný předmět)
- ITS bak.prez.16/17 (povinně volitelný předmět)
- LED bak.prez.16/17 (povinně volitelný předmět)
- BEZ bak.prez.16/17 (povinně volitelný předmět)
- DOS bak.prez.17/18 - v 1.sem. si NEZAPSALI 14DB (povinně volitelný předmět)
- DOS bak.prez.17/18 - v 1.sem. si ZAPSALI 14DB (povinně volitelný předmět)
- LOG bak.prez.17/18 - v 1.sem. si NEZAPSALI 14DB (povinně volitelný předmět)
- LOG bak.prez.17/18 - v 1.sem. si ZAPSALI 14DB (povinně volitelný předmět)
- ITS bak.prez.17/18 - v 1.sem. si NEZAPSALI 14DB (povinně volitelný předmět)
- ITS bak.prez.17/18 - v 1.sem. si ZAPSALI 14DB (povinně volitelný předmět)
- LED bak.prez.17/18 - v 1.sem. si NEZAPSALI 14DB (povinně volitelný předmět)
- LED bak.prez.17/18 - v 1.sem. si ZAPSALI 14DB (povinně volitelný předmět)
- BEZ bak.prez.17/18 - v 1.sem. si NEZAPSALI 14DB (povinně volitelný předmět)
- BEZ bak.prez.17/18 - v 1.sem. si ZAPSALI 14DB (povinně volitelný předmět)
- LOG bak.prez.17/18 - včetně 11FYZ v 3.s. (povinně volitelný předmět)
- LED bak.prez.17/18 - včetně 11FYZ v 3.s. (povinně volitelný předmět)
- DOS bak.prez.18/19 (povinně volitelný předmět)
- LOG bak.prez.18/19 (povinně volitelný předmět)
- ITS bak.prez.18/19 (povinně volitelný předmět)
- LED bak.prez.18/19 (povinně volitelný předmět)
- DOS bak.prez.18/19 (skok do 3.r.) (povinně volitelný předmět)
- CŽV pro LED bak.prez. v 18/19 (povinně volitelný předmět)
- LOG bak.prez.18/19 (skok do 3.r.) (povinně volitelný předmět)
- ITS bak.prez.18/19 (skok do 3.r.) (povinně volitelný předmět)
- LED bak.prez.18/19 - skok z 2.r.do 3.r. (povinně volitelný předmět)
- LED bak.prez.19/20 angličtina (povinně volitelný předmět)
- DOS bak.prez.19/20 (povinně volitelný předmět)
- LOG bak.prez.19/20 (povinně volitelný předmět)
- ITS bak.prez.19/20 (povinně volitelný předmět)
- LED bak.prez.19/20 (povinně volitelný předmět)
- ITS bak.prez.19/20 (skok do 3.r.) (povinně volitelný předmět)
- DOS bak.prez.19/20 (skok do 3.r.) (povinně volitelný předmět)
- LED bak.prez.19/20 (skok do 3.r.) (povinně volitelný předmět)
- LED bak.prez.20/21 angličtina (povinně volitelný předmět)
- DOS bak.prez.20/21 (povinně volitelný předmět)
- LOG bak.prez.20/21 (povinně volitelný předmět)
- LOG bak.prez.20/21 (skok do 3.r.) (povinně volitelný předmět)
- ITS bak.prez.20/21 (povinně volitelný předmět)
- ITS bak.prez.20/21 (skok do 3.r.) (povinně volitelný předmět)
- LED bak.prez.20/21 (povinně volitelný předmět)
- LED bak.prez.20/21 (skok do 3.r.) (povinně volitelný předmět)
- LED bak.prez.21/22 (skok do 3.r.) (povinně volitelný předmět)
- DOS bak.prez.21/22 (skok do 3.r.) (povinně volitelný předmět)
- LOG (obor) bak.prez.21/22 (skok do 3.r.) (povinně volitelný předmět)
- ITS bak.prez.21/22 (skok do 3.r.) (povinně volitelný předmět)
- DOS bak.prez.21/22 (povinně volitelný předmět)
- ITS bak.prez.21/22 (povinně volitelný předmět)
- LED bak.prez.21/22 (povinně volitelný předmět)