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 $
$ \ro _AOB(T(z_1,z_2,z_3)) = log_{2n + 1} N $, kde $ N=z_1 z_2 z_3 : <math> log_{2n + 1) N $ n=3