LS 2010, Jiří
Sgall, pondělí 9:00, S5
Kontakt a konzultace
Konzultace nejlépe po předběžné domluvě mailem. Nejčastěji mě
zastihnete v pondělí 11-12 a 14-15 a v úterý 11-12 a 13-14.
E-mail: last name at
kam.mff.cuni.cz
Telefon: 221 914 293
http://kam.mff.cuni.cz/~sgall/
Pracovna: 3. patro,
místnost
326, Malostranské nám. 25
Cvičení
a formulář pro odevzdání domácích úkolů
Zkoušky
Termíny
Další opravné termíny budou spíše po individuální dohodě, buď v první polovině července nebo v září.
Řádné termíny jsou úterý 25. 5. (i odpoledne od 14 hod), úterý 1.
6., středa 2. 6.,
strředa 9. 6., úterý 15. 6., pátek 18. 6. (bude otevřen podle potřeby),
úterý 22. 6. a úterý 29. 6.
Všechny termíny jsou vypsány v posluchárně S1 od 9 hodin. Můžete ale
přijít kdykoliv během dopoledne, tím si můžete i ušetřit čekání.
Před složením zkoušky je nutné získat zápočet. Abych umožnil plánování
zkoušek s předstihem, není to formální podmínka v SIS. Ale před
samotnou zkouškou musíte mít zápočet zapsaný aspoň v SIS, případně
dostatečný počet bodů od cvičících a žádné nedořešené problémy. Pokud
Váš zápočet závisí na dodatečných příkladech, musíte se domluvit s
cvičícími, aby je včas opravili.
Když se přihlásíte na některý termín, tak jej
využijte nebo se včas omluvte či odhlašte. Propadlým termínem ztracíte
svůj pokus, navíc případně
propadlý termin mohl využít některý z vašich spolužáků. Naplánujte si
první termín tak, abyste měli čas na případný opravný termín.
Průběh zkoušky
Součastí zkoušky jsou příklady (napsat duální program, napsat
lineární program pro daný problém, spočítat vrchol mnohostěnu apod.).
Tato část zkoušky je prominuta studentům, kteří získali z úkolů alespoň
50 bodů.
Hlavní částí zkoušky je ústní zkouška z probírané teorie. Po zadání
otázek budete mít čas na přípravu. Studijní materiály (skripta,
učebnice a zápisky z přednášek)
ani notebooky, kalkulačky, PDA, atd., nejsou u zkoušky dovoleny.
Společenský oblek není nutný.
Literatura a další pomůcky
- Poznámky k přednáškám
- Knihy a skripta:
- skripta J. Matouška Lineární programování a lineární
algebra pro informatiky,
vyšla
v ITI Series
2006-311 a jsou k zapůjčení v informatické
knihovně MFF UK
- skripta J. Matouška Introduction to Discrete Geometry
vyšla
v ITI Series
2003-150 a jsou k zapůjčení v informatické
knihovně MFF UK
- William J.
Cook, William H. Cunningham, William R. Pulleyblank, and Alexander
Schrijver: Combinatorial Optimization
- Laurence A. Wolsey and George L. Nemhauser: Integer and
Combinatorial
Optimization
- Laurence A. Wolsey: Integer Programming
- Howard Karloff: Linear Programming
- Zdroje na internetu:
Probraná témata - aktuální
- 22. 2.
- úloha lineárního programování
- převedení rovnic na nerovnice
- příklad: hledání nejkratší cesty
- 1. 3.
- úloha celočíselného programování
- příklady: vrcholové pokrytí, nezávislá množina
- příklad: perfektní párování maximální váhy, optimum LP relaxace
je rovno celočíselnému optimu
- opakování: afinní prostory, obal, kombinace, nezávislost
- definice: dimenze, konvexní množina, konvexní obal, konvexní
kombinace
- konvexní obal X je množina všech konvexních kombinací bodů z X
- definice: nadrovina, poloprostor
- definice: konvexní mnohostěn jako průnik poloprostorů
- terminologie: omezený konvexní mnohostěn
- věta Minkowski-Weyl znění
- 8. 3.
- věta o oddělování konvexních množin nadrovinou
- věta (Caratheodory): bod konvexního obalu X je konvexní
kombinací kombinací nejvýše d+1 bodů z X, kde d je dimenze X
- věta Minkowski-Weyl: X je omezený mnohostěn právě když X je
konvexní obal konečné množiny bodů
- 15. 3.
- definice: stěna mnohostěnu, vrchol, faseta
- věta: omezený mnohostěn je konvexní obal vrcholů, vrcholy jsou
právě extremální body
- věta: stěna stěny je stěna
- minimální popis mnohostěnu
- věta: dimenze polytopu je dána hodností systému rovnic v
minimálním popisu
- věta: v minimálním popisu polytopu nerovnosti vzájemně
jednoznačně odpovídají fasetám
- stěna jako průnik faset
- svaz stěn mnohostěnu
- 22. 3.
- dualita pro různé tvary LP, rovnicový tvar apod.
- Farkasovo lemma pro nerovnice pomocí Fourier-Motzkinovy
eliminace
- Farkasovo lemma pro rovnice
- věta o odvozování libovolné platné nerovnosti, která je
důsledkem soustavy nerovností
- 29. 3.
- dokončení důkazu duality LP
- simplexová metoda
- příklad
- pivotovací krok obecně
- ukončení (optimum, neomezenost)
- nalezení počátečního řešení dvoufázovou metodou
- 12. 4.
- simplexová metoda
- degenerovanost
- pivotovací pravidla
- efektivnost, zacyklení
- totálně unimodulární matice
- definice, důsledky pro LP
- totálně unimodulární matice se dvěma nenulovými prvky ve
sloupci
- příklady: incidenční matice orientovaných grafů, incidenční
matice neorientovaných bipartitních grafů
- použití duality a totální unimodularity
- Königova věta: v bipartitním grafu je velikost
maximálního párování rovna velikosti minimálního vrcholového pokrytí
- 19. 4.
- toky v sítích pomocí duality a totální unimodularity
- perfektní párování minimální ceny v bipartitním grafu
pomocí primárně duálního algoritmu
- 26. 4.
- párování v obecných grafech
- párování maximální velikosti
- perfektní párování minimální ceny (Edmonsův
kvítkový/blossom algoritmus)
- 3. 5.
- polytop párování, jeho vlastnosti, vrcholy, fasety
- elipsoidová metoda, separační orákulum
- 10. 5.
- metoda řezů (sečných nadrovin, cutting plane methods)
- věta o univerzalitě: lze odvodit každou nerovnost
platnou pro všechna celočíselná řešení
- přehled metod celočíselného programování
- 17. 5.
- aproximační algoritmy
- 2-aproximační algoritmus pro vrcholové pokrytí
- matroidy
- definice, charakterizace množiny bází
- příklady: vektorové prostory, lesy
- hladový algoritmus
- polytop matroidu, jeho celočíselnost
- průnik matroidů - jen formulace