PředmětyPředměty(verze: 780)
Předmět, akademický rok 2015/2016
   Přihlásit přes CAS
Optimalizační metody - NOPT048
Anglický název: Optimization methods
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2015 do 2015
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: čeština, angličtina
Způsob výuky: prezenční
Garant: prof. RNDr. Jiří Sgall, DrSc.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Optimalizace
Anotace -
Poslední úprava: T_KAM (25.04.2008)

Přednáška podává úvod do zejména diskrétní optimalizace. Centrálním tématem jsou různé aspekty lineárního programování.
Cíl předmětu
Poslední úprava: LOEBL/MFF.CUNI.CZ (09.11.2010)

Cílem přednášky je, aby se studenti seznámili se základními metodami diskrétní optimalizace a naučili se v optimalizaci orientovat tak, aby byli schopni sami rozpoznat nové trendy.

Literatura -
Poslední úprava: LOEBL/MFF.CUNI.CZ (09.11.2010)

A. Schrijver, Theory of linear and integer programming, John Wiley, 1986

W.J.Cook, W.H. Cunningham W.R.Pulleyblank, A. Schrijver, Combinatorial Optimization, John Wiley, 1997

J. Matoušek Lineární programování a lineární algebra pro informatiky. ITI Series 2006-311, MFF UK, 2006

J. Matoušek Introduction to Discrete Geometry. ITI Series 2003-150, MFF UK, 2003

Sylabus -
Poslední úprava: LOEBL/MFF.CUNI.CZ (09.11.2010)

Úloha lineárního a celočíselného programování, příklady

Kombinatorická geometrie, mnohostěny, Minkowski-Weylova věta, minimální popis mnohostěnu

Dualita lineárního programování, Farkasovo lemma

Simplexová metoda, pivotovací pravidla

Polynomiální algoritmy pro lineární programování (přehled)

Unimodularita, Königovo lemma, toky v sítích

Vážené párování v obecných grafech, Edmondsův algoritmus

Mnohostěn párování

Celočíselné programování, metoda řezů

Aproximační algoritmy

Matroidy

 
Univerzita Karlova | Informační systém UK