Odvoďte maximální y takové, že mřížku <math>M(3,y)</math> vnoříme do mřížky <math>M(10,9)</math> s dil = 1 a load = 2. Příslušné vnoření popište algebraicky nebo schématickým obrázkem. Odvoďte hodnotu hranového zahlcení.

Mareen: Použitím harmoniky (viz příklady za 4b, PAR - Vyřešené zkouškové příklady za 4 body) v prostřední rovince se dosáhne y=48, ecng = 2:

Vnoření M(22,24) do M(x,5) s load=2 a min dil, určit ecng.

Viz skripta CZ [2006] str. 87 nebo EN [2009] str. 70

<math>\frac{22}{2}=11</math>
<math>11*5=55=x</math>
<math>ecng=6</math>

Edit1: Dobře se to počítá takto:

Na horní straně se střídá pět druhů hran. U každé z nich musíme ověřit ecng. Vezměme si jednu z nich. Podíváme se, jaký “vrchol hada” se nachází bezprostředně nalevo od ní. Najdeme první odpovídající “vrchol hada” napravo od ní. Pak snadno odpočítáme od toho pravého, vzdálenějšího, počet “vrcholů hada” cestou doleva směrem k naší hraně. Tyto všechny pravé “vrcholy hada”, včetně toho prvního, musí vést doleva přes naší hranu. A těch je pět pro každou z pěti druhů hran. K tomu ale nesmíme zapomenout u příslušných hran přičíst jednoduchou, “hadovou” hranu. To znamená, že ecng = 6.

Edit2: chvíli mi trvalo, než jsem prokouknul tuhle kupeckou matematiku, takže to radši rozepíšu: Celkem chceme namotat 22 hadů do cílové mřížky. Z obrázku vidíme, že 2 hadi zaberou 5 sloupců. Kolik sloupců zabere 22 hadů (hint: trojčlenka)? 22 hadů zabere 55 sloupců.

Edit3: Spočtení ecng a dil je jednoduché. Zde je obrázek k popisu v Edit1:

Klíčové je správně určit místo, kde budeme měřit - je jasné, že na kraji by nám to vyšlo jinak.

Vnoření M(13,13) do M(x,5) s load=2 a min dil, určit ecng.

Viz skripta CZ [2006] str. 87 nebo EN [2009] str. 70

<math>x = 20</math>
<math>ecng = 4</math>
<math>dil = 2</math>

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.

• ENG skripta str. 150 dole
• CZ skripta str. 173
• přednáška 10 / slide 16 (2015)

• na začátku zdroj rozešle paket všemi možnými směry
• pokud mi přišel paket z i-té dimenze, pošli ho dál v i-té dimenzi, pokud nejsem v i-té dimenzi poslední
• pošli paket v dimenzích (i+1)+, (i+1)-, …, (n-1)+, (n-1)-

<math>\rho = exc(M(…), s)</math> - nikdy nemůžu být rychlejší než vzdálenost nejvzdálenějšího uzlu od zdroje. Pozor spodní mez není poloměr mřížky, musíte tam napsat, že je to excentricita, jinak je to špatně.

<math>\tau = exc(M(…), s)(t_s + \mu t_d)</math> - délka jednoho kroku v SF mřížce je 1 a dělám <math>exc(G, s)</math> kroků, proto takový výraz

<math>r = diam(M(…)) = z_1 + … + z_n</math> - zdroj má nejhorší vzdálenost do nejvzdálenějšího uzlu právě průměr grafu

<math>t = diam(M(…))(t_s + \mu t_d) = (z_1 + … + z_n)(t_s + \mu t_d)</math>

Dotaz: Nesedí mi výše uvedený diam(M(…)). Ten se podle mě rovná: <math>\sum_{i=1}^{n}\left(z_{i}-1\right)</math>.

Máš pravdu, ale Tvrdík mi to uznal tak, jak to tu je. Možná chvilková slabost, říkal totiž, že tenhle příklad přede mnou ještě nikdo neudělal…

Dotaz II.: Můžete mi prosím vysvětlit, co ve výše uvedeném vzorečku znamená <math>t_s</math>? V přednáškách je u tohoto příkladu SF zpoždění zapsáno jako <math>t_s + t_d + \mu t_m</math>. Chápu, že je to asi nepodstatné, ale přijde mi, že je to pokaždé značené jinak.

Tento algoritmus je krokově i časově optimální.

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

Přednáška 7/7 2014, skripta eng 96(dole + figure 6.8)

PPS EREW PRAM - základní optimální algoritmus

★ Bylo ve zkoušce: 2015-01-28 (samotný PPS EREW PRAM)

• SF mřížka neumožňuje lepší časové řešení než hloupé sekvenční řešení, protože posílání zpráv v SF je citlivé na vzdálenost.
• Na WH použijeme simulaci PPS na přímém stromu, který zploštíme do 1D lineárního pole.

Simulace na přímém stromu(Lemma 6.5):

Simulovat stromový PPS v <math>T = O (\log {n})</math> krocích

Pokud je p<n, pak <math>T(n,p) = O ( \frac{n}{p} + \log {p})</math>, součet má fáze:

1. Každý procesor provede součet nad svými čísly v <math>T_1 = O (\frac{n}{p})</math> krocích.
2. Provede se PPS nad p hodnotami. <math>T_2 = O (\log{p})</math>
3. <math>P_i</math> pošle svůj součet procesoru <math>P _i _+ _1</math>. <math>T_3 = O (1)</math> Edit: Tento krok platí pro PRAM, ale ne pro strom, kde není nutné nic posílat.
4. <math>P_i</math> přijme hodnotu a provede dopočet nad svými hodnotami. <math>T_4 = O (\frac{n}{p})</math>

<math>T(n,p) = O ( \frac{n}{p} + \log {p} + 1 + \frac{n}{p}) = O ( \frac{n}{p} + \log {p})</math>

PPS na stromě funguje takto:

1. Každý list pošle svému rodiči svoji hodnotu.
2. Rodič sečte hodnoty od svývh podstromů a pošle je svému rodiči. Hodnotu z levého podstromu pošle do pravého podstromu.
3. Co dostane od svého rodiče pošle svým potomkům

Na 2-portové mřížce se z hlediska maximálního počtu kroků nic nezlepší, pouze bude větší množství uzlů dříve informovaných.

“Důkaz správnosti”: 28.1.2015 - VasekJ: u PPS na PRAMu nemusíte ani psát psedoalgoritmus, stačí pouze popsat obrázek

Pero: Můžete mi prosím tohle někdo vysvětlit? Jednak nechápu, jak se třeba 3. krok může provést v jednom kroku na WH mřížce, vždyť se ty cesty kříží. A pak v tom vůbec nevidím simulaci PPS přímého stromu. Na stromu například v prvním kroku probíhá komunikace (při postfix značení) mezi uzly 1-3, 4-6, 8-10, 11-13.

Vysvětlení k simulaci na WH: Není to tam jednoduše vidět, ale je to tam :)

Vychází to z paralelní redukce na WH mřížce:

Nejlépe je to vysvětlené na videu ze 7. přednášky z roku 2004 (https://mipar.vjirovsky.cz/data.lecture/detail200407), ve skriptech ani na pozdějších přednáškách se o tom moc Tvrdík nezmiňuje. Jedná se o simulaci nepřímého úplného binárního stromu s 16 listy a tedy výškou 4. Z toho vyplývá i počet kroků, který je <math>2*T(h)=2*4=8</math>

Tady je stejný algoritmus jako na obrázku od Tvrdíka, jen odkrokovaný na nepřímém stromu. Stále platí pravidlo pošli data rodiči (modrá nahoru), rodič pošle hodnoty z levého podstromu do pravého podstromu (modrá dolů) a co dostane rodič od rodiče, pošle potomkům (červená).

Popište pseudokódem NC algoritmus pro paralelní sčítání 2 n-bitových čísel a dokažte jeho korektnost. Odvoďte jeho časovou složitost T(n,p), 1 ≤ p ≤ n, na EREW PRAM v jednotkovém modelu (čili všechny R,L,W operace trvají jednotkový čas).

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

Viz skripta CZ [2006] str. 101-102, skripta EN [2009] str. 98-99

Rychlé paralelní sčítačky 2 n-bitových čísel musí obsahovat obvod pro predikci přenosu, jinak by operace sčítání trvala čas O(n). Pro tyto účely se používá PPS. Uvažujme 2 n-bitová čísla X a Y, z kterých chceme vypočítat Z v O(log n) krocích. To provedeme předpočítáním pole přenosových bitů C = Cn , … , C1, C0, kde vždy C0 = 0. Pole C vypočteme prefixovým součtem s operací, která je dána následující tabulkou:

for i=0,...,n-1 do_in_parallel {
  if (x[i]==y[i]==1) b[i]=g // generace
  else if (x[i]==y[i]==0) b[i]=s  // stop
  else b[i]=p // propagate
}
aplikuj PPS s operací [kolečko] nad B[] a ulož výsledek do B’[]
for i=1,...,n do_in_parallel {
  if (b‘[i-1]==g) c[i]=1
  else c[i]=0
}

Takto je podle mě kompletní kód:

def ParBinAdder(X, Y) {

    B = array(n + 1)
    B' = array(n)

    # Naplní pole B
    for i=0 .. n - 1 do_in_parallel {
        if X[i] == Y[i] == 1:
            B[i] = GENERATE
        elif X[i] == Y[i] == 0:
            B[i] = STOP
        else:
            B[i] = PROPAGATE
    }

    B[n] = STOP
    
    # Odstraní PROPAGATE
    B' = PPS(data=[B[n], ..., B[0], s], operation=(*))
    C = array(n, fill_with=0)

    for i=1 .. n do_in_parallel {
        if B'[i-1] == GENERATE:
            C[i] = 1
    }

    for i=0 .. n-1 do_in_parallel {
        Z[i] = X[i] + Y[i] + C[i]
    }
}

Můžete tu prosím ještě někdo vysvětlit, jak funguje to vytváření B' za pomoci operace kolečko? Jak je definováno B'[i]?

• Odpoved: jsem presvedceny, ze je to takhle - scitacka ma prenosy zprava doleva, takze i tady bude ta operace aplikovana zprava doleva, a kod pro sekvencni reseni by vypadal nejspis: for i:=n,…,1 do { B[i] := B[i+1] O B[i] } a takhle upravene pole B se nazve B'. Akorat paralelne se to nedela znak po znaku, ale logaritmicky pomoci PPS, kde se misto operace +:RxR→R pouzije to kolecko O:{g,s,p}x{g,s,p}→{g,s,p} (bliznjan)

Toto je schéma, jak se dělá PPS nad B:

Popis (korektnost): Algoritmus v každém bitu zjistí, jak se bude chovat přenos, zda vznikne vždy, nebo jen pokud přišel z nižšího bitu, nebo zda bude spolknut. Následný PPS dá tyto chování do souvislosti tím, že projde pole z LSB do MSB a odstraní propagace. Tím již víme, v jakém bitu budeme a v jakém nebudeme přičítat k součtu původních bitů přenos.

V prvním cyklu může každý procesor vyřídit naráz poměrnou část n/p bitů. Pro každý bit provede dvě čtení (x_i a y_i) a jeden zápis (b_i), tj. tři operace.

<math>T_1(n,p) = 3\frac{n}{p}</math>

PPS přes n bitů pomocí p procesorů trvá:

<math>T_2(n,p) = \alpha\frac{n}{p} + \beta log p</math>

Poslední cyklus dělá jedno čtení a jeden zápis pro každý bit, který má procesor na starosti.

<math>T_3(n,p) = 2\frac{n}{p}</math>

<math>T(n,p) = T_1(n,p) + T_2(n,p) + T_3(n,p) = 3\frac{n}{p} + \alpha\frac{n}{p} + \beta log p + 2\frac{n}{p} = (\alpha + 5) \frac{n}{p} + \beta log p = O(\frac{n}{p} + log p)</math>

Edit: Nechyba tu nahodou este jeden krok, kedy sa finane vypocita ten sucet? Ten algoritmus vypocita len carry-on pre kazdy bit, ale este potrebujeme 2 operacie citania a 1 operaciu na zapis na kazdy bit, aby sme mali finalny vysledok, nie? - Chybí, ale algoritmus tak jak je definovaný v definici 9 přednáška 7 slide 20 má na výstupu jenom pole C.

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.

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

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

1. “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
2. “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í.

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: 2016-01-15

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

V podstatě stejné jako 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ě.

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

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:

Je li w=0, pak k-tý bit adresy paketu zůstává nezměněn, ke směrování nedochází = žádná kolize

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.

Dokažte, že minimální směřování pro nepřímý oBF_n 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: 2011-05-19

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

1. 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
2. jelikož výstupy ze stupně 0 jdou na vstupy disjunktních podmotýlků, dá se 1) aplikovat znovu.

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

Jsou dány uzly u=[12,4,8], v=[5,9,3] v 3D mřížce M(14,16,10). Souřadnice uzlu začínají v každé dimenzi od nuly. Zkonstruujte všechny uzlově disjunktní cesty mezi u a v, aby byly co nejkratší a určete jejich délky. Řešení vysvětlete a popište algebraicky, doplňte schm. obrázkem.

Obrázek je špatně, což je zřejmé z nedokreslené poslední cesty - ta by v tomto obrázku již nešla udělat s délkou nejkratší cesty + 4. Správný obrázek i s vysvětlením viz příklad níže.

Počet cest je roven dvojnásobku počtu dimenzí. Nejkratší cesty v 3D M získám pomocí dimenzionálního X-Y-Z směrování ? pohyb striktně nejdříve v dimenzi X, potom v dimenzi Y a pak v dimenzi Z. Rotací pořadí dimenzí, zkonstruuji další 2 cesty ?
3 cesty délky (12 - 5) + (9 - 4) + (8 - 3) = 17

1. <math>(12,4,8) \rightarrow{X} (5,4,8) \rightarrow{Y}(5,9,8) \rightarrow{Z} (5,9,3)</math>
2. <math>(12,4,8) \rightarrow{Y} (12,9,8) \rightarrow{Z}(12,9,3) \rightarrow{X} (5,9,3)</math>
3. <math>(12,4,8) \rightarrow{Z} (12,4,3) \rightarrow{X}(5,4,3) \rightarrow{Y} (5,9,3)</math>

<math> Z^{-} + X^{\Delta X}+ Y^{+} + Z^{+} + Z^{ \Delta Z} + Y^{-} </math>
<math>Y^{-} + Z^{\Delta Z} + X^{\Delta X} + X^{+}</math>

Zbývající 3 cesty jsou délky 17 + 4 = 21 (vždy v dvou dimenzích odskočíme tam a zpátky)
<math>A^-</math> … pohyb v ose A v opačném směru než je cíl
<math>\Delta A</math> … pohyb v ose A o rozdíl mezi počátkem a cílem směrem k cíli
jedna cesta je: <math>X^-, \Delta Z, Z^+, \Delta X, X^+, \Delta Y, Z^-</math>
zbývající vzniknou zase rotací dimenzí

Pozn. tady na to pozor! Trošku jinak by se to počítalo kdyby uzly měli nějakou dimenzi shodnou. Pak existuje pouze jedna minimální cesta. Nemůže se obecně říct “Pro jakékoliv dva uzly.” Dobré je si to aspoň trochu načrtnout!

Pozn2 (bangom). Stejne tak pokud bude nejaky uzel na konci mrizky, tak do nej nepujde udelat maximalni pocet cest (stupen uzlu?)… kreslete si to

Cvičení 6, 16:10 začína 2D, 28:40 začína 3D, 43:50 začína 4D

Dány vnitřní uzly u a v ve 4D mřížce, zkonstruujte všechny možné uzlově disjunktní cesty z u do v takové, aby jejich délky byly co nejmenší. Řešení popište algebraicky a doplňte schematickým náčrtkem. Udejte délky a počty cest pro obecný případ dvou uzlu v k-rozměrné mřížce.

• Disjunktní cesty jsou takové, které nemají žádný společný uzel (krome zdroje a cile), tj. uzly se musí lišit ve všech dimenzích. Takových cest existuje 2*k.
• Zkonstruujeme k cest délky <math>\sum_{i=1}^{k}{|u_i-v_i|}</math> pomocí minimálního dimenzionálního směrování (začátek v dimenzi 1 ≤ i ≤ k).
• Dalších k cest délky <math>4+\sum_{i=1}^{k}{|u_i-v_i|}</math> zkonstruujeme takto:
  1. Začneme v dimenzi 1 ≤ i ≤ k a uděláme jeden krok ve směru -(v_i - u_i) (tj. „špatným směrem“).
  2. Z tohoto uzlu postupujeme pomocí minimálního směrování začínajícího dimenzí (i + 1) mod_k. Toto směrování má k kroků. Pro dimenze (i - 1) mod_k a i udělám jeden krok navíc – posunu se o |u_i - v_i| +1 hran.
  3. Poslední krok udělám v dimenzi j = (i - 1) mod_k ve směru -(v_j - u_j), tj. posunu se o 1 hranu až do cíle.

Protože mi to nefungovalo při kreslení ve 3D, řekl bych, že ten krok 2 je špatně. Podle mě by tam mělo být, že jeden krok navíc provedeme v dimenzi (i + 1) mod_k a dále jedeme dle minimálního směrování. Viz obrázek.

• Jelikož jsme na začátku šli špatným směrem jeden krok, musíme se taky o jeden krok vrátit ⇒ + 2 kroky oproti nejkratší cestě.
• Jelikož jsme v dimenzi (i + 1) mod_k šli o krok dál, musíme se o tento krok také vrátit ⇒ + další 2 kroky oproti nejkratší cestě.
• Celkem je tedy délka trasy: nejkratší cesta + 4.

Pokud si nebude jisti představou, kudy vlastně cesta vede, podívejte se na barvu v překřížení. Funguje to jednoduše - vždy se jde v pořadí XYZ nebo ZXY nebo YZX (rotace dimenzí). Při konstrukci delších cest (šedé) vyjdu špatným směrem, v následující dimenzi jdu o krok dál, než bych šel při minimálním směrování, a poté už jdu čistě dle minimálního směrování.

Tohle platí pouze pro případ, kdy se počáteční a cílový uzel liší ve všech dimenzích a nejsou na okraji mřížky. Jinak je počet cest rovný nejnižšímu stupni z obou uzlů. V případě, že mají nějaké dimenze stejné, se více cest vede s odskokem. Až někdo bude mít náladu, vymyslete univerzální postup.

Neví někdo, jak na papír nakreslit cestu ve 4D mřížce, resp. hyperkrychli? Halucinogenní látky jsou přeci ve škole zakázané… (edit to uz sis spis neco vzal, ze to nedokazes, ne? :))

Cvičení 6, 16:10 začína 2D, 28:40 začína 3D, 43:50 začína 4D Kde tohle “cvičení” seženu? Doplnit odkaz prosím.

Mně to připadá nějaké složité. Nestačí tato jednoduchá úvaha? Nejkratší cesty získám minimiálním směrováním. V každém kroku se tedy musím přibližovat cíli. Z toho plyne, že v prvním kroku musím udělat posun v jakékoli dimenzi směrem k cíli, čili mám n možností, kam se vydat. (Kde n je počet dimenzí, ve kterých se uzly u a v liší.) Neplyne z toho rovnou, že cest je n? Jakákoli další by musela v prvním kroku jít přes jeden z n již použitých uzlů a nebyla by s předchozími uzlově disjuktní. Jedna taková triviální n-tice je postupný průchod dimenzemi, tak že začnu pokaždé jinou (ABCD, BACD, CABD, DABC). Není to vše, co je potřeba pro plný počet? Nebo je jasné, že jich je n, ale jde v úloze o to zkontruovat VŠECHNY takové n-tice uzlově disjunktních cest? (plech.d)

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)

Řešení obdobného příkladu: 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

Viz skripta [2006] str. 161-162 && [2015] 9. přednáška / slide 33

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:

1. 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.
2. 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_n-1 (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í.

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)

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

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