[zk] 27/1/2010
Napsal: 29. 1. 2010 13:44
Oneskorene, ale predsa...
Písomná časť:
trvanie hodina a pol, dva príklady
1) daný počet strojov, čas t a množina úloh s jednotkovým trvaním zadaná grafom, kde hrana je medzi úlohami, ktoré sa nesmú prekrývať v čase. Navrhnúť polyn.alg. ktorý pre t=2 rozhodne, či je možné rozvrhnúť úlohy na m strojov, tak aby boli dokončené v čase 2 a dodržali závyslosti dané grafom.
2) ukázať, že pre t väčšie ako 2 je NPúplné
Známe príklady, riešenia dohľadateľné.
Ústna časť:
Počuť bolo všetky klasické otázky. Ja som mal ukázať NPúplnosť SP pomocou VP a vysvetliť, čo je to pseudopolyn.alg.
písomná 1,5 bodu + ústna komplet ok = velmi dobře
GL
Písomná časť:
trvanie hodina a pol, dva príklady
1) daný počet strojov, čas t a množina úloh s jednotkovým trvaním zadaná grafom, kde hrana je medzi úlohami, ktoré sa nesmú prekrývať v čase. Navrhnúť polyn.alg. ktorý pre t=2 rozhodne, či je možné rozvrhnúť úlohy na m strojov, tak aby boli dokončené v čase 2 a dodržali závyslosti dané grafom.
2) ukázať, že pre t väčšie ako 2 je NPúplné
Známe príklady, riešenia dohľadateľné.
Ústna časť:
Počuť bolo všetky klasické otázky. Ja som mal ukázať NPúplnosť SP pomocou VP a vysvetliť, čo je to pseudopolyn.alg.
písomná 1,5 bodu + ústna komplet ok = velmi dobře
GL