|
|
Hlavní nabídka Prohlížení IS/STAG
Nalezené předměty, počet: 1
Stránkování výsledků vyhledávání
Nalezeno 1 záznamů
Export do Xls
Informace o předmětu
KMA / TSI
:
Popis předmětu
Pracoviště / Zkratka
|
KMA
/
TSI
|
Akademický rok
|
2016/2017
|
Akademický rok
|
2016/2017
|
Název
|
Teorie sítí
|
Způsob zakončení
|
Zkouška
|
Způsob zakončení
|
Zkouška
|
Akreditováno / Kredity
|
Ano,
4
Kred.
|
Forma zakončení
|
Kombinovaná
|
Forma zakončení
|
Kombinovaná
|
Rozsah hodin
|
Přednáška
2
[HOD/TYD]
Cvičení
1
[HOD/TYD]
|
Zápočet před zkouškou
|
Ano
|
Zápočet před zkouškou
|
Ano
|
Automatické uznávání zápočtu před zkouškou
|
Ano v případě předchozího hodnocení 4 nebo nic.
|
Počítán do průměru
|
ANO
|
Vyučovací jazyk
|
Čeština
|
Obs/max
|
|
|
|
Automatické uznávání zápočtu před zkouškou
|
Ano v případě předchozího hodnocení 4 nebo nic.
|
Letní semestr
|
9 / -
|
3 / -
|
0 / -
|
Počítán do průměru
|
ANO
|
Zimní semestr
|
0 / -
|
0 / -
|
0 / -
|
Opakovaný zápis
|
NE
|
Opakovaný zápis
|
NE
|
Rozvrh
|
Ano
|
Vyučovaný semestr
|
Letní semestr
|
Vyučovaný semestr
|
Letní semestr
|
Minimum (B + C) studentů
|
1
|
Volně zapisovatelný předmět |
Ano
|
Volně zapisovatelný předmět
|
Ano
|
Vyučovací jazyk
|
Čeština
|
Počet dnů praxe
|
0
|
Počet hodin kontaktní výuky |
|
Hodnotící stupnice |
1|2|3|4 |
Periodicita |
každý rok
|
Hodnotící stupnice pro zp. před zk. |
S|N |
Periodicita upřesnění |
|
Základní teoretický předmět |
Ne
|
Profilující předmět |
Ne
|
Základní teoretický předmět |
Ne
|
Hodnotící stupnice |
1|2|3|4 |
Hodnotící stupnice pro zp. před zk. |
S|N |
Nahrazovaný předmět
|
Žádný
|
Vyloučené předměty
|
KMA/TGD1
|
Podmiňující předměty
|
Nejsou definovány
|
Předměty informativně doporučené
|
KMA/DMA nebo KMA/DMB
|
Předměty,které předmět podmiňuje
|
Nejsou definovány
|
Graf četnosti udělených hodnocení studentům napříč roky:
Obrázek PNG
,
XLS
|
Cíle předmětu (anotace):
|
Cílem předmětu je seznámit studenty se základy teorie grafů a výpočetní složitosti. Student bude schopen po absolvování předmětu porozumět a vysvětlit základní pojmy z teorie grafů, výpočetní složitosti a řešit základní úlohy na grafech, řešitelných v polynomiálním čase.
|
Požadavky na studenta
|
Zápočet: 1 test ke konci semestru alespoň 8 bodů z 15.
Zkouška: písemná část - 3 příklady, ústní část - 2 otázky.
|
Obsah
|
- Základní pojmy z teorie grafů. Maticový popis grafu: matice sousednosti, incidenční matice grafu a jejich algebraické vlastnosti. Ohodnocené grafy.
- Základní úlohy na grafech řešitelné v polynomiálním čase:
* prohledávání grafu, souvislost, silná souvislost,
* minimální kostra, hladové algoritmy,
* vzdálenost v grafech, Bellmanův princip, potenciály,
* eulerovské grafy, úloha čínského pošťáka,
* acyklické grafy, kritická cesta a metody CPM
- Toky a cirkulace v sítích. Ford-Fulkersonova věta o maximálním toku. Dualita a lineární programování. Toky v sítích s cenami a minimalizace celkové ceny. Algoritmy řešení a jejich výpočetní složitost. Praktické úlohy.
- Potenciálové rozdíly a cirkulace, Kirchhoffovy zákony.
- Základní pojmy z výpočetní složitosti - efektivní algoritmy, polynomialita, NP-úplnost.
- Základní NP-úplné a NP-těžké úlohy: hamiltonovské grafy a problém obchodního cestujícího, nezávislé množiny a pokrytí, klikovost, dominance, jádro, barevnost grafu, splnitelnost logických formulí. Praktické aplikace.
- Přibližné algoritmy a heuristiky. Praktické aplikace.
|
Aktivity
|
|
Studijní opory
|
|
Garanti a vyučující
|
|
Literatura
|
-
Doporučená:
Gibbons, Alan. Algorithmic graph theory. Cambridge : Cambridge University Press, 1994. ISBN 0-521-28881-9.
-
Doporučená:
Vágó, I. Graph Theory - Application to the Calculation of Electrical Networks. Budapest, 1985.
-
Doporučená:
Andrásfai, B. Graph Theory - Flows, Matrices. Budapest, 1991.
-
Doporučená:
Kučera, Luděk. Kombinatorické algoritmy. 2. nezm. vyd. Praha : SNTL, 1989.
-
Doporučená:
Holenda, Jiří; Ryjáček, Zdeněk. Lineární algebra II : úvod do diskrétní matematiky. 1. vyd. Plzeň : ZČU, 1992. ISBN 80-7082-060-8.
-
Doporučená:
Teorie grafů a diskrétní optimalizace I. Pracovní texty přednášek
(Ryjáček, Zdeněk)
-
On-line katalogy knihoven
|
Časová náročnost
|
Všechny formy studia
|
Aktivity
|
Časová náročnost aktivity [h]
|
Kontaktní výuka
|
39
|
Příprava na souhrnný test [6-30]
|
25
|
Příprava na zkoušku [10-60]
|
40
|
Celkem
|
104
|
|
Předpoklady - další informace k podmíněnosti studia předmětu |
U studentů se předpokládají znalosti základů diskrétní matematiky v rozsahu předmětu KMA/DMA nebo KMA/DMB. |
Získané způsobilosti |
Student bude po absolvování předmětu:
- rozumět základním pojmům z teorie grafů.
- rozumět základním pojmům z výpočetní složitosti
- mít přehled o základních NP-úplných úlohách
- schopen řešit základní úlohy na grafech řešitelných v polynomiálním čase: minimální cesty a kostry, vzdálenost, souvislost, Eulerovské grafy, acyklické grafy, kritická cesta a metody CPM,
transportní úlohy převodem na tok v sítích
- ovládat základy teorie NP-úplnosti,
- u konkrétních grafových a kombinatorických problémů umět ověřit jejich NP-úplnost, včetně
konstrukce příslušných polynomiálních převodních algoritmů.
- umět použít přibližné algoritmy a heuristiky pro řešení konkrétních kombinatorických problémů
|
Vyučovací metody |
- Přednáška s aktivizací
- Přednáška
- Cvičení
|
Hodnotící metody |
|
|
|
|