PředmětyPředměty(verze: 908)
Předmět, akademický rok 2022/2023
   Přihlásit přes CAS
Lineární programování a kombinatorická optimalizace - NOPT048
Anglický název: Linear Programming and Combinatorial Optimization
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2020
Semestr: letní
E-Kredity: 5
Rozsah, examinace: letní s.:2/2, Z+Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Další informace: https://iuuk.mff.cuni.cz/~sgall/vyuka/LP/
Garant: prof. RNDr. Martin Loebl, CSc.
prof. RNDr. Jiří Sgall, DrSc.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Optimalizace
Neslučitelnost : NOPX048
Záměnnost : NOPX048
Je neslučitelnost pro: NOPX048
Je záměnnost pro: NOPX048
Soubory Komentář Kdo přidal
stáhnout 01-uvod.mp4 úvod, úloha LP prof. RNDr. Jiří Sgall, DrSc.
stáhnout 01-uvod.pdf úvod, úloha LP prof. RNDr. Jiří Sgall, DrSc.
stáhnout 02-konvexni-mnoziny.mp4 nejkratší cesty, konvexní množiny prof. RNDr. Jiří Sgall, DrSc.
stáhnout 02-konvexni-mnoziny.pdf nejkratší cesty, konvexní množiny prof. RNDr. Jiří Sgall, DrSc.
stáhnout 03-konvexni-mnohosteny.mp4 konvexní mnohostěny prof. RNDr. Jiří Sgall, DrSc.
stáhnout 03-konvexni-mnohosteny.pdf konvexní mnohostěny prof. RNDr. Jiří Sgall, DrSc.
stáhnout 04-steny-mnohostenu.mp4 stény mnohostěnů prof. RNDr. Jiří Sgall, DrSc.
stáhnout 04-steny-mnohostenu.pdf stény mnohostěnů prof. RNDr. Jiří Sgall, DrSc.
stáhnout 05-minimalni-popis-mnohostenu.mp4 minimální popis mnohostěnu prof. RNDr. Jiří Sgall, DrSc.
stáhnout 05-minimalni-popis-mnohostenu.pdf minimální popis mnohostěnu prof. RNDr. Jiří Sgall, DrSc.
stáhnout 06-simplexova-metoda.mp4 simlplexová metoda prof. RNDr. Jiří Sgall, DrSc.
stáhnout 06-simplexova-metoda.pdf simlplexová metoda prof. RNDr. Jiří Sgall, DrSc.
stáhnout 07-algoritmy-pro-LP.mp4 algoritmy pro lineární programování prof. RNDr. Jiří Sgall, DrSc.
stáhnout 07-algoritmy-pro-LP.pdf algoritmy pro lineární programování prof. RNDr. Jiří Sgall, DrSc.
stáhnout 08-dualita-LP.mp4 dualita lineárního programování prof. RNDr. Jiří Sgall, DrSc.
stáhnout 08-dualita-LP.pdf dualita lineárního programování prof. RNDr. Jiří Sgall, DrSc.
stáhnout 09-dualita-parovani.mp4 dualita, podmínky komplementarity, párování v bipartitních grafech prof. RNDr. Jiří Sgall, DrSc.
stáhnout 09-dualita-parovani.pdf dualita, podmínky komplementarity, párování v bipartitních grafech prof. RNDr. Jiří Sgall, DrSc.
stáhnout 10-parovani-obecne-grafy.mp4 párování v obecných grafech prof. RNDr. Jiří Sgall, DrSc.
stáhnout 10-parovani-obecne-grafy.pdf párování v obecných grafech prof. RNDr. Jiří Sgall, DrSc.
stáhnout 11-totalni-unimodularita.mp4 totální unimodularita prof. RNDr. Jiří Sgall, DrSc.
stáhnout 11-totalni-unimodularita.pdf totální unimodularita prof. RNDr. Jiří Sgall, DrSc.
stáhnout 12-matroidy.mp4 matroidy a hladový algoritmus prof. RNDr. Jiří Sgall, DrSc.
stáhnout 12-matroidy.pdf matroidy a hladový algoritmus prof. RNDr. Jiří Sgall, DrSc.
stáhnout 13-celociselne-programovani.mp4 celočíselné programování, metoda řezů, mnohostěn párování, aproximační algoritmy prof. RNDr. Jiří Sgall, DrSc.
stáhnout 13-celociselne-programovani.pdf celočíselné programování, metoda řezů, mnohostěn párování, aproximační algoritmy prof. RNDr. Jiří Sgall, DrSc.
Anotace -
Poslední úprava: T_KAM (25.04.2008)
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í.
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: 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.

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
  • Záznam přednášky
Požadavky ke zkoušce -
Poslední úprava: 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.

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

 
Univerzita Karlova | Informační systém UK