Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- courses:a4b35ko:test3 [2012/04/19 21:09]
nardi
+++ courses:a4b35ko:test3 [2025/01/03 18:28] (aktuální)
@@ Řádek 1: / Řádek 1: @@
 ====== Test 3 ======
-==== Test 2012 ====
+===== Test 2015 =====
-=== A ===
+==== 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
+1 0 0
+0 1 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.
-{{:courses:a4b35ko:wp_000161.jpg|}}
+Ř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.
-=== B ===
+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, p , -1;
+0 0 0, 1 0 0 0,0;
+1 0 0, 0 1 0 0,0;
+0 1 0, 0 0 1 0,0;
+0 0 1, 0 0 0 1,0;
+     %pridané řádky pro matici M
+0 0 0, 0 0 1 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 =====
+{{:courses:a4b35ko:img_20150504_200112.jpg?200|}}
+===== Test 2013 =====
+{{:courses:a4b35ko:a4m35ko_test_2013.jpg?200|}}
+===== Test 2012 =====
+==== A ====
+== zadani ==
+{{:courses:a4b35ko:wp_000161.jpg?200|}}
+== reseni ==
+Par hintu na prvni pokuk:
+  * matice A bude obsahovat tenhle vzor: ''Apartial = [ 1 0 0 0 0 0 0 1; 1 1 0 0 0 0 0 0; 0 1 1 0 0 0 0 0; ... ];'' kazde cislo v radku je jedna 3hodinovka, vyznam je stejny jako v domacim ukolu s telefonim operatorem
+  * take se nam tam vyskytne ''-[bmin, bmax]'; ''
+  * tipuju to na neco jako minimalizace pres vsechna ''x'' (tedy: ''c=ones(length(A),1)'') pro matici ''A = [ Apartial -bmin'; -Apartial bmax'];''
+  * vektor x obsahuje pocet sluzeb zacinajicich v te ktere hodine
+Tim konci myslenkove pochody a prichazi vecerni odpocinek =D Je to jen tip reseni na prvni pohled. Melo by se stacit podivat na domacak s Telefonnim operatorem a brat jednu 3hodinovku jako 1h.
+==== B ====
 == zadani ==
 Jednalo se o planovaci ulohu ctyr uloh na dvou procesorech.
@@ Řádek 102: / Řádek 163: @@
-==== Test 2011 ====
+===== Test 2011 =====
-=== A ===
+==== A ====
   n(5) dam na sachovnici. (n queens problem)
   zjednodusena uloha n vezi, z te pak dodelat uhlopricky pro damy.
   vychazelo se z ukolu na sudoku
-=== B ===
+==== B ====
   problem batohu pomoci ILP
   nejaka omezeni, ktere veci nejdou vzit spolu (prosim doplnte)
-==== Test 2010 ====
+===== Test 2010 =====
 {{:courses:a4b35ko:a4m35ko-test3-2010.jpg?500|}}
 ~~DISCUSSION~~

courses/a4b35ko/test3.1334862561.txt.gz · Poslední úprava: 2025/01/03 18:24 (upraveno mimo DokuWiki)

Nahoru