Fichas
Definice ze 4. přednášky (topologie)
Fichas del conjunto (73)
- 1Topologiemnožina grafů (=instancí topologie), jejichž velikost a struktura je definovaná parametry (=hodnotami dimenzí).
- 2Hierarchicky rekurzivní topologieinstance nižších dimenzí jsou podgrafy instancí vyšších dimenzí.
- 3Inkrementálně škálovatelná topologiedefinovaná pro \(\forall N\)
- např. kružnice - 4Částečně škálovatelná topologiedefinovaná pro některé, ale \(\infty\) mnoho \(N\).
- krychle, mřížka, toroid... - 5Efektivně škálovatelná topologiepro 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) - 6Spodní 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).
\) - 7Pož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. - 8\(V(Q_n)\)\(B^n\)
(B je binární abeceda, která tu za čerta nejde zobrazit stylizovaně) - 9\(E(Q_n)\)\( E(Q_n) = \{\langle x,neg_i(x)\rangle; x\in V(Q_n),0\leq i
- 10\(|V(Q_n)|\)\(|V(Q_n)|=2^n\)
- 11\(|E(Q_n)|\)\(|E(Q_n)|=n2^{n-1}\)
- 12\(diam(Q_n)\)\(diam(Q_n)=n\)
- 13\(deg(Q_n)\)\(deg(Q_n)=\{n\}\)
- 14\( bw_e (Q_n)\)\( bw_e (Q_n)=2^{n-1}\)
- 15Je krychle řídký graf?Stupeň je logaritmicky závislý na velikosti grafu, není to konstanta => NE
- 16Hammingova 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}\) - 17Z jakých krychlí můžu vyrobit krychli dimenze N?Kartézským součinem krychlí, kdy součet jejichž dimenzí bude roven N
- 18Kanonická dekompozice krychle\(Q_n\equiv Q_{n-1}[j=0]\times Q_{n-1}[j=1]\)
~půlení krychle, podle bitu \(j\) - 19Reprezentace právě 1 podkrychle\(s_{n-1}\ldots s_1s_0 \), kde \(s_i\in\{0,1,{*}\}\)
- 20Je 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ý - 21Kolik má krychle automorfismů?\(2^n\times n!\)
n! - hranové
\(2^n\) - uzlové, kolik existuje binárních řetězců délky n - 22Je krychle optimálně souvislá?Ano.
\(\lambda(Q_n)=\kappa(Q_n)=n\) - 23Kolik existuje různých nejkratších cest mezi dvěma uzly ve vzdálenosti k v krychli?k!
- 24\(V(M(\ldots))\)\(\{(a_1,a_2,..,a_n) ; 0\leq a_i\leq z_i-1\ \forall i\in\{1,..,n\}\}
\) - 25\(E(M(\ldots))\)\(\{\langle (..,a_i,..),(..,a_i+1,..)\rangle; 0\leq a_i\leq z_i-2\}
\) - 26\(|V(M(\ldots))|\)\(|V(M(\ldots))|=\Pi_{i=1}^n z_i\)
- 27\(|E(M(\ldots))| \)\(\Sigma_{i=1}^n(z_i-1)\Pi_{j=1\atop j\not=i}^n z_j
\) - 28\(diam(M(\ldots))\)\(\Sigma_{i=1}^n(z_i-1)=\Omega(\sqrt[n]{|V(M(\ldots))|})\)
- 29\(deg(M(\ldots))\)\(\{n,..,n+j\}, j=|\{z_i; z_i>2\}|\)
- 30\(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}\) - 31Je mřížka symetrická?Obecně ne
- 32Je mřížka efektivně škálovatelná?Obecně ne.
- 33Je mřížka optimálně souvislá?Ano
- 34Je mřížka bipartitní?Ano, ale ne nutně vyvážená
- 35\(V(K(\ldots))\)\(V(K(\ldots))=V(M(\ldots))\)
- 36\((E(K(\ldots))\)\(\{\langle (..,a_i,..),..,a_i\oplus_{z_i}1,..)\rangle; 0\leq a_i
- 37\(|E(K(\ldots))|\)\(|E(K(\ldots))|=n\times \Pi_{i=1}^n z_i\)
- 38\(diam(K(\ldots))\)\(\Sigma_{i=1}^n\left\lfloor {z_i/2}\right\rfloor\)
- 39\(deg(K(\ldots))\)\(deg(K(\ldots))=\{2n\}\)
- 40\(bw_e (K(\ldots))\)\(bw_e (K(\ldots))=2 bw_e (M(\ldots))\)
- 41Je toroid symetrický?Ano, hranově i uzlově.
- 42Je toroid hierarchicky rekurzivní?Ne, ale dá se dekomponovat na kart. součin kružnic. Nejde rozložit na stejnorozměrné podtoroidy
- 43Je toriod bipartitní?Ano, pokud jsou VŠECHNY délky stran sudé. (Lichá kružnice nemůže být bipartitní)
- 44\(V(wBF_n)\)\(\{(i,x); 0\leq i
- 45\(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)\}
\) - 46\(|V(wBF_n)|\)\(n2^n\)
- 47\(|E(wBF_n)|\)\(n2^{n+1}\)
- 48\(diam(wBF_n)\)\(n+\lfB n\over 2\rfB\)
- 49\(deg(wBF_n)\)\(\{4\}\)
- 50\(bw_e(wBF_n)\)\(2^n\)
- 51Je zabalený motýlek symetrický?Uzlově ano. Hranově částečně hyperkubické x kružnicové hrany (vychází z představy CCC)
- 52Je zabalený motýlek hierarchicky rekurzivní?Ne
- 53Je zabalený motýlek bipartitní?Ano, za předpokladu, že n je sudé
- 54Tvoří zabalený motýlek hamiltonovský graf?Ano
- 55\(V(oBF_n)\)\(\{(i,x); 0\leq i\leq n \wedge x\in B^n\}\)
- 56\(E(oBF_n)\)\(\{\langle(i,x),(i+1,x)\rangle, \langle(i,x),(i+1, neg_i(x))\rangle\mid i
- 57\(|V(oBF_n)|\)\((n+1)2^n\)
- 58\(|E(oBF_n)|\)\(n2^{n+1}\)
- 59\(diam(oBF_n)\)\(2n\)
- 60\(deg(oBF_n)\)\(\{2,4\}\)
- 61\(\bw_e (oBF_n)\)\(2^n\)
- 62Jak 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)
- 63Je obyčejný motýlek symetrický?Ne (ani uzlově, ani hranově)
- 64Je obyčejný motýlek hamiltonovský?Ne
- 65Je obyčejný motýlek hierarchicky rekurzivní?Ano, obsahuje dva \( oBF_{n-1}\) jako podgrafy
- 66Je obyčejný motýlek bipartitní?Ano.
- 67Typy nepřímých sítí– vícestupňové nepřímé sítě (Multistage Indirect Networks) MIN
– stromové sítě
– nepravidelné sítě (Internet...) - 68Vlastnost Banyan sítí \(N\times N\)existuje jedinečná cesta mezi lib. dvojicí vstupu a výstupu
- 69k-á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 - 70obecná k-ární MINK stupňů N/k přepínačů
\(k\times k, N=k^n\) - 71Spodní mez na počet stupňů v MIN\(K=\Omega(\log_k N)=\Omega(n)\)
- 72Z jakých přepínačů se skládá MIN?Statické a dynamické
- 73Kdy 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čů
Información
- Descripción
- Definice ze 4. přednášky (topologie) MI-PAR
- Creado por
- 秀一 幽遊 · nov 2015
- Actualizado
- 10 ene 2017
- Visitas
- 60
- Etiquetas
- Valoración