PředmětyPředměty(verze: 825)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Diskrétní a spojitá optimalizace - NOPT046
Anglický název: Discrete and Continuous Optimization
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2017 do 2017
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
Stav předmětu: vyučován
Jazyk výuky: angličtina
Způsob výuky: prezenční
Garant: Andreas Emil Feldmann, Dr.
doc. Mgr. Milan Hladík, Ph.D.
prof. RNDr. Martin Loebl, CSc.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Optimalizace
Je neslučitelnost pro: NMMB438
Je záměnnost pro: NMMB438
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.
Podmínky zakončení předmětu -
Poslední úprava: doc. 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: doc. Mgr. Milan Hladík, Ph.D. (04.05.2015)

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: doc. Mgr. Milan Hladík, Ph.D. (14.02.2018)

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

Sylabus -
Poslední úprava: doc. 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