Differences

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

--- users:martin.kocicka:pdp:2b [2017/06/09 06:21] – [Řešení] martin.kocicka
+++ users:martin.kocicka:pdp:2b [2017/06/13 14:11] (current) – [Spodní mez počtu kroků OAB/SF na Qn] martin.kocicka
@@ Line 5: / Line 5: @@
 U spodních mezí komunikačních operací dávejte pozor na to, že se jedná o spodní meze. Neměli byste tedy tvrdit, že nějaká operace trvá tolik a tolik, ale že teoreticky musí trvat nejméně takto. Tzn. upozornit v testu na to, že se jedná o spodní mez, ale že to vůbec neznamená, že takový alogirtmus existuje. Nemusí. Snad to dává smysl, Tvrdík za to bral body.
-===== Spodní mez uzlového zatížení(load) při vnoření 3D mřížky M(z1,z2,z3) do 2D toroidu T(w1,w2) =====
+===== *Spodní mez počtu kroků OAB/SF na Qn =====
-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: [[škola:předměty:mi-par:par_zkouska_2013-01-30|2013-01-30]], [[škola:předměty:mi-par:par_zkouska_2013-12-20|2013-12-20]]//
-==== Řešení ====
-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 (K(...)).
-<math>max(1, \frac{{z_1}{\cdot}{z_2}{\cdot}{z_3}}{{w_1}{\cdot}{w_2}}) == \text{load}\left(\varphi,\xi\right)\geq\left\lceil \frac{\left|V\left(G\right)\right|}{\left|V\left(H\right)\right|}\right\rceil = \lceil \frac{{z_1}{\cdot}{z_2}{\cdot}{z_3}}{{w_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
-===== Spodní mez počtu kroků AAB/SF na Qn =====
-Jaká je spodní mez počtu kroků nekombinujícího AAB na Q<sub>n</sub>. Všeportový. Odvoďte.
-==== Řešení ====
-  * 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>\lceil \frac{2^n-1}{n} \rceil</math>
-**Trocha teorie:**
-   * AAB - kolektivní komunikační operace typu vysílání všichni-všem
-   * Přednáška 2014/10 slide 6 bod 2
-===== Spodní mez počtu kroků OAB/SF na Qn =====
 Jaká je spodní mez počtu kroků nekombinujícího OAB na Q<sub>n</sub>. Všeportový. Odvoďte.
@@ Line 47: / Line 14: @@
 Zdroj pošle paket všem sousedům a jakýkoli jiný uzel obdržený paket zkopíruje a pošle ho zbývajícím sousedům.
-===== Spodní mez počtu kroků OAS/SF na Qn =====
-Jaká je spodní mez počtu kroků nekombinujícího OAS na Q<sub>n</sub>. Všeportový. Odvoďte.
-==== Řešení ====
-  * Uzel musí postupně kontaktovat všechny ostatní uzly <math>2^{n}-1</math>. Ale za jeden krok může poslat pouze <math>n</math> zpráv. Nejrychleji tedy odešle všechny zprávy v <math>\lceil \frac{2^n-1}{n} \rceil</math> krocích.
-<math> \rho_{OAS,k}^{SF}\left(G,s\right)=\left\lceil \frac{\left|V\left(G\right)\right|-1}{k}\right\rceil =\left\lceil \frac{2^{n}-1}{n}\right\rceil </math>
-===== Spodní mez počtu kroků AAS/SF na Qn =====
-Jaká je spodní mez počtu kroků nekombinujícího AAS na Q<sub>n</sub>. Všeportový. Odvoďte.
-==== Řešení ====
-  * Každý uzel <math>2^{n}</math> <del>musí postupně kontaktovat všechny ostatní uzly <math>2^{n-1}</math></del>. Jedna zpráva z uzlu půjde alespoň dimenzi kroků. V jednom globálním kroku však může každý uzel <math>2^{n}</math> odeslat pouze zprávu do každé dimenze <math>n</math>. <math>(2^{n-1} \cdot 2^{n} \cdot n )/(2^{n} \cdot n)= 2^{n-1}</math>
-:?: dotaz: Opravdu je tohle zduvodneni korektni? Vzdyt preci neni pravda, ze ostatnich uzlu je <math>2^{n-1}</math>. Ostatnich uzlu je <math>2^{n}-1</math>. Kdyz vezmu i samotny zdrojovy uzel (ve vzdalenosti 0) je pak prumerna vzdalenost od zdroje k <math>2^{n}</math> cilum <math>n/2</math>. Zpravy potrebuje rozesilat vsech <math>2^{n}</math> uzlu, ale v jednom kroku <math>2^{n}</math> uzlu zaroven odesila zpravy do <math>n</math> smeru. Vyjde to stejne, ale jak rikam, jde mi hlavne o ten duvod, kteremu dost nerozumim. (bliznjan)
-:?: Opravdu to má být <math>2^{n-1}</math>? Já si spíš myslím, že když každý krok můžu vyslat maximálně <math>n*2^n</math> zpráv a obdržet celkem potřebuji <math>(2^{n}-1)*2^n</math> zpráv, tak by výsledek měl být spíš <math>((2^{n}-1)*2^n)/(n*2^n) = (2^{n}-1)/n</math>. Nebo se mýlím?
-:?: Reakce na předchozí otázku: Podle skript (10.1.4 Příklad výpočtů spodních mezí) to je skutečně těch <math>2^{n-1}</math>. Ohledně odečítání té jedničky si nejsem jistý, ale v tvém výpočtu chybí ta úvaha, že ta zpráva musí putovat přes další uzly, takže nestačí ji odeslat a zapomenout na ni jako by už neexistovala, ona totiž přidá práci ostatním uzlům (a stejnětak sousední uzly takto přidávají práci našemu jednomu uvažovanému uzlu) a té práce bude v celém grafu dohromady tolik, jak moc daleko ty zprávy musí odesílat. Tím, že pro každý uzel ve vzdálenosti <math>n</math> existuje uzel ve vzdálenosti <math>0</math>, pro každý ve vzdálenosti <math>n-1</math> existuje ve vzdálenosti <math>1</math> až po <math>n/2</math>, tak průměrně každá zpráva musí provést <math>n/2</math> kroků, proto je to potřeba vynásobit ještě právě tím <math>n/2</math>, díky čemuž ve finále obě <math>n</math> zmizí a <math>(2^{n})/(2)=2^{n-1}</math>. (bliznjan)
-:!: **Vysvětlení ze skript (CZ 2006 str. 171):** AAS je vlastně <math>2^{n}</math> operací OAS běžících současně a proto se celková práce opět sčítá, celková práce <math>h_{AAS}(Q_{n}) = 2^{n}*h_{OAS}(Q_{n}) = n*2^{2*n-1}</math>. Plně duplexní všeportová <math>Q_{n}</math> může provést v jednom paralelním kroku nejvýše <math>n*2^{n}</math> hopů. Proto celkovou práci pro AAS nemůže zvládnout dříve než v <math>\frac{n*2^{2*n-1}}{n*2^n} = 2^{n-1}</math> krocích. (maurever)
-Poznámka: Souhlasím s posledním vysvětlením, viz přednáška 10, slide 6, rok 2016. Jen doplním, že v této přednášce se počítá se spodní mezí <math>\eta</math> a nikoliv horní, nicméně vychází to stejně. A ještě pro úplnost tento vzorec: <math>\eta_{OAS}\left(Q_{n}\right)=\sum_{k=1}^{n}k*\binom{n}{k}=n2^{n-1}</math>
 ===== Spodní mez pro OAB/WH na toroidu =====
@@ Line 132: / Line 73: @@
 **Poznámka by nguyedu7:** Ve jmenovateli zlomku je **nejnižší stupeň uzlu** v grafu. Pokud by se jednalo o 3D mřížku, tak by k = 3 (rohový uzel)
-====== Hamiltonování a cykly ======
+====== Cykly ======
-===== Neexistence Hamiltonovské cesty na Q4 pro zadané 2 uzly =====
-Dokažte, že v **Q<sub>4</sub>** mezi uzly u = 1010 a v = 0101 neexistuje Hamiltonovská cesta.
-==== Řešení ====
-Hamiltonovská cesta je taková cesta v daném grafu, která prochází každým jeho vrcholem právě jednou. V grafu **Q<sub>n</sub>** je délka Hamiltonovské cesty o jedno nižší než počet uzlů, tedy **2<sup>n</sup> - 1**. Z toho vyplývá, že její délka je **vždy liché** číslo.
-Uzly v **Q<sub>n</sub>** jsou značeny binárními řetězci o délce **n** a dva uzly jsou sousední, právě když se liší v 1 bitu. Přechod z uzlu **u** do sousedního uzlu po hraně v dimenzi **i** je tedy negace i-tého bitu řetězce **u**. Cestu mezi dvěma uzly **u** a **v** tedy lze jednoznačně popsat jako n-tici dimenzí hran, po kterých jsem postupně šel. Je zřejmé, že počet jejích prvků odpovídá vzdálenosti uzlů. Jelikož dvojitá negace je identita a jsme v ortogonálním systému, tak platí následující úsudek. Pokud se uzly **u** a **v** liší v i-té dimenzi (neboli i-tém bitu), tak cesta mezi nimi musí obsahovat //lichý// počet hran v i-té dimenzi. Z toho vyplývá, že pokud se uzly **u** a **v** liší v lichém počtu bitů, tak mezi nimi existují pouze cesty liché délky a pokud v sudém, tak pouze sudé délky.
-Zadané uzly **u** a **v** se liší v sudém počtu bitů, takže mezi nimi nemůže existovat cesta liché délky. Jelikož víme, že Hamiltonovská cesta v **Q<sub>n</sub>** má vždy lichou délku, tak je jasné, že mezi těmito uzly Hamiltonovská cesta neexistuje.
-===== Neexistence hamiltonovské kružnice v mřížce M(7,5)  =====
-Dokažte, že na **M(7,5)** neexistuje Hamiltonovská kružnice (nejsnáze přes důkaz sporem).
-★ //Bylo ve zkoušce: [[škola:předměty:mi-par:par_zkouska_2013-01-09|2013-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.
-==== Obecná varianta ====
-★ //Bylo ve zkoušce: [[škola:předměty:mi-par:par_zkouska_2016-01-28|2016-01-28]]//
-Formulujte a dokažte existenci Hamiltonovské kružnice na 2D mřížce M(z1,z2)
-FIXME
-postup je úplně stejný, jako v příkladě nahoře, akorát musíme rozhodnout, kdy má mřížka sudý a kdy lichý počet vrcholů
-možnosti jsou S*S, S*L, L*S, L*L - S = sudý (2k), L = lichý (2k+1)
-k * 2l = 4kl  - vždy sudé (4* vše přebije)
-(2k+1) * 2l = 4kl + 2l - vždy sudé
-(2k+1) * (2l+1) = 4kl + 2k + 2l + 1 - vždy liché (+1 vše obrátí na liché)
-takže ham.kružnice existuje vždy, kromě případu, kdy obě dimenze mřížky jsou liché, pak má lichý počet vrcholů + parita z příkladu nad tímto.
-:!: To neni tak jednoduchy. Uz proto, ze treba v M(1,4) asi zadna Ham. kruznice neexistuje i kdyz ma sudej pocet uzlu. Navic to ze nejakej graf ma sudej pocet uzlu znamena jenom to, ze POKUD v nem existuje Ham. kruznice, pak bude mit sudou delku. Bude potreba obecne popsat konstrukci takovy kruznice.
 ===== 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í ====
@@ Line 189: / Line 83: @@
 **Důkaz:** 2-D toroid vznikne jako kartézský součin 1-D toroidů **K<sub>1</sub>(6)** a **K<sub>2</sub>(10)**. Na **K<sub>1</sub>** ani **K<sub>2</sub>** 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 =====
+====== Nejkratší cesty, počet cest ======
-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-1} b_{n-2} ... 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.
-====== Nejkratší cesty, počet cest ======
 =====  Počet všech nejkratších cest mezi dvěma uzly v n-dimenzionální mřížce  =====