Tohle je stránka cvičení z Optimalizačních metod 2014/2015, na které budu chodit já a snad i vy. Koná se v úterý od 15:40 v S7. For English students: My exercise session in English has a webpage here.
Studijní materiály
- 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 nově také na webu!
- Literatura od prof. Sgalla z předchozího roku.
- Cvičení z let minulých:
- moje cvičení 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.
Studijní materiály v angličtině
- Understanding and Using Linear Programming (Jiří Matoušek, Bernd Gärtner). An introductory book to Linear Programming for computer scientists which covers a large part of the lecture. Very accessible and readable. Contains applications, but no exercises.
- 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.
Obsah cvičení
- 1. cvičení (bez opáčka): opakování lineární algebry, algoritmů, kombinatoriky.
- 2. cvičení (bez opáčka): trénink formulování lineárních programů.
- 3. cvičení (opáčko): konvexita a afinita.
- 4. cvičení (bez opáčka): mnohostěny, jejich vrcholy a stěny.
- 14. března: První úkol je zadán! Přečtěte si zadání, projděte si tutoriál, vyřešte úkol, pošlete email. Termín: 18. 4. 2015 08:00.
- 5. cvičení (opáčko): Simplexový algoritmus.
- 6. cvičení (opáčko): Pokračování simplexu, trocha mnohostěnové geometrie. Byl jsem pryč, ochotně zaskočil Radek Hušek.
- 31.3.: První písemka.
- 7. cvičení (bez opáčka): Dualita.
- 8. cvičení (opáčko): Plán: totální unimodularita.
- 9. cvičení (bez opáčka): Komplementarita.
- 10. cvičení (bez opáčka): Primárně-duální algoritmy.
- 5.5.: Druhá písemka pokrývající látku z cvičení 1-10.
- 10. května: Druhý úkol je zadán! Přečtěte si zadání, vyřešte úkol, pošlete email. Termín: 11. 6. 2015, 08:00. Doporučuji vyřešit dříve, ať se můžete zapsat na zkoušku s klidem.
- 11. cvičení bylo o přípravě na zkoušku. Hodně štěstí!
- 12. cvičení nebude, výuka 19.5. odpadá.
Konzultace
Pokud vám něco z látky není jasné, pokud máte otázky k nějakému příkladu, pokud si chcete popovídat s cvičícím, budu moc rád, pokud se zastavíte na konzultacích. Nově jsem vypsal pevné konzultační sloty; pokud chcete přijít na konzultaci, vyplňte svou přezdívku do některého volného slotu. Konzultace jsou hodinové, s limitem 3 studenti na jednu hodinu zároveň. Zapište se, kam se vám to hodí. Kdyby došly sloty, vypíšu další (a další pak budou v příštích týdnech).
Pokud se zapisete na termin, setkame se pred kabinetem doktorandu S320 ve 3. patre na Malostranskem namesti, vedle S3.
Zapisujte se tady, níže je tabulka (pro čtení) s aktuálně zapsanými:
Zápočet
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.
Všimněte si, že je mnoho způsobů, jak získat 60 bodů; vyberte si tu cestu, která vám vyhovuje nejvíce. Všechna cvičení mají stejné podmínky na zápočet.
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.
FAQ
Q: Jsou obě Tvá cvičení záměnná?
A: Vzhledem k tomu, že jedno bude česky a jedno anglicky, tak asi nebudou, čili neslibuji, že ta samá látka bude na obou cvičení ve stejný týden.
Q: Můžu chodit pouze na anglické cvičení místo českého?
A: Určitě! Budu víc než rád.
Q: Jak hodnotíš opisování?
A: Velmi přísně. Spolupráci např. na přípravě na písemku mám moc rád, ale samotnou plagiarizaci netoleruji. Pokud už píšete řešení, které jste vymysleli se spolužákem, pište ho svými slovy bez čtení spolužákova textu. Dejte si pozor také na to, abyste svá řešení neposílali spolužákům -- oni jej mohou opsat a problémy budete mít oba.
O opisování se tu rozepisuji proto, protože jsme to museli loni řešit a nebylo mi to moc příjemné.
Q: Optimalizace mi moc nejde a na cviceni se nechytam. Co ted?
A: Přijďte na konzultaci! Napište email a můžeme si domluvit čas. Pokud máte kratší dotaz, stači ho napsat v emailu a pořešíme ho elektronickou cestou.