Differences

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

--- users:martin.kocicka:pdp:4b [2017/06/13 07:14] – vytvořeno martin.kocicka
+++ users:martin.kocicka:pdp:4b [2017/06/13 11:21] (current) – [PAR - Vyřešené zkouškové příklady za 4 body] martin.kocicka
@@ Line 1: / Line 1: @@
-======= PAR - Vyřešené zkouškové příklady za 4 body =======
+======= PDP - Vyřešené zkouškové příklady za 4 body =======
@@ Line 246: / Line 246: @@
 <math>\mathtt{dil}\left(\right)\geq\frac{2^{\left\lceil \frac{\left(n-1\right)}{2}\right\rceil }}{n}</math>
-===== CBTn očíslovaný InOrder a jeho namapování na Q(n+1) s load=1 a dil=2 =====
-CBT<sub>n</sub> očíslovaný InOrder, dokažte že mapování na Q<sub>n+1</sub> jde provést s load = 1 a dil = 2. Spočítejte co nejpřesněji průměrnou hodnotu dilatace.
-★ //Bylo ve zkoušce: [[par_zkouska_2012-02-03|2012-02-03]] //
-==== Řešení ====
-:!://Viz skripta EN [2009] str. 60 nebo CZ [2006] str. 80//
-Konstrukční důkaz viz. obrázek:
-{{:škola:předměty:mi-par:cbtnqndil2load1.png|}}
-n = 1 - Očísluje se binárně in order od 1. Hammingova vzdálenost(a tedy i dilatace) je max. 2.
-n = n + 1 - Přidá se nový kořen a levý podstrom n s prefixem 0, pravý podstrom n s prefixem 1. Prefix nemění Hammingovu vzdálenost, takže v rámci podstromu zůstane stejná. A novým kořenem jsme zase přidali jednu hranu s dilatací 1 a jednu s dilatací 2. Tzn. průměrná dilatace bude 1.5.
-**Ostatní intuitivní pokusy o řešení:**
-Jde o to že se očísluje CBT od jedničky pomocí InOrder (levý podstrom, kořen, pravý...), Qn+1 se očísluje klasicky podle dimenzí (já to čísloval od nuly ale mělo by to jít i od jedničky).
-Řešení pro n<=2 se dá jednoduše nakreslit a load=1 a dil=2 je na první pohled vidět z obrázků
-{{:škola:předměty:mi-par:vyřešené_příklady:cbtn_do_qn.jpg|}}
-Pozn. Pokud si to někdo kreslí a nevychází mu to, tak možná to je tim, že je třeba tu krychli očíslovat opravdu v tomhle pořadí, jako je na obrázku (akorát teda ne od 0), ne třeba po směru hodinových ručiček, což třeba mně dává větší smysl, ale pak tam ty vzdálenosti prostě nevychází.
-Dokázat že to tak platí obecně lze přes Hammingovu vzdálenost... CBT očíslovaný InOrder má potomky všech uzlů daleko maximálně dvě (Hammingově) (neptejte se mě jak?), takže když se to přenese do krychle, je jasné že dilatace bude maxiálně dvě...
-** Průměrná diletace **[[http://slovnik-cizich-slov.abz.cz/web.php/slovo/diletant]]
-Z náčrtů je vidět že polovina hran má dil=1 a druhá dil=2 (to Tvrdíkovi stačilo), takže průměrná dilatace je 1.5 ... Určitě by se to taky dalo dokázat pomocí nějakého šíleného vzorce přes tu Hammingovu vzdálenost...
-Pozn.(ckd.4ever): Myslím, že ten vzorec nebo vysvětlení postavené na Hammingově vzdálenosti by nebylo tak těžké sestavit. Lze vycházet z binárního zápisu inorder číslování uzlu stromu, podle něj je pak snadné namapovat CBTn na Qn+1, již jen podle samotných hodnot uzlů bin. stromu. Lze už ve stromu vidět, že Hammingova vzdálenost těchto binárních čísel uzlů, které mají mezi sebou hranu, je v polovině případů 2 a v polovině 1. Pro názornost jsem si dovolil obrázek z vlastní zahrádky.
-{{:škola:předměty:mi-par:vyřešené_příklady:cbt2_do_q3.jpg|}}
-Pozn. Akorát Tvrdík říkal, že to má jednu podmínku a sice že se nesmí začít číslovat od nuly, jinak to nevyjde. Tobě to ale zdá se vyšlo, i když si začal od nuly, tak nevim. :o)
-Edit: (MiKe)... pravdaze mu to nevychazi... musis zacit 1 v inorder cislovani, aby si mel vsechny hrany lisici se v 1, nebo 2 bitech... pak to nemusis kreslit ani do stromu, staci oznacit hrany bitem kterym se lisej... (FIT prednaska 5, slide 19 pro ukazku oznaceni bitu)
-Pozn. (DW): CBT je symetrický podle kořenu, takže v něm je průměrná hodnota excentricity a exc(CBTn) = n, to samé se dá udělat s Qn. Ta je uzlově symetrická, což je o to snazší a tak exc(Qn+1) = n+1. Pokud dosadíme hodnoty pro CBT2 a Q3 do vzorce pro dilataci dostáváme:
-dil = exc(Q3) / exc(CBT2) =>
-dil = 3 / 2 =>
-dil = 1,5
-bez důkazu indukcí je to za 2b ze 4
-Dôkaz indukciou (pokus o predklad z ENG skripta str 60.):
-Dekomponujeme Qn+1 na dve podkrychle: Qn s vrcholmi 0xxx a Qn s vrcholmi 1xxx (teda krychle se má číslovat od 000). Ďalej dekomponujeme CBTn na ľavý podstrom T_L s podkoreňom r_L a pravý podstrom T_R s podkoreňom r_R a hlavný koreň r (ktorý je nad nimi).
-Indukčný predpoklad je, že podstrom T_L je vnorený do podkrychle Qn 0xxx s load=1 a dil=2, podkoreň r_L má index 010xx. Obdobne je strom T_R vnorený do podkrychle Qn 1xxx, podkoreň r_R má index 110xxx. Koreň r (ktorý je nad r_L a r_R) má index 100xx a teda je v podkrychli Qn s vrcholmi 1xxx.
-A teraz k výpočtu dilatácie: hrana <r, r_L> má dilatáciu 2 a hrana <r, r_R> má dilatáciu 1. Keď si tieto dve hrany predstavíme v tom najmenšom strome (ktorý má len 2 hrany), tak môžeme povedať, že polovica hrán ma dil=1 a polovica má dil=2. Vzhľadom k tomu, že toto platí pre všetky nadstromy tak to platí celkovo a dilatácia je 1,5.
-Okrem toho, myslím že na skúške mi povedal niečo v tom zmysle, že dilatace nesouvisí s excentricitou, ale nie som si istý.
 ===== Spodní mez dilatace při vnoření hyperkrychle do 2D toroidu =====
@@ Line 320: / Line 264: @@
 ====== Algoritmy ======
-===== Plně paralelní PRAM algoritmus pro konstrukci Eulerovy kružnice =====
-Popište paralelní algoritmus pro konstrukci eulerovské kružnice v N uzlovém stromu A na EREW PRAM s počítači s P procesory. Popište potřebné prezentace stromu S, odvoďte výraz pro paralelní čas T(n,p) v standardním PRAM, předpokládejte, že lokální operace trvají čas 1, operace R a W trvají čas k>1. **Dokažte korektnost algoritmu.**
-==== Řešení ====
-:!://Viz přednáška 7, slide 35 [2014/15] příp. slide 31 [2007/08]//
-:!://Viz česká skripta [2006] strana 108//
-Předpokládáme Eulerovský strom, kde každá hrana původního stromu je nahrazena dvojicí antiparalelních hran. Strom reprezentujeme jako dva seznamy:
-  - seznam uzlů s ukazateli do seznamu hran (Tvrdík značí jako Adj),
-  - seznam hran tvořený podseznamy hran incidujícími s jednotlivými uzly (Tvrdík značí jako AA). U každé hrany je ukazatel na její antiparalelní dvojče (ukazatel //sibling//) a podseznamy tvoří cyklus (//next// je ukazatel do AA na další hranu vycházející z téhož uzlu.).
-{{:škola:předměty:mi-par:vyřešené_příklady:euler.jpg|}}
-{{http://i.imgur.com/opAQpTV.png|}}
-Máme-li tuto reprezentaci, pak pro **p = 2n - 2** (počet hran) je algoritmus pro konstrukci Eulerovy cesty následující. ET je pole následníků (cyklicky spojovy zoznam hran).
-<code c>
-//Algorithm EREW_PRAM_Eulerian_Tour(in: AA; out: ET;)
-for all arcs e in AA of a tree T do_in_parallel
-    ET[e] = AA[e].Sib->Next;
-</code>
-To samé v jiné syntaxi:
-<code python>
-# edges - seznam hran AA
-# succs - seznam následníků [ID hrany => ID následující hrany]
-def createEulerianTour(edges) {
-    succs = array( edges.length );
-    for edge in edges do_in_parallel {
-        succs[edge] = edge.sibling.next;
-    }
-    return succs;
-}
-</code>
-Pokud je **p < 2n-2**, potom každý procesor vyplňuje buňky pole <del>EA</del> ET pro <math>\normalsize \frac{2n-2}{p}</math> hran. Původní 1krokový algoritmus je nyní dokončen v čase
-<math>T(n,p) = O(\frac{m}{p})</math>, <math>C(n,p) = p\cdot T(n,p) = O(m)</math>, kde <math>m=2n-2</math>.
-Sekvenční algoritmus musí projít všechny hrany => <math>\normalsize SU(n)=2n-2</math> => algoritmus je optimální (cenovo optimálny, pretože paralelná cena je rovnaká ako sekvenčná cena).
-:?: Mohl by nekdo tohle vysvetlit? Protoze ja vidim jenom to, ze je potreba pro kazdy uzel precist sourozence, pak precist nasledujici hranu tohoto sourozence a pak ji zapsat do vystupniho pole nasledniku. Tzn. T(n) = n * 3 * k; <math>T(n,p) = {\Large\lceil}\frac{n}{p}{\Large\rceil} \cdot 3 \cdot k</math>
-Doplnenie T(n,p):
-edge.sibling.next je permutacia vsetkych hran v grafe a vypocet ET sa zapisuje do inej casti pameti, preto tieto operacie mozu na EREW prebiehat paralene na vsetkych procesoroch bez problemov v case O(1).
-Dokaz korektnosti algoritmu (prebrany z EN skript strana 105): \\
-Algoritmus je zalozeny na pravidle prechodu labyrintom. Vieme, ze prechadzame strom, takze v nom neexistuje cyklus. Preto, ak vzdy "zabocime" doprava, tak sa v jednom momente dostaneme spet na povodne miesto. Pravidlo "zabocime doprava" je vykonane tym, ze vzdy vykoname operaciu edge.sibling.next
-[ martin: uznal tvrdik takovyhle dukaz? ]
-hanouto: Ve zkoušce 5.2.2016 jsem doslova napsal "důkaz je založen na průchodu labyrintem tak, že se stále dotýkám zdi pravou rukou". Ostatní jsem měl v pořádku, na nic se neptal a dal plný počet.
 ===== Konstrukce Hamiltonovské kružnice v obecném grafu =====
@@ Line 665: / Line 554: @@
 ====== Nepřímé sítě ======
-===== Důkaz bezkoliznosti operace přeložení na indBFn =====
-<math>indBF</math> důkaz, že operace přeložení je bezkolizní, //x->x xor w// (//w// je n-bitová posloupnost)
-★ //Bylo ve zkoušce: [[.:par_zkouska_2012-12-18|2012-12-18]]//
-==== Řešení ====
-Tady je dobrý nakreslit tabulku XORu a k tomu napsat, že když se čísla liší, tak se provede výměna, když jsou čísla stejné, jede se rovně. Taky je dobrý nakreslit schéma infBF (pokud není už v zadání) a udělat tam třeba posun o w=1 i s vyznačením cest.
-Tvrdík hlavně chce vidět to, že když je XOR řetězec třeba 011 tak se v prvních dvou úrovnich dají všechny přepínače křížem a v poslední všechny na rovno.
-----
-Nutné si uvědomit:
-  - Musíme si uvědomit, že nepřímý motýlek je síť přepínačů (X označím přepnutí a = označím identitu). To zapojení těch přepínačů neříká nic jiného než to, jak budu vystavovat jednotlivé bity adresy. Navíc platí hiearchická rekurze struktury motýlek.
-  - Přeložení není nic jiného než cílová_adresa=počáteční_adresa XOR vektor_pro_přeložení. XOR funguje tak, že kde je 1, tak dojde k negaci bitu cílové_adresy (např. 010 xor 100 = 110).
-  - Pokud mám tedy v přeložení na pozici vektor_pro_přeložení hodnotu 1, tak všechny přepínače se nastaví do polohy X a směřují pakety do disjunktní podmotýlků, kde se problém opakuje pro jiný bit vektoru_pro_přeložení. V případě hodnoty 0 dochází k identitě a problém je úplně stejný.
-Formálně zapsanáno:
-//Indukční předpoklad//
-Dokážeme, že se na pozici i nemohou srazit dva pakety. označme Xi bit i ve vektoru přeložení. Na všech přepínačích na pozici i mohou nastat dva jevy:
-  - Pokud je Xi = 0, tak se přepínač nastaví na identitu (tzn. nepřeklopí se) a nedojde tedy ke srážce
-  - Pokud je Xi = 1, tak se přepínač nastaví na překlopení (tzn. výstupy se prohodí) a nedojde tedy ke srážce
-//Indukční krok//
-Pokud pakety dorazí do prvního sloupce motýlku indBFn, tak jsou poté rozděleny a směřovány do dvou podmotýlků (namalujte si obrázek) menší dimenze indBFn-1
-  * lichého motýlku -> LSB bit je nastaven na 1
-  * sudého motýlku -> LSB bit je nastaven na 0
-Díky hiearchické rekurzi můžeme aplikovat ten samý postup v jednotlivých podmotýlcích (tzn. problém je stejný, ale na jiném bitu vektoru přeložení).
-Edit by vd: Stejný příklad je za 6 bodů, tam je to také dobře vysvětleno. Přikládám pro úplnost tabulku XORu. Označme <math>X</math> jako adresu paketu a <math>W</math> jako vektor přeložení. Mohou nastat **pouze 2 situace**:
-) Pokud <math>w_{k}=0</math>, pak zůstává k-tý bit adresy **nezměněn** viz tabulka XORu:
-^ <math>x_{k}=0</math> ^ <math>w_{k}=0</math> ^ <math>x_{k}\oplus w_{k}</math> ^
-| 0                    | 0                    | 0                              |
-| 1                    | 0                    | 1                              |
-) Pokud <math>w_{k}=1</math>, pak se k-tý bit adresy **neguje** a přepínače se nastaví na kříž, viz tabulka XORu:
-^ <math>x_{k}=0</math> ^ <math>w_{k}=0</math> ^ <math>x_{k}\oplus w_{k}</math> ^
-| 0                    | 1                    | 1                              |
-| 1                    | 1                    | 0                              |
-{{http://i.imgur.com/Dhrj3CE.png?600|}}
-Nepřímý motýlek indBF_4.
 ===== Odvodit vztah pro průměrnou vzdálenost v obousměrném indBFn =====
@@ Line 802: / Line 637: @@
    - (000 → prepinacA0 → prepinacB1 → prepinaC1 -> prepinaB3 -> prepinaA2 → 100)
    - (000 → prepinacA0 → prepinacB1 → prepinaC3 -> prepinaB3 -> prepinaA2 → 100)
-===== Konstruktivní důkaz, že Closova síť je striktně neblokující =====
-Dokažte konstruktivně, že Closova síť <math>(m, n, r)</math>, kde <math>m \geq 2n - 1</math> je striktně neblokující. Demonstrujte na příkladu Closovy sítě (3,2,3) na obrázku.
-{{:škola:předměty:mi-par:2015-01-28_closova-sit.png}}
-★ //Bylo ve zkoušce: [[.:par_zkouska_2015-01-28|2015-01-28]]//
-==== Řešení ====
-(viz [[http://en.wikipedia.org/wiki/Clos_network#Strict-sense_nonblocking_Clos_networks_.28m_.E2.89.A5_2n_-_1.29_-_the_original_1953_Clos_result|Wikipedia]]) a viz přednáška 9 (2014/2015) slide 39/51:
-  * Striktně neblokující = mezi libovolnou dvojicí neobsazených portů lze vytvořit spojení, aniž bychom museli přearanžovat již existující spojení.
-  * Síť má
-    * //r// vstupních přepínačů s //n// vstupními a //m// výstupními porty (1. stupeň)
-    * //m// středních přepínačů s //r// vstupními a //r// výstupními porty (2. stupeň)
-    * //r// výstupních přepínačů s //m// vstupními a //n// výstupními porty (3. stupeň)
-  * Směrovací volba proběhne pouze na začátku
-  - Existuje volný vstupní port //a.x// a volný výstupní port //b.y// (1 ≤ //a// ≤ //r//; 1 ≤ //b// ≤ //r//; 1 ≤ //x// ≤ //n//; 1 ≤ //y// ≤ //n//)
-  - V nejhorším případě je v přepínači //a// obsazeno //n-1// vstupních portů a v přepínači //b// je obsazeno //n-1// výstupních portů. V nejhorším případě ještě neexistuje žádné spojení mezi přepínači //a// a //b//, tj. //n-1// spojení z //a// vede do **jedněch //n-1// středních přepínačů** a //n-1// spojení z //b// **vede do druhých //n-1// přepínačů**.
-  - => //2n-2// středních přepínačů nelze použít (buďto je již obsazena cesta z //a// do nich, nebo z nich do //b//). V nejhorším případě je 2n-2 středních přepínačů obsazených.
-  - Potřebujeme **alespoň jeden** střední přepínač **navíc**, abychom mohli vytvořit spojení mezi přepínači //a// a //b//. //2n-2// (které již máme obsazené cestou **z //a//**, nebo cestou **do //b//**) //+ 1// (který přidáme) = //2n-1//.
-  * Středních přepínačů je //m//, //m// tedy musí být //m ≥ 2n-1//
-//kotynvla//: Zkusil jsem to nakreslit pro případ (m, n, r) = (3, 2, 3): //Obyč. tužkou// je //struktura sítě//, **černým centropenem** jsou již **existující spojení** a __modrou propiskou__ je __nově vytvářené spojení__. Pod obrázkem je popsáno směrovací rozhodování.
-{{:škola:předměty:mi-par:clos-323.png?200| (by kotynvla)}}
-//VasekJ//: PT mi říkal, že chtěl slyšet, že když je m >= 2n-1, tak je Closova síť striktně neblokující (2014/15 přednáška 4, slide 48/51). Jestli jsem ho dobře pochopil, v takovém případě si můžu v síti dělat co chci a vždycky mi to vyjde neblokující (prosím potvrdit).
-//kotynvla//: **Mně říkal prof. Tvrdík, že pro plný počet bodů mu stačí napsat do písemky přesně to, co je na slidu 48 přednáška 4 (ZS 14/15), ale hlavně, že "je to přepínač NxN pro N = rn. Pro každou dvojici vstup-výstup existuje m hranově disjunktních cest, směrovací volba pouze na začátku. Potom je striktně neblokující pro m >= 2n - 1". Navíc se hodilo napsat, co je m, n a r.**
-//kubisjir//: (ZS 2015/2016) Pokud je otázka na konstruktivní důkaz toho, že Closova síť je striktně neblokující (jak je nyní napsáno v zadání), pak se neptá na to co je na slidu 48 přednáška 4. Nutné je popsat a vyznačit na zadaném obrázku to, co je na slidu 39/51 přednáška 9 ZS-15/16.
-====== .  ======
-{{tag>škola s_řešením předměty zkoušky}}