navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4b35ko:test3-prednaska [2014/05/06 12:44] furtuand |
courses:a4b35ko:test3-prednaska [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 5: | Řádek 5: | ||
| ===== A ===== | ===== A ===== | ||
| - | -Bratley’s algorithm(tree)\\ | + | - Bratley’s algorithm(tree) |
| - | r=[5,0,4,0]\\ | + | |
| - | p=[3,2,2,1]\\ | + | r=[5,0,4,0] |
| - | d=[10,3,10,2]\\ | + | 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 | ||
| - | a) nakreslit strom a Ganttuv diagram\\ | ||
| - | b) je to optimalni reseni? Proc? | ||
| - | -2-aproximation alg for knapsack | ||
| - | a) popsat pomoci pseudokodu\\ | ||
| - | b) dukaz, ze aprox koef je 2 | ||
