Lineární programování a kombinatorická optimalizace (NOPT048) - cvičení
Cvičení probíhá každou středu od 9:00 v učebně S8. Výuka bude do odvolání probíhat distančně přes Zoom ve středu ve 12:20.
Cvičení povede Martin Balko. E-mail cvičícího: balko (AT) kam.mff.cuni.cz
Stránky přednášky.
|
- Získání alespoň 50 bodů z celkového počtu 100 bodů.
- V průběhu semestru zadám:
- Praktický programovací domácí úkol, za který bude možné získat 30 bodů a který zadám zhruba v polovině semestru a čas na jeho vyřešení a sepsání bude zhruba měsíc.
- Čtyři teoretické domácí úkoly, celkem za 70 bodů. Čas na vyřešení a sepsání teoretických domácích úkolů bude zhruba dva týdny. V případě lepšího řešení je možné odevzdat jej znovu. Domácí úkoly můžete posílat i emailem, ale snažte se, prosím, dodržet rozumnou velikost přílohy.
- Při zisku aspoň 70 bodů bude odpuštěna písemná část u zkoušky.
- Všechny úlohy (domácí i ty řešené na cvičeních) budou dostupné zde na webu.
- Účast na cvičeních je nepovinná.
- Z důvodu ochrany osobních údajů u prvních odevzdaných řešení napište kromě jména i přezdívku, pod kterou chcete mít své body zveřejněny na webu. U dalších řešení už stačí psát buď jméno, nebo přezdívku. Pokud jste první sérii úkolů odevzdali jen pod svým jménem, bude uveřejněno na webu. Pokud Vám to nevyhovuje, napište mi email s přezdívkou a já to změním.
- Aktuální seznam bodů:
| Přezdívka: | 1. teoretický úkol | 2. teoretický úkol | 3. teoretický úkol | 4. teoretický úkol | Praktický úkol | Součet | Zápočet |
| Maxim Dokonalý | 12 | 15 | 25 | 18 | 30 | 100 | --- |
| mixal | 12 | 14 | 18 | | 26 | 70 | ANO |
| Dejf | 12 | 15 | 24 | | 25 | 76 | ANO |
| martinp9 | 12 | 15 | 24 | | 25 | 76 | ANO |
| Kapur | 11 | 15 | 25 | 18 | 8 | 77 | ANO |
| Špulka | 12 | 15 | 25 | 18 | 20 | 90 | ANO |
| Knightlon | 12 | 15 | 25 | | | 52 | ANO |
| MOMO | 12 | 15 | 24 | | 29 | 80 | ANO |
| DS | 8 | 15 | 22 | 15 | 23 | 83 | ANO |
| Wintermute | 12 | | 17 | | 29 | 58 | ANO |
| | | | | | | | |
- Zadání domácích úkolů:
- 1. teoretický domácí úkol [PDF] (zadáno 17.3.2021, termín odevzdání 1.4.2021)
- 2. teoretický domácí úkol [PDF] (zadáno 31.3.2021, termín odevzdání 14.4.2021)
- 3. teoretický domácí úkol [PDF] (zadáno 14.4.2021, termín odevzdání 28.4.2021)
- 4. teoretický domácí úkol [PDF] (zadáno 19.5.2021, termín odevzdání 2.6.2021)
- Praktický domácí úkol [PDF, ZIP] (zadáno 28.4.2021, termín odevzdání 2.6.2021)
- Seznam literatury:
- [L] Martin Loebl: Skriptíčka z lineárního programování. [link]
- [M] Jiří Matoušek: Lineární programování: Úvod pro informatiky. [PDF]
- [S] Jiří Sgall: Lineární programování a kombinatorická optimalizace. [PDF]
|
- První cvičení (3.3.2021): Úvod, podmínky zápočtu a lineární nerovnice. Cvičení proběhlo online přes Zoom. Probrány příklady 1, 2, 3.2 a 3.2. Seznam příkladů ze cvičení [PDF].
- Druhé cvičení (10.3.2021): Celočíselné programy. Cvičení proběhlo online přes Zoom. Probrány příklady 1, 2, 3 a první část 4 a dokončili jsme řešení příkladů 4 a 5 z minula. Seznam příkladů ze cvičení [PDF].
- Třetí cvičení (17.3.2021): Ostré nerovnosti a další NP-těžké úlohy a celočíselné programy. Cvičení proběhlo online přes Zoom. Probrány příklady 1, 2, 3 a dokončili jsme řešení příkladu 4 z minula. Seznam příkladů ze cvičení [PDF].
- Čtvrté cvičení (24.3.2021): Základní pojmy z geometrie. Cvičení proběhlo online přes Zoom. Probrány příklady 1, 2, 3, 4 a dokončili jsme řešení příkladů 3 a 4 z minula. Seznam příkladů ze cvičení [PDF].
- Páté cvičení (31.3.2021): Mnohostěny. Cvičení proběhlo online přes Zoom. Probrány příklady 1, 2, 3, 4 a dokončili jsme řešení příkladu 5 z minula. Seznam příkladů ze cvičení [PDF].
- Šesté cvičení (7.4.2021): Simplexová metoda. Cvičení proběhlo online přes Zoom. Probrán příklad 1 a ukázali jsme si řešení 1. teoretického úkolu. Seznam příkladů ze cvičení [PDF].
- Sedmé cvičení (14.4.2021): Simplexová metoda o něco podrobněji. Cvičení proběhlo online přes Zoom. Probrán příklad 2 a dokončili jsme řešení příkladu 3 z minula. Seznam příkladů ze cvičení [PDF].
- Osmé cvičení (21.4.2021): Cvičení proběhlo online přes Zoom formou konzultace. Dokončili jsme řešení příkladu 1 z minula a příkladu 1 z předminula a ukázali jsme si řešení 2. teoretického úkolu.
- Deváté cvičení (28.4.2021): Dualita. Cvičení proběhlo online přes Zoom. Probrány příklady 1, 2 a 3 a bylo vysvětlené zadání praktického úkolu. Seznam příkladů ze cvičení [PDF].
- Desáté cvičení (5.5.2021): Dualita a její aplikace. Cvičení proběhlo online přes Zoom. Probrány příklady 1, první část 2 a 3a a ukázali jsme si řešení příkladu 4 z minula a 3. teoretického úkolu. Seznam příkladů ze cvičení [PDF].
- Jedenácté cvičení (12.5.2021): Cvičení se nekoná (rektorské volno).
- Dvanácté cvičení (19.5.2021): Komplementarita. Cvičení proběhlo online přes Zoom. Probrány příklady 1 a 3 a ukázali jsme si řešení příkladů 2 a 3b z minula. Seznam příkladů ze cvičení [PDF].
- Třinácté cvičení (26.5.2021): Totální komplementarita. Cvičení proběhlo online přes Zoom. Probrány příklady 1, 2 a 3 a ukázali jsme si řešení příkladu 2 z minula. Seznam příkladů ze cvičení [PDF].
- Čtrnácté cvičení (2.6.2021): Cvičení proběhlo online přes Zoom. Probrány příklady 4 a 5 z minula a ukázali jsme si řešení 4. teoretického úkolu a praktického úkolu.
|
|