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:

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.

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.


Profile for TarkenCZE-Maso sDn