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

Zde se budou nacházet informace pro studenty Optimalizačních metod (2014/2015), pondělní cvičení od 14:00 k přednáškám profesora Martina Loebla. Další cvičení vedou kolegové Martin Böhm a Radek Hušek.

Studijní materiály:

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

  • 1.hodina (bez opáčka): Zavedení základního tvaru LP, motivace proč studovat LP (existuje polynomiální algoritmus, P-úplnost, "snadné" ověření, dualita, aproximace), Zopakování triku z přednášky (vytvoření rovnosti z nerovností). Příklady.
  • 2.hodina (bez opáčka): Doplnění příkladu z přednášky (odděluji dvě množiny pomocí přímky. Bylo potřeba ošetřit případ, kdy opt řešením byla přímka kolmá na osu x), jak se zbavit ostrých nerovností v případě, že mám úlohu ve které nepotřebuji optimalizovat. Příklady na formulace LP.
  • 3.hodina (opáčko): LP formulace základního tokového problému, příklady z minula, zopakování definic, příklady a definice.
  • 4. hodina (bez opáčka): Dořešení restů z minulého cvičení. Geometrie II.
  • 5. hodina (opáčko): Příklady na Simplex. Zkuste si projít a sami zkusit základní případ simplexu (Příklad šestý). K ostatním se ještě trochu vrátíme příště a řekneme si i nějaké další tipy a triky.
  • 6. hodina (opáčko): Jak si uštřit práci při simplexové metodě a další příklady, včetně ukázky řešení prvního příkladu. Příklady na geometrii jsme na cvičení neměli, ale můžete je použít na procvičování. Tedy Simplex+řešení a geometrie. Motivace na dualitu ukázána přes horní odhady a tím neformálně dokázána slabá věta o dualitě.
  • 7. hodina (bez opáčka): 1. velká písemka.
  • Velikonoce
  • 8. hodina (bez opáčka) (P. Veselý): Ukázání příkladu na MaxCut z písemky (dvě různá řešení). Příklady na dualitu.
  • 9. hodina (opáčko) (P. Veselý): Příklady na unimodularitu.
  • 10. hodina (bez opáčka) (P. Veselý): Dualizace SATu z opáčka, Příklady na komplementaritu.
  • 11. hodina (bez opáčka): 2. velká písemka.
  • 12. hodina (bez opáčka): Podrobně popsán primárně duální algoritmus na vážené vrcholové pokrytí s důkazem 2-aproximace, Příklady na primárně duální algoritmy.
  • 13. hodina (opáčko): Podorobné řešení 2. písemky, podrobné vysvětlení primárně duálního algortmu pro nejkratší cestu z 12. cvičení, anketa.

Domácí úkoly:

První domácí úkol: Přečtěte si zadání a projděte si manuál. Hotové úkoly posílejte emailem do: 18. dubna 2015 8:00.

Druhý domácí úkol: Přečtěte si zadání a můžete si opět projít manuál. Hotové úkoly posílejte emailem do: 11. června 2015 8:00.

Požadavky na zápočet:

Podmínky na všech cvičeních budou stejné a zápočet bude potřeba ke zkoušce.

Zápočet získáte za dosažení alespoň 60 bodů. Body můžete získat těmito způsoby:

  • Aktivita na cvičení: ~2 body za předvedený příklad.
  • 5-6-krát za semestr: 10-minutové opáčko za 2 body.
  • Dvě písemky: každá za 25 bodů.
  • Dva praktické domácí úkoly: každý za 25 bodů.

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

Písemka je 90-minutový klasický test, obsahující cca 5 příkladů po 5 bodech. Bude se konat v polovině semestru a ke konci semestru -- vyhlášena bude 14 dní dopředu. Písemka také není povinná, silně však doporučujeme na písemky přijít. Pokud se nemůžete na písemku dostavit, kontaktujte mne co nejdříve předem emailem.

Domácí úkoly budou praktické a programovací. Za úkol většinou bude vyřešit daný problém pomocí lineárního programování a napsat program/skript, který zadané konkrétní řešení vyřeší a vypíše výsledek. Úkoly budou jiné než ty loňské, ale podobné. 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í.

Všimněte si, že je mnoho způsobů, jak získat 60 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