4004279
| Question | Answer |
| Topologie | množina grafů (=instancí topologie), jejichž velikost a struktura je definovaná parametry (=hodnotami dimenzí). |
| Hierarchicky rekurzivní topologie | instance nižších dimenzí jsou podgrafy instancí vyšších dimenzí. |
| Inkrementálně škálovatelná topologie | definovaná pro \(\forall N\) - např. kružnice |
| Částečně škálovatelná topologie | definovaná pro některé, ale \(\infty\) mnoho \(N\). - krychle, mřížka, toroid... |
| Efektivně škálovatelná topologie | pro konst. \(k>0\) lze \( (N+k)\)-uzlovou instanci konstruovat z \(N\)-uzlové instance tak, že # odebraných hran je \(O(k)\). (~ pokud přidám k uzlů, musím přidat jen úměrně (konst * k) hran) |
| Spodní mez průměru N-uzlové řídké sítě (stupeň je omezen konstantou) | \(\Omega(\log N)\) vysvětlení: jdu BFS z jednoho uzlu, v prvním kroku pokryju maximálně k sousedů, v i-tém kroku max. \(k^i\) sousedů. Udělám nejvýše kroků kolik je průměr grafu \( N=O(k^{diam(G)}) \implies diam(G)=\Omega(\log_k N). \) |
| Požadavky na propojovací sítě | – symetrie – konstantní délka hran – škálovatelnost – malý průměr a malá prům. vzdálenost (snižuje komun. spoždění) – malý a konstantní stupeň uzlu – hierarchicky rekurzivní - vysoká souvislost – efektivně inkrementální topologie – velká bisekční šířika ( o algoritmicky, x konstrukčně) – vnořitelnost (do) jiných topologií – podpora pro směrování a kolekt. oper. |
| \(V(Q_n)\) | \(B^n\) (B je binární abeceda, která tu za čerta nejde zobrazit stylizovaně) |
| \(E(Q_n)\) | \( E(Q_n) = \{\langle x,neg_i(x)\rangle; x\in V(Q_n),0\leq i<n\} \) |
| \(|V(Q_n)|\) | \(|V(Q_n)|=2^n\) |
| \(|E(Q_n)|\) | \(|E(Q_n)|=n2^{n-1}\) |
| \(diam(Q_n)\) | \(diam(Q_n)=n\) |
| \(deg(Q_n)\) | \(deg(Q_n)=\{n\}\) |
| \( bw_e (Q_n)\) | \( bw_e (Q_n)=2^{n-1}\) |
| Je krychle řídký graf? | Stupeň je logaritmicky závislý na velikosti grafu, není to konstanta => NE |
| Hammingova vzdálenost v krychli | \(\varrho\) (vzdálenost mezi řetězci o n bitech – v kolika bitech se liší) # uzlů ve vzdálenosti i je \(C_{n, i}\) |
| Z jakých krychlí můžu vyrobit krychli dimenze N? | Kartézským součinem krychlí, kdy součet jejichž dimenzí bude roven N |
| Kanonická dekompozice krychle | \(Q_n\equiv Q_{n-1}[j=0]\times Q_{n-1}[j=1]\) ~půlení krychle, podle bitu \(j\) |
| Reprezentace právě 1 podkrychle | \(s_{n-1}\ldots s_1s_0 \), kde \(s_i\in\{0,1,{*}\}\) |
| Je krychle dimenze n (uzlově/hranově) symetrická? | Ano uzlově i hranově, protože \(Q_n\equiv Q_1^n\) kartézský součin symetrických grafů je taky symetrický |
| Kolik má krychle automorfismů? | \(2^n\times n!\) n! - hranové \(2^n\) - uzlové, kolik existuje binárních řetězců délky n |
| Je krychle optimálně souvislá? | Ano. \(\lambda(Q_n)=\kappa(Q_n)=n\) |
| Kolik existuje různých nejkratších cest mezi dvěma uzly ve vzdálenosti k v krychli? | k! |
| \(V(M(\ldots))\) | \(\{(a_1,a_2,..,a_n) ; 0\leq a_i\leq z_i-1\ \forall i\in\{1,..,n\}\} \) |
| \(E(M(\ldots))\) | \(\{\langle (..,a_i,..),(..,a_i+1,..)\rangle; 0\leq a_i\leq z_i-2\} \) |
| \(|V(M(\ldots))|\) | \(|V(M(\ldots))|=\Pi_{i=1}^n z_i\) |
| \(|E(M(\ldots))| \) | \(\Sigma_{i=1}^n(z_i-1)\Pi_{j=1\atop j\not=i}^n z_j \) |
| \(diam(M(\ldots))\) | \(\Sigma_{i=1}^n(z_i-1)=\Omega(\sqrt[n]{|V(M(\ldots))|})\) |
| \(deg(M(\ldots))\) | \(\{n,..,n+j\}, j=|\{z_i; z_i>2\}|\) |
| \(bw_e(M(\ldots))\) | \(\begin{cases} (\Pi_{i=1}^n z_i)/\max_iz_i & \text{jestliže} \max_iz_i \text{je sudé},\\ \Omega((\Pi_{i=1}^n z_i)/\max_iz_i) & \text{v opačném případě.}\\ \end{cases}\) |
| Je mřížka symetrická? | Obecně ne |
| Je mřížka efektivně škálovatelná? | Obecně ne. |
| Je mřížka optimálně souvislá? | Ano |
| Je mřížka bipartitní? | Ano, ale ne nutně vyvážená |
| \(V(K(\ldots))\) | \(V(K(\ldots))=V(M(\ldots))\) |
| \((E(K(\ldots))\) | \(\{\langle (..,a_i,..),..,a_i\oplus_{z_i}1,..)\rangle; 0\leq a_i<z_i\} \) |
| \(|E(K(\ldots))|\) | \(|E(K(\ldots))|=n\times \Pi_{i=1}^n z_i\) |
| \(diam(K(\ldots))\) | \(\Sigma_{i=1}^n\left\lfloor {z_i/2}\right\rfloor\) |
| \(deg(K(\ldots))\) | \(deg(K(\ldots))=\{2n\}\) |
| \(bw_e (K(\ldots))\) | \(bw_e (K(\ldots))=2 bw_e (M(\ldots))\) |
| Je toroid symetrický? | Ano, hranově i uzlově. |
| Je toroid hierarchicky rekurzivní? | Ne, ale dá se dekomponovat na kart. součin kružnic. Nejde rozložit na stejnorozměrné podtoroidy |
| Je toriod bipartitní? | Ano, pokud jsou VŠECHNY délky stran sudé. (Lichá kružnice nemůže být bipartitní) |
| \(V(wBF_n)\) | \(\{(i,x); 0\leq i<n \wedge x\in B^n\}\) |
| \(E(wBF_n)\) | \( \{\langle (i,x),(i\oplus_n1,x)\rangle, \langle(i,x),(i\oplus_n1, neg_i(x))\rangle \) \( \mid(i,x)\in V(wBF_n)\} \) |
| \(|V(wBF_n)|\) | \(n2^n\) |
| \(|E(wBF_n)|\) | \(n2^{n+1}\) |
| \(diam(wBF_n)\) | \(n+\lfB n\over 2\rfB\) |
| \(deg(wBF_n)\) | \(\{4\}\) |
| \(bw_e(wBF_n)\) | \(2^n\) |
| Je zabalený motýlek symetrický? | Uzlově ano. Hranově částečně hyperkubické x kružnicové hrany (vychází z představy CCC) |
| Je zabalený motýlek hierarchicky rekurzivní? | Ne |
| Je zabalený motýlek bipartitní? | Ano, za předpokladu, že n je sudé |
| Tvoří zabalený motýlek hamiltonovský graf? | Ano |
| \(V(oBF_n)\) | \(\{(i,x); 0\leq i\leq n \wedge x\in B^n\}\) |
| \(E(oBF_n)\) | \(\{\langle(i,x),(i+1,x)\rangle, \langle(i,x),(i+1, neg_i(x))\rangle\mid i<n\}\) |
| \(|V(oBF_n)|\) | \((n+1)2^n\) |
| \(|E(oBF_n)|\) | \(n2^{n+1}\) |
| \(diam(oBF_n)\) | \(2n\) |
| \(deg(oBF_n)\) | \(\{2,4\}\) |
| \(\bw_e (oBF_n)\) | \(2^n\) |
| Jak se ze zabaleného motýlka stal obyčejný? | Rozřezáním kružnic v uzlech (tj. uzel se rozdělí na dva uzly) |
| Je obyčejný motýlek symetrický? | Ne (ani uzlově, ani hranově) |
| Je obyčejný motýlek hamiltonovský? | Ne |
| Je obyčejný motýlek hierarchicky rekurzivní? | Ano, obsahuje dva \( oBF_{n-1}\) jako podgrafy |
| Je obyčejný motýlek bipartitní? | Ano. |
| Typy nepřímých sítí | – vícestupňové nepřímé sítě (Multistage Indirect Networks) MIN – stromové sítě – nepravidelné sítě (Internet...) |
| Vlastnost Banyan sítí \(N\times N\) | existuje jedinečná cesta mezi lib. dvojicí vstupu a výstupu |
| k-ární delta MIN | – obecný pojem, který popisuje všechny sítě, kt. mají obdélníkovou strukturu = skládají se ze stejně velkých sloupců přepínačů – mají banyan vlastnost – mají N/k přepínačů k x k |
| obecná k-ární MIN | K stupňů N/k přepínačů \(k\times k, N=k^n\) |
| Spodní mez na počet stupňů v MIN | \(K=\Omega(\log_k N)=\Omega(n)\) |
| Z jakých přepínačů se skládá MIN? | Statické a dynamické |
| Kdy je MIN přestavitelná? | Když má \(K=2\log N -1\) ~ např. Benešova síť (back-to-back butterfly) – pro zadanou permutaci vstupů na výstupy lze předpočítat bezkolizní nastavení přepínačů |
Want to create your own Flashcards for free with GoConqr? Learn more.