Lineární programování a kombinatorická optimalizace (NOPT048) - cvičení

---

Hlavní stránka

Cvičení probíhá každý čtvrtek od 15:40 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.

Podmínky získání zápočtu:	nahoru

• 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	---
Thalion	11	15	25	18	8	77	ANO
Nina	12	15	25		20	72	ANO
TS	12	15	25	14	11	77	ANO
Yongaron	12	15	23		24	74	ANO
Erúvin	9	5	20	14		48
bug	11	15	25	18	17	86	ANO
Alexandr Kafka	9	15	25	12	20	81	ANO
TescoLife	12		22	6	16	56	ANO
JV	12	15	25	18		70	ANO
Jakoma02	12	15	25	18	20	90	ANO
Evžen	12	15	19	18	17	81	ANO
Enigma	12	15	21	12	10	70	ANO
Ada			23	12	16	51	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]

Jednotlivá cvičení:	nahoru

• 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.