Převzato z Exfort Wiki za účelem dalšího zušlechťování. Původní verze z Exfort je k dispozici v PDF.

Určete spodní mez na uzlové zatížení (load) vnoření 3-D mřížky <math>M(z_1, z_2, z_3)</math> do 2-D toroidu <math>K(w_1, w_2)</math>.

★ Bylo ve zkoušce: 2013-01-30, 2013-12-20

Dle mého názoru se jedná o obecnou spodní mez pro load, který vnikne vnořením jednoho grafu do druhého.

Takže jednoduše poměr počtu uzlů grafu vnořovaného (M(…)) k počtu uzlů grafu, do kterého vnořujeme (T(…)).

<math>max(1, \lceil \fracz_1_cdot_z_2_cdot_z_3w_1_cdot_w_2 \rceil)</math>

Edit: Kdyz tam das horni celou cast, uz nemusis resit nejaky max(1,…), vzdy ten <math>\lceil zlomek \rceil</math> vyjde minimalne 1

Edit2: Edit ma pravdu.

★ Bylo ve zkoušce: 2014-01-13

Stejně jak předchozí, akorát s jinými hodnotami

- Motýlek dimenze n má více uzlů než mřížka M(n,n), proto uzlové zatížení musí být nutně větší nebo rovno poměru počtu uzlů obou grafů:
<math>|V(wBF_n)| = n*2^n
|V(M(n,n))| = n*n
load(\varphi , \xi ) \geq \lceil \frac{|V(wBF_n)|}{|V(M(n,n))|} \rceil = \lceil \frac{n*2^n}{n*n} \rceil = \lceil \frac{2^n}{n} \rceil</math>

<math>\frac{2^n}{n} \geq 2</math>, proto není třeba dělat max(1, load)

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

• V jednom kroku lze informovat max. n sousedů (kde n je dimenze)
• Každý uzel musí dostat <math>N-1</math> zpráv, <math>N=2^n</math>
• Spodní mez na počet kroků k obdržení všech zpráv je tedy <math>\frac{2^n-1}{n}</math>

Trocha teorie:

• AAB - kolektivní komunikační operace typu vysílání všichni-všem

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. Inf_i = Inf_i-1(2n) + Inf_i-1 ⇒ Inf_i = Inf_i-1(2n + 1) = (2n + 1)(2n + 1)Inf_i-2 = …. 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>

Trocha další teorie:

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

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

EN skripta pg. 168

• n=dimenze, N=počet uzlů
• Uzel může v každém kroku přijmout 2n zpráv
• 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{N-1}{2n}</math>

Spodní mez pro <math>T(z_1,z_2,z_3)</math> tedy vychází <math>\rho_{AAB} = \frac2013-01-09]] a [[škola:předměty:mi-par:par_zkouska_2014-01-06|2014-01-06]]// ==== Řešení ==== Mřížka má evidentně lichý počet uzlů, které musím všechny právě jednou navštívit. Bez ohledu na počáteční uzel, neboť se do něj musím vrátit. Vykonám tedy **lichý** počet kroků. Nyní vytvořím 2D vektor, odpovídající rozměrům mřížky podle počtu hran, dostanu (000000,0000) - mezi sedmi uzly je šest hran, ve druhém rozměru pak čtyři. Zajímají mě skupiny hran, ne jednotlivé hrany, nebo dokonce uzly. Nyní si vyberu jakýkoli uzel a udělám jeden krok - podle vybrané hrany provedu negaci bitu ve vektoru. Můžu jich provést kolik chci, ale je zřejmé, že abych se dostal do výchozího uzlu, musím provést za každý krok právě jeden zpět. Tedy **sudý** počet kroků. **=> spor** :!: Dodatek by Empire: V podstate do funguje stejne jako je dukaz na Qn, jen misto negace je tu parita (0-suda, 1-licha) dane souradnice vektoru. Parita parity je stejny jako negace negace. Takhle mi to uznal. ===== Cykly liché délky na 2-D toroidu T(6,10) ===== Dokažte, že na 2-D toroidu T(6,10) neexistují cykly liché délky. ==== Řešení ==== **Důkaz:** 2-D toroid vznikne jako kartézský součin 1-D toroidů **K₁(6)** a **K₂(10)**. Na **K₁** ani **K₂** neexistuje cyklus liché délky, tato vlastnost se po operaci kartézského součinu zachová. Jinými slovy, pokud se pohybuji jen po hranách, které jsou shodné s mřížkou stejných rozměrů, vykonám vždy sudý počet kroků (jdu tam a zpátky, inkrementuju a potom dekrementuju nějakou souřadnici v libovolném pořadí). Abych udělal lichý počet kroků, musel bych použít hranu kružnice, která má lichou délku. ===== Cyklus liché délky v n rozměrné hyperkrychli ===== Dokažte, že cyklus v hyperkrychli nemůže být liché délky. ==== Řešení ==== Neberte to jako dogma, ale podle toho, jak mi vysvětloval Tvrdík je to:\\ - možnost Důkaz, že v malé (3D krychli, popřípadě 2D čtverci) není cyklus liché délky a analogicky nějak potvrditl, že přidáváním hran se prodlužuje kružnice=cyklus a zůstává tohle zachováno.\\ - asi lepší důkaz, ale složitější - důkaz indukcí: v n-D krychli budu tak dlouho odebírat dimenze, až se mi rozpadne cyklus na dva malé cykly a potom se musí dokázat, že každá z těch dvou částí bude dohromady sudá. - podle slajdu - negací bitů: pokud cyklus, tak končí a začíná v jednom uzlu. Ten má adresu <math>b_n b_{n-1} ... b_0</math>. Pokud chci dělat cyklus, musím z něj cestovat - každá jedna hrana v cyklu = negace nějakého bitu. Pokud se mám dostat do stejného bodu, musí těchto negací být sudý počet (vždycky tam a zpátky). Tedy sudý počet hran, tedy sudá kružnice. :?: K 3ti moznosti - v hyperkrychli jsou uzly v binarnim zapisu jen <math>b_n b_{n-1} ... b_1</math> Napr. bitovy zapis <math>Q4</math> ma jen 4 bity. ====== Nejkratší cesty, počet cest ====== ===== Počet všech nejkratších cest mezi dvěma uzly v n-dimenzionální mřížce ===== ==== Řešení ==== Zde je třeba rozlišit, jestli se jedná o disjunktní cesty nebo všechny cesty. * Disjunktní cesty: * Uzlově disjunktní cesty nesmí sdílet žádný uzel, až na ty koncové. * Hranově disjunktní cesty nesmí sdílet žádnou společnou hranu. * Uzlově nebo hranově(?) disjunktních cest existuje tolik, v kolika se uzly liší dimenzích. * Všechny cesty: * Viz video z prosemináře 06/2008 od 2:30. Zde je to uvedeno pro 2 dimenze. * Pro dvě dimenze si představme obdélník o stranách x a y, v jehož rozích jsou vrcholy u a v. * Nejkratší cesty leží v tomto obdélníku. Všechny nejkratší cesty mají délku <math>\normalsize d=x+y</math>. * Cestu si můžeme představit jako d-rozměrný vektor čísel, každé číslo ve vektoru znamená směr, kterým se vydáme (index dimenze číslovaný od 0 - tedy v 2D mřížce např. 0=X, 1=Y). Pokud třeba směr x bude 0 a y bude 1, tak takový vektor může vypadat třeba <math>\normalsize (0,0,1,0,1,1,1)</math>. Odpovídá to cestě doprava, doprava, nahoru, doprava, nahoru, nahoru, nahoru. V tomto případě tedy <math>\normalsize x=3,\: y=4</math>. Cesta má délku <math>\normalsize d=7</math>. * Počet všech nejkratších cest tedy převedeme na úlohu vybrání 4 jedniček ze 7 možností, což je <math>\normalsize {{x+y}\choose{y</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á. Edit apelttom: nemyslím si, že obě 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>\frac{(\sum_{i=1}^{n} |u_i - v_i|)!}{\prod_{i=1}^{n} |u_i - v_i|!}</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 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.

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>.

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}}}u_1\oplus_{_{z_{1}}}v_1,x_2\oplus_{_{z_{2}}}u_2 \oplus_{_{z_{2}}}v_2,x_3\oplus_{_{z_{3}}}u_3 \oplus_{_{z_{3}}}v_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 uzli (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}</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.

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.

Pozn: Bacha, na untitled03 ma na konci, ze <math>CBT_n</math> sa neda vlozit do <math>Q_{n}</math>, co je jasne aj bez ofarbenia, pretoze <math>Q_{n}</math> ma ovela menej uzlov ako <math>CBT_n</math>. Autor tym myslel do <math>Q_{n+1}</math>

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

<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

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> (do šířky) 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ě.

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ů).

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.

<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.

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: 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>

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

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.

V případě automofismu Q(n) musí být zachována hammingova vzdálenost dvojic zobrazených uzlů - což v tomto případě není (původní 2 adresy jsou vzdálené 2 bity, zobrazené pak 5 bitů).

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+

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

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čí.

Úplně nejjednodušší řešení: automorfismy v krychli jsou přeložení a permutace. Ani jedna operace nemění hammingovu vzdálenost. Když si spočtu vzdálenost obrazů a vzorů, vyjde pro oba automorfismy jiná ⇒ nejedná se o stejný automorfismus na krychli

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

• Obecné řešení:
  1. když si to napíšeš pod sebe a v některém bitu, kde není *, se liší, automaticky je průnik nulový
  2. jinak, pokud je někde hvězdička, dáš tam hodnotu bitu z druhé krychle
  3. dimenze je potom počet hvězdiček ve výsledku
• konkrétně pro toto zadání:
  1. podkrychle se liší v nejnižším bitu, takže průnikem je prázdná množina
• kdyby bylo zadání: <math>s_1 = *0101</math> a <math>s_2 = 11*01*1</math> - v prvním a 4 bitu (tam, kde jsou nad sebou čísla) se shodují, jdeme dál - sloučíme dohromady: <math>s = s_1 \cap s_2 = 1011*01*1</math> - dimenze průniku je 2 Dodatek by voho: 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 | S1 | x | 0 | 1 | x | x | 0 | x | x | 1 | | S2 | 1 | x | x | 1 | x | 0 | 1 | x | 0 | | Sloučení f(S1[i],S2[i]) | 1 | 0 | 1 | 1 | x | 0 | 1 | x | 0 | Dimenze je počet “x” ve výsledku, v tomto případě 2. Edit by plech.d: Ta tabulka je nějaká divná, odporuje funkci, jaks ji definoval. V posledním sloupečku je 0 a 1, čili výsledkem je prázdná množina. Ten rozdílný bit způsobí, že jsou to dvě různé podkrychle. Třeba dvě protější úsečky na ve čtverci. ====== Passé (neprobíralo se) ====== ===== Chybový průměr hyperkrychle Qn ===== ★ Na konzultaci říkal že už to tam nedává. Uveďte a dokažte vztah pro chybový průměr hyperkrychle Q_n. ==== Řešení ==== * Chybová vzdálenost mezi u a v je maximum z délek všech možných a co nejkratších uzlově disjunktních cest mezi u a v. * fault distance between u and v is the maximum over the lengths of paths between u and v in all possible graphs, made from G by removing connectivity(G) - 1 verticies. * Chybový průměr je maximum ze všech chybových vzdáleností. V <math>Q_n</math> mezi uzly u a v, které se liší v <math>{k}</math> bitech, existuje: * <math>{k}</math> cest délky <math>{k}</math> * <math>{n-k}</math> cest délky <math>{k+2}</math> Nejhorší případ je pro uzly lišící se v <math>{n-1}</math> bitech
  ⇒ existuje tedy <math>{n-k}</math> cest délky <math>{k+2=n-1+2=n+1}</math> (chybová vzdálenost)
  ⇒ chybový průměr je <math>{n+1}</math> Důkaz**: Pokud se liší v <math>{k}</math> bitech, pak min. cestu získám lib. permutací P těchto dimenzí. Dalších <math>k-1</math> cyklických posuvů generuje tedy celkem <math>{k}</math> nejkratších cest. Dalších <math>n-k</math> hran z uzlu využiji tak, že pomocí kterékoli z nich se přesunu do jiné dimenze, v ní pak použiji lib. permutaci <math>{k}</math> dimenze určujících min. směrování a na konec se vrátím zpět stejnou dimenzí jako na začátku ⇒ <math>n-k</math> dalších cest délky <math>1+k+1=k+2</math>.

Pozn.: Výpočet chybového průměru <math>Q_n</math> je v českých skriptech špatně.

EN skripta [2009] str. 41 (lemma 3.17 and corollary 3.18).

PDF přednáška 4/10

Je graf <math>CCC_n</math> bipartitní? Svoji odpověď konstrukčně dokažte.

★ CCCn nebylo probráno.

Je, a to pro sudá n. Na konzultacích nám ukázal, že se to dokazuje na obrázku pohledu z vrchu (je vidět kružnice + ocásky do dalších kružnic). Přechodem na jinou kružnici se změní parita, takže stačí, když jsou kružnice sudé a liché parity obarveny inverzně.

Edit: Ja to okomentujem trochu odlisne. <math>CCC_n</math> je podgrafom kartezskeho sucinu Qn a Kn. Qn je vzdy bipartitne, Kn len pre parne (sude) n. To, ci je bipartitny aj podgraf kartezskeho sucinu sa zisti rozborom hran veducich do ostatnych kruznic. Hrana je popisana dvojicou uzlov <(i,x), (i, negi(x))>. Vzdy sa neguje prave jeden bit → zarucene sa meni parita. To plati pre vsetky uzly danej kruznice → hrany vedu vzdy medzi kruznicami opacnej parity. CBTD

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