PředmětyPředměty(verze: 953)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
Lineární programování a kombinatorická optimalizace - NOPX048
Anglický název: Linear programming and combinatorial optimization
Zajišťuje: Studijní oddělení (32-STUD)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2020
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
Způsob výuky: prezenční
Způsob výuky: prezenční
Je zajišťováno předmětem: NOPT048
Garant: prof. RNDr. Martin Loebl, CSc.
prof. RNDr. Jiří Sgall, DrSc.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Optimalizace
Prerekvizity : {NXXX015, NXXX018, NXXX022, NXXX023, NXXX024, NXXX025, NXXX030, NXXX031, NXXX033}
Neslučitelnost : NOPT048
Záměnnost : NOPT048
Je neslučitelnost pro: NOPT048
Je záměnnost pro: NOPT048
Anotace -
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í.
Poslední úprava: T_KAM (25.04.2008)
Cíl předmětu

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.

Poslední úprava: LOEBL/MFF.CUNI.CZ (09.11.2010)
Podmínky zakončení předmětu -

Pro získání zápočtu je nutné získat polovinu z celkového počtu bodů za domácí úkoly zadané během semestru. Povaha kontroly studia neumožňuje opakování zápočtu.

Zápočet je nutnou podmínkou účasti u zkoušky.

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (24.05.2019)
Literatura -
  • 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
  • Záznam přednášky
Poslední úprava: Jedelský Petr, Mgr. (07.02.2018)
Požadavky ke zkoušce -

Zkouška je ústní. Požadavky odpovídají sylabu v míře pokryté přednáškami. Je pravděpodobné, že se značná část zkoušek či zápočtů může konat distanční formou. Závisí to na vývoji aktuální situace a o jakékoli změně budete včas informováni.

Poslední úprava: Balko Martin, doc. RNDr., Ph.D. (28.04.2020)
Sylabus -

Ú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

Poslední úprava: LOEBL/MFF.CUNI.CZ (09.11.2010)
 
Univerzita Karlova | Informační systém UK