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 [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: angličtina
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: doc. 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

čeština

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

angličtina

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (25.01.2018)

Review course covering fundamental fields of optimization, incl. computational methods. There are countless examples from almost all branches of human doing leading to problems coming under this discipline. Introduction to several other courses specialized in the solution of particular classes of optimization problems.

Literatura

čeština

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

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

čeština

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

angličtina

Poslední úprava: doc. Andreas Emil Feldmann, Dr. (14.02.2018)

Fundamentals of discrete optimization:

• Introduction, examples of optimization examples and techniques. Analysis of algorithms, implementation and complexity.

• Euler walk, greedy algorithms, shortest path and relations.

• Maximum matching and applications, relation to flows in networks. Heuristics and algorithms for matchings (incl. probabilistic). Postman problem.

• Traveling salesman problem (TSP): heuristics, applications and relations.

• Comparisons of hard and polynomial algorithms: TSP, postman problem, Euler tours, minimal spanning tree, minimal Steiner tree.

Fundamentals of continuous optimization:

• Convex functions and sets

• Convex optimization

• Quadratic programming

• Cone programming and duality

• Karush-Kuhn-Tucker optimality conditions

• Basic methods

• Programming with uncertain data, robust optimization