Pro absolvování předmětu (se známkou lepší než F) požaduju, abyste každý vypracoval samostatný domácí úkol, jehož výsledek odprezentujete ostatním na poslední konzultaci v květnu. Možná témata se ústně domluví na konzultacích dříve, ale náměty jsou uvedeny níže.

Dualita z Farkase jinak

Dokázali byste lépe odvodit silnou větu o dualitě z našich uvedených reformulací Farkasova lematu, tj. bez použití limitního epsilon jako ve výukovém textu?

IP popisy problému band-width

Podstatou úlohy je implementovat různé IP popisy permutace vrcholů grafu, nad nimiž se dá napsat optimalizační problém "bandwidth", a pak porovnat jejich efektivitu při praktickém řešení úlohy.

Popisy souvislých podgrafů v IP

Nastíníme si, jak by se dala alternativně popsat souvislost vybraného podgrafu v daném grafu. Úkolem by bylo tyto nové možnosti popisu implementovat v balíku LPsolve a prozkoumat, jak jsou "výkonné" v praktických výpočtech. Pro takovéto vyhodnocení výpočtu nakonec není nutné interagovat s LPsolve, stačí jen jedním programem vypsat textový vstup do LPsolve a ten tam vyřešit (a poznamenat si čas a náročnost výpočtu).