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


Cvičení probíhá každé úterý od 15:40 v učebně S6.

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:
    • Dvě velké písemky na celé cvičení (90 minut). Z každé písemky bude možné získat 25 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.
    • Opáčka a dva teoretické domácí úkoly, celkem za 20 bodů. Opáčko bude krátká písemka zadaná na začátku cvičení, hlášená aspoň týden předem. Č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:  Opáčko 1   Opáčko 2   Opáčko 3   Teoretický úkol 1   Teoretický úkol 2   Praktický úkol   1. písemka   2. písemka   Součet   Zápočet 
 Maxim Dokonalý  3 3 3 4 7 30 25 25 100 ---
 Kopretinka123  2.5 3 4 7 10 25 51.5 ANO
 Ryba  2.5 3 3 2 7 18 16 51.5 ANO
 Semo  2.5 3 3 4 7 24.5 21 65 ANO
 Flower2733  2 3 3 4 7 25 22 66 ANO
 Zatencas  1.5 1 2.5 3 10 22.5 16 56.5 ANO
 SS  3 3 3 4 2 10 20 6 51 ANO
 Apollo  3 3 3 4 24 24 61 ANO
 Sova  3 3 3 4 2 13 24 24 76 ANO
 opar  1.5 3 16 20.5
 TZ  3 3 3 3 4 18 18 52 ANO
 Whoamihf  3 3 2 4 7 23.5 24 66.5 ANO
 dotaz  2 2
 Martin  3 3 4 2 17 21 13 63 ANO
 Lopata  0 3 3 5 11
 Speedy  3 3 2 4 7 24 25 68 ANO
 Bankai  3 3 3 4 24 24 61 ANO
 Náměstí Míru  2.5 3 3 4 8 21 25 66.5 ANO
 Fíla  3 3 3 4 27 24.5 64.5 ANO
 Zuzka  3 3 3 4 7 27 25 24 96 ANO
 Adél  3 3 3 4 24.5 25 62.5 ANO
 AP  2.5 3 2 4 7 8 24.5 51 ANO
 FM  2 3 4 14 19.5 8 50.5 ANO
 Ž  1 3 3 4 8 25 18 62 ANO
 MM  3 4 24 23 54 ANO
  
  • Zadání domácích úkolů:
    • 1. teoretický domácí úkol [PDF] (zadáno 6.4.2020, termín odevzdání 21.4.2020)
    • Praktický domácí úkol [PDF] (zadáno 21.4.2020, termín odevzdání 19.5.2020)
    • 2. teoretický domácí úkol [PDF] (zadáno 5.5.2020, termín odevzdání 19.5.2020)
  • 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í (18.2.2020): Úvod, podmínky zápočtu a lineární nerovnice. Probrány příklady 1, 2, 3 a 5. Seznam příkladů ze cvičení [PDF].
  • Druhé cvičení (25.2.2020): Celočíselné programy. Probrány příklady 1, 2, 3, 4 a první část příkladu 5. Seznam příkladů ze cvičení [PDF].
  • Třetí cvičení (3.3.2020): Ostré nerovnosti a další NP-těžké úlohy a celočíselné programy. Psali jsme první opáčko, probrány příklady 1, 2, 3, 4 a nastíněn příklad 5. Seznam příkladů ze cvičení [PDF].
  • Čtvrté cvičení (10.3.2020): Základní pojmy z geometrie. Probrány příklady 2, 5 a téměř celá 1 a ukázali jsme si řešení opáčka. Seznam příkladů ze cvičení [PDF].
  • Páté cvičení (17.3.2020): Mnohostěny. Cvičení probíhá formou samostudia. Seznam příkladů ze cvičení [PDF].
  • Šesté cvičení (24.3.2020): Simplexová metoda. Cvičení proběhlo online přes Zoom. Bylo zadané druhé opáčko s jedním týdnem na řešení a nelze odevzdávat opakovaně. Seznam příkladů ze cvičení [PDF].
  • Sedmé cvičení (31.3.2020): Byla zadána první písemka formou domácího úkolu s jedním týdnem na řešení a nelze odevzdávat opakovaně. Proběhla online konzultace přes Zoom.
  • Osmé cvičení (7.4.2020): Simplexová metoda o něco podrobněji. Cvičení proběhlo online přes Zoom. Byl zadaný 1. teoretický domácí úkol [PDF] a ukázali jsme si řešení první písemky. Seznam příkladů ze cvičení [PDF].
  • Deváté cvičení (14.4.2020): Dualita. Cvičení proběhlo online přes Zoom. Ukázali jsme si řešení příkladů z osmého cvičení. Seznam příkladů ze cvičení [PDF].
  • Desáté cvičení (21.4.2020): Dualita a její aplikace. Cvičení proběhlo online přes Zoom. Ukázali jsme si řešení 1. teoretického domácího úkolu a příkladů z devátého cvičení. Byl zadaný praktický domácí úkol. Seznam příkladů ze cvičení [PDF].
  • Jedenácté cvičení (28.4.2020): Komplementarita. Cvičení proběhlo online přes Zoom. Ukázali jsme si řešení příkladů z desátého cvičení a bylo zadané třetí opáčko formou domácího úkolu. Seznam příkladů ze cvičení [PDF].
  • Dvanácté cvičení (5.5.2020): Totální unimodularita. Cvičení proběhlo online přes Zoom. Ukázali jsme si řešení příkladů z jedenáctého cvičení a třetího opáčka. Byl zadaný 2. teoretický úkol [PDF]. Seznam příkladů ze cvičení [PDF].
  • Třinácté cvičení (12.5.2020): Byla zadána druhá písemka formou domácího úkolu s jedním týdnem na řešení a nelze odevzdávat opakovaně. Cvičení proběhlo online přes Zoom. Ukázali jsme si řešení příkladů z dvanáctého cvičení.
  • Čtrnácté cvičení (19.5.2020): Cvičení proběhlo online přes Zoom. Ukázali jsme si řešení druhé písemky, 2. teoretického úkolu a praktického úkolu.

Valid XHTML 1.0 Transitional