Cvičení z Optimalizačních metod.

Zde se budou nacházet informace pro studenty Optimalizačních metod (2015/2016), úterní cvičení od 14:00 k přednáškám profesora Jiřího Sgalla. Další cvičení vedou kolegové Pavel Veselý a Radek Hušek.

Studijní materiály:

Studijní materiály v angličtině:
Linear programming, A Concise Introduction (Thomas S. Ferguson). A writeup of a lecture with a similar linear programming content, but missing other combinatorial optimization topics.
Combinatorial Optimization: Polyhedra and Efficiency (Alexander Schrijver). A series of three textbooks containing almost everything one needs to know from combinatorial optimization. A bit dense in some places, but it is readable.
Introduction to Discrete Geometry and Lectures on Discrete Geometry (Jiří Matoušek). The first link are lecture notes from a discrete geometry class, available for borrowing at the Faculty of Math and Physics library. The second book is a normal book on the same subject. You do not need to read the whole book; the essential parts are the lectures on convexity and on convex polytopes.
Studijní materiály v češtině:
Lineární programování pro informatiky (Jiří Matoušek, 2006) --- dostupné v knihovně MFF UK (jako Lineární programování a lineární algebra pro informatiky) a také na webu!
Literatura od prof. Sgalla z předpředchozího roku.
Cvičení z let minulých:
Moje loňské cvičení z LS 2014/2015,
cvičení Martina Böhma z LS 2013/2014,
cvičení Marka Eliáše z LS 2013/2014,
cvičení Dušana Knopa z LS 2012,
cvičení Dušana Knopa z LS 2011,
cvičení Marka Eliáše z LS 2012,
cviceni Vojty Tůmy z LS 2012.
cvičení Marka Krčála z LS 2010/2011 a z LS 2009/2010.

Co se dělo na cvičeních:

1.hodina: Podmínky na zápočet. Afinní prostory, aneb opakování lingebry: Definice + příklady. Stihli jsme pouze příklady 1--3, kde zbytek trojky a 4 krátce ukážu na začátku příští hodiny. Zbytek geometrie budeme řešit pravděpodobně třetí hodinu.
2.hodina: Ukázání řešení příkladu 3--6 z prvního cvičení. Příklady na formulace LP, stihli jsme příklady 1--5. Součástí cvičení je také zadání dvou domácích úkolů.
3.hodina (Opáčko 1): Formulace celočíselných problémů a jejich relaxace, konstrukce 2-approximace. Příklady 1--4. Dále pro příklad 4 v nevážené variantě důkaz, že pro bipartitní graf platí, že existuje-li dosažitelné řešení, potom existuje celočíselné řešení stejné hodnoty účelové funkce.
4.hodina: Ukázáno řešení příkladu 5 z minulého cvičení, řešení pomocí dvou esenciálně různých LP, kde triviální z nich má exponenciálně podmínek a ten druhý pouze lineárně, při zachování lineárního počtu proměnných. Příklady na Konvexitu a afinitu, stihli jsme příklady 1--4, zbytek příště.
5.hodina (Opáčko 2): Příklady na geometrii polytopů, stihli jsme příklady 1--4 (včetně příkladů z minulého cvičení).
6.hodina: Ukázáno řešení Opáčka 1 a Opáčka 2 a příkladu 2 z minulého cvičení. Dále formulace problému nejkratší cesty a pár slov o celočíselnosti optimálního řešení a různých formulacích. Příklady na počítání: určování vrcholů mnohostěnu a určování polohy nadroviny vůči polytopu zadaném body. Důkaz věty: Obsahuje-li mnohostěn vrhol, potom vrchol obsahuje i každá jeho vlastní neprázdná stěna (použití indukce dle dimenze a věty o fasetách z přednášky).
7.hodina (R. Hušek): Příklady na simplex, stihly se všechny příklady.
8.hodina (R.Hušek): Další příklady na simplex, stihly se příklady 1--3.
9.hodina (Opáčko 3): Příklady na dualitu, stihly se všechny příklady kromě 4.
10.hodina: Příklady na unimodularitu, stihly se všechny příklady.
11.hodina (Opáčko 4): Příklady na komplementaritu, ukázání konkrétního příkladu (problém batohu) na metodu řezů.
12.hodina: Velká písemka
13.hodina: Příklady na primárně duální algoritmy, stihly se všechny příklady, kromě posledního.
14.hodina (Opáčko 5): Ukázání 8. domácího úkolu. Řešení posledního příkladu z minulého cvičení. Zmíněna metoda řezů pro TSP a aproximační algoritmus pomocí min kostry pro TSP.

Domácí úkoly:

Teoretické domácí úkoly:

Úkol 1 a 2, deadline je 15. března, 14:00.
Úkol 3 a 4, deadline je 22. března, 14:00.
Úkol 5, deadline je 29. března, 14:00.
Úkol 6, deadline je 19. dubna, 14:00.
Úkol 7, deadline je 10. května, 14:00.
Úkol 8, deadline je 17. května, 14:00.
Úkol 9, deadline je 31. května, 14:00.

Praktické domácí úkoly:

Nejprve si projděte manuál. Hotové úkoly posílejte emailem.

Praktický úkol 1 a obecné povídání, deadline je 9. dubna 8:00.
Praktický úkol 2, deadline je 16. května 10:00.
Praktický úkol 3, deadline je 27. června 10:00.

Požadavky na zápočet:

Všechna česká cvičení mají stejné podmínky na zápočet a ten bude vyžadován k přihlášení na zkoušku.

Zápočet získáte za dosažení alespoň 55 bodů, pokud získáte 75 bodů budete mít snažší průběh zkoušky u prof. Sgalla. Body můžete získat těmito způsoby:

aktivita na cvičení: ~2 body za kompletně předvedený příklad,
5-krát za semestr: 15-minutové opáčko à 4 body,
jedna velká písemka za 30 bodů,
asi tři praktické domácí úkoly dohromady za 30 bodů,
teoretické domácí úkoly celkem za 20 bodů.

Opáčko je opakování látky z posledních dvou cvičení a přednášek formou minipísemky s jedním či dvěma příklady. Bude probíhat 5-krát za semestr, vždycky prvních 15 minut cvičení. Opáčka jsou dobrovolná a nejsou přepadová; tj. týden dopředu vyvěsíme na web, jestli se příští cvičení bude konat.

Písemka je 90-minutový klasický test. Bude se konat ke konci semestru --- vyhlášena bude 14 dní dopředu. Písemka také není povinná, silně však doporučujeme na ni přijít. Pokud se nebudete moci na písemku dostavit, kontaktujte mne co nejdříve předem emailem.

Praktické domácí úkoly budou programovací. Za úkol bude vyřešit daný problém pomocí lineárního programování --- tedy napsat program/skript, který zadanou úlohu vyřeší a vypíše výsledek. Úkoly budou jiné než ty loňské, ale obdobné. Na domácí úkoly bude vždy alespoň měsíc času. Rád bych vás ještě upozornil, abyste se vyvarovali plagiátorství.

Teoretické domácí úkoly budou zadávány průběžně, většinou formou drobnějších příkladů po cca 2 bodech. Na jejich řešení můžete spolupracovat, důležité ale je, abyste řešení důkladně rozumněli a sami ho sepsali. Na teoretické úkoly bude více než týden času, přesněji do začátku obdalšího cvičení.

Obecně: Všechny kroky se snažte pečlivě zdůvodňovat, je to důležitější než mít správný výsledek. Naopak můžete používat cokoli z přednášek či cvičení bez důkazu, jen vždy uveďte, co právě využíváte. Ještě bych rád upozornil, že bodové hodnocení jednotlivých příkladů nemusí vždy nutně odpovídat jejich obtížnosti. Všimněte si, že je mnoho způsobů, jak získat 55 bodů; vyberte si tu cestu, která vám vyhovuje nejvíce.

Vaše průběžné výsledky budeme zveřejňovat na webu. Pokud chcete, můžete si místo jména zvolit přezdívku --- buď na prvních cvičeních, nebo emailem.

Výsledky a nárok na zápočet:

Dosavadní výsledky v google dokumentu.

masarik<a>mimuw.edu.pl

CENT building room 03.111, MIMUW, Banacha 2, Warsaw, 02-097, Poland
Room 1650, MIMUW, Banacha 2, Warsaw, 02-097, Poland
Room 8514, Department of Mathematics, Simon Fraser university, 8888 University Drive, Burnaby, V5A 1S6, Canada
Room 320, KAM MFF, Malostranské náměstí 25, Praha 1, 11800, Czech Republic