|
|
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 / TGD1
:
Popis předmětu
Pracoviště / Zkratka
|
KMA
/
TGD1
|
Akademický rok
|
2023/2024
|
Akademický rok
|
2023/2024
|
Název
|
Teorie grafů, optimalizace a složitost 1
|
Způsob zakončení
|
Zkouška
|
Způsob zakončení
|
Zkouška
|
Název dlouhý
|
Teorie grafů, diskrétní optimalizace a výpočetní složitost 1
|
Akreditováno / Kredity
|
Ano,
5
Kred.
|
Forma zakončení
|
Kombinovaná
|
Forma zakončení
|
Kombinovaná
|
Rozsah hodin
|
Přednáška
3
[HOD/TYD]
Seminář
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
|
Ne
|
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
|
Ne
|
Letní semestr
|
0 / -
|
0 / -
|
0 / -
|
Počítán do průměru
|
ANO
|
Zimní semestr
|
29 / -
|
0 / -
|
3 / -
|
Opakovaný zápis
|
NE
|
Opakovaný zápis
|
NE
|
Rozvrh
|
Ano
|
Vyučovaný semestr
|
Zimní semestr
|
Vyučovaný semestr
|
Zimní 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 |
Ano
|
Profilující předmět |
Ne
|
Základní teoretický předmět |
Ano
|
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
|
Nejsou definovány
|
Podmiňující předměty
|
Nejsou definovány
|
Předměty informativně doporučené
|
Nejsou definovány
|
Předměty,které předmět podmiňuje
|
KIV/DSSZ, KMA/DIM, KMA/DM, KMA/DMI, KMA/PNM, KMA/SZMZ
|
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 algoritmické teorie grafů a výpočetní složitosti. Student bude schopen po absolvování předmětu aktivně ovládat základní grafové pojmy, bude schopen navrhnout algoritmy jejich řešení a posoudit jejich výpočetní složitost. Bude ovládat základy teorie NP-úplnosti a u vybraných konkrétních grafových a kombinatorických problémů ověřit jejich NP-úplnost, včetně konstrukce příslušných polynomiálních převodních algoritmů.
|
Požadavky na studenta
|
Zápočet: zápočtový test.
Zkouška: písemná část - 3 příklady, 2 vyučovací hodiny, ústní část - 2 otázky.
U všech otázek je hlavní důraz kladen na algoritmické aspekty daného problému (tj. algoritmy řešení a jejich výpočetní složitost).
Garantem předmětu je stanoveno, že zápočet se při opakovaném zapsání neuznává (viz čl. 24, odst. 3 SZŘ ZČU).
|
Obsah
|
Základní úlohy řešitelné v polynomiálním čase: minimální cesty a kostry, vzdálenost, souvislost a k-souvislost, Eulerovské grafy, acyklické grafy, kritická cesta a metody CPM.
Toky v sítích a transportní úlohy, Ford-Fulkersonova věta o maximálním toku.
Grafy a matice: rozložitelnost, slabá rozložitelnost a generická hodnost matice a její určení převodem na grafovou úlohu.
Základní NP-úplné úlohy: hamiltonovské grafy a problém obchodního cestujícího, nezávislé množiny a pokrytí, klikovost, dominance, jádro, barevnost grafu.
Základy teorie NP-úplnosti: deterministické a nedeterministické algoritmy, jazyky třídy P a NP, NP-úplnost úlohy splnitelnosti logických formulí, vzájemné polynomiálních převody NP-úplných úloh, NP-úplnost úloh nezávislosti, klikovosti a 3-obarvitelnosti grafu.
|
Aktivity
|
|
Studijní opory
|
|
Garanti a vyučující
|
|
Literatura
|
-
Základní:
Čada, Roman; Kaiser, Tomáš; Ryjáček, Zdeněk. Diskrétní matematika. Plzeň : Západočeská univerzita, 2004. ISBN 80-7082-939-7.
-
Základní:
Bondy, Adrian; Murty, U.S.R. Graph Theory. Springer-Verlag London, 2008. ISBN 978-1-84996-690-0.
-
Základní:
Kučera, Luděk. Kombinatorické algoritmy. 2. nezm. vyd. Praha : SNTL, 1989.
-
Doporučená:
Sanjoy Dasgupta; Papadimitriou, Christos; Vazirani, Umesh. Algorithms. New York : McGraw-Hill, 2008. ISBN 978-0-07-352340-8.
-
Doporučená:
Papadimitriou. Computational Complexity. 1995.
-
On-line katalogy knihoven
|
Časová náročnost
|
Všechny formy studia
|
Aktivity
|
Časová náročnost aktivity [h]
|
Kontaktní výuka
|
52
|
Příprava na zkoušku [10-60]
|
60
|
Příprava na souhrnný test [6-30]
|
25
|
Celkem
|
137
|
|
Předpoklady
|
Odborné znalosti - pro úspěšné zvládnutí předmětu se předpokládá, že je student před zahájením výuky schopen: |
formulovat základní pojmy z teorie grafů (v rozsahu předmětu KMA/DMA) a vysvětlit jejich základní vlastnosti, včetně porozumění souvislostem |
popsat maticový popis grafu a vysvětlit vztahy mezi vlastnostmi grafu a algebraickými vlastnostmi příslušné matice |
vysvětlit základní pojmy z teorie relačních struktur: binární relace, ekvivalence (včetně aplikace na aritmetiku modulo 2), uspořádání a částečné uspořádání, Booleovy algebry a Booleovské polynomy a funkce |
Odborné dovednosti - pro úspěšné zvládnutí předmětu se předpokládá, že student před zahájením výuky dokáže: |
aktivně ovládat pojmy ekvivalence a rozkladu množiny na třídy ekvivalence |
navrhnout a formulovat algoritmy řešení základních grafových úloh (v rozsahu předmětu KMA/DMA) |
prakticky použít základy teorie Booleových algeber, včetně vyjádření Booleovského polynomu v konjunktivní a disjunktivní normální formě |
Obecné způsobilosti - před zahájením studia předmětu je student schopen: |
bc. studium: své učení a pracovní činnost si sám plánuje a organizuje, |
|
Výsledky učení
|
Odborné znalosti - po absolvování předmětu prokazuje student znalosti: |
analyzovat konkrétní algoritmy z hlediska jejich výpočetní složitosti |
klasifikovat základní problémy teorie grafů a diskrétní matematiky z hlediska výpočetní složitosti |
vysvětlit probírané pojmy a úlohy teorie grafů a jejich základní vlastnosti, včetně porozumění souvislostem |
vysvětlit základy teorie výpočetní složitosti a základní principy teorie NP-úplnosti |
Odborné dovednosti - po absolvování předmětu prokazuje student dovednosti: |
aktivně ovládat probírané pojmy a úlohy teorie grafů |
navrhnout, formulovat a prakticky použít algoritmy řešení základních grafových úloh |
ovládat klasifikaci algoritmů z hlediska jejich výpočetní složitosti a posoudit výpočetní složitost konkrétních algoritmů |
pro vybrané algoritmicky obtížné úlohy navrhnout heuristické algoritmy umožňující jejich přibližné nebo částečné řešení |
u vybraných konkrétních grafových a kombinatorických problémů ověřit jejich NP-úplnost, včetně konstrukce příslušných polynomiálních převodních algoritmů |
Obecné způsobilosti - po absolvování předmětu je student schopen: |
bc. studium: samostatně získávají další odborné znalosti, dovednosti a způsobilosti na základě především praktické zkušenosti a jejího vyhodnocení, ale také samostatným studiem teoretických poznatků oboru, |
aktivně využívá získané znalosti a dovednosti při řešení praktických problémů |
|
Hodnoticí metody
|
Odborné znalosti - odborné znalosti dosažené studiem předmětu jsou ověřovány hodnoticími metodami: |
Kombinovaná zkouška, |
Test, |
Demonstrace dovedností (praktická činnost), |
Odborné dovednosti - odborné dovednosti dosažené studiem předmětu jsou ověřovány hodnoticími metodami: |
Demonstrace dovedností (praktická činnost), |
Test, |
Obecné způsobilosti - obecné způsobilosti dosažené studiem předmětu jsou ověřovány hodnoticími metodami: |
Kombinovaná zkouška, |
|
Vyučovací metody
|
Odborné znalosti - pro dosažení odborných znalostí jsou užívány vyučovací metody: |
Cvičení (praktické činnosti), |
Přednáška založená na výkladu, |
Odborné dovednosti - pro dosažení odborných dovedností jsou užívány vyučovací metody: |
Cvičení (praktické činnosti), |
Obecné způsobilosti - pro dosažení obecných způsobilostí jsou užívány vyučovací metody: |
Přednáška založená na výkladu, |
|
|
|
|