PředmětyPředměty(verze: 802)
Předmět, akademický rok 2016/2017
   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 2016 do 2016
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: Hans Raj Tiwary, M.Sc., Ph.D.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Optimalizace
Je neslučitelnost pro: NMMB438
Je záměnnost pro: NMMB438
Anotace -
Poslední úprava: G_I (11.04.2003)

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.
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.

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