Test 3 - 6.5.2014

Čas cca 40min.

1. Bratley’s algorithm(tree)

  r=[5,0,4,0]
  p=[3,2,2,1]
  d=[10,3,10,2]

   a) nakreslit strom a Ganttuv diagram
   b) je to optimalni reseni? Proc?

Mohl by nekdo ukazat, jestli je nebo neni optimalni? Mne vysly dva BRTP. Podle prednasek (scheduling 14/70) museji vsechny tasky bezet bez „idle waiting“. V nejlepsim reseni se musi cekat.

1. 2-aproximation alg for knapsack

  a) popsat pomoci pseudokodu
  b) dukaz, ze aprox koef je 2

Bratley

• r=[1,8,2,0]
• p=[2,1,2,3]
• d=[6,9,7,6]

Christofidesův algoritmus

• Popsat pseudokódem
• Jaký má aproximační faktor