Definice ze 4. přednášky (topologie)

秀一 幽遊
Flashcards by 秀一 幽遊, updated more than 1 year ago
秀一 幽遊
Created by 秀一 幽遊 over 5 years ago
25
0

Description

Definice ze 4. přednášky (topologie) MI-PAR

Resource summary

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čů
Show full summary Hide full summary

Similar

Definice z 2. přednášky
秀一 幽遊
Definice ze 4. přednášky (grafy)
秀一 幽遊
Definice z 5. přednášky
秀一 幽遊
Definice z 6. přednášky
秀一 幽遊
Grafy II.
Michal Roch
FITNESS
Montse Em
Statistics - topic 2
David Klingenber
Algebra
秀一 幽遊
sport
Saki Kuwae
Fundamentos
luis lopez
1. okruh
David Klingenber