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

---

Hlavní stránka

Cvičení probíhá každé pondělí od 10: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:	nahoru

• 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. Při zápisu na kurz použijte token 46b8c1563aa6.
• Úč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 3.3.2025, termín odevzdání 17.3.2025)
  • 2. teoretický domácí úkol [PDF] (zadáno 24.3.2025, termín odevzdání 7.4.2025)
• 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í:	nahoru

• První cvičení (17.2.2025): Ú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í (24.2.2025): Celočíselné lineární programy. Probrány příklady 1, 2, 3, 4 a 5. Seznam příkladů ze cvičení [PDF].
• Třetí cvičení (3.3.2025): 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í (10.3.2025): Základní pojmy z geometrie. Probrány příklady 1, 2, 3, 4 a 5. Seznam příkladů ze cvičení [PDF].
• Páté cvičení (17.3.2025): Mnohostěny. Ukázali jsme si řešení 1. teoretického domácího úkolu. Probrány příklady 1, 2, 3 a 4. Seznam příkladů ze cvičení [PDF].
• Šesté cvičení (24.3.2025): Simplexová metoda. Probrány příklady 1, 2 a 3. Seznam příkladů ze cvičení [PDF].
• Sedmé cvičení (31.3.2025): Psali jsme první písemku.
• Osmé cvičení (7.4.2025): Bude doplněno.