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

Cvičení probíhá každou středu od 12:20 v učebně S6. 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 ---
 JŠ  12 15 24 16 10 77 ANO
 rudvav  12 12
 brot  12 15 25 30 82 ANO
 KŠ  12 15 25 18 70 ANO
 Metyk  12 15 25 12 18 82 ANO
 Eldar  12 15 25 20 72 ANO
 50713  12 15 25 52 ANO
 Bruce Wayne  12 15 25 72 ANO
 samo  12 15 24 20 71 ANO
 Parzival  12 15 25 52 ANO
 JT  8 7 24 39
 JA  12 14 19 12 57 ANO
 JK  12 15 23 18 10 78 ANO
 Venca  12 15 25 18 70 ANO
 Alešek  10 14 25 6 55 ANO
 Alex  12 13 17 12 17 71 ANO
 riadok  6 15 23 18 23 85 ANO
 MaF  11 10 15 17 53 ANO
 Harry Potter  11 10 25 6 52 ANO
 czecha  12 15 25 18 70 ANO
 12345  11 14 20 6 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í:
  • 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