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áš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ě velké 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. 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:  Teoretický úkol 1   Teoretický úkol 2   Teoretický úkol 3   Praktický úkol   1. písemka   2. písemka   Součet   Zápočet 
 Maxim Dokonalý  12 15 13 30 15 15 100 ---
 tury  12 10 8 12 12 54 ANO
 hyperkrychle  12 15 13 13 53 ANO
 Kyberšurt  12 9 8 12 10 51 ANO
 Kinaj  12 11 8 12 7 50 ANO
 NejsemTonda  9 14 25 8 5 61 ANO
 Xay  12 15 3 10 10 50 ANO
 unidentified V  12 15 27
  
  • Zadání domácích úkolů:
    • 1. teoretický domácí úkol [PDF] (zadáno 1.3.2022, termín odevzdání 15.3.2022)
    • 2. teoretický domácí úkol [PDF] (zadáno 12.4.2022, termín odevzdání 26.4.2022)
    • 3. teoretický domácí úkol [PDF] (zadáno 17.5.2022, termín odevzdání 30.6.2022)
    • Praktický domácí úkol [PDF, ZIP] (zadáno 19.4.2022, termín odevzdání 17.5.2022 30.6.2022 (s menší bodovou penalizací))
  • 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í (15.2.2022): Ú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í (22.2.2022): Celočíselné programy. Probrány příklady 1, 2, 3 a 4 a dokončili jsme řešení příkladů 3 a 5 z minula. Seznam příkladů ze cvičení [PDF].
  • Třetí cvičení (1.3.2021): Ostré nerovnosti a další NP-těžké úlohy a celočíselné programy. Probrány příklady 1, 2, 3 a 4. Seznam příkladů ze cvičení [PDF].
  • Čtvrté cvičení (8.3.2022): Cvičení se nekonalo.
  • Páté cvičení (15.3.2022): Základní pojmy z geometrie. Probrány příklady 1 (první část), 2, 3 a 4 a ukázali jsme si řešení 1. teoretického domácího úkolu. Seznam příkladů ze cvičení [PDF].
  • Šesté cvičení (22.3.2022): Mnohostěny. Probrány příklady 1, 2, 3a a 4. Seznam příkladů ze cvičení [PDF].
  • Sedmé cvičení (29.3.2022): Simplexová metoda. Probrány příklady 1, 2 a 3. Seznam příkladů ze cvičení [PDF].
  • Osmé cvičení (5.4.2022): Psali jsme první písemku.
  • Deváté cvičení (12.4.2022): Simplexová metoda podrobněji. Ukázali jsme si řešení první písemky a probrány příklady 1 a 3. Seznam příkladů ze cvičení [PDF].
  • Desáté cvičení (19.4.2022): Dualita. Probrány příklady 1, 2, 3 a 4 a bylo vysvětlené zadání praktického úkolu. Seznam příkladů ze cvičení [PDF].
  • Jedenácté cvičení (26.4.2022): Dualita a její aplikace. Probrány příklady 1, 2 (částečně) a 3 a ukázali jsme si řešení 2. teoretického domácího úkolu. Seznam příkladů ze cvičení [PDF].
  • Dvanácté cvičení (3.5.2022): Psali jsme druhou písemku.
  • Třinácté cvičení (10.5.2022): Komplementarita. Ukázali jsme si řešení druhé písemky a probrány příklady 1 a 2. Seznam příkladů ze cvičení [PDF].
  • Čtrnácté cvičení (17.5.2022): Totální unimodularita. Probrány příklady 1, 2, 3 a 4 a nastínili jsme řešení praktického domácího úkolu. Seznam příkladů ze cvičení [PDF].

Valid XHTML 1.0 Transitional