Matroidy a submodulární optimalizace - NDMI111

• Anglický název: Matroids & Submodular Optimization
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2021
• Semestr: zimní
• E-Kredity: 5
• Rozsah, examinace: zimní 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: angličtina
• Způsob výuky: prezenční
• Garant: doc. Mgr. Petr Kolman, Ph.D.; prof. RNDr. Martin Loebl, CSc.; doc. Hans Raj Tiwary, M.Sc., Ph.D.
• Vyučující: RNDr. Martin Černý; doc. Mgr. Petr Kolman, Ph.D.; prof. RNDr. Martin Loebl, CSc.; doc. Hans Raj Tiwary, M.Sc., Ph.D.

Anotace

čeština

Pokračování přednášky Lineární programování a kombinatorická optimalizace NOPT048

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

angličtina

Continuation of NOPT048 Linear programming and combinatorial optimisation

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

Literatura

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

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

Sylabus

čeština

Matroidy: dualita, representabilita, průnik 2 matroidů, algorithmy

Submodulární funkce: úvod, optimizace a aproximační algoritmy, aplikace pro aukce a algoritmickou teorii her

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

angličtina

Matroids: duality, representability, intersection, algorithms

Submodular functions: introduction, optimisation and approximation algorithms, application to auctions & Game Theory

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