Differences

This shows you the differences between two versions of the page.

--- users:martin.kocicka:pdp:6b [2017/06/13 09:48] – vytvořeno martin.kocicka
+++ users:martin.kocicka:pdp:6b [2017/06/13 10:16] (current) – martin.kocicka
@@ Line 20: / Line 20: @@
 :!://Viz skripta CZ [2006] str. 87 nebo EN [2009] str. 70//
-{{:škola:předměty:mi-par:vyřešené_příklady:m2224_do_mx5.png?600|}}
+{{:škola:předměty:mi-par:vyřešené_příklady:m2224_do_mx5.png?500|}}
 <math>\frac{22}{2}=11</math>\\
@@ Line 54: / Line 54: @@
 To poslední mapování hrany, ten modrý oblouček co začíná nejvíc vpravo nepřechází přes tu hranu, kterou pozorujeme ( svislá růžová čára ), takže ta se do ecng nepočítá, ale tlusta cervena vodorovna hrana, ktera tu svislou caru krizuje ( spoj v rámci stejnýho sloupce ) už jo.
-===== Algebraické vnoření CBTn do Qn+1 =====
-  - Dokažte, že **úplný binární strom** o výšce //n//, <math>CBT_n</math>, **nemůže** být **podgrafem hyperkrychle** <math>Q_{n+1}</math>. \\
-  - Pak popište algoritmus pro vnoření <math>CBT_n</math> do <math>Q_{n+1}</math> s load = ecng = 1 a dil = 2, kde dilataci 2 má jediná hrana. Aplikací tohoto algoritmu zkoustruujte a **algebraicky** popište vnoření <math>CBT_3</math> do <math>Q_4</math>.
-★ //Bylo ve zkoušce: [[.:par_zkouska_2012-12-18|2012-12-18]]//
-==== Řešení ====
-{{:škola:předměty:mi-par:cbtinq.pdf|zdroj}}
-=== První část ===
-viz [[par_řešené_příklady_2b#vnoření_cbtn_do_qn_1|Vnoření CBTn do Qn+1]] - barvení grafu, strom má nepoměr barev, krychle má stejné množství uzlů obou barev.
-=== Druhá část ===
-:!://viz. 7. proseminář 2008, je to tam fakt dobře vysvětlené//
-:!:// viz česká skripta 2006 strana 80 //
-Zakladní myšlenka algoritmu je zdvojení kořenu CBT<sub>n</sub>, čímž vznikne vyvážený bipartitní graf CBT<sub>n</sub>' s 2<sup>n+1</sup> uzly a dilatací 2 na jedné hraně. Algoritmus je indukční přes dimenzi n. Indukční základ a indukční krok je ukázán na následujícím obrázku:
-{{:škola:předměty:mi-par:vyřešené_příklady:cbt_do_q_indukce.png?640|Indukční základ a indukční krok}}
-Indukční základ (a) ukazuje vnoření <math>CBT_1</math> do <math>Q_2</math>. Máme-li <math>CBT_{n-1}</math> vnořenou do <math>Q_{n}</math> (b), jejím zrcadlením pomocí transformace a následným spojením dostaneme v indukčním kroku <math>CBT_{n}</math> vnořené do <math>Q_{n+1}</math> %%(c)%%. Transformace souřadnic, kterou získáme zrcadlový obraz, je určena těmito třemi transformacemi:\\
-<math>
-' = 1\to2\\
-' = 2\to3\\
-' = 3\to4
-</math>\\
-Konkrétně, vnoření <math>CBT_2 \to Q_3</math> a <math>CBT_3 \to Q_4</math> podle následujícího obrázku je definované takto:
-{{:škola:předměty:mi-par:vyřešené_příklady:cbt_do_q_vnoreni.png?640|Vnoření CBT3 do Q4}}
-|          přesun          ^ Výchozí adresa <math>abc</math> ^ Cílová adresa <math>a'b'c'</math> ^
-^  <math>1\to2\\</math>  |                000                |             100                     |
-^  <math>2\to3\\</math>  |                100                |             101                     |
-^  <math>3\to4\\</math>  |                101                |             111                     |
-Ve výsledné transformaci lze použít pouze permutaci pořadí a negaci (automorfismus), pretože musíme zachovávať vzdálenosti. Transformace je popsaná vzorcem <math>\varphi(abc) = \bar{b}ca</math>.
-:?: //Co mi není jasné je, zda to stačí takto, či zda je potřeba provést explicitně pomocí algoritmu i přechod z Q2 do Q3. V PDFku to není, a na scanech je ten mezikrok sice zmíněn, ale proveden metodou kouknu a vidím.//
-Ten krok z Q2 do Q3 se dělá úplně stejně jako zmíněný Q3 do Q4. Akurát že uzly se indexují dvěma bity. Mapování se provádí obdobně 00->10, 10->11 .. atp. Opět jde vždy o to, nalézt 4 významné uzly (v pripadě Q2 jde o všechny jeho uzly) u obou kopií - dvou Q2jek. Tyto významné uzly jsou následně propojeny nalezenou mapovací funkcí a dále jsou také umazány dve hrany z původních Q2jek (jedu stale dle obrazku).
-pre 4D ->5D. V 4D krychli nájdeme 4 významné uzly, zistíme ich adresy (budú to 4bity). Nová tabuľka bude popisovať presuny z 1->2, 2->3, 3->4.
 ====== Algoritmy ======
-===== Offline permutační směrování na nepřímé Benešově síti =====
-Máme nepřímou Benešovu síť. Popište, jak se offline vytvářejí cesty pro permutace, a znázorněte, jak je vytvoříte pro konkrétní zadanou permutaci 1->3, 2->0, 3->5, 4->4, 5->2, 6->7, 7->1, 0->6.
-★ //Bylo ve zkoušce: [[.:par_zkouska_2012-02-03|2012-02-03]] a [[par_zkouska_2013-01-02|2013-01-02]]//
-==== Řešení ====
-:!://Viz skripta CZ [2006] str. 163 nebo EN [2009] str. 142//
-Cesta se tvoří rekurzivně. Benešova síť <math>BN_n</math> obsahuje sloupce <math>2^n</math> křížových přepínačů na vstupu, dvě Benešovy sítě <math>BN^{0/1}_{n-1}</math> nad sebou a <math>2^n</math> křížových přepínačů na výstupu. Cesty buduji tímto způsobem
-Edit (5/16) k definici nepřímé BN. Přijde mi, že je to zde popsané trochu jinak než v EN skriptech, zde je překlad:
-Nechť <math>N=2^{n}</math>. <math>BN_{n}</math> má <math>2n-1</math> sloupců, kde každý sloupec obsahuje <math>\frac{N}{2}</math> křížových přepínačů <math>2\times2</math>. Síť má <math>N</math> vstupních a <math>N</math> výstupních kanálů. Tvrzení o horní/dolní BN už je OK.
-  - Vyberu libovolné <math> i </math> a tvořím cestu <math>i \rightarrow \Pi(i)</math>, cestu označím <math>p_1</math>. První hrana cesty vede např. do horní <math>BN^0_{n-1}</math>
-  - Najdu cestu (permutaci) <math>j\rightarrow \Pi(j)</math>, která je s <math>p_i</math> spřažená na výstupu <math>\Pi(i)</math> a <math>\Pi(j)</math> se liší právě v posledním bitu a poslední hranu této cesty <math>p_2</math> vedu do dolní <math>BN^1_{n-1}</math>.
-  - Najdu cestu <math>k\rightarrow \Pi(k)</math>, která je s <math>p_2</math> spřažena na vstupu => <math> k </math> a <math> j </math> se liší právě v posledním bitu a podívám se, zda cesta <math>p_3</math> již byla rozhodnuta (jestli horem nebo spodem). Pokud ano, byl dokončen 1 cyklus permutace a dál vyberu libovolné dosud nerozhodnuté <math>l\rightarrow \Pi(l)</math> a pokračuji steně jako v bodě 1.
-  - Pokud <math>p_3</math> ještě nebyla rozhodnuta, vedu <math>p_3</math> do opačné <math>BN_{n-1}</math> než <math>p_2</math>. Dál pokračuji obdobně pro <math>p_4</math> ... dokud nevyčerpám všechny vstupní kanály.
-  - Permutace v <math>BN_{n-1}</math> vyřeším stejným způsobem
-Postup jednoduše:
-  - Zvolím si jeden bod, kterým začnu. Ideálně třeba 0.
-  - Zvolím si směr, kterým půjdu (horní <math>BN_{n-1}</math> nebo spodní <math>BN_{n-1}</math>)
-  - Pokud např. 0 půjde do spodní <math>BN_{n-1}</math>, tak je jasné, že 1 musí jít do horní <math>BN_{n-1}</math>
-  - Podívat se do tabulky a např. pro 0->6 udělat na druhé straně to, že 6 musí jít také do spodní <math>BN_{n-1}</math>
-  - Tím pádem půjde 7 (je v páru s 6) do horní <math>BN_{n-1}</math> (stejný případ jako bod 3.)
-  - Postupně takto doplním všechny dvojice (potom zkontrolovat, jestli to opravdu sedí jako zadání - dost snadno se dá něco překouknout)
-  - A ten samý postup opakovat 2x pro menší vzniké <math>BN_{n-1}</math>
-{{:škola:předměty:mi-par:vyřešené_příklady:benes_1.png?600|}}
-{{:škola:předměty:mi-par:vyřešené_příklady:benes_2.png?600|}}
-{{:škola:předměty:mi-par:vyřešené_příklady:benes_3.png?600|}}
-Pozn by topas: Na slajdech 9/30 je sice první krok výpočtu symetrický, ale nemusí to tak být. Ta symetrie na slajdech je vcelku náhodná (dobře zvolený první krok a dobře zvolená permutace)
-Pozn by darkdiablo: imho je na tom přikladu blbě nakreslená benešova síť, viz přednáška 9 slide 29.
-Pozn. by honzab: dle mého je ta síť taky špatně, vyšlo mi to takhle:\\
-Pozn. by Hoogoo: honzab sit se zda, ze ma dobre algoritmus, ale sit je u 5 na prave strane spatne zakreslena.
-{{:škola:předměty:mi-par:vyřešené_příklady:prima_benesova_sit.jpg|}}
-Pozn. by Karry: mě takhle:
-{{:škola:předměty:mi-par:vyřešené_příklady:benes_4.jpg|}}
-Pozn. by Fry: Všechny obrázky kromě honzab jsou špatně. Nepřímá i přímá síť má dané spoje mezi přepínači viz slajdy 9/29. Jediné co se u nepřímé podle návodu mění je jak se uvnitř přepne (jak říkal Tvrdík, dostanete vytvořené spoje z továrny a vy si volíte přepnutí, aby to odpovídalo požadovaným cestám). A variant jak to uvnitř přepnout je vícero, aby to v důsledku vyšlo podle zadání, stačí se držet návodu (přepnutí nemusí být symetrické jen musíte dodržet popsaná pravidla). U přímé je jediný rozdíl, že jakoby nemáte přepínače (máte přímo připojené vstupy, takže boxů je 2x víc než u nepřímé, protože jedno jsou přepínače a jedno jen vstupy), tak jen vyberete jednu možnou cestu z těch dvou daných (např. si ji vytáhněte propiskou, ale struktura je daná od začátku).\\
-Pozn. IMHO jsou všechny obrázky správně, jde to nakreslit dvěma způsoby. Viz obrázek ze skript a z přednášek:
-{{:škola:předměty:mi-par:par_bn_skripta.jpg|}}
-{{:škola:předměty:mi-par:par_bn_prednaska.jpg|}}
-Tento obrázok som kreslil s kamošom, čo BN dal na skúške, tak snáď je dobre:
-{{:škola:předměty:mi-par:bn_ind.jpg|}}
-Pozn. 14-01-2016 Vyslo mi to stejne jako posledni barevny obrazek.
-<del>**Pozor vsichni, vsimete si, ze vetsina techto Ben siti je spatne nakreslenych, zkontrolujte to podle skript.**</del>
-:?: V čem jsou špatně? Všechny obrázky tady se liší maximálně v tom, jestli vodorovné a šikmé hrany vedou vždy ze stejné pozice přepínače (šikmá ze spodní jako ve skriptech) a nebo jestli šikmá vede vždy z té bližší pozice (jako v přednáškách). Vzhledem k tomu, že existují obě varianty BN a my v tomhle algoritmu neřešíme, jak se mají nastavit konkrétní přepínače, ale kudy mají ve výsledku jít cesty, tak je to podle mě úplně jedno a jsou tedy obě varianty zcela správné. Další v čem se liší jednotlivé obrázky nahoře je jestli jsme pro první cestu zvolili horní nebo dolní polovinu (v každé podsíti), což ale je také obojí správně, protože se téhle volbě zbytek cest přizpůsobí. (bliznjan)
-mm mas pravdu, prislo mi to, ze je dulezite kde jsou umistene jednotlive hrany.
-===== Offline permutační směrování na přímé Benešově síti =====
-Máme přímou Benešovu síť. Popište, jak se offline vytvářejí cesty pro permutace, a znázorněte, jak je vytvoříte pro konkrétní zadanou permutaci 1->3, 2->0, 3->5, 4->4, 5->2, 6->7, 7->1, 0->6.
-==== Řešení ====
-:!://Viz skripta CZ [2006] str. 163 nebo EN [2009] str. 142//
-Analogické k nepřímé síti až na to, že spřažené uzly (liší se v nejvyšším bitu) jsou tvořeny tak, aby se nepotkaly v jednom následujícím uzlu. Pro názornost s předchozím příkladem je zvolená stejná požadovaná permutace.
-Postup:
-  - zvolíme si libovolný uzel a libovolnou cestu. Např na obrázku zvolena 0 (zelená barva). K ní je spřažená 4, ta tedy musí jít nahoru.
-  - mrkneme se na síť z druhé strany - požadované cílové uzly musí jít do stejné části podsítě jako uzly z prvního kroku
-  - v druhém kroku jsme spojili zas některé uzly, tedy spřažené cesty jsou jasně dány, propojíme, mrkneme ke kterým uzlům patří a kam chtějí atd.\\
-{{:škola:předměty:mi-par:vyřešené_příklady:neprima_benesova_sit.jpg|}}
-Pozn. by Fry: propiskou je vyznačeno rozhodnutí, tužkou co je dáno konstrukcí...
-Pozn. sprazene uzly jsou v i-tem kroku ty, ktere maji rozdilny i-ty bit zleva
-Pozn. Já to v tom obrázku asi nějak nevidím, ale kde přesně má být ta zelená barva a ty čáry propiskou, o kterých se tu mluví?
-Pozn. k Pozn. Spřažené hrany jsou např. (0, 000) a (0, 100) a když jdu v (0, 000) dolů, tak musím v (0, 100) nahoru.
-===== Algoritmus pro pořadí na zřetězeném seznamu =====
-Uveďte časově optimální algoritmus pro určení pořadí (rank) ve zřetězeném seznamu n prvků na CREW (EREW) PRAM s p procesory. Zhodnoťte škálovatelnost.
-★ //Bylo ve zkoušce: [[.:par_zkouska_2013-01-16|2013-01-16]] a [[.:par_zkouska_2012-02-03|2012-02-03]] (ve variantě za 8 b)//
-==== Řešení ====
-:!://Viz skripta CZ [2006] str. 105-106; EN [2006] str. 103; předn. 7, sl. 28 [FIT 2014/15]//
-=== Algoritmus ===
-Optimální algoritmus pro tuto úlohu se jmenuje **přeskakování ukazatelů** (pointer jumping). Pro počet procesorů rovný velikosti pole (p = n) má následující podobu:
-<code>
-Vstup: pole Succ[1,...,n] ve sdílené paměti
-Výstup: modifikované pole Succ[1,...,n] a pole Rank[1,...,n]
-for i=1..n do_in_parallel {
-    if (Succ[i] == i) then Rank[i] = 0 else Rank[i] = 1
-    repeat ⌈log n⌉ times {
-        Rank[i] += Rank[Succ[i]]
-        Succ[i] = Succ[Succ[i]]
-    }
-}
-</code>
-To samé zapsané v jiné syntaxi:
-<code java>
-// arrays are 1-based
-// succs: ID prvku => ID jeho následníka
-// ranks: ID prvku => pořadové číslo v seznamu od konce */
-listRanking(int[] succs) {
-    int[] ranks = new int[ succs.length ];
-    for (int i = 1; i <= PROCESSORS; i++) do_in_parallel {
-        // pokud následník prvku je on sám (poslední prvek) -> rank = 0
-        if (succs[i] == i) ranks[i] = 0; else ranks[i] = 1;  // <RLW> = 3
-        repeat (⌈log(n)⌉) {  // <4R,L,2W>^log(n) = 7*log(n)
-            ranks[i] += ranks[ succs[i] ];
-            succs[i] = succs[ succs[i] ];  // pointer jump
-        }
-    }
-    return ranks;
-}
-</code>
-=== Složitost ===
-Pro **p = n**:
-  * <math>T(n,n) = 3 + 7 \cdot log(n) = O(log(n))</math>
-  * <math>C(n,n) = n \cdot log(n) = \Omega(n \cdot log(n)) </math>
-Pro **p < n** (každý procesor simuluje činnost n/p procesorů):
-  * <math>T(n,p) = O(\frac{n}{p} \cdot log(p))</math>
-  * -pozn. je tam log(p)? ten cyklus dělá každý procesor sám a je dlouhý log(n)
-  * <math>C(n,p) = p \cdot \frac{n}{p} \cdot log(p) = \Omega(n \cdot log(p))</math>
-Na EREW PRAM by byl výpočet zpomalen v každém kroku o <math>\log p</math>, což je čas potřebný pro zdvojení kopie načtené hodnoty.
-Algoritmus je sice časově optimální, ale ne cenově, neboť:
-<math>C(n,p) = O(n \cdot log(n)) = \Omega(SU(n));\: SU(n) = \Theta(n)</math>
-Škálovatelnost je kvůli nelokalitě dat špatná a rozdělení na více/méně procesorů to nijak neovlivní, cena bude stejně narůstat rychle.
-- není ani časově optimální ne?
-Podle skript "Any algorithm with T(n,p) matching lower bound SL(n)/p is optimal".
-Toho ale algoritmus nedosahuje, <math>SL(n) = \Theta(n)</math>, při n=p je ta spodní hranice <math>n/n= \Theta(1)</math>, my máme čas <math>\Theta(log n)</math>, což asymtoticky není to samý.
-Nebo se pletu?
-- Pozn.: souhlasím, také si myslím, že není ani časově optimální
-CZ skripta str. 106:
-Pole Succ (následovníci) v najhoršom prípade nemusí vykazovať žádnou lokalitu (nedá se rozdelit rovnomerne medzi CPU). Muže se stát, že počas lokálneho výpočtu n/p prvkov budú všetci ich succ v paměti iného CPU a teda lokálny výpočet bude theta (n/p) ukazatelů. Ich paralelné provádení bude trvat znovu n/p*log(p) kroků a z toho nejako plyne, že CENA bude <math>C = \Omega(n*log n)</math>
-Predstavte si to tak, ze puvodni pole rozsekate na mensi o velikosti p (=> bude n/p dilku), kazdy procesor tedy musi zpracovat n/p cisel => bude to trvat nejmene cas n/p * paralelni cast. Ale to je jen pripad, ze by byly vsichni nasledovnici hezky za sebou.. Pokud budou nasledovnici v ruznych blocich, bude to strasne rozhazene, takze tech iteraci bude mnohem vice. Takze vezmeme ten nejlepsi pripad a vsechny ostatni moznosti budou vzdy horsi, tzn.
-<math>T(n,p) = \Omega(\frac{n}{p} \cdot O(log(p))) = \Omega(\frac{n}{p} \cdot log(p))</math>
-:?: Kde se pro <math>p<n</math> najednou v T(n,p) i C(n,p) vzalo <math>log(p)</math> místo <math>log(n)</math>, když musím provést počet kroků pro 1 prvek v závislosti na počtu prvků za ním, a ne procesorů za ním? (bliznjan)
-Taky si myslim, ze by to melo byt log(n). (viz. prednaska 7 slide 31) (kucerjo)
-Ja si myslim, že pokud nastane ideální případ, že prvky spojáku sou v tom poli hezky za sebou a tedy může každej procesor svoji část kompletně vyřešit, potom je to <math>log(p)</math>, tedy: <math>T(n,p) = \Omega(\frac{n}{p} \cdot log(p))</math>, jinak pokud nastane nejhorší případ, že po rozdělení na <math>n/p</math> částí nejsou v žádné části přímo sousedící prvky, potom to bude <math>log(n)</math>, tedy <math>T(n,p) = O(\frac{n}{p} \cdot log(n))</math>. To pro to, že pokud si každej procesor vyřeší svou část sekvenčně (v <math>n/p</math> krocích), tak potom už bude opravdu zbývat jen <math>p</math> částí k paralelnímu řešení (proto <math>log(p)</math>), ale pokud nastane ten nejhorší případ a žádný procesor nemůže teda vyřešit sekvenčne ani ťuk, tak potom se musi řešit paralelně <math>n</math> částí. Ale jestli je to jak říkám tak by to asi mělo bejt podobně jako u PPS: v <math>\frac{n}{p}</math> krocích si <math>P_i</math> spočítá sekvenční část (tady toho v nejhoršim případě moc nespočíta, ale to, že zjistí, že sám sekveněně nemůže nic vyřešit bude trvat taky lineární čas (asi)), v <math>\frac{n}{p} \cdot log(n)</math> se provede paralelní výpočet a nakonec v <math>\frac{n}{p}</math> krocích každý procesor provede dopočet nad svými hodnotami (což je v nejhoršim případě asi zbytečnost). Takže teda celkově:  <math>T(n,p) = O(\frac{n}{p} + \frac{n}{p} \cdot log(n) + \frac{n}{p}) = O(\frac{n}{p} \cdot log(n))</math>.
-**Ale v tomhle sem nikdy nebyl moc dobrej, tak tomu nevěřte :-D. Může to někdo potvrdit?!** FIXME
-===== Velikost podstromů (PRAM) =====
-Velikost podstromů, je zadáno RANK, není nutné předpočítat. Známe AL, EL, EA.
-  * Bylo [[.:par_zkouska_2014-01-13|2014-01-13]]
-==== Řešení ====
-:!://Viz skripta CZ [2006] str. 108; EN skripta 107 - 6.7.2.2 //
-Pozn.:
-  * AL - adjacency list - seznam uzlů - AL[x] je ukazatel do seznamu hran EL
-  * EL - edge list - seznam hran, který se skládá z podseznamů hran vycházejících z jednotlivých uzlů
-  * EA - edge array - pole hran, jak jdou za sebou v eulerovské cestě
-:!: **2. varianta zadání - datové struktury (by zatretom):** :!:
-V termínu 9. 2. 2015 bylo v zadání konkrétně napsáno, že máme EL (seznam hran) a zkonstruovanou cestu v poli EK, kde EK[i] je i-tá hrana eulerovské cesty. Nic víc. Při opravě docela tepal na tom, jak pracuju s datovejma strukturama - napsal jsem pseudokód v podstatě jako tady a hned mi vytknul, co to je Rank(xy) a podobně.
-Ze zadání jsem pochopil, že v EK jsou hrany uloženy jako ukazatelé do EL akorát v pořadí tý cesty. Takže IMHO by se to mělo řešit takto (pro takto vybudované struktury):
-  * Pro rodiče potřebuju znát pořadí, takže procházím do_in_parallel přes EK.
-  * Protože pak potřebuju znát rank antiparalelního dvojčete a z EL se zpět na pořadí v EK nedostanu (znám pořadí xy, protože xy = EK[i], přes ukazatel se dostanu do EL a pak na dvojče yx, ale ukazatel zpět do EK nemám), musím si buď obohatit EL o rank nebo vytvořit vlastní datovou strukturu (to při prvním do_in_parallel zvládnu plně paralelně).
-  * Pak už můžu postupovat podle kódu tady - budu mít obohacené EL (ve skriptech značeno jako EL')
-Tato myšlenka vyjádřena pseudokódem:
-<code c>
-// Vstup: pole EK
-// Výstup: modifikovaný seznam EL`
-for i = 1 ... 2n - 2 in EK do_in_parallel{
-  EK[i].rank = i; // v poli EK[i] jsou ukazatelé na hrany v EL (EL tedy obohatím o rank)
-}
-// Vstup: EL`
-// Výstup: Parent
-for all xy in EL` do_in_parallel{
-  if (xy.rank < xy.sibling.rank) Parent[y] = x; // xy.sibling je antiparalelní dvojče (yx)
-}
-Parent[root] = null;
-// Vstup: EL`, Parent
-// Výstup: Subtree
-for all uzly i in EL` do_in_parallel{
-  Subtree[i] = (Rank[ij] - Rank[ji] + 1)/2 ; //kde j=Parent[i];
-}
-Subtree[root] = n;
-</code>
-EDIT: Předpokládám, že to, co chtěl slyšet je algoritmus ze strany 111 CZ skript, tedy POSTfixovy součet na hrany, kde dopředné mají váhu 1, zpětné 0.... pak u dvojice xy a yx, kde xy je dopředna (tedy y je potomek x) je Subtree[y] = vaha[xy]-vaha[yx].
-=== Algoritmus ===
-== Pole rodičů ==
-Na výpočet pole rodičů použijeme algoritmus(označíme hrany jako zpětné a dopředné):
-<code c>
-//Dir[xy] je příznak dané hrany
-//Rank[xy] je hodnota pořadí hrany
-for all xy in EL do_in_parallel{
-   if(Rank[xy] < Rank[yx]) {
-      Dir[xy] = F; //Forwarding(dopředná)
-      Dir[yx] = R; //retreating(zpětná)
-      Parent[y] = x;
-   }
-}
-Parent[root] = null
-</code>
-To samé zapsané v pseudokódu, který alespoň více připomíná programovací jazyk… Snažil jsem se přitom zachovat původní strukturu, aby se z toho dala správně spočítat složitost.
-<code python>
-# edges: pole hran a anti-paralelních hran (Tvrdík značí AA)
-#        [ID počátečního + ID koncového uzlu => hrana]
-# parents: pole rodičů [ID uzlu => ID jeho rodičovského uzlu]
-def findAllParents(edges) {
-    parents = array( nodes.length );
-    for edge in edges do_in_parallel {  # 4m = 4*(2n-2)
-        if (edge.rank < edge.sibling.rank) {  # <2R,L>^m = 3m
-            parents[ edge.endNode ] = edge.startNode;  # <R,W>^(m/2) = m
-        }
-    }
-    return parents
-}
-</code>
-Algoritmus dostane na vstupu pole hran a jejich anti-paralelních hran (AA), které už jsou ohodnoceny algoritmem pro výpočet pořadí na Eulerovské cestě (známe „rank“). Ty paralelně projde a zastaví se jen u těch, které jdou směrem **od kořenu** (tj. mají nižší „rank“). Počáteční uzel této hrany prohlásí za rodiče koncového uzlu, resp. zapíše do pole rodičů.
-Podle slajdů by měl ještě ukládat příznaky Dir (UP | DOWN) podle toho, kterým směrem hrana vede. Ty v těchto algoritmech ale nijak nevyužijeme, takže je zbytečné se jimi zabývat.
-Pozn. existuje ještě jeden algoritmus, který využívá právě těch UP|DOWN šipek, pokud to někoho zajímá, tak třeba v EN skriptech na straně 107 úplně dole.
-== Velikost podstromů ==
-Pak provedeme výpočet velikosti podstromů pomocí algoritmu:
-<code c>
-//Rank[ij] je vzdálenost na eulerovské kružnici od uzlu i k jeho rodiči.
-for all uzly i != root do_in_parallel{
-   Subtree[i] = (Rank[ij] - Rank[ji] + 1)/2 ; //kde j=Parent[i];
-}
-Subtree[root] = n;
-</code>
-To samé zapsané v pseudokódu, který alespoň více připomíná programovací jazyk…
-<code python>
-# nodes: pole uzlů
-# edges: pole hran a antiparalelních hran (Tvrdík značí AA)
-# parents: pole rodičů
-# subtreeSizes: pole velikostí podstromů [ID uzlu => velikost podstromu]
-def countSubtreeSizes(nodes, edges, parents) {
-    subtreeSizes = array( nodes.length );
-    for node in nodes do_in_parallel {  # <3R,L,W>^n = 5n
-        if (node.isRoot) continue;  # kořenový uzel přeskočí
-        parentNode = parents[ node ];
-        edge = edges[ node +""+ parentNode ];  # hrana ve směru k rodiči
-        subtreeSizes[ node ] = (edge.rank - edge.sibling.rank +1)/2;
-    }
-    subtreeSizes[ ROOT ] = nodes.length;
-    return subtreeSizes;
-}
-</code>
-Tento algoritmus využívá toho, že počet uzlů v podstromu je roven počtu všech hran v podstromu **dělený dvěma** (máme tu antiparalelní dvojčata!) Na vstupu dostane pole hran (AA) jako předchozí, dále pole uzlů a pole rodičů vypočtené předchozím algoritmem. Paralelně prochází pole všech uzlů, kromě kořenového. Každý najde rodiče daného uzlu **//v//** a následně hranu **//e//** vedoucí z **//v//** směrem k rodiči. Poté spočte velikost podstromu **//v//** jako rozdíl //ranku// **//e//** a //ranku// jejího dvojčete +1 a celé děleno dvěma.
-Zde přikládám ještě pro úplnost druhou variantu algoritmu (viz EN skripta s. 107 úplně dole), která pracuje s počítáním DOWN hran ve stromu.
-<code python>
-def EREW_PRAM_AllSubtreeSizesII(EA[])
-{
-  # [1, ..., n]
-  SubtreeSizes = array(EA.Length)
-	for edge in EA do_in_parallel {
-		if edge.Direction == DOWN:
-			ea.Weight = 1
-		else
-			ea.Weight = 0
-	}
-	# postfixový součet!
-	PSS(EA, attribute=Weight)
-	for edge in EA do_in_parallel {
-		if edge.Direction == DOWN:
-			SubtreeSizes[edge.EndNode] = edge.Weight - edge.Sibling.Weight
-	}
-	SubtreeSizes[ROOT] = EA.Length # Počet všech uzlů grafu
-	return SubtreeSizes;
-}
-</code>
-A takto je vizualizace algoritmu výše:
-{{:škola:předměty:mi-par:image_4a.png?400|}}
-=== Složitost ===
-Počet procesorů nutný k provedení algoritmu v O(1) krocích je <math>\normalsize p = 2n-2</math> (tj. rovný početu hran). Při menším počtu procesorů <math>\normalsize p < m;\: m = 2n-2</math> se složitost zvýší na:
-<math>T(n,p) = O(\frac{2n-2}{p}) = O(\frac{n}{p})</math>, <math>C(n,p) = p \cdot (\frac{n}{p}) = O(n) = O(SU(n))</math>.
-Jedná se tedy o plně paralelní algoritmus.
-**JDU:** Nepotvrzená domněnka\\
-Algoritmus ze skript už má na vstupu pole rodičů. Sníží se tím potřebný počet procesorů, protože pak už nepotřebuju procesorů jako hran, ale jen jako procesorů.\\
-V případě, že nám nedali pole rodičů k dispozici, nebudeme výpočet velikosti podstromu přece zbytečně rozdělovat na výpočet rodičů a samotného výpočtu podstromů, když velikosti podstromů můžeme drobnou modifikací počítat právě už při (místo) zjišťování rodičů (místo ukládání rodiče, spočítám už velikost).
 ===== OAB na M(z1, ... zn), SF, všeport, spodní a horní meze na kroky a komunikaci, napsat algoritmus, zhodnotit optimalitu =====
@@ Line 483: / Line 89: @@
 hanouto: Přidal jsem navíc obrázek s nejhorším případem v 3D mřížce, k optimalitě jen napsal, že optimální je bez nějakého dalšího odůvodnění a plný počet bodů.
-===== AAB na 1-portové mřížce s kombinováním paketů, SF, taab, r =====
-==== Řešení ====
-(jestli je to full duplex nebo ne bývá v zadání. tohle je full duplex. )
-:!://Viz přednáška 11 FIT slajd 10//
-Algoritmus pro AAB na k-rozměrné 1-portové mřížce s kombinováním paketů je založen na AAB na 1 rozměrné 1-portové mřížce. Provádí se technikou sudo-lichých výměn.
-  * V lichém kroku si každý lichý a následující sudý vymění zprávy. Posílají pouze nové zprávy, to jest ty, které se dozvěděly v předchozím kroku (neplatí pro první dva kroky, viz dále).
-  * V sudém kroku udělá to samé každý sudý a následující lichý.
-  * Na **M(z)** je počet kroků **k = z**, pokud je **//z//** liché, **k = z-1** v opačném případě.
-Na začátku má každý uzel svou jednu zprávu, kterou chce poslat všem ostatním. V prvním kroku si tedy každá licho-sudá dvojice uzlů vymění vzájemně jednu zprávu, čímž už bude mít každý zprávy dvě (kromě posledního v případě lichého počtu uzlů). Ve druhém kroku si každá sudo-lichá dvojice vymění vše co mají, což jest dvě zprávy. V každém dalším kroku už se vyměňují pouze ty zprávy, které uzel nově obdržel v předchozím kroku, což jsou pokaždé právě dvě zprávy. Velikost zprávy je tedy v podstatě konstantní a délka trasy je vždy 1.
-Obrázek za tisíc slov:
-{{:škola:předměty:mi-par:sudo_licha_vymena.png|}}
-**Je-li //z// liché:** <math>r_{\tiny AAB} = z,\: t_{\tiny AAB} = z t_s + (2z-2) \mu t_m</math>,
-**jinak:** <math>r_{\tiny AAB} = z-1,\: t_{\tiny AAB} = (z-1) t_s + (2z-3) \mu t_m</math>.
-To (2z - 2) vykoukám z obrázku. V prvním kroku pošle jednička jeden paket velikosti <math>\mu</math> dvojce a dvojka jeden paket velikosti <math>\mu</math> jedničce. Protože to ty procesory provádějí paralelně, tak je zpoždění v prvním kroku <math>\mu t_m</math>. V druhém kroku jeden procesor posílá najednou dva pakety, proto <math>2 \mu t_m</math>. Ve třetím kroku <math>\mu t_m</math>. Dohromady tedy <math>4 \mu t_m</math>. Když to zobecním, tak (2z - 2).
-Na více rozměrné mřížce se postupuje po dimenzích. Například ve 2D mřížce se nejprve provede AAB ve všech řádcích (tj. dimenze **//z<sub>1</sub>//**), poté ve všech sloupcích (tj. dimenze  **//z<sub>2</sub>//**).
-<math>r_{\tiny AAB} = \sum_{i=1}^k r_{\tiny AAB}(M(z_i)) = \sum_{i=1}^k z_i - (z_i-1 \normalsize\text{ mod2})</math>
-Na začátku bude každý uzel začínat s jednou zprávou. Po dokončení AAB v první dimenzi už bude mít každý uzel tolik zpráv, kolik je velikost této dimenze. V dalším AAB ve druhé dimenzi už tedy budou uzly začínat se <math>\normalsize z_1</math> a končit se <math>\normalsize z_1 \cdot z_2</math> zprávami. A tak dále.
-<math>t_{\tiny AAB}(M(z_1,....,z_n),\mu) = \sum_{i=1}^k t_{\tiny AAB}(M(z_i),(\prod_{j=1}^{i-1} z_j) \cdot \mu))</math>
-FIXME v tom vzorečku chybí ta zpoždění Ts a Tm. Těch Ts bude asi stejně jako r(AAB), ta Tm je třeba ověřit, já jsem do toho vzorečku ještě nepronikl...
-Řekl bych, že:
-<math>t_{\tiny AAB}(M(z_1,....,z_n),\mu) = \sum_{i=1}^n t_{\tiny AAB}(M(z_i),(\prod_{j=1}^{i-1} z_j) \cdot \mu) = \sum_{i=1}^n ( (z_i - 1 + (z_i mod 2) ) t_s + (2 z_i - 3 + (z_i mod 2) ) t_m \mu \prod_{j=1}^{i-1} z_j )</math>
 ===== PPS na 1-portové 1-D mřížce =====
@@ Line 575: / Line 144: @@
 {{http://i.imgur.com/npkBML3.png|}}
-===== Popsat smerovani na 1D toroidu odolne proti deadlocku =====
-Popsat směrování na 1D toroidu odolné proti deadlocku + jaké řešení + důkaz.
-==== Řešení ====
-Popis je jasný, prostě člověk musí umět teorii
-:!://Viz skripta CZ [2006] str. 146, skripta EN [2009] str. 90, prednaska 6, strana 38.//
-Důkaz se udělá tak, že se nakreslí graf kanál. závislostí a ukáže se, že neobsahuje cykly.
-:!: Dodatek by voho (nejsem si ale jistý): Dělá se to přes virtuální kanály. V toroidu o dimenzi //N// má každý uzel //2N// sousedů (portů). Každý port může být plně duplexní. Kdybychom byli v mřížce, tak uděláme dimenzionálně uspořádané směrování, ale to v toroidu nejde (viz tornádo, cyklický posun). Když chceme zamezit deadlocku, rozdělíme fyzické kanály logicky na dva poloduplexní virtuální kanály (VK). Změní se směrovací funkce, která podle nějaké hlavičky v paketu pozná, ve kterém VK se paket pohybuje. Mějme VK //incr// a //decr//. VK //incr// se využívá pouze pro posílání paketů v **striktně rostoucím** pořadí, VK //decr// pro posílání paketů v pořadí **striktně klesajícím**.
-**Pro 1D toroid K(z) a směrování mezi uzly u, v**
-Jestliže <math>u < v</math>, posílají se pakety v kanálu <math>c_{1u} \ldots c_{10}</math> a pak <math>c_{0(z-1)} \ldots c_{0(v+1)}</math>. Jestliže <math>u > v</math>, posílají se pakety v kanálu <math>c_{0u} \ldots c_{0(v+1)}</math>.
-{{:škola:předměty:mi-par:vyřešené_příklady:smerovani_1d_toroid.png|}}
-edit Radek: nejlépe je to vidět na obrázku ze skript, pokud je uzel tedy uzel <math>u < v</math>, pak se jde horní cestou přes <math>c_{1u} \ldots c_{10}</math> a pak se pokračuje spodní cestou <math>c_{0(z-1)} \ldots c_{0(v+1)}</math>. Tím dojde ke zrušení cyklu a nemožnosti vzniknutí zablokování.
-pozn.: každý fyzický kanál lze rozdělit na <math>k >= 2</math> virtuálních kanálů
-{{:škola:předměty:mi-par:toroid.png?600|}}
 ===== Paralelní sčítačka =====
@@ Line 692: / Line 234: @@
 Edit 2: Chybí a na straně 99 v ENG skriptech je v textu ten součet popsán. Přidal jsem výše pseudokód, který obsahuje i finální součet Z=X+Y+C.
-===== EREW PRAM algoritmus pro pořadí uzlů v průchodu inorder =====
-★ //Bylo ve zkoušce: [[par_zkouska_2012-05-18|2012-05-18]]//
-Popište EREW PRAM algoritmus pro výpočet pořadí uzlů při průchodu inorder (levý podstrom, kořen, pravý podstrom) všech **n** uzlů Eulerova binárního stromu **S**. Výsledkem bude pole IN[1..n]. Eulerův strom **S** má **m = 2n-2** hran a je reprezentován polem uzlů, které mají odkazy na cyklický seznam svých hran. Předpokládejte, že je již zkonstruovaná Eulerova cesta vzniklá při průchodu **S** do hloubky a je uložená v poli EA[1..m], kde EA[i] je //i-tá// hrana této cesty. Odvoďte paralelní čas **T(m,p)** pro **1 ≤ p ≤ m** tohoto algoritmu. Předpokládejte, že lokální operace trvají jednotkový čas a operace R/W mají čas **d > 1**.
-==== Řešení ====
-Podobná myšlenka jako PreOrder Přednáška 7 slide 42
-{{:škola:předměty:mi-par:erew_pram_preorder.png|}}
-<code>
-alg. EREW_PRAM_InOrder(In:EA[1..m]; Out: inOrder[1..n])
-  for xy in EA do parallel:
-    if xy.direction <> xy.next.direction      // ak má moje next hrana jinou orientaci než já
-      weight[xy.next] = 1
-    else
-      weight[xy.next] = 0
-  call pps on EA
-  for xy in EA list do parallel:
-    if xy.direction <> xy.next.direction then
-      inOrder[y] = weight[xy]
-</code>
-malo by to fungovat pre binarne stromy, v tejto podobe to cisluje od '1'\\
-este by sa tam asi malo doplnit, ze pre koren plati: root = pocet uzlov
-Pozn. Pozor, není myšlena //next// hrana dle definice reprezentace grafu pro Eulerovské stromy jako je tomu v přednášce 7/34, ale je tím myšlena následující hrana v eulerovské cestě.
-Časová složitost tohoto algoritmu je velice podobná jako [[škola:předměty:mi-par:par_řešené_příklady_6b#paralelní_sčítačka|paralelní sčítačka]]. Jen koeficient u m/p bude o pár jednotek vyšší.
-:!: Pokud algoritmus správně chápu, tak není korektní, protože přestane fungovat ve chvíli, kdy nějaký uzel nemá levý podstrom (extrémní případ by byl třeba spojový seznam).
-:!: EA je eulerovský strom, podívej se na přednášku 7 slide 41, tam je krásně nakreslený jak vypadá. Tvoří eulerovskou kružnici, takže tam vždycky bude next.
-EDIT: Trošku problém může být, že neznáme next. V EA máme uloženou jen hranu a její směr (Down, Up).
-JDU: Domnívám se, že ten pseudokód nefunguje. Už když ten strom bude vypadat jako nudle doleva a na konci třešeň tak to nečísluje dobře (ty uzly v té nudli to kvůli tomu IF ani nijak neočísluje, protože jejich NEXT nemá jiný směr).
-EDIT: Předpokládam, že ten algoritmus je zamýšlen pro plné bin. stromy - každý vnitřní uzel ma pravý i levý podstrom. Ostatně u neplných stromů jako ten, který navrhuje JDU nedává in-order číslování smysl
-Pero: Myšlenka algoritmu mi připadá správná, ale nefungovala by, pokud by poslední patro binárního stromu nebylo plné. Ale snad to jen někdo tady zapomněl dopsat do zadání, že je úplný.\\
-Jen ten algoritmus není dotažený do konce, má někdo nápad, jak nakonec získám to pole IN?
-Edit VD: Myslím, že algoritmus funguje správně, ale tedy jen na binární stromy. Jak je uvedeno výše, že ještě potřebujeme root = pocet uzlov, tak to podle mě není pravda (alespoň pokud si alg. odkrokujete na binárním stromu, kořen dostane správné číslo).
-<code>
-def EREW_PRAM_InOrder([] EA) {
-  for edge in EA do_in_parallel {
-		# Tato hrana má jinou orientaci než další hrana
-		# v eulerovské cestě
-		if edge.Direction != edge.Next.Direction:
-			# Pozor: ne této hraně ale další
-			EA[indexOf(edget.Next)].Weight = 1
-		else:
-			EA[indexOf(edget.Next)].Weight = 0
-	}
-	pps(EA, on_attribute=Weight)
-	InOrder = array(EA.Length)
-  for edge in EA do_in_parallel {
-		# Tato hrana má jinou orientaci než další hrana
-		# v eulerovské cestě
-		if edge.Direction != edge.Next.Direction:
-			# edge = x -> y (hrana vede z vrcholu x do y)
-			InOrder[edge.Y] = EA[indexOf(edge)].Weight
-	}
-	return InOrder;
-}
-</code>
-===== EREW PRAM na hloubku uzlů ve stromu =====
-★ //Bylo ve zkoušce: [[.:par_zkouska_2012-01-03|2012-01-03]]//
-==== Řešení ====
-Slajd 7/34 FEL
-Analogicky jako EREW PRAM (třeba číslování preorder), jen hrany dolů ohodnotím 1 a hrany nahoru -1. Důležité je podle mě taky to, jaký byl vstup. Tím byl graf, každý uzel znal odkazy do pole na své hrany, hrany znaly odkazy na své protějšky a byla zkonstruována eulerovská kružnice, která byla k dispozici ve formě pole jako zobrazení pořadí hrany v kružnici → idetifikátor hrany.
-{{:škola:předměty:mi-par:erew_pram_alllevels.png|}}
-Zde stejný algoritmus jen to trochu připomíná kód:
-<code python>
-def EREW_PRAM_AllLevels(EA):
-    for edge in EA do_in_parallel:
-        if edge.Direction == DOWN:
-            ea.Weight = 1
-        else:
-            ea.Weight = -1
-    pps(EA, on_attribute=Weight)
-    Level = array(EA.Length)
-    for edge in EA do_in_parallel:
-        if edge.Direction == DOWN:
-            # edge = x -> y
-            Level[edge.Y] = EA[indexOf(edge)].Weight
-    Level[indexOf(ROOT)] = 0
-    return Level
-</code>
 ====== Teorie a důkazy ======
-===== Dokažte, že e-cube směrování v Qn při zhuštění je bezkolizní =====
-★ //Bylo ve zkoušce: [[.:par_zkouska_2013-01-09|2013-01-09]]//
-==== Řešení ====
-//viz skripta {{:škola:předměty:x36par-skriptacz2.pdf|x36par-skriptacz2.pdf}} strana 161 nebo přednáška 9 slide 30 (2013/2014)//
-Důkaz je induktivní, v prvním kroku může dojít ke kolizi při směrování podle nejnižšího bitu. Je zřejmé, že ke kolizi může dojít pouze pro dvojici sousedů spojených hranou v nejnižší dimenzi (tj. máme uzly bbb0 a bbb1).\\
-Jelikož je to sousední dvojice, tak i ve výsledku budou sousední v tomto pořadí (z definice zhuštění).
-Tedy mohou nastat dva případy :
-  - "bbb0->ccc0, bbb1->ccc1": výsledné permutované dva uzly mají stejný nejnižší bit => v e-cube směrování k pohybu nedochází => kolize nenastane
-  - "bbb0->ccc1, bbb1->ddd0": výsledné permutované dva uzly mají rozdílný nejnižší bit => e-cube směrování generuje pohyb v nejnižší dimenzi => oba se pohnou a vymění si pozice => opět bezkolizní => tímto krokem se každý z obou uzlů vnoří do jiné podkrychle Qn-1. Pro ni dokážeme bezkoliznost stejným způsobem.
-:?: Jak se může v druhém bodu vnořit do jiné podkrychle, když permutoval na nejnižším bitu (a ne na nejvyšším)?
-Pozn: Neni tady nahodou ta druha cast spatne? Ja bych rekl, ze ten nejnizsi bit je ten nejvic v pravo.
-Pozn: Zhusteni zachovava poradi, takze kdyz jeden paket zacina na uzlu s poslednim bitem = 0 a druhy vedle nej, tedy s poslednim bitem = 1, budou i ve vysledku muset mit v cili posledni bit roven: jeden 0 a druhy 1 nebo opacne) Proto mame 2 moznosti viz vyse.
-Zaroven se tu pouziva e-cube smerovani, ktere postupne porovnava bity zdrojoveho a ciloveho uzlu - pokud se nelisi (prvni pripad, protoze posledni bit v cili ccc0 a zdroji bbb0 je stejny), posle ty 2 pakety pod sebou rovne => nedojde ke kolizi.
-V druhem pripade se zdrojovy a cilovy uzel lisi v poslednim bite => bude se lisit i u zdroje a cile toho druheho paketu. Opet e-cube porovna i-ty bit zdroje a cile a pokud se lisi, posle pakety krizem => opet nebude kolize - nenabouraji do sebe
-Ještě přidám moji verzi (bliznjan): V i-tém kroku (kroky i bity indexuji od nuly, bity indexuji zprava od nejnižšího) řeším vzájemně pouze ty dvojice paketů, jejichž souřadnice se liší právě v i-tém bitu zprava (jinak by v Qn nebyly v sousedních uzlech). Kolize by mohla nastat, kdybych takovouto dvojici paketů chtěl přesunout do stejného uzlu, tedy na stejné souřadnice. Vzhledem k e-cube směrování už mám bity vpravo (nižší) vyřešené a mohou se v následujících krocích měnit už jen vyšší bity, ale ty se naopak zatím neměnily. U dvou paketů, co zrovna řeším, tudíž platí, že jejich vyšší bity byly od začátku rovny, takže na začátku (i teď) byly od sebe vzdálené o méně než <math>2^{i+1}</math> pozic (vzdáleností nemyslím Hammingovu vzdálenost, ale to celkové pořadí, o které ve zhuštění jde). Po celkovém zhuštění nesmí dva pakety skončit na stejné pozici, a proto kdybych teď, v i-tém kroku, oběma nastavil i-tý bit na stejnou hodnotu, tak bych potom v dalších krocích musel nastavit alespoň jeden jejich bit ve vyšších pozicích na různé hodnoty. Kdybych nějaký vyšší bit změnil, tak by pak ale ve výsledku byla vzdálenost (opět nemyslím Hammingovu) alespoň <math>2^{i+1}</math>, takže by byla vzdálenost vyšší než před zhuštěním, jenže zhuštění nikdy vzdálenost zvýšit nesmí, takže by to byl spor s tím, že se jedná o zhuštění.
-===== Dokažte, že neúplná online permutace zhuštění na indBFn je bezkolizní =====
-Popište, jak si procesory na zadané indBFn zjistí pořadí, když lokálně mají jen flag 0/1 (zda patří do množiny) a následně proveďte neúplnou online permutaci zhuštění procesorů s flagem 1. Dokažte, že online směrování na indBF je pro ni bezkolizní
-★ //Bylo ve zkoušce: [[.:par_zkouska_2016-01-15|2016-01-15]]//
-==== Řešení ====
-zjištění cílového umístění, když teď zná jen ten flag 0/1 - provede se prefixový součet, viz obrázek, předpokladem je třeba, že přepínače po cestě umí sčítat, naprosto v pohodě mi zde uznal, že se udělá PPS, napsat co je PPS (1-2 věty) a obrázek
-{{ :škola:předměty:mi-par:výstřižek.png |}}
-V podstatě stejné jako [[škola:předměty:mi-par:par_řešené_příklady_4b#doka%C5%BEte_%C5%BEe_e-cube_sm%C4%9Brov%C3%A1n%C3%AD_v_qn_p%C5%99i_zhu%C5%A1t%C4%9Bn%C3%AD_je_bezkolizn%C3%AD|přechdchozí příklad]] (s e-cube směrováním).
-Důkaz je ve slidech, slide 31 přednáška 9 (pro oBFn, ale to je v skoro to samé).
-Minimální směrování v indBFn funguje tak, že se porovnají adresy cíle a zdroje (postupně od LSB k MSB, v každé úrovni jeden). Když se bit adresy zdroje a cíle liší, tak se jde směrovačem křížem, když se neliší, tak se jde rovně.
-Kolize může nastat v 1. úrovni motýlka pouze pro sousední uzly (tedy např. zdrojové uzly bbbb0 a bbbb1). Ty se permutují buď na uzly se stejnou paritou (xxxx0 a xxxx1) nebo s opačnou paritou (xxxx1 a xxxy0). Žádný jiný případ nemůže nastat.
-Když je parita stejná, tak oba uzly chtějí v cestě pokračovat rovně - není kolize a když je různá, tak chtějí oba pokračovat křížem - není kolize.
-Po prvním stupni indBFn budou pakety směrovány do disjunktních podmotýlků indBFn-1 a důkaz tam induktivně probíhá stejně.
-===== Důkaz bezkoliznosti operace přeložení na Qn při použití e-cube =====
-Dokažte, že v Qn je operace přeložení //i->i xor w// je při směrování e-cube bezkolizní (//w// je n-bitová posloupnost)
-==== Řešení ====
-E-cube směrování se řídí bity řetězce //w// (protože <math>i \; \oplus_2 \; (i \; \oplus_2 \; w) = w</math>). //w// je v podstatě maska - tam, kde má //w// 1, tam se invertuje bit //i//. Jinak řečeno, po hranách se bude přecházet v těch dimenzích, kde má //w// bit nastavený na 1. Např. pro <math>Q_3</math> a <math>w = 001</math> se bude přecházet po hraně v první dimenzi, pro <math>w = 110</math> v druhé a třetí.
-Ke kolizi může nastat v libovolném kroku //k// mezi uzly spojenými hranou dimenze //k//.
-Existují 2 možnosti:
-  * a) //k//-tý bit řetězce //w// je 0 => k pohybu v //k//-té dimenzi nedojde => kolize nenastává
-  * b) //k//-tý bit řetězce //w// je 1 => u obou uzlů dojde k pohybu v dimenzi //k// => vymění se pozice => kolize nenastává
-//Pozn. by Klaara (ad pochybnosti o XORech): Řešení je OK. Jde o to si jakoby "vyjádřit"// w//. A že //w = i XOR (i XOR w)//, to prostě platí :), zkuste si to na příkladu. Taky si to můžete představit tak, že vám někdo zadá jen //i -> j//, tj. adresy zdroje a cíle. A vy z toho potřebujete vytáhnout ty rozdílné bity, což zjistíte tak, že uděláte //i XOR j//. Když za //j //dosadíte //(i XOR w)//, vyjde zas to samé.// - no a čo? Úloha znie dokáž bezkolíznosť a nie nájdi w, ktoré je zadané. Celý pokec o dvoch XORoch je tu podľa mňa zbytočný a zavádza.
----
-Edit: dovysvětlení by Rulfik \\
-jelikož permutace na <math>Q_n</math> je definována následujícím předpisem <math>\pi_{u \mapsto v}(x)= x\oplus (u \oplus v)</math>, kde <math> \oplus </math> je bitová nonekvivalence (XOR). A v zadání je přeložení <math>{u \mapsto v}</math> zadáno pro <math>u = i</math> a <math>v = i \oplus w</math>
-Potom cílová adresa permutovaného paketu vyslaného z uzlu <math>x</math> v <math>Q_n</math> po přeložení je dána následujícím vzorcem <math>i \oplus i \oplus w \oplus x = w \oplus x</math>
-Edit: aby to bylo jasné, jak jsme se dostali k tomuto vzorci: <math>\overbrace{i}^{u}\mapsto\overbrace{i\,\mathtt{XOR}\,w}^{v}\text{.}</math>
-xor je definován následovně
-^ <math>x_k</math> ^ <math>w_k</math> ^ <math>x_k \oplus w_k</math> ^
-|0|0|0|
-|0|1|1|
-|1|0|1|
-|1|1|0|
-Je nutné si uvědomit, že se směruje e-cube (tedy po jednotlivých dimenzích od LSB k MSB) tedy celkem v n krocích.
-Pro každý k-tý krok mohou nastat následující 2 případy:
-^ <math>x_k</math> ^ <math>w_k</math> ^ <math>x_k \oplus w_k</math> ^
-^0|**0**^0|
-^1|**0**^1|
-Je li w=0, pak k-tý bit adresy paketu zůstává nezměněn, ke směrování nedochází = žádná kolize
-^ <math>x_k</math> ^ <math>w_k</math> ^ <math>x_k \oplus w_k</math> ^
-^0|**1**^1|
-^1|**1**^0|
-Je-li w=1, pak k-tý bit se zneguje = čili u dvou sousedních uzlů dojde ke křížové výměně paketů = žádná kolize.
-Čili je pravda, že směrování se řídí bity řetězce k jak již bylo uvedeno.
-===== Minimální směrování pro nepřímý oBFn =====
-Dokažte, že minimální směřování pro nepřímý oBF<sub>n</sub> je vždy uzlově disjuktní pro permutaci cyklicky posun <math>\pi^{\delta}_{s} : (0, i) \mapsto (n, i \oplus_{2^n} \delta), i \in = \{1, .., 2^n\}</math> (posouváme o <math>\delta</math>), kde <math>\delta</math> je konstanta.
-★ //Bylo ve zkoušce: [[.:par_zkouska_2011-05-19|2011-05-19]]//
-==== Řešení ====
-[[https://edux.fit.cvut.cz/courses/MI-PAR.2/_media/lectures/mi-par2015-prednaska9-permutations.pdf|mi-par2015-prednaska9-permutations.pdf]] slide 34
-Cyklický posun jsou 2 operace zhuštění na stejné síti. Důkaz je tedy skoro stejný jako u důkazu že zhuštění je bezkonfliktní:
-  - záleží na paritě slova o které se posouváme. Pokud je parita lichá, v prvním sloupci se vždy nastaví přepínače křížem = není kolize. Pokud je parita sudá, nejnižší bit se vůbec nemění a čili se nastaví přepínače rovně = není kolize
-  - jelikož výstupy ze stupně 0 jdou na vstupy disjunktních podmotýlků, dá se 1) aplikovat znovu.
-{{https://i.imgur.com/TP2Hz9D.png?850|}}
-(a) Cyklický posun o <math>\delta=5</math>  na <math>indBF_{4}</math>, (b) Cyklický posun o <math>\delta=10</math>  na <math>indBF_{4}</math>.
 ===== Konstrukce všech uzlově disjunktních cest v 3D mřížce s nejkratšími délkami =====
@@ Line 987: / Line 306: @@
 Nestačí. Nemáš najít pouze nejkratší cesty, ale všechny disjunktní cesty tak, aby byly co nejkratší. Disjunktních cest může být max 2*dimenze (to ti požere všechny sousední uzly k počátečnímu uzlu a žádné disjunktní cesty už neuděláš) a ty se je snažíš najít tak, aby byly co nejkratší -> najdeš dimeze-krát úplně nejkratších pomocí přímýho směrování + ty úhybný. (hroncmir)
-===== SF,oBFn monotonni permutace =====
-//Řešení obdobného příkladu: [[škola:předměty:mi-par:par_řešené_příklady_8b#důkaz_proveditelnosti_bezkolizní_monotonní_permutace_na_obf_algoritmus_složitost|PAR - Vyřešené zkouškové příklady za 8 bodů]]//
-Dokázat, že každou monotónní permutaci lze na SF oBFn realizovat bezkolizně, tj. v O(n) krocích, odhadnout skrytou konstantu
-==== Řešení ====
-:!://Viz skripta [2006] str. 161-162// && [2015] 9. přednáška / slide 33
-=== Důkaz bezkoliznosti ===
-Monotónní permutace se skládá ze zhušťovací, roztažné a identity. Identita je triviálně bezkolizní, to vyplývá přímo z její definice. Roztažná je jen zrcadlová ke zhušťovací. Musíme tedy dokázat, že zhuštění je bezkolizní.
-Důkaz je induktivní. Uvažujme, že žádné dva pakety se nemohou srazit na stejném uzlu v 1. úrovni (číslujeme od nuly). Ke kolizi by mohlo dojít jen mezi pakety, které by tvořily sudo–lichou dvojici po sobě jdoucích paketů. Tyto pakety by ovšem po zhuštění skončily také na dvou po sobě jdoucích výstupech. Mohou nastat dvě situace:
-  - Výstupní uzly budou **sudo–lichá dvojice** (nejnižší bit se neliší). → Pakety šly v 1. úrovni **rovně** (dle pravidel min. směrování). → Nemohlo dojít ke kolizi.
-  - Výstupní uzly budou **licho–sudá dvojice** (nejnižší bit se liší). → Pakety šly v 1. úrovni **křížem**. → Nemohlo dojít ke kolizi.
-Po tomto kroku se pakety dostanou na vstupy dvou navzájem disjunktních podmotýlků oBF<sub>n-1</sub> (sudý a lichý), jejich cesty se tedy rozchází. Jelikož obyčejný motýlek je rekurzivní, tak lze na oba podmotýlky induktivně aplikovat stejný postup. Tím je zřejmé, že všechny tři permutace jsou bezkolizní.
-=== Časová složitost ===
-Každá z permutací má složitost O(n). PPS má složitost O(2n) (FIXED). Celkem tedy O(5n), skrytá konstanta je 5.
-PPS n vstupních hodnot lze řešit na libovolné n-uzlové síti v čase T = O(diam(G)) viz Prednaska 7, slide 11.
-diam(oBFn) = 2n viz Prednaska 4, slide 37.
-DOTAZ :?:: v tom zminenem tvrzeni se preci pise, ze to PPS lze resit v O(log n), kde n je pocet vstupnich hodnot, u nas tedy v O(log 2^n) = n. Podminku toho, ze tvrzeni to plati mame splnenou (diam(G) = 2*n = O(log2^n) = O(n). Budu rad za objasneni, diky. (navic tam se navic predpoklada, ze pocet uzlu je stejne jako pocet hodnot)
-=== Trocha teorie ===
-  * Monotónní permutace je jakákoli neúplná permutace, která nemění pořadí paketů. Jinak řečeno, jedná se o směrování z libovolné podmnožiny vstupů do stejně velké podmnožiny výstupů, které mohou být různě posunuté, ale musí zachovávat stejné pořadí paketů. Každou monotónní permutaci lze vytvořit složením z permutace zhušťovací a roztažné.
-  * Zhušťovací permutace je směrování paketů z libovolné podmnožiny **//x//** vstupů do //prvních, nebo posledních **x**// výstupů (tj. odshora, nebo odspoda), přičemž se opět zachovává relativní pořadí paketů.
-  * Roztažná permutace (též zředění) je zrcadlovým otočením zhušťovací permutace. Je pro ni nutné zrcadlově otočit i celého motýlka, tj. posílat pakety zprava doleva.
-  * Identita je směrování paketů z libovolné podmnožiny (nebo všech) vstupů do protějších výstupů. Jednoduše řečeno, pouze přenese pakety z jedné strany na druhou ve stejné řádce.
-Realizace monotónní permutace na obyčejném motýlkovi má celkem **čtyři fáze**. Nejprve musíme spočítat relativní pořadí paketů (tj. aktivních vstupů) pomocí **paralelního prefixového součtu** (PPS). To je potřeba k výpočtu výstupních adres pro druhou fázi, **zhušťovací permutaci**. Ve třetí fázi provedeme **roztažnou permutaci**. Nejprve jsme pakety poslali zleva doprava, poté zpátky doleva, takže nakonec musíme provést **identitu**, poslat je na protější výstupu doprava.
-{{tag>škola zkoušky s_řešením}}