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í
• 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

čeština

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)

angličtina

An introduction to mainly discrete optimisation is given. The lecture is centered around the theory of linear programming.

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

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

čeština

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)

angličtina

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.

Poslední úprava: Tiwary Hans Raj, doc., M.Sc., Ph.D. (16.02.2022)

Literatura

čeština

• 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)

angličtina

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

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

Požadavky ke zkoušce

čeština

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)

angličtina

Hans Raj Tiwary:

For the main exam, the requirements correspond to the syllabus as covered by the lectures.

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

Sylabus

čeština

Ú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)

angličtina

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

Matching polytope

Integer programming

Approximation algorithms

Matroids

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