Matematické programování a polyedrální kombinatorika - NOPT034

• Anglický název: Mathematical Programming and Polyhedral Combinatorics
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2021
• Semestr: letní
• E-Kredity: 4
• Rozsah, examinace: letní s.:2/1, 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, angličtina
• Způsob výuky: prezenční
• Další informace: https://kam.mff.cuni.cz/~kolman/matprog.html
• Garant: prof. RNDr. Martin Loebl, CSc.; doc. Mgr. Petr Kolman, Ph.D.; doc. Hans Raj Tiwary, M.Sc., Ph.D.
• Vyučující: doc. Mgr. Petr Kolman, Ph.D.; doc. Hans Raj Tiwary, M.Sc., Ph.D.
• Třída: Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Diskrétní matematika, Optimalizace
• Je neslučitelnost pro: NOPX034
• Je záměnnost pro: NOPX034

Anotace

čeština

Volné pokračování přednášky Lineární programování a kombinatorická optimalizace - NOPT048. Specializovanější témata.

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

angličtina

A follow-up to the lecture Linear programming and combinatorial optimization NOPT048.

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

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.

V případě omezení přítomnosti studentů na univerzitě je možné zkoušku konat distančně.

Poslední úprava: Kolman Petr, doc. Mgr., Ph.D. (30.09.2020)

angličtina

The exam is oral. The requirements correspond to the syllabus as covered by the lectures. If university attendance is limited, the exam may be held online.

Poslední úprava: Kolman Petr, doc. Mgr., Ph.D. (30.09.2020)

Literatura

• M. Grotschel, L. Lovasz, A. Schrijver: Geometric Algorithms and Combinatorial Optimization

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

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

• B. Korte, J. Vygen: Combinatorial Optimization, Springer, 2000

• A. Schrijver: Combinatorial Optimization (3 volume, A,B, & C)

• Guenter M. Ziegler: Lectures on Polytopes

• Various research articles.

Poslední úprava: Hubička Jan, doc. Mgr., Ph.D. (06.09.2021)

Požadavky ke zkoušce

čeština

Zkouška je ústní. Požadavky odpovídají sylabu v míře pokryté přednáškami.

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

angličtina

The exam is oral. The requirements correspond to the syllabus as covered by the lectures.

Poslední úprava: Kolman Petr, doc. Mgr., Ph.D. (30.09.2020)

Sylabus

čeština

Mnohostěny a polytopy: základní pojmy, struktura množiny stěn, polární dualita

Elipsoidový algoritmus.

Metody vnitřního bodu.

Rozšířené formulace.

Poslední úprava: Hubička Jan, doc. Mgr., Ph.D. (06.09.2021)

angličtina

Polyhedra/Polytopes: basic notions, face lattice, polar duality

Ellipsoid algorithm

Interior point

Extended formulations

Poslední úprava: Hubička Jan, doc. Mgr., Ph.D. (06.09.2021)