navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4b35ko:test3 [2015/05/04 20:05] papouada |
courses:a4b35ko:test3 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| ====== Test 3 ====== | ====== Test 3 ====== | ||
| + | |||
| + | ===== Test 2015 ===== | ||
| + | ==== Varianta 1 ==== | ||
| + | Jednalo se o podobné zadání jako varianta B z roku 2012. Navíc byla zadána matice | ||
| + | <code> | ||
| + | M = 1 0 1 0 | ||
| + | 0 1 0 0 | ||
| + | 1 0 1 0 | ||
| + | 0 0 0 1 | ||
| + | </code> | ||
| + | Kde 1 značí: Úloha i musí být vykonávána na stejném procesoru jako úloha j, i je řádkový a j je sloupcový index. | ||
| + | |||
| + | Řešení: | ||
| + | Test vstupních podmínek. Matice M musí být symetrická, např. pokud úloha 1 musí být vykonávána na stejném procesoru jako úloha 3, tak úloha 3 musí být vykonávána na stejném procesoru jako úloha 1. Na diagonále musí být 1, samostatná úloha se vykonává na stejném (jednom) procesoru. Preempce nebyla povolena. | ||
| + | Vektor proměnných obsahuje xij - x11 x21 x31 x41 x12 x22 x32 x42 Cmax, kdy i je číslo úlohy, j je procesor, více viz popis úlohy níže. | ||
| + | |||
| + | Matice M nám říká, že úloha 1 má běžet na stejném procesoru jako úloha 3. Tedy nemůže se stát, že pokud je úloha 1 rozvržena na procesor 1 (x11), tak bude úloha 3 rozvržena na procesor 2 (x32). Součet těchto proměnných musí být 1. Analogicky, nemůže se stát, že pokud je úloha 1 rozvržena na procesor 2 (x12), tak bude úloha 3 rozvržena na procesor 1 (x31). Součet těchto proměnných musí být opět 1. | ||
| + | Matici A tedy rozšíříme o řádky pro omezení z matice M: | ||
| + | <code> | ||
| + | A = [p , 0 0 0 0, -1; | ||
| + | 0 0 0 0, p , -1; | ||
| + | 1 0 0 0, 1 0 0 0,0; | ||
| + | 0 1 0 0, 0 1 0 0,0; | ||
| + | 0 0 1 0, 0 0 1 0,0; | ||
| + | 0 0 0 1, 0 0 0 1,0; | ||
| + | %pridané řádky pro matici M | ||
| + | 1 0 0 0, 0 0 1 0,0; | ||
| + | 0 0 1 0, 1 0 0 0,0]; | ||
| + | </code> | ||
| + | Je třeba i upravit vektor b, rozšířit ho o dvě jedničky | ||
| + | <code>b = [0; 0; ones(n,1); 1;1];</code> | ||
| + | a porovnávací podmínky | ||
| + | <code>ctype = ['L'; 'L'; repmat('E',n,1);'E';'E'];</code> | ||
| + | |||
| + | Pokud bych něco opomenul, pište do diskuze, případně upravte s poznámkou. | ||
| + | |||
| + | |||
| + | P.S. Proč mne řešení napadnou vždy až v klidu při kávičce a příjemné hudbě, místo při psaní testu :-). | ||
| + | |||
| + | |||
| ===== Test 2014 ===== | ===== Test 2014 ===== | ||
