FANDOM


CRCW PRIORITY vs. CRCW ARBITARY/COMMONEdit

ARBITARY je vybrán náhodně. Můžeme tedy jednoduše nahradit PRIORITNÍM (PRIORITY) pomocí vhodného zvolení priorit. Podle příslušné věty dostáváme: ARBITARY (NÁHODNÝ) lze implementovat pomocí PRIORITY => PRIORITY je alespoň stejně výpočetně silný jako ARBITARY (náhodný)

platí: PRIORITY >= ARBITARY >= COMMON(SHODNÝ) >= CREW >= EREW

Zkostruujte vnoření úplného binárního stromu CBT_3 do Q_4 s load=edge-congession=1 a dilatací=2Edit

CBT_n nelze vnořit do Q_{n + 1} s dilatací=load=1, neboť Q_n+1 je vyvážený bipartitní graf, zatímco CBT_n je nevyvážený \left| V \left( CBT_n \right) \right| = 2^{n + 1} - 1 \mbox{ a } \left| C \left( Q_{n + 1} \right) \right| = 2^{n + 1}
vnoření s dilatací 1 nemění barvení, potom by musel být load=2

  • V našem případě dilatace=2 , tedy:














Dokažte, že 2D mřížka  M(6,7) je podgrafem své optimální hyperkrychle Q_6 . Důkaz proveďte zkonstruováním vnoření M(6,7) do Q_6 s dilatací = load = 1 . Vnoření popište jako mapování uzlů.Edit

Mřížka  M(6,7) => je faktorem hyperkrychle  Q_n , kde n = n_1 + n_2 , v našem případě  n = 3 + 3 = 6 M(x,y,z) lze namapovat do Q_n , kde n = \log x + \log y + \log z . Toto vnoření je optimální právě tehdy, když :  \log x + \log y + \log z = \log (xyz)
Vnoření lze zkonstruovat takto:

  • rozlož mřížku M(x,y,z) \mbox{ na } M(x) \mbox{ x } M(y) \mbox{ x } M(z). M(a_i) lze vnořit do Q_{n_i} , kde n_i = \log a_i => vnoříme M(x), M(y), M(z) \mbox{ do } Q_{\log x}, Q_{\log y}, Q_{\log z}
  • proveď kartézský součin Q_n = Q_{\log x} x Q_{\log y} x Q_{\log z}, který realizuje požadované vnoření


f(3,2) = ?
f(5,4) = ?


G = \left\{\begin{matrix} g_{i} = b_{i} & i = n - 1 \\ g_i = b_i XOR b_{i + 1} & \mbox{pokud } 0<=i<={n-2} \end{matrix}\right.

b_3 = 011 => g_3 = 010
b_2 = 010 => g_3 = 011
b_5 = 101 => g_3 = 111
b_4 = 100 => g_3 = 110

f(3,2) = 010 | 011
f(5,4) = 111 | 110
vzdálenost (odlišné bity) = 4 <= { 1. 3. 4. 6. bit }

Odvod spodni mez pro OAB na T[z_1,z_2,z_3] , prepinani je WH, Startovni uzel je  S[s_1,s_2,s_3] \mbox{, kde} s_i  z_i , uzly jsou vystupne vseportoveEdit

  • vysledek nezavisi na pozici startovniho uzlu S , protoze toroid je uzlove symetricky.
  • je-li vystupne vseportovy, znamena to, ze uzel muze informovat 2n sousedu (stupen uzlu je 2n )
v kroku k bude pocet informovanych uzlu (2n + 1)^k
  • v kroku t bude hotovo (2n + 1)^t = N => t = log_{2n + 1} N
Failed to parse (unknown function\ro): \ro _AOB(T(z_1,z_2,z_3)) = log_{2n + 1} N

, kde Failed to parse (syntax error): N=z_1 z_2 z_3 : <math> log_{2n + 1) N

 n=3

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.