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

Cvičení probíhá každé úterý od 17:20 v učebně S1.

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ě 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. Domací úlohy prosím nahrávejte na Sovičku.
  • Všechny příklady z cvičení i domací úkoly budou na Sovičce. Pří zápisu na kurz použijte token 870ccd22bc07. Všechny úlohy (domácí i ty řešené na cvičeních) budou dostupné i zde na webu.
  • Účast na cvičeních je nepovinná, nicméně doporučovaná z povahy podmínek získání zápočtu.
  • Zadání domácích úkolů:
    • 1. teoretický domácí úkol [PDF] (zadáno 28.2.2023, termín odevzdání 14.3.2023)
    • 2. teoretický domácí úkol [PDF] (zadáno 28.3.2023, termín odevzdání 11.4.2023)
    • 3. teoretický domácí úkol [PDF] (zadáno 9.5.2023, termín odevzdání 30.6.2023)
    • Praktický domácí úkol [PDF, ZIP] (zadáno 18.4.2023, termín odevzdání 16.5.2023 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í (14.2.2023): Úvod, podmínky zápočtu a lineární nerovnice. Probrány příklady 1, 2, 4 a část 5. Seznam příkladů ze cvičení [PDF].
  • Druhé cvičení (21.2.20223): Celočíselné lineární programy. Probrán příklad 5 z minula a příklady 1, 2, 3, 4 a 5. Seznam příkladů ze cvičení [PDF].
  • Třetí cvičení (28.2.2023): Ostré nerovnosti a další NP-těžké úlohy a celočíselné programy. Probrány příklady 1a, 1b, 2, 3 a 4. Seznam příkladů ze cvičení [PDF].
  • Čtvrté cvičení (7.3.20223): Základní pojmy z geometrie. Probrány příklady 1, 2, 4 a 5. Seznam příkladů ze cvičení [PDF].
  • Páté cvičení (14.3.20223): Mnohostěny. Ukázali jsme si řešení 1. teoretického domácího úkolu. Probrány příklady 1, 2, 3 a a. Seznam příkladů ze cvičení [PDF].
  • Šesté cvičení (21.3.20223): Simplexová metoda. Probrány příklady 1, 2 a 3. Seznam příkladů ze cvičení [PDF].
  • Sedmé cvičení (28.3.20223): Simplexová metoda podrobněji. Probrány příklady 1 a 3. Seznam příkladů ze cvičení [PDF].
  • Osmé cvičení (4.4.20223): Psali jsme první písemku.
  • Deváté cvičení (11.4.20223): Dualita. Ukázali jsme si řešení 2. teoretického domácího úkolu a 1. písemky. Probrány příklady 1, 2, 4 a náčrt 3. Seznam příkladů ze cvičení [PDF].
  • Desáté cvičení (18.4.20223): Dualita a její aplikace. Probrány příklady 1 a 2 a zadán praktický domácí úkol. Seznam příkladů ze cvičení [PDF].
  • Jedenácté cvičení (25.4.20223): Komplementarita. Probrány příklady 1, 2 a 4. Seznam příkladů ze cvičení [PDF].
  • Dvanácté cvičení (2.5.20223): Psali jsme druhou písemku.
  • Třinácté cvičení (9.5.20223): Totální unimodularita. Ukázali jsme si řešení 2. písemky. Probrány příklady 1, 2 a 3. Seznam příkladů ze cvičení [PDF].
  • Čtrnácté cvičení (16.5.20223): Matroidy. Ukázali jsme si řešení pratického úkolu. Probrány příklady 1 a 2. Seznam příkladů ze cvičení [PDF].
Valid XHTML 1.0 Transitional