PředmětyPředměty(verze: 964)
Předmět, akademický rok 2024/2025
   Přihlásit přes CAS
Základy spojité optimalizace - NMMB438
Anglický název: Fundamentals of Continuous Optimization
Zajišťuje: Katedra algebry (32-KA)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2021
Semestr: letní
E-Kredity: 6
Rozsah, examinace: letní s.:2/2, Z+Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, 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: M Mgr. MMIB
M Mgr. MMIB > Povinně volitelné
Kategorizace předmětu: Matematika > Optimalizace
Neslučitelnost : NOPT046
Záměnnost : NOPT046
Anotace -
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).
Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (25.01.2018)
Podmínky zakončení předmětu -

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

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

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.

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

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.

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

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

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (07.04.2016)
 
Univerzita Karlova | Informační systém UK