|
|
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 / TGD2
:
Popis předmětu
Pracoviště / Zkratka
|
KMA
/
TGD2
|
Akademický rok
|
2024/2025
|
Akademický rok
|
2024/2025
|
Název
|
Teorie grafů, optimalizace a složitost 2
|
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 2
|
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
|
11 / -
|
1 / -
|
1 / -
|
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
|
Nejsou definovány
|
Podmiňující předměty
|
Nejsou definovány
|
Předměty informativně doporučené
|
KMA/TGD1
|
Předměty,které předmět podmiňuje
|
KMA/DIM, KMA/DM, KMA/DMI, 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 diskrétní optimalizace. Student bude mít po absolvování předmětu přehled o základních optimalizačních úlohách na grafech a sítích, bude schopen aktivně ovládat základní metody a algoritmy jejich řešení, a to včetně posouzení jejich výpočetní složitosti. Bude rozumět teoretickému pozadí jednotlivých metod a jejich vzájemné převoditelnosti, včetně pochopení role charakterizačních vět při konstrukci efektivních algoritmů.
|
Požadavky na studenta
|
U studentů se předpokládají znalosti algoritmické teorie grafů a základů teorie výpočetní složitosti v rozsahu předmětu KMA/TGD1.
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).
|
Obsah
|
Optimalizační úlohy na grafech a sítích: tok v síti s cenami, minimalizace celkové ceny řešení a optimální tok, potenciály, algoritmy nalezení optimálního toku.
Lineární programování (reálné), různé formulace úlohy a jejich ekvivalence, simplexový algoritmus, výpočetní složitost. Degenerované úlohy a cyklení. Dualita úloh LP. Úloha celočíselného lineárního programování a její NP-úplnost, celočíselné optimalizační úlohy s totálně unimodulární maticí.
Formulace optimalizačních úloh na grafech a sítích jako úloh lineárního programování.
Přiřazovací problémy, maximální a optimální párování a maďarská metoda.
Speciální třídy grafů a vliv speciální struktury grafu na výpočetní složitost problému: hranové grafy, rovinné grafy. Přibližné algoritmy a heuristiky pro některé úlohy diskrétní optimalizace.
|
Aktivity
|
|
Studijní opory
|
Studentům jsou k dispozici kompletní studijní materiály na webové stránce předmětu
https://home.zcu.cz/~ryjacek/TGD2.php
|
Garanti a vyučující
|
|
Literatura
|
-
Základní:
Pracovní texty přednášek
-
Doporučená:
Hromkovič, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. 2nd ed. Berlin : Springer, 2003. ISBN 3-540-44134-4.
-
Doporučená:
Cook, W.J.; Cunningham, W.H.; Pulleyblank, W.R.; Schrijve, A. Combinatorial Optimization. New York: Wiley, 1998.
-
Doporučená:
Papadimitriou, Christos H.; Steiglitz, Kenneth. Combinatorial optimization : algorithms and complexity. 1st pub. Mineola : Dover Publications, 1998. ISBN 0-486-40258-4.
-
Doporučená:
Korte, Bernhard; Vygen, Jens. Combinatorial optimization : theory and algorithms. 2nd ed. Berlin : Springer, 2002. ISBN 3-540-43154-3.
-
Doporučená:
Kučera, Luděk. Kombinatorické algoritmy. 2. nezm. vyd. Praha : SNTL, 1989.
-
Doporučená:
Plesník, Ján; Dupačová, Jitka; Vlach, Milan. Lineárne programovanie. 1. vyd. Bratislava : Alfa, 1990. ISBN 80-05-00679-9.
-
Doporučená:
Lovász, L.; Plummer, M. Matching Theory. Budapest: Akadémiai Kiadó, 1986.
-
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: |
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 pojmy a úlohy teorie grafů (v rozsahu předmětu KMA/TGD1) 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 - 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 a úlohy teorie grafů v rozsahu předmětu KMA/TGD1 |
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 - 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: |
formulovat základní optimalizační úlohy na grafech a sítích, vysvětlit jejich vlastnosti a základní metody |
popsat algoritmy řešení základních optimalizačních úloh a posoudit jejich výpočetní složitost |
vysvětlit teoretické pozadí jednotlivých metod a jejich vzájemné převoditelnosti, včetně role charakterizačních vět a dobrých charakteristik při konstrukci efektivních algoritmů |
Odborné dovednosti - po absolvování předmětu prokazuje student dovednosti: |
aktivně používat metody a algoritmy řešení jednotlivých úloh |
klasifikovat jednotlivé problémy z hlediska výpočetní složitosti a u NP-těžkých problémů ovládat základní heuristické a aproximační algoritmy |
ovládat základní optimalizační úlohy na grafech a sítích |
používat vzájemné převody úloh, včetně převodů grafových a síťových optimalizačních úloh na úlohy lineárního programování |
Obecné způsobilosti - po absolvování předmětu je student schopen: |
mgr. studium: srozumitelně a přesvědčivě sdělují odborníkům i širší veřejnosti vlastní odborné názory, |
mgr. studium: používají své odborné znalosti, odborné dovednosti a obecné způsobilosti alespoň v jednom cizím jazyce, |
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), |
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: |
Přednáška založená na výkladu, |
Skupinová výuka, |
Odborné dovednosti - pro dosažení odborných dovedností jsou užívány vyučovací metody: |
Skupinová výuka, |
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, |
|
|
|
|