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: LOEBL/MFF.CUNI.CZ (09.11.2010)
An introduction to mainly discrete optimisation is given. The lecture is centered around the theory of
linear programming.
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.
Podmínky zakončení předmětu -
Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (24.05.2019)
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: doc. Hans Raj Tiwary, M.Sc., Ph.D. (16.02.2022)
Hans Raj Tiwary:
Students need to pass 50% of the homeworks and 50% of the quizzes to pass the tutorial. Due to the requirements, additional attempts to pass the tutorial are excluded.
Passing the tutorials is required before taking the exam.
Literatura -
Poslední úprava: Mgr. Petr Jedelský (07.02.2018)
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
Poslední úprava: prof. Mgr. Milan Hladík, Ph.D. (22.11.2012)
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, B. Gärtner, Understanding and using linear programming, Springer, 2006.
J. Matoušek Introduction to Discrete Geometry. ITI Series 2003-150, MFF UK, 2003
Požadavky ke zkoušce -
Poslední úprava: doc. RNDr. Martin Balko, Ph.D. (28.04.2020)
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: doc. Mgr. Jan Kynčl, Ph.D. (23.05.2019)
Hans Raj Tiwary:
For the main exam, the requirements correspond to the syllabus as covered by the lectures.
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
Poslední úprava: LOEBL/MFF.CUNI.CZ (09.11.2010)
Linear and integer programming problem, examples
Combinatorial geometry, polytopes and their minimal description, Minkowski-Weyl's theorem
Duality of linear programming, Farkas' lemma
Simplex method, pivoting rules
Polynomial algorithms for linear programming (overview)
Unimodularity, König's lemma, network flows
Weighted matchings in general graphs, Edmonds' algorithm
