Lineární programování a kombinatorická optimalizace (NOPT048) - cvičení
Cvičení probíhá každé pondělí od 14:00 v učebně S6.
Cvičení povede Martin Balko. E-mail cvičícího: balko (AT) kam.mff.cuni.cz
Stránky přednášejícího.
Podmínky získání zápočtu:
- Získání alespoň 50 bodů z celkového počtu 100 bodů.
- V průběhu semestru zadám:
- Dvě 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. Domací úlohy prosím nahrávejte na Sovičku.
- Všechny příklady z cvičení i domací úkoly budou na Sovičce. Při zápisu na kurz použijte token 4c2eb97666d6. Všechny úlohy (domácí i ty řešené na cvičeních) budou dostupné i zde na webu.
- Účast na cvičeních je nepovinná, nicméně doporučovaná z povahy podmínek získání zápočtu.
- Zadání domácích úkolů:
- 1. teoretický domácí úkol [PDF] (zadáno 11.3.2024, termín odevzdání 25.3.2024)
- 2. teoretický domácí úkol [PDF] (zadáno 8.4.2024, termín odevzdání 29.4.2024)
- 3. teoretický domácí úkol [PDF] (zadáno 20.5.2024, termín odevzdání 30.6.2024)
- Praktický domácí úkol [PDF, ZIP] (zadáno 29.4.2024, termín odevzdání
20.5.202430.6.2024 (s menší bodovou penalizací))- Seznam literatury:
Jednotlivá cvičení:
- První cvičení (26.2.2024): Ú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í (4.3.2024): Celočíselné lineární programy. Probrán příklad 5 z minula a příklady 1, 2, 3, 4 a 5. Seznam příkladů ze cvičení [PDF].
- Třetí cvičení (11.3.2024): Ostré nerovnosti a další NP-těžké úlohy a celočíselné programy. Probrány příklady 1, 2, 3 a 4 a náčrt 1c. Seznam příkladů ze cvičení [PDF].
- Čtvrté cvičení (18.3.2024): Základní pojmy z geometrie. Probrány příklady 2, 3, 4 a 5 a první čast 1. Seznam příkladů ze cvičení [PDF].
- Páté cvičení (25.3.2024): Mnohostěny. Ukázali jsme si řešení 1. teoretického domácího úkolu. Probrány příklady 1, 2, 4 a část 3. Seznam příkladů ze cvičení [PDF].
- Šesté cvičení (8.4.2024): Simplexová metoda. Probrány příklady 1, 2 a 3. Seznam příkladů ze cvičení [PDF].
- Sedmé cvičení (15.4.2024): Simplexová metoda podrobněji. Probrány příklady 1 a 2. Seznam příkladů ze cvičení [PDF].
- Osmé cvičení (22.4.2024): Psali jsme první písemku.
- Deváté cvičení (29.4.2024): Dualita. Ukázali jsme si řešení 1. písemky a byl zadán praktický domácí úkol. Probrány příklady 1, 2, 3a a 4. Seznam příkladů ze cvičení [PDF].
- Desáté cvičení (6.5.2024): Dualita a její plaikace a komplementarita. Ukázali jsme si řešení 2. teoretického domácího úkolu. Probrány příklady 1, 4 a část 2 a 3. Seznam příkladů ze cvičení [PDF].
- Jedenácté cvičení (13.5.2024): Psali jsme druhou písemku.
- Dvanácté cvičení (20.5.2024): Totální unimodularita. Ukázali jsme si řešení 2. písemky. Probrány příklady 1, 2 a 3. Seznam příkladů ze cvičení [PDF].