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.


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:
    • 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]

Jednotlivá cvičení:
  • 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.

Valid XHTML 1.0 Transitional