|
|
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 / KO
:
Popis předmětu
Pracoviště / Zkratka
|
KMA
/
KO
|
Akademický rok
|
2024/2025
|
Akademický rok
|
2024/2025
|
Název
|
Kombinatorická optimalizace
|
Způsob zakončení
|
Zkouška
|
Způsob zakončení
|
Zkouška
|
Akreditováno / Kredity
|
Ano,
5
Kred.
|
Forma zakončení
|
-
|
Forma zakončení
|
-
|
Rozsah hodin
|
Přednáška
3
[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
|
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
|
2 / -
|
0 / -
|
0 / -
|
Opakovaný zápis
|
NE
|
Opakovaný zápis
|
NE
|
Rozvrh
|
Ano
|
Vyučovaný semestr
|
Zimní + Letní
|
Vyučovaný semestr
|
Zimní + Letní
|
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 |
Ano
|
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/TGD2
|
Předměty,které předmět podmiňuje
|
KMA/DM, KMA/DMI
|
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 podat široký přehled metod řešení lineárních a nelineárních úloh diskrétní optimalizace.
|
Požadavky na studenta
|
Zápočet: semestrální práce.
Zkouška: písemný test, ústní část.
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
|
1. Lineární programování. Geometrie lineárních nerovností. Polyedry.
2. Polyedrální kombinatorika. Farkasovo lemma. Dualita. Maticové hry.
3. Simplexová metoda. Duální simplexová metoda. Citlivostní analýza.
4. Homotopie. Parametrické programování. Revidovaná simplexová metoda.
5. Metoda generování sloupců. Dantzigova-Wolfeova dekompozice.
6. Celočíselné a smíšené lineární programování. Metody řezů. LP a Lagrangeova relaxace. Metody větví a mezí, větví a cen, větví a řezů.
7. Nelineární optimalizace. Konvexní optimalizace. KKT podmínky. Dualita.
8. Metody vnitřního bodu pro lineární programování. Centrální cesta. Kvadratické programování.
9. Semidefinitní programování. Spektraedry. Dualita. Vektorové programování. Metody vnitřního bodu.
10. Kuželové programování. Nelineární celočíselné programování.
11. Vícekriteriální optimalizace. Fuzzy optimalizace. Stochastická optimalizace.
12. Robustní optimalizace. Víceúrovňová optimalizace. Stackelbergovy hry.
13. Aproximační algoritmy. Moderní heuristické algoritmy. Prostor řešení úloh diskrétní optimalizace a jeho analýza. Programování s omezenými podmínkami.
14. Paralelní algoritmy pro lineární a semidefinitní programování.
|
Aktivity
|
|
Studijní opory
|
|
Garanti a vyučující
|
|
Literatura
|
-
Základní:
Cook, W.J.; Cunningham, W.H.; Pulleyblank, W.R.; Schrijver, A. Combinatorial Optimization. Wiley, 1997. ISBN 978-0-471-55894-1.
-
Základní:
Boyd, S.; Vandenberghe, L. Convex Optimization. Cambridge University Press, 2004. ISBN 978-0521833783.
-
Základní:
Roos, C.; Terlaky, T.; Vial, J.-Ph. Interior Point Methods for Linear Optimization. Springer-Verlag New York Inc., 2010. ISBN 9781441938879.
-
Základní:
Vanderbei, Robert J. Linear programming : foundations and extensions. Fifth edition. 2020.
-
Rozšiřující:
Dempe, S. Foundations of Bilevel Programming. Springer US, 2002. ISBN 978-1-4020-0631-9.
-
Rozšiřující:
Sakawa. Fuzzy Sets and Interactive Multiobjective Optimization. 1993.
-
Rozšiřující:
Wang, S.; Watada, J. Fuzzy Stochastic Optimization. Springer-Verlag New York Inc., 2014. ISBN 1489992731.
-
Rozšiřující:
Nesterov, Yu. Introductory Lectures On Convex Optimization: A Basic Course. Springer, 2014. ISBN 9781441988546.
-
Rozšiřující:
Joyce, J. Ulysses. 2024.
-
Doporučená:
Schrijver, Alexander. Combinatorial Optimization. Springer International Publishing AG, part of Springer Nature, 2003. ISBN 978-3-540-44389-6.
-
Doporučená:
Korte, Bernhard; Vygen, Jens. Combinatorial optimization : theory and algorithms. 2nd ed. Berlin : Springer, 2002. ISBN 3-540-43154-3.
-
Doporučená:
Pearl. Heuristics. 1984.
-
Doporučená:
Birge, J.R.; Louveaux, F. Introduction to Stochastic Programming. Springer, New York, NY, 2011. ISBN 978-1-4614-0236-7.
-
Doporučená:
Ehrgott, M. Multicriteria Optimization. Springer Berlin - Heidelberg, 2005. ISBN 978-3-540-21398-7.
-
On-line katalogy knihoven
|
Časová náročnost
|
Všechny formy studia
|
Aktivity
|
Časová náročnost aktivity [h]
|
Příprava na zkoušku [10-60]
|
56
|
Kontaktní výuka
|
52
|
Příprava na souhrnný test [6-30]
|
35
|
Celkem
|
143
|
|
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: |
vysvětlit základní pojmy lineární algebry |
vysvětlit základní pojmy matematické analýzy |
vysvětlit základní pojmy teorie pravděpodobnosti |
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: |
vyřešit základní úlohy lineární algebry |
analyzovat jednoduché úlohy optimalizace funkcí |
zhodnotit výpočetní složitost jednoduchých algoritmů |
Obecné způsobilosti - před zahájením studia předmětu je student schopen: |
bc. studium: kriticky přistupuje ke zdrojům informací, informace tvořivě zpracovává a využívá při svém studiu a praxi, |
bc. studium: vytváří hypotézy, navrhuje postupné kroky, zvažuje využití různých postupů při řešení problému nebo ověřování hypotézy, |
|
Výsledky učení
|
Odborné znalosti - po absolvování předmětu prokazuje student znalosti: |
formulovat standardní úlohy diskrétní optimalizace |
vysvětlit základní optimalizační metody |
vysvětlit použití relaxačních metod |
klasifikovat optimalizační úlohy podle jejich aproximovatelnosti |
Odborné dovednosti - po absolvování předmětu prokazuje student dovednosti: |
řešit standardní úlohy diskrétní optimalizace |
aplikovat aproximační algoritmy na standardní optimalizační úlohy |
analyzovat složitější úlohy diskrétní optimalizace |
posoudit vhodnost aproximačních a heuristických algoritmů pro danou úlohu |
Obecné způsobilosti - po absolvování předmětu je student schopen: |
mgr. studium: používají své odborné znalosti, odborné dovednosti a obecné způsobilosti alespoň v jednom cizím jazyce, |
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, |
|
Hodnoticí metody
|
Odborné znalosti - odborné znalosti dosažené studiem předmětu jsou ověřovány hodnoticími metodami: |
Ústní zkouška, |
Odborné dovednosti - odborné dovednosti dosažené studiem předmětu jsou ověřovány hodnoticími metodami: |
Demonstrace dovedností (praktická činnost), |
Test, |
Ústní zkouška, |
Obecné způsobilosti - obecné způsobilosti dosažené studiem předmětu jsou ověřovány hodnoticími metodami: |
Ústní zkouška, |
Test, |
|
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, |
Přednáška s aktivizací studentů, |
Cvičení (praktické činnosti), |
Odborné dovednosti - pro dosažení odborných dovedností jsou užívány vyučovací metody: |
Cvičení (praktické činnosti), |
Přednáška s aktivizací studentů, |
Obecné způsobilosti - pro dosažení obecných způsobilostí jsou užívány vyučovací metody: |
Cvičení (praktické činnosti), |
Přednáška s aktivizací studentů, |
|
|
|
|