====== Test 3 - 6.5.2014 ======

Čas cca 40min.

===== A ===== 

  - 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?

{{:courses:a4b35ko:ko3_b.png?200|}}

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.
{{:courses:a4b35ko:20150515_174959.jpg?100|}}

  - 2-aproximation alg for knapsack

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

{{:courses:a4b35ko:ko3_a.png?200|}}
===== B ===== 
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