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

• Anglický název: Mathematical Programming and Polyhedral Combinatorics
• Podoba výuky: přednáška+cvičení
• Zajišťuje: Studijní oddělení (32-STUD)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2022 do 2025
• Počet semestrů výuky: 1
• Semestr: zimní
• E-Kredity: 5
• Rozsah, examinace: zimní s.:2/1, Z+Zk [HT]
• Počet míst: neomezen
• Maximální kapacita předmětu: 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
• Forma uskutečňování: prezenční
• Je zajišťováno předmětem: NOPT034
• Možnost opakovaného zápisu: 2 / 2 / 2 / 2
• Garant: prof. RNDr. Martin Loebl, CSc.; doc. Mgr. Petr Kolman, Ph.D.
• Třída: Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Diskrétní matematika, Optimalizace
• Prerekvizity : {NXXX007, NXXX008, NXXX009, NXXX036, NXXX037}
• Neslučitelnost : NOPT034
• Záměnnost : NOPT034

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)

Kontroly studia předmětu a podmínky pro jejich úspěšné vykonání, způsob hodnocení

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