Lineární programování a kombinatorická optimalizace (NOPT048) - cvičení
|
- Získání alespoň 50 bodů z celkového počtu 100 bodů.
- V průběhu semestru zadám:
- Dvě velké písemky na celé cvičení (90 minut). Z každé písemky bude možné získat 15 bodů. První písemka bude zhruba v polovině semestru, druhá na konci. Termíny později upřesní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.
- Tři teoretické domácí úkoly, celkem za 40 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.
- 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: | Teoretický úkol 1 | Teoretický úkol 2 | Teoretický úkol 3 | Praktický úkol | 1. písemka | 2. písemka | Součet | Zápočet |
| Maxim Dokonalý | 12 | 15 | 13 | 30 | 15 | 15 | 100 | --- |
| tury | 12 | 10 | 8 | | 12 | 12 | 54 | ANO |
| hyperkrychle | 12 | 15 | 13 | | 13 | | 53 | ANO |
| Kyberšurt | 12 | 9 | 8 | | 12 | 10 | 51 | ANO |
| Kinaj | 12 | 11 | 8 | 12 | 7 | | 50 | ANO |
| NejsemTonda | 9 | 14 | | 25 | 8 | 5 | 61 | ANO |
| Xay | 12 | 15 | 3 | | 10 | 10 | 50 | ANO |
| unidentified V | 12 | 15 | | | | | 27 | |
| | | | | | | | | |
- Zadání domácích úkolů:
- 1. teoretický domácí úkol [PDF] (zadáno 1.3.2022, termín odevzdání 15.3.2022)
- 2. teoretický domácí úkol [PDF] (zadáno 12.4.2022, termín odevzdání 26.4.2022)
- 3. teoretický domácí úkol [PDF] (zadáno 17.5.2022, termín odevzdání 30.6.2022)
- Praktický domácí úkol [PDF, ZIP] (zadáno 19.4.2022, termín odevzdání
17.5.2022 30.6.2022 (s menší bodovou penalizací))
- 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í (15.2.2022): Úvod, podmínky zápočtu a lineární nerovnice. Probrány příklady 1, 2, 3 a část 5. Seznam příkladů ze cvičení [PDF].
- Druhé cvičení (22.2.2022): Celočíselné programy. Probrány příklady 1, 2, 3 a 4 a dokončili jsme řešení příkladů 3 a 5 z minula. Seznam příkladů ze cvičení [PDF].
- Třetí cvičení (1.3.2021): Ostré nerovnosti a další NP-těžké úlohy a celočíselné programy. Probrány příklady 1, 2, 3 a 4. Seznam příkladů ze cvičení [PDF].
- Čtvrté cvičení (8.3.2022): Cvičení se nekonalo.
- Páté cvičení (15.3.2022): Základní pojmy z geometrie. Probrány příklady 1 (první část), 2, 3 a 4 a ukázali jsme si řešení 1. teoretického domácího úkolu. Seznam příkladů ze cvičení [PDF].
- Šesté cvičení (22.3.2022): Mnohostěny. Probrány příklady 1, 2, 3a a 4. Seznam příkladů ze cvičení [PDF].
- Sedmé cvičení (29.3.2022): Simplexová metoda. Probrány příklady 1, 2 a 3. Seznam příkladů ze cvičení [PDF].
- Osmé cvičení (5.4.2022): Psali jsme první písemku.
- Deváté cvičení (12.4.2022): Simplexová metoda podrobněji. Ukázali jsme si řešení první písemky a probrány příklady 1 a 3. Seznam příkladů ze cvičení [PDF].
- Desáté cvičení (19.4.2022): Dualita. Probrány příklady 1, 2, 3 a 4 a bylo vysvětlené zadání praktického úkolu. Seznam příkladů ze cvičení [PDF].
- Jedenácté cvičení (26.4.2022): Dualita a její aplikace. Probrány příklady 1, 2 (částečně) a 3 a ukázali jsme si řešení 2. teoretického domácího úkolu. Seznam příkladů ze cvičení [PDF].
- Dvanácté cvičení (3.5.2022): Psali jsme druhou písemku.
- Třinácté cvičení (10.5.2022): Komplementarita. Ukázali jsme si řešení druhé písemky a probrány příklady 1 a 2. Seznam příkladů ze cvičení [PDF].
- Čtrnácté cvičení (17.5.2022): Totální unimodularita. Probrány příklady 1, 2, 3 a 4 a nastínili jsme řešení praktického domácího úkolu. Seznam příkladů ze cvičení [PDF].
|
|