U spodních mezí komunikačních operací dávejte pozor na to, že se jedná o spodní meze. Neměli byste tedy tvrdit, že nějaká operace trvá tolik a tolik, ale že teoreticky musí trvat nejméně takto. Tzn. upozornit v testu na to, že se jedná o spodní mez, ale že to vůbec neznamená, že takový alogirtmus existuje. Nemusí. Snad to dává smysl, Tvrdík za to bral body.

Jaká je spodní mez počtu kroků nekombinujícího OAB na Q_n. Všeportový. Odvoďte.

<math>\rho_{OAB}^{SF}\left(Q_{n},s\right)=\text{diam}\left(Q_{n}\right)=n</math>

Zdroj pošle paket všem sousedům a jakýkoli jiný uzel obdržený paket zkopíruje a pošle ho zbývajícím sousedům.

Odvoďte spodní mez pro OAB na toroidu <math>T(z_1,z_2,z_3)</math> s přepínáním WH. Startovní uzel je <math>[s_1,s_2,s_3]\quad s_i<z_i</math>.
Uzel je výstupně všeportový.

Viz skripta CZ [2006] str. 177 nebo přednáška 10 slajd 28

• Nezávisí na vybraném počátečním uzlu, protože topologie je uzlově symetrická.
• V každém kroku se informace posílá <math>2n</math> sousedům, což odpovídá stupni uzlu v toroidu. V kroku <math>\mathrm{i}</math> je informovaných <math>(2n+1)^i</math> uzlů.

Nejdřív zná tajemství jeden. Pošle to šesti a ví jich to sedm. Každý ze sedmi to pošle dalším 6. Tzn. že to bude znát dalších 42, ale předtím jich to už znalo 7.. 42+7=49..

Ještě mě napadlo sem rozepsat, proč to je zrovna <math>(2n+1)^k</math>.. Jak jsem psal výše, aktuální počet informovaných, je počet informovaných v předchozím kroku, krát <math>2n</math> (to proto, že každý může informovat max <math>2n</math> dalších uzlů), plus počet aktuálně informovaných.. Tzn.

<math>Inf_i = Inf_{i-1}(2n) + Inf_{i-1} </math>

<math>Inf_i = Inf_{i-1}(2n + 1) = Inf_{i-2}(2n + 1)(2n + 1) = …. = (2n+1)^i</math>

Nakonec se akorát místo toho násobení těch závorek napíše mocnina…

Všechny uzly budou informovány v <math>\mathrm{k}</math> krocích (uzlů je <math>\mathrm{N}</math>) ⇒ <math>N=(2n+1)^k</math> ⇒ <math>\log_{(2n+1)}{N}=k</math>
⇒ pro 3D je výsledek <math>\log_{7}{({z_1}{\cdot}{z_2}{\cdot}{z_3})}</math>

Výše uvedený výpočet zapsaný obecně:

<math>\rho_{OAB}^{WH}\left(G,s\right)=\left\lceil \log_{k+1}\left(\left|V\left(G\right)\right|\right)\right\rceil </math>, kde <math>k</math> je počet portů sítě, v případě toroidu tedy <math>(2*n)+1 = (2*3)+1 = 7</math>.

Trocha další teorie:

• OAB - kolektivní komunikační operace typu vysílá jeden všem
• WH - červí technika přepínání
• slajd 10/18, 10/28 2014

Určete spodní mez pro počet kroků operace AAB na všeportovém 3D toroidu. BEZ kombinování paketů.

EN skripta pg. 168 Lemma 9.24

• n= počet dimenzí
• N= počet všech uzlů = <math>|V(T_n)|</math>
• Uzel může v každém kroku přijmout 2n zpráv = <math> degree(T_n)</math>
• Při AAB musí celkově přijmout N-1 zpráv
• Všechny zprávy tedy přijme nejdříve po <math>\mathrm{k}</math> krocích, kde <math>\mathrm{k}=\frac{|V(T_n)|-1}{degree(T_n)}=\frac{N-1}{2n}</math>

Spodní mez pro <math>T(z_1,z_2,z_3)</math> tedy vychází <math>\rho_{AAB} = \fracuzlove_disjunktni_cesty_nesmi_sdilet_zadny_uzel_az_na_ty_koncove._hranove_disjunktni_cesty_nesmi_sdilet_zadnou_spolecnou_hranu._uzlove_nebo_hranove</math>. Stejně tak můžeme vybrat 3 nuly ze sedmi možností, což je <math>\normalsize x_y_choose_x</math>. Obě čísla jsou stejná.

• Nyní to zobecníme pro více dimenzí. Pro 3 dimenze to může vypadat třeba tak, že vektor bude obsahovat čísla 0, 1 a 2. Bude-li mít cesta délku např. <math>\normalsize d = x+y+z = 5+3+2 = 10</math> (např. vektor <math>\normalsize (0,2,0,1,1,0,0,1,0,2)</math>), nejprve vybereme 5 nul z deseti možností <math>\normalsize x_y_z_choose_x</math> a 3 jedničky z toho zbytku <math>\normalsize y_z_choose_y</math> (jde to udělat i v jiném pořadí). A tohle vynásobíme mezi sebou. <math>\normalsize x_y_z_choose_xy_z_choose_y</math>. A tak dále pro více dimenzí.
• Popsaná kombinační čísla lze přepsat na podíl faktoriálů <math>(x + y)!\over(x!y!)</math>, ve kterém pro další dimenze stačí jednoduše přidat z a z! do čitatele i jmenovatele <math>(x + y + z)!\over(x!y!z!)</math> (výraz o dvě odrážky výše je ekvivalentní po vyčíslení kombinačních čísel). Obecne tedy <math>(\sum z_i)!\over \prod z_i!</math>
• O co tady jde je počet permutací s opakováním, které přesně popisuje vzorec výše. <math>x + y + z</math> je totiž celková délka cesty, kterou permutujeme, a výsledek musíme podělit, protože „doprava“ na prvním místě je ekvivalentní s „doprava“ na třetím místě atd.

Jak přijít na ten vzoreček :

Vycházet budeme ze stejné myšlenky. Jestliže se dva uzly liší ve třech dimenzích a liší se pro jednu dimenzi “5krát”, pro druhou “3krát” a pro třetí “2krát”, jde jenom o to, jaké všechny kombinace můžete získat v tom, jak se budete postupně přibližovat z jednoho uzlu do druhého.

V našem případě si můžeme dimenze označit jako A,B,C a pak cesta může vypadat třeba nějak takhle : (A,A,A,B,B,B,C,C,A,A). Otázka je, kolik takových permutací mohu udělat. No jde o všechny, kde budu mít 5Aček, 3Bčka a 2 Cčka. A to je permutace s opakováním.

<math>P(5, 3, 2)' = \frac{(5+3+2)!}{5!3!2!}</math>

Pozn. by plech.d: Ještě bych si dovolil odvodit z uvedené permutace s opakováním úplný obecný vzoreček. Je-li <math>u_i</math> i-tá souřadnice bodu <math>u</math> a <math>v_i</math> i-tá souřadnice bodu <math>v</math> a <math>n</math> je počet dimenzí mřížky, pak tedy pro počet cest mezi <math>u</math> a <math>v</math> platí vztah:

<math>\left|\mathcal{P}\left(u,v\right)\right|=\frac{\left({\displaystyle \sum_{i=1}^{n}}\left|u_{i}-v_{i}\right|\right)!}displaystyle_prod_i_1_n\left|u_{i}-v_{i}\right|!},\,u,v\in V\left(G\right) </math>

Odvoďte výraz pro počet různých nejkratších cest mezi 2 uzly u, v v Q_n ve vzdálenosti d ≤ n.

Vzdálenost d znamená, že se uzly u, v liší v d bitech. Pořadí, v jakém se tyto bity invertují (tedy se v krychli posouvám), je libovolné. Z toho vyplývá, že různých cest mezi těmito uzly je d! (všechny permutace).

Odvoďte výraz pro počet uzlově disjunktních nejkratších cest mezi 2 uzly u, v v Q_n ve vzdálenosti d ≤ n.

★ Bylo ve zkoušce: 2012-01-17

Vzdálenost d znamená, že se uzly u, v liší v d bitech. Pořadí, v jakém se tyto bity invertují (tedy se v krychli posouvám), je libovolné. Uzlově disjunktních cest je d, protože na začátku si můžu vybrat jaký ten bit zinvertuju, což je přesně d možností. Přes tyto uzly už nemohou jít jiné další cesty a jiný bit, než v kterém se ty 2 řetězce liší, zinvertovat nemůžu (vzdálil bych se).

Porovnat (a porovnání zdůvodnit) CRCW náhodný a CRCW shodný (common).

★ Bylo ve zkoušce: 2016-01-15

Silnější je náhodný CRCW.

Náhodný (ARBITRARY) CRCW <math>\geq</math> Shodný (COMMON) CRCW

Jakýkoliv algoritmus napsaný pro Shodný CRCW může beze změn běžet na náhodném. Shodný předpokládá, že když procesory v jednom kroku chtějí zapisovat do stejné paměťové buňky, musí být hodnota stejná. To jde bez problému udělat na náhodném, zápis reálně provede náhodně vybraný z nich, ale protože je hodnota stejná, ničemu to nevadí.

Opačně to udělat nejde. Náhodný předpokládá, že v jednom kroku můžou do stejné paměťové buňky zapsat všechny, zápis se podaří náhodnému z nich (a algoritmus nesmí dělat předpoklady o tom, který z nich to bude). Kdyby se ale na Shodném CRCW pokusilo zapsat více procesorů najednou různou hodnotu do stejné paměťové buňky, nastane pro Shodný CRCW nedefinovaný stav.

Porovnat (a porovnání zdůvodnit) CRCW prioritní a CRCW shodný (common).

CRCW: jsou dovoleny současná čtení a současné zápisy téže paměťové buňky.

Prioritní (Priority) CRCW: Procesorům jsou přiděleny pevné priority. Zápis je povolen procesoru s nejvyšší prioritou.

Shodný (Common) CRCW: Všem žádajícím procesorům je dovoleno dokončit zápis právě tehdy, když všechny zapisované hodnoty jsou stejné. Algoritmus musí zajistit splnění této podmínky. V opačném případě není algoritmus správný a stav počítače není definován.

Prioritní CRCW je výpočetně silnější, protože algoritmus napsaný pro shodný CRCW poběží beze změn na prioritním CRCW, ale obráceně to neplatí. Kdyby prioritní běžel na shodném, pak bychom museli být schopní nechat zapisovat proces pouze s nejvyšší prioritou. Pokud by ovšem procesů, které chtějí zapisovat různou hodnotu, bylo více, pak pro shodný CRCW nastává nedefinovaný stav. V opačném případě, pokud má více procesů stejnou hodnotu, pak jeden z nich zapíše jako prioritní a tudíž dochází ke stejnému chování.

Dodatek by Mirax: Pokud má běžet program pro prioritní CRCW na shodném CRCW, tak se může obecně stát, že více procesorů bude chtít zapsat najednou různou hodnotu do téže paměťové buňky. Toto je ovšem pro shodný CRCW nepřípustné.

PDF přednáška 3/10

Trocha teorie:

• CRCW - Concurrent Read Concurrent Write

Který model je výpočetně silnější, prioritní nebo náhodný CRCW. Dokažte.

★ Bylo ve zkoušce: 2013-01-02

Viz EN skripta [2010] str. 24 nebo CZ skripta [2006] str. 40

Výpočetní síla modelů: PRIORITY (prioritní) CRCW ≥ ARBITRARY (náhodný) CRCW ≥ COMMON (shodný) CRCW ≥ CREW ≥ EREW

Náhodný (Arbitrary) CRCW: Ukončit zápis je povoleno náhodně vybranému procesoru. Algoritmus nesmí činit žádné předpoklady o tom, který procesor bude vybrán.

Na náhodném nejde odsimulovat prioritní, protože k zápisu se vybírá náhodný procesor (to nemusí být vždy ten s největší prioritou). Naopak náhodný na prioritním odsimulovat lze, protože k zápisu se vždy vybere jeden procesor a ten jako prioritní zapíše. Prioritní je tedy výpočetně silnější.

Dodatek: U všech těhle porovnávání je dobré se nad tím zamyslet z pohledu, jak se bude chovat algoritmus napsaný pro tento typ CRCW na jiném typu CRCW - jestli máme algoritmus pro CRCW typu A a v pohodě se provede i na CRCW typu B, tak B je výpočetně silnější.

Dodatek by voho: Při simulaci na prioritním CRCW se každému procesoru přiřadí náhodné číslo jako priorita a tím se simuluje náhodné chování. - táto veta je kec, za ktorý dostanete -1bod, takže v žiadnom prípade to tam nepíšte. Prioritný simuluje náhodný bezo zmeny a náhodnému algoritmu je fuk ktorý P má akú prioritu. Jednoducho zapíše.

Dodatek: Algoritmus pro arbitary počítá s tím, že se ukončení W při kolizi bude provádět náhodně, takže ho nerozhodí, když se ukončení W bude dělat podle nějaké priority. Naopak pokud alg. počítá s prioritou a vybere se random, tak to nemusí spočítat správný výsledek.

Co je superlineární zrychlení a kdy může nastat?

★ Bylo ve zkoušce: 2013-01-16 a 2012-01-24

Viz CZ skripta [2006] str. 6 nebo EN [2009] str. 4

K superlineárnímu zrychlení dochází pokud úloha spuštěná na p procesorech doběhne v čase menším než T/p, kde T je čas řešení pomocí jednoho procesoru, tedy čas sekvenčního řešení. Tedy pomocí p procesorů jsme úlohu spočetli víc jak p-krát dřív. O všem pojednává přednáška 2 (slajd 16). Nastává ve 2 případech:

1. Stavový prostor, ve kterém hledáme řešení, byl rozdělen takovým způsobem (Rozděl a Panuj), že se po nějaké kratší době, než by odpovídalo času T/p, dostaneme do míst stavového prostoru, kde je hledané řešení.
2. Další vliv mají paměti, kdy na více procesorech můžeme mít pro výpočet dostupno více paměti, takže se nedostaneme např. ke swapování na disk, které by mohlo zpomalovat výpočet jen na jednom pocesoru (zmíněno v první přednášce).

Charakterizujte uzlovou a hranovou symetrii 3D toroidu <math>T(z_1,z_2,z_3)</math>, odpověď dokažte.

Graf <math>{G}</math> je uzlově symetrický, když pro <math>\forall u_1 , u_2 \in V(G) \text{ }\exists</math> automorfismus <math>{f}</math> takový, že <math>f(u_1)=u_2</math>.
Graf <math>{G}</math> je hranově symetrický, když pro <math>\forall e_1 , e_2 \in E(G) \text{ }\exists</math> automorfismus <math>{f}</math> takový, že <math>f(e_1)=e_2</math>.

Dokaz, ze kartazsky sucin zachovava uzlovu symetrie

Toroid je uzlově symetrický, protože existuje např. přeložení (automorfismus) pro <math>\forall u , v \text{ } \tau_{u \mapsto v}(x)=(x_1\oplus_{_{z_{1}}}(v_1\ominus_{_{z_{1}}}u_1),x_2\oplus_{_{z_{2}}}(v_2 \ominus_{_{z_{2}}}u_2),x_3\oplus_{_{z_{3}}}(v_3 \ominus_{_{z_{3}}}u_3))</math>. Uzlová symetrie je dána vlastnostmi kartézského součinu, který uzlovou symetrii zachovává (a kružnice je uzlově symetrická).

Toroid je hranově symetrický, jen pokud má všechny dimenze stejně veliké - existuje automorfismus rotace. To je dáno tím, že k-ární n-toroid vznikne kartézskou mocninou kružnice o délce n, <math>K_n^k</math>, a kartézská mocnina zachovává i hranovou symetrii (4 přednáška, slide 7, video cca 2:10:00 konrétně pro toroid). Vlastnosti toroidu v PDF 4. přednášky na slajdu č. 30 (MI-PAR 2011/2012).

Dodatek Graf je uzlove symetricky, pokud pro kazde dva uzly existuje automorfismus.
Automorfismus

• je mapovani mnoziny uzlu na mnozinu ulzu,
• zachovava vzdalenosti

Automorfismus rotace o jeden uzel, na K(4) je namapovani uzlu 1→2, 2→3, 3→4, 4→1

Dukaz automorfismu : pro libovolne dva sousedni uzly aplikujem automorfismus a ve vysledku jsou opet sousedni. Proste staci namalovat rotaci kruznice.

Pozor, pokud do písemky napíšete jako zdůvodnění pouze automorfizmus pro K(z) a to, že kartézský součin zachovává uzlovou symetrii, Tvrdík vám to za plný počet neuzná. To, že kartézský součin zachovává automorfismus by se totiž muselo ještě samostatně dokázat. Chce to asi(?) opravdu přímo tam ten příklad automorfismu pro 2D napsat.

pozn.: k tomu dokazování - stačí aspoň ten důkaz naznačit, když uvidí, že víte jak na to, tak vám ty body dá:) Tzn. vyjít z automorfismů jednotlivých kružnic + definice kart. součinu a napsat si automorfismus pro uzly (u1,u2) a (v1,v2) a naznačit tam, že se využije těch automorfismů např. pro K(z1) a K(z2). Viz video z prosemináře.

Automorfismy hyperkrychle Q_n, kolik jich je a vysvětlit proč.

★ Bylo ve zkoušce: 2012-01-24

Viz CZ skripta [2006] str. 59 nebo záznam 7. prosemináře, čas 22:40

Q_n má 2ⁿ uzlů (roven počtu n-bitových binárních řetězců), tudíž máme 2ⁿ možností odkud definovat počátek souřadného systému (tj. do kterého uzlu umístit nulu). Dále máme n! možností, jak uspořádat pořadí dimenzí (tj. který směr bude souřadnice X, Y atd.).

Formálněji řečeno, pro Q_n existuje 2ⁿ přeložení (translací) a každé má n! permutací dimenzí.

• Přeložení je automorfismus <math>\tau_{u \mapsto v}(x)= x\oplus (u \oplus v) = x\oplus y</math>, kde <math>\oplus</math> je bitová nonekvivalence (XOR).
• Počet všech permutací n-bitového řetězce je <math>n!</math>

Celkový počet automorfismů je tedy <math>2^n\cdot {n!}</math>

Zdůvodněte proč nelze na CBT_n pro n > 1 vnořit do Q_n+1 s load = dil = 1.

★ Bylo ve zkoušce: 2012-01-10

Viz přednáška 5 slide 19 nebo CZ skripta [2006] str. 79, EN skripta [2009] str. 59

• počet uzlů <math>CBT_n = 2^{n+1}-1</math>
• počet uzlů <math>Q_{n+1}=2^{n+1}</math>
• jestliže existuje vnoření <math>CBT_n</math> do <math>Q_{n+1}</math> s parametry load=dil=1, pak <math>CBT_n</math> musí být podgraf <math>Q_{n+1}</math>
• protože <math>CBT_n</math> není podgrafem <math>Q_{n+1}</math>, vnoření nemůže existovat.
• <math>Q_{n+1}</math> je vyvážený bipartitni graf ⇒ má stejný počet černých a bílých uzlů
• <math>CBT_n</math> není vyvážený bipartitní graf

<math>\text{|bilych|} = 1+2^2 + 2^4 + … + 2^{2k}</math>

<math>\text{|cernych|} = 2+2^3 + 2^5 + … + 2^{2k+1} = 2 \cdot {\underbrace{(1+ 2^2 + 2^4 + … + 2^{2k})}_{\text{bile}}}</math>

• |bílých| ≠ |černých| ⇒ <math>CBT_n</math> skutečně není vyvážený bipartitní graf.

<math>CBT_n</math> není vyvážený bip. graf a tudíž není podgrafem <math>Q_{n+1}</math>, nelze tedy vnořit <math>CBT_n</math> do <math>Q_{n+1}</math> s load=dil=1.

Nápad na jednodušší důkaz respektive interpretaci:

• <math>CBT_n</math> má <math>2^n</math> listů, což si spočítáme jako rozdíl počtu uzlů <math>CBT_n</math> a <math>CBT_{n-1}</math>, ty listy jsou od kořene ve vdálenosti n.
• Tak si najdeme, kolik uzlů je od libovolného uzlu v takové vzdálenosti v <math>Q_{n+1}</math>
• když použijeme důkaz, který je o něco málo níže, zjistíme, že těch uzlů, na které by se měli namapovat listy je pouze <math>n+1</math>.
• Což pro <math>n=1</math> ukazuje, že vnoření s danými parametry je možné, ale pro vyšší hodnoty už ne.
• Tudíž nemůže být podgraf a nemůže dojít k vnoření s takovými parametry.

Pozn. by Vity: Obecně si namalujte strom, kde v každé úrovni obarvěte uzly jinou barvou a všimněte si, že s každou další úrovní má mnohem více uzlů poslední barvě než té předešlé barvy.

Otazka: Zda se mi, ze se tu operuje s myslenkou: “(Graf A je vyvazeny bipartitni a graf B je nevyvazeny bipartitni) ⇒ graf B nemuze byt podgrafem grafu A”. To mi ale prijde jako blabol (nebo to alespon neplati obecne) - napr. kdyby graf A byl Q3 a graf B by vzniknul z grafu A odsranenim jednoho uzlu.

Trocha teorie:

• CBT - úplný binární strom

Mřížku M(x, y, z) mapujeme do krychle Q_n. Určete n a nalezněte zobrazovací fci [x,y,z] → Q_n, dil = load = 1.

Viz skripta CZ [2006] str. 83 nebo přednáška 5, FIT slide 25, FEL slide 16, EN skripta [2009] strana 64 Lemma 4.24

<math>\normalsize M(x, y, z)</math> je podgrafem hyperkrychle <math>\normalsize Q_n, \:n= \lceil\log{x}\rceil+\lceil\log{y}\rceil+\lceil\log{z}\rceil,\: x, y, z \ge 2</math>. Toto vnoření je optimální pokud <math>\normalsize \lceil\log{x}\rceil+\lceil\log{y}\rceil+\lceil\log{z}\rceil=\lceil\log(x \cdot y \cdot z)\rceil</math>.

Mřížku rozdělíme na kartézský součin <math>\normalsize M(x)\times M(y)\times M(z)</math>. Každou z jednorozměrných mřížek <math>\normalsize M(a)</math> namapujeme do krychle <math>\normalsize Q_{\lceil {\log{a}} \rceil}</math>. Výsledné vnoření je dáno kartézským součinem <math>\normalsize Q_{\lceil {\log{x}} \rceil}\times{Q_{\lceil {\log{y}} \rceil}}\times {Q_{\lceil {\log{z}} \rceil}}</math>, tedy <math>\normalsize n=\lceil\log{x}\rceil+\lceil\log{y}\rceil+\lceil\log{z}\rceil=\lceil\log(x \cdot y \cdot z)\rceil</math>

Mapovací funkce je dána zřetězením mapovacích fcí pro jednorozměrné mřížky. Mapovací funkce jednorozměrné mřížky <math>M(a)</math> do krychle <math>Q_{\lceil{\log{N}\rceil}}</math> je nějaký Grayův kód.

Grayův kód pro vnoření je definování jako: (CZ skripta 79str. lepe)

nechť je b=b_n-1…b₀ bin. číslo pak BRGC (Binary reflected gray code) G_n pro b je definován jako:

1) b_n-1=g_n-1

2) b_i=g_n-1 +₂ … g_i+1 +₂ g_i pro i=n-2, … , 0

V přednáškách 2015/16 přednáška 5, slide 17 je definice BRGC takováto: BRGC zakódování binárního čísla b = b_n-1…b₀ je Gn(b) = g_n−1…g₀, kde

1) <math>g_{n-1}=b_{n-1}</math>,

2) <math>g_{i}=b_{i+1}\mathtt{\,XOR\,}b_{i}</math> pro <math>i=n-2,\ldots,0</math>.

Je tu obecny popis “ze by se to delalo zretezenim mapovacich funkci”, ale chtelo by to dat vsechny tyhle informace dohromady a napsat tu finalni funkci

Dokažte, že do libovolného souvislého grafu G lze vnořit kružnice s n uzly s load = 1, dil ≤ 3.

★ Bylo ve zkoušce: 2012-01-31 4b

Viz přednáška 5 FIT [2012] slide 41, skripta CZ [2006] str. 89 nebo EN [2009] str. 72

1. Najdeme kostru <math>{T_g}</math> (libovolnou) grafu G
2. Procházíme kostru <math>{T_g}</math> do hloubky. Uzly v liché hloubce přidáme při prvním vstupu do daného uzlu, uzly v sudé hloubce přidáme při posledním vstupu do daného uzlu.
   

Load je vždy 1, protože do každého uzlu přidáme max. jeden uzel.
Dilatace je max. 3 a to pouze při přechodu mezi podstromy přes společný kořen. Důkaz, že dilatace nikdy nemůže být horší než 3 je indukcí za použití faktu, že stromy jsou rekurzivní.

Dokažte, že 2D toroid T(z₁, z₂) je výpočetně ekvivalentní s 2D mřížkou M(z₁, z₂).

★ Bylo ve zkoušce: 2012-01-17 a 2015-01-06 (ale obecně pro (z₁, …, z_n))

Viz přednáška 5, FIT slide 27, FEL slide 20 nebo CZ skripta [2006] str. 85

• Sítě G a H jsou kvaziizometrické pokud G může být vnořen do H a naopak s konstantními měřítky vnoření.
• G a H jsou výpočetně ekvivalentní pokud jedna může simulovat druhou s konstantním zpomalením.
• Jsou-li sítě kvaziizometrické, tak jsou i výpočetně ekvivalentní (opačně to neplatí, protože vnoření nemohou postihnout dynamické chování aplikací na cílové síti).

<math>M(z_1,z_2)</math> se vnoří do <math>T(z_1,z_2)</math> s load = dil = ecng = 1, protože <math>M(z_1,z_2)</math> je podgraf <math>T(z_1,z_2)</math>.

<math>T(z_1,z_2)</math> lze vnořit do <math>M(z_1,z_2)</math> s load=1, dil=ecng=2 takto:

1. provedeme dekompozici <math>T(z_1,z_2)</math> na <math>T(z_1)\times{T(z_2)}</math>
2. vnořím dekomponové toroidy <math>T(x)</math> do dekomponovaných mřížek <math>M(x)</math>
3. první polovinu <math>T(x)</math> uzlů namapuji na liché uzly <math>M(x)</math> a druhou polovinu uzlů <math>T(x)</math> namapuji na sudé uzly <math>M(x)</math>.

Na liché uzly mapuji vzestupně a na sudé sestupně.

V podstatě je to stejné jako mapování kružnice na kostru, která je pouze lineárním seznamem. Viz předchozí úkol. Důkaz možnosti vnoření kružnice do libovolného G s load=1, dil⇐3.

Trocha teorie:

• dil - dilatace - maximální délka obrazů zdrojových hran v cílové siti
• load - zatížení - max počet zdrojových vrcholů mapovaných na 1 uzel
• ecng - linkové zahlcení - maximální počet obrazů zdrojových hran procházejících skrz cílové linky, tj. kolik cest vede přes 1 hranu

Kolik udělá permutací nepřímá síť, která má k úrovní, N čísel na vstupu, jeden přepínač 2 × 2.

★ Bylo ve zkoušce: 2012-01-03 a 2015-01-06

Viz přednáška 4, slide 37 FEL; slide 42 FIT; EN skripta [2010] str. 48

V každé úrovni je <math>\normalsize {\Large\lceil} \frac{N}{2} {\Large\rceil}</math> přepínačů. Pokud je N liché, tak poslední nemůže přepínat, takže se použije jen <math>\normalsize {\Large\lfloor} \frac{N}{2} {\Large\rfloor}</math>. Každý přepínač se může vyskytovat v jednom ze dvou stavů – rovně nebo křížem (=, ×). Každá úroveň tedy může vytvořit <math>\normalsize 2^large_lfloor_frac_n_2_large_rfloor</math> permutací. Protože síť má k úrovní, může tedy vytvořit <math>\normalsize {\rm min}\bigl(2^{\lfloor\frac{N}{2}\rfloor k}, N!\bigr)</math> permutací (N! je maximální počet permutací N prvků).

V přednášce 4, slide 39 (2011), je “Přepínače 2 x 2 mohou být v 1 ze 4 stavů”, proč tady se tedy píše jen o dvou stavech?

Po použití druhých dvou stavů (upper/lower broadcast) by již něslo o permutaci. Ztratil bych totiž jeden ze vstupů.

Odvodit průměr na oBFn.

Viz přednáška 4/2014, FIT slide 37

diam(oBFN) = 2*n

Stačilo pouze vysvětlit, že je to vzdálenost mezi nejvzdálenějšími uzly.

Já tam (za 2 body) napsal něco takového + nakreslil <math>oBF_3</math>. Předpokládám, že bez posledního odstavce by to tedy takto šlo použít i pro <math>wBF_n</math>:

<math>wBF_n</math> vzniká z <math>Q_n</math> nahrazením každého uzlu kružnicí <math>K(n)</math> a zároveň zdvojením hyperkubických hran tak, že nespojují jen dva stejnolehlé uzly, ale uzly sousední, jak nalevo, tak napravo. Průměr je vzdálenost mezi nejvzdálenějšími uzly, u <math>wBF_n</math> je tedy tvořen průměrem <math>Q_n</math>, což je <math>n</math> a průměrem <math>K(n)</math>, což je <math>\lfloor \frac{n}{2} \rfloor</math>.

<math>oBF_n</math> vzniká z <math>wBF_n</math> tak, že se “horní” uzel kružnice v rozdělí na dva a kružnice se vlastně nahradí mřížkou <math>M(n+1)</math>. Průměr <math>oBF_n</math> je tedy tvořen průměrem původní <math>Q_n</math>, což je <math>n</math> a průměrem <math>M(n+1)</math>, což je rovněž <math>n</math>.

⇒

<math>diam(oBF_n) = 2n</math>

★ Bylo ve zkoušce: 2015-01-28

Odvodit průměr na wBFn.

★ Bylo ve zkoušce: 2012-02-03

Viz přednáška 4, FIT slide 35, FEL slide 35 nebo skripta CZ [2006] str. 66, EN [2009] str. 47

Uzel ve <math>wBFn</math> je dvojice <math>(i,x), 0\leq{i}< n, x=B^n, B=\lbrace0,1\rbrace</math>.
Hrana je definována mezi uzly <math>(i,x)</math> a <math>(j,y)</math> pokud

• a) <math>x=y</math> a <math>j=i\oplus_n{1}</math> (pohyb po kružnici)
• b) <math>j=i\oplus_n{1}</math> a <math>y=neg_i{x}</math> (pohyb po hyperkubických hranách)
  

⇒ pokud se <math>{x}</math> a <math>{y}</math> liší v <math>{n}</math> bitech, je zapotřebí <math>{n}</math> hyperkubických hran ke změně <math>{x}</math> na <math>{y}</math>, teda z uzlu <math>(i,x)</math> se dostanu do <math>(i\oplus_n{n},y)=(i,y)</math>
V nejhorším případě musí ještě udělat <math>\left\lfloor {\frac{n}{2}} \right\rfloor</math> kroků v této kružnici ⇒ <math>n + \left\lfloor {\frac{n}{2}} \right\rfloor</math> kroků
⇒ <math>\phi(wBF_n)=n + \left\lfloor {\frac{n}{2}} \right\rfloor</math>

Pozn. by Vity: Ty pohyby po topologii možná vypadají děsně, ale podívejte se přitom na obrázek a co to dělá s těmi hranami - jak se mění index řádku <math>{i}</math> a index sloupce <math>{x}</math> (což je de facto sloupeček s tou kružnicí) a zjistíte, že to už dávno umíte.

Pozn. Když jsem si to zkoušel na obrázku pro n=3, zarazilo mě, že se nemůžu dostat po hyperkubických hranách do 010, jak tedy dokážu, že je výše zmíněný průměr správně? Musím se dostat za n tahů do správného sloupce. To udělám tak, že procházím bity odzadu. Pokud se shodují, udělám pohyb po kružnici, jinak udělám pohyb po hyperkubické hraně. Poté kontroluji další bit.

<math>wBF_n</math> je uzlově symetrický, proto je tato vzdálenost pro všechny uzly stejná

Viz přednáška 4, FIT slide 25, FEL slide 20 nebo CZ skripta [2006] str. 59 a EN [2010] str. 41

• Pro všechny uzly ve vzdálenosti i od našeho uzlu v Q_n platí, že se jejich adresa liší v i bitech (dimenzích). Počet uzlů ve vzdálenosti i je <math>{n \choose i}</math>, tj. všechny možné kombinace i bitů.
• Na vše se můžeme podívat stylem, že máme uzel, jehož adresa má samé nuly = n nul. Ve vzdálenosti i jsou uzly, jejichž adresa má (n - i) nul a i jedniček. Takže se ptáme, kolik existuje kombinací i jedniček a (n - i) nul ve vektoru délky n, tj. <math>{n \choose i}</math>.
• Krychle je uzlově symetrická, z každého uzlu vypadá graf stejně, takže pro každý uzel platí to samé.

★ Bylo ve zkoušce: 2012-12-18 2012-05-18

Poloměr je minimum z excentricit. Excentricita pro uzel udává, jak je od něj vzdálený nejvzdálenější uzel. 2D toroid nemusí být hranově symetrický, protože může mít různě dlouhé dimenze, ale je uzlově symetrický. Rozložit si ho lze na kartézský součin kružnic. Má-li kružnice <math>z</math> uzlů, nejvzdálenější v ní je ve vzdálenosti <math>\lfloor\frac{z}{2}\rfloor</math> – tedy je někde v pomyslné polovině, přičemž tam půjdu tou kratší stranou. Nejvzdálenější uzel ke každému uzlu bude takový, když se v každé dimenzi hnu o těch <math>\lfloor\frac{z}{2}\rfloor</math> – tedy excentricity všech uzlů by měly vyjít stejně, a to jako suma <math>\lfloor\frac{z_i}{2}\rfloor</math> přes všechny dimenze, tzn. ve 2D <math>\lfloor\frac{z_1}{2}\rfloor + \lfloor\frac{z_2}{2}\rfloor</math>, kde to <math>z</math> se mění a je to počet uzlů v dané dimenzi. Poloměr by měl být minimum z těchto stejných hodnot, takže je to to samé.

Domněnka by voho: uzlově symetrické grafy mají excentricitu všech uzlů stejnou.

Edit by plech.d: Ano a to navíc znamená, že u US grafů je poloměr roven průměru.

Obecně:

<math>\text{radius}\left(K\left(z_{1},z_{2},\dots,z_{n}\right)\right)=\text{diam}\left(K\left(z_{1},z_{2},\dots,z_{n}\right)\right)=\sum_{i=1}^{n}\left\lfloor \frac{z_{i}}{2}\right\rfloor</math>

Poloměr grafu je minimum z excentrit. Excentricita uzlu je nejkratší možná vzdálenost do nejvzdálenějšího uzlu. Krychle je uzlově symetrická, všechny uzly budou mít stejnou excentricitu – nejvzdálenější uzel od zvoleného uzlu je ve vzdálenosti n – jde o to, že mám n dimenzí, a všechny musím zinvertovat. Hledáme minimum z hodnot, které jsou všechny n, takže výsledek by měl být n.

Ještě jinak: excentricita(u) = maximální vzdálenost z uzlu u na kraj grafu. Což v případě <math>Q_n=n</math> (vždycky)
poloměr = minimální excentricita (ze všech uzlu)
průměr = maximální excentricita (ze všech uzlu)
Takže poloměr v <math>Q_n</math> = průměr = n

Domněnka by voho: uzlově symetrické grafy mají excentricitu všech uzlů stejnou.

Důkaz sporem by wabbit: Nechť G je uzlově symetrický graf a mějme automorfismus <math>f:f(v)=u</math>, předpokládejme že:

<math>\exists u, v \in V(G): exc(u) \gt exc(v)</math> potom by platilo že <math>exc(u) \gt exc(f(v))=exc(u)</math> což neplatí

★ Bylo ve zkoušce: 2016-05-26

<math>\text{radius}\left(M\left(a,b,c\right)\right)=\left\lceil \frac{a}{2}\right\rceil +\left\lceil \frac{b}{2}\right\rceil +\left\lceil \frac{c}{2}\right\rceil </math>

(sry za špatné formátování, ale je to třikrát horní část)

EDIT: podle mýho dolní celá část.

★ Bylo ve zkoušce: 2014-02-12

Dimenze k = počet *, např. 101*0* je dvourozměrná podkrychle

počet podkrychlí = (kolika způsoby můžeme rozmístit hvězdičky) * (počet kombinací zbývajících 0 a 1)

<math>n_choose_k{\cdot}2^{(n-k)}</math>

Podrobněji

Všimněmě si, že se jedná o zobecnění tvrzení o počtu hran na <math>Q_{n}</math>, kde se tvrdí, že to je <math>n\cdot2^n</math>, což odpovídá tomuto vztahu. Dimenze nám definuje jaké podkrychle hledáme. Dimenze 0 tedy znamená, že hledáme vrcholy a dimenze 1 počet hran.

Pokud hledáme vyšší dimenze, tak bereme v potaz dvě operace. Kolik kombinací dimenzí můžeme “zafixovat” (např pro dimenzy 2 jde o: <math>(d_1,d_2),(d_1,d_3),…(d_{n-1},d_n)</math>). Pro každé toto zafixování generujeme všechny možné variace s opakováním jedniček a nul. Máme však už jen omezené množství dimenzí. (Například pro dimenzi 2 už máme pouze <math>n-2</math> volných pozic pro variace. Na ty pozice postupně generujeme všechny možné variace: <math>(0,0…0),(0,0…0,1),…(1,1…1))</math>. Jejich význam je takový, že nám každá konkrétní variace definuje jednu konkrétní podkrychli.

Příklad

Mějme dimenzi 3, tudíž krychli.

1. k=0, (body), každá variace definuje konkrétní souřadnice bodu [0,0,0] je bod
2. k=1, (hrany), každá variace definuje konkrétní dva body, které tvoří hranu [0,0,*] ⇒ umožňuje dosadit [0,0,0] a [0,0,1], což nám jednoznačně určuje hranu
3. k=2, (čtverec), každá variace definuje konkrétní 4 body, které dohromady tvoří čtverec [0,*,*] ⇒ umožňuje dosadit [0,0,0], [0,0,1], [0,1,0] a [0,1,1], což nám jednoznačně určuje čtverec
4. k=3, (krychle), ta je v krychli jen jedna, neboť 3 proměnné dávají pouze jednu možnost [*,*,*] ⇒ umožňuje dosadit [0,0,0], [0,0,1], [0,1,0], [0,1,1], [1,0,0], [1,0,1], [1,1,0] a [1,1,1], což nám jednoznačně určuje krychli

Možností na zafixování dimenzí odpovídá problému “kolik kombinací k dimenzí můžu vybrat z n” ⇒ kombinace bez opakování

Kolik takových podkrychlí existuje odpovídá “kolik je možností jak zapsat 1 a 0 do <math>n-k</math> pozic” ⇒ variace s opakováním

Uvažujte bijekci <math>f: V(Q_7) \to V(Q_7)</math>, o níž pouze víme, že f(0101110) = 1010110 a f(1101010) = 0101111. Může být f automorfismem hyperkrychle Q₇? Svoji odpověď zdůvodněte.

★ Bylo ve zkoušce: 2013-01-23, 2012-06-26, 2014-02-04

Automorfismy v krychli vzniknou přeložením a permutace a nebo kombinací obojího. Ani jedna operace nemění hammingovu vzdálenost vzorů a obrazů (musí platit, že hammingova vzdálenost dvou obrazů odpovídá vzdálenosti jejich vzorů - aneb sousedi zůstávají sousedy!). Když si spočtu vzdálenost obrazů a vzorů, vyjde pro oba automorfismy jiná (vzory mají 2 a obrazy 5). Nejedná se o stejný automorfismus na krychli, neboť původně byli v krychli vzdálení 2 dimenze (cesta 2 hran) a v automorfismu by byli vzdáleni 5 (cesta o 5 hranách).

Nemůže - automorfismy hyperkrychle nastávají při kombinaci permutací a negací adresových bitů.
Když se ty dvě posloupnosti napíšou pod sebe, tak originální adresy mají 5 stejných sloupců. Nové adresy ale mají jen 2 stejné sloupce, což by nemělo nastat.

Pozn. by Kugel: Ja si myslím, že jednoduchšie to je takto: Povedzme, že prvé <math> f </math> nám definuje automorfizmus, teda je to buď posun alebo rotácia. Rotácia to určite nie je, pretože 0101110 má 3 jedničky po sebe a 1010110 nemá, takže rotácie určite nie. Ešte by to mohol byť posun. Definovaný takto: <math>{f}_{u \rightarrow v}(x) = x \oplus (u \oplus v)</math> teda <math>{f}_{u \rightarrow v}(1101010) = 1101010 \oplus (0101110 \oplus 1010110) = 0010010</math>, čo teda rozhodne nie je 0101111 ako ukazuje druhé <math> f </math> v zadaní. Pozn: Aby se zachoval automorfizmus musí se zachovat sousednost uzlů - sousedé musí zůstat sousedy, čehož docílíme aplikováním stejných operací na adresy uzlů. 7. proseminář, čas 22:40+

Pozor! Nestačí rotace nebo posun, ale může to také být jejich kombinace! Takže je třeba si vyzkoušet nalézt takovou funkci, XOR sám nestačí.

Info přímo od Tvrdíka od zkoušky: Stačí aby byla stejná Hammingova vzdálenost vzorů a obrazů. Tečka. Na vzdálenosti změněnejch bitů nezáleží.

+1, dneska jsem to přesně tak napsal a dal mi dva body ještě než jsem si sednul

Jakou adresu a dimenzi má průnik dvou podkrychlí s1 = * 0 1 * * 0 * * 1 a S2 = 1 * * 1 * 0 1 * 0 v hyperkrychli Q₉, Zdůvodněte.

★ Bylo ve zkoušce: 2012-01-31

Formálněji: sloučení vznikne použitím této funkce f na jednotlivé bity:

• f(0,0) = 0
• f(1,1) = 1
• f(0,1) = f(1,0) = prazdna množina
• f(x,0) = f(0,x) = 0
• f(x,1) = f(1,x) = 1
• f(x,x) = x

Lidsky:

Pro každou dimenzi se snažíme vyhovět oběma krychlím. Pokud jedna použije “Jokera” neboli * tak tam může být jak 0 tak 1. Jestliže se krychle liší v nějaké dimenzi, tak potom nemají průnik. Pokud k takové situaci nedojde, tak výsledek je počet hvězdiček v průniku.

Dimenze je 0 ( tím je myšleno Ø tedy žádný průnik ), neboť se krychle liší v poslední dimenzi. Výsledek znázorňuje dva protější čtverce, ale nemají průnik, neboť je každý v trochu jiné dimenzi.

Kdyby bylo zadání: <math>s_1 = *0101</math> a <math>s_2 = 1**1*01*1</math>

1. sloučíme dohromady: <math>s = s_1 \cap s_2 = 1011*01*1</math>
2. dimenze průniku je 2
3. Průnik jsou body [1,0,1,1,[0|1],0,1,[0|1],1]

škola zkoušky s_řešením