PředmětyPředměty(verze: 901)
Předmět, akademický rok 2021/2022
  
Diskrétní a spojitá optimalizace - NOPX046
Anglický název: Discrete and Continuous Optimization
Zajišťuje: Studijní oddělení (32-STUD)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2020
Semestr: letní
E-Kredity: 6
Rozsah, examinace: letní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: ne
Stav předmětu: vyučován
Jazyk výuky: angličtina
Způsob výuky: prezenční
Je zajišťováno předmětem: NOPT046
Garant: prof. Mgr. Milan Hladík, Ph.D.
prof. RNDr. Martin Loebl, CSc.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Optimalizace
Prerekvizity : {NXXX014, NXXX015, NXXX016, NXXX017, NXXX018, NXXX022, NXXX023, NXXX024, NXXX025, NXXX033}
Neslučitelnost : NOPT046
Záměnnost : NOPT046
Je neslučitelnost pro: NOPT046
Je záměnnost pro: NOPT046
Anotace -
Poslední úprava: Mgr. Jan Kynčl, Ph.D. (25.01.2018)
Přehledová přednáška pokrývající základní oblasti optimalizace, včetně výpočetních metod. Na úlohy spadající pod tuto problematiku vede nesčetné množství problémů z téměř všech oborů lidské činnosti. Má velmi široké možnosti použití. Úvod k dalším přednáškám specializovaným na řešení jednotlivých tříd optimalizačních úloh. Pro absolvování předmětu jsou vhodné (nikoli však nutné) předběžné znalosti lineárního programování, např. z přednášky NOPT048 Lineární programování a kombinatorická optimalizace (dříve Opt. Metody).
Podmínky zakončení předmětu -
Poslední úprava: prof. Mgr. Milan Hladík, Ph.D. (14.02.2018)

Pro zápočet je potřeba získat dostatečný počet bodů za vypracované domácí úkoly, které se zveřejňují průběžně během semestru, a za aktivitu na cvičení. Účast na cvičení však není povinná.

Bližší informace k zápočtům jsou k dispozici na stránce:

https://kam.mff.cuni.cz/~hladik/DSO

Literatura -
Poslední úprava: prof. Mgr. Milan Hladík, Ph.D. (30.09.2021)

Doprovodný text (pro část spojité optimalizace):

https://kam.mff.cuni.cz/~hladik/DSO/text_dso.pdf

Další literatura:

M.S. Bazaraa, H.D. Sherali, C.M. Shetty: Nonlinear Programming, Wiley, New Jersey, 2006.

S. Boyd, L. Vandenberghe: Convex Optimization, Cambridge University Press, 2009.

W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver. Combinatorial Optimization. Wiley, New York, 1998.

Požadavky ke zkoušce -
Poslední úprava: prof. Mgr. Milan Hladík, Ph.D. (28.04.2020)

Zkouška je ústní a požadavky odpovídají sylabu předmětu v rozsahu, který byl presentován na přednášce.

Ve výjimečných situacích může mít zkouška distanční formu.

Sylabus -
Poslední úprava: prof. Mgr. Milan Hladík, Ph.D. (07.04.2016)

Základy diskrétní optimalizace:

  • Úvod, příklady optimalizačních problémů a optimalizačních technik. Analýza algoritmů, implementace, složitost.
  • Eulerovská procházka, hladový algoritmus, nejkratsi cesta a jejich souvislosti.
  • Párování a aplikace, souvislost s toky v sítích. Heuristiky a algoritmy, i pravděpodobnostní, na párování. Problém pošťáka.
  • Problém obchodního cestujícího (TSP): heuristiky, aplikace a souvislosti
  • Porovnání těžkých a polynomiálních problémů: TSP, problém pošťáka, Euler tours, minimální kostra, minimální Steiner tree.

Základy spojité optimalizace:

  • Konvexní funkce a množiny
  • Konvexní optimalizace
  • Kvadratické programování
  • Kuželové programování a dualita
  • Karush-Kuhn-Tuckerovy podmí­nky optimality
  • Základní metody
  • Programování s nepřesnými daty, robustní optimalizace

 
Univerzita Karlova | Informační systém UK