Perhosverkko.
Kaarityssa verkossa kuva laitetaan
"rullalle"
siten, etta kunkin rivin alku- ja
loppusolmu yhtyvat.
Perhosverkossa on N = n2n solmua. Solmun osoite on muotoa (x; r), missa 0 x 2n 1 on rivinumero ja 0 r n 1 sarakenumero.
Kaarityssa perhosverkossa solmujen (x; r) ja (y; s) valilla on yhteys, jos s = (r + 1) mod n ja lisaksi joko
1. x = y ("suora kaari") tai
2. x ja y eroavat tasan (s + 1). bittipositiossa ("vaihtokaari").
Perhosverkosta saadaan hyperkuutio romauttamalla kukin rivi yhdeksi isoksi solmuksi.
Toisin kuin hyperkuutiossa, perhosverkossa solmujen aste on vakio, ja kaaria on O(N). Jos siis onnistumme suorittamaan reitityksen samassa ajassa kuin hyperkuutiossa, tama on jossain mielessa tehokkaampi topologia.
Myos perhosverkossa otamme lahtokohdaksi bitinkorjausalgoritmin, jota tassa kaytetaan vain rivin korjaamiseen:
1. Olkoot lahto- ja maalisolmu (x; r) ja (y; r), missa x = (a1; : : : ; an) ja y = (b1; : : : ; bn).
2. Toista arvoilla i = 0; : : : ; n:
(a) j := ((i + r) mod n) + 1
(b) Jos aj = bj, siirry sarakkeeseen j mod n suoraa kaarta, muuten vaihtokaarta.
Satunnaistettu versio on nyt kolmevaiheinen. Solmusta (x; r) solmuun (y; s) matkalla oleva paketti reititetaan seuraavasti:
Vaihe I: valitse satunnainen w 2 f 0; : : : ; 2n 1 g ja reitita solmuun (w; r) bitinkorjauksella.
Vaihe II: reitita solmuun (w; s) suoria kaaria pitkin.
Vaihe III: reitita solmuun (y; s) bitinkorjauksella.
Osoitamme, etta tama johtaa suurella todennakoisyydella permutaatioreitityksen valmistumiseen ajassa O(n).
Toisin kuin hyperkuutiossa, meidan taytyy kiinnittaa huomiota myos jonotusprotokollaan. Kaytamme seuraavia saantoja:
1. Jos paketti on vaiheessa i ja on taman vaiheen aikana jo kulkenut t kaarta, sen prioriteetti on (i 1)n + t.
2. Jos useampi paketti haluaa kayttaa samaa kaarta, valitaan
prioriteettiluvultaan pienin. Tasatilanteissa ensin saapunut paketti valitaan ensin.
Koska kussakin vaiheessa pisin polku on n kaarta, niin erityisesti
myohemmat vaiheet eivat paase haittaamaan aikaisempia. Voimme siis olettaa, etta vaiheet suoritetaan erikseen, ja laskea suoritusajat yhteen.
Tarkastellaan ensin vaihetta II.
Olkoon Xw niiden pakettien lukumaara, joiden valitavoite sattuu riville w.
Nyt Xw B(n2n; 2 n) ja lause 4.5 antaa Pr(X 4n)
e3 44
n
3 2n:
Riveja w on 2n kappaletta. Todennakoisyys etta jollekin riville tulee yli 4n pakettia on korkeintaan 2n3 2n = O(N 1).
Koska vaiheessa II kaytetaan vain suoria kaaria, kaikki solmut voivat
lahettaa paketteja vahintaan yhta nopeasti, kuin niita saapuu. Siis minkaan solmun jonon pituus ei kasva.
Vaiheessa II kaikki paketit kulkevat samoja polkuja pitkin. Tasta seuraa, etta jos paketti k saapuu solmuun v prioriteetilla i, niin myohemmin
saapuvat paketit eivat voi ajaa sen ohi jonossa.
Siis paketin kokonaisjonotusaika on summa niista jononpituuksista, jotka solmuissa on paketin saapuessa. Koska jononpituudet eivat kasva, tama on korkeintaan sama kuin kokonaispituuksien summa vaiheen II alkaessa, eli Xw. Siis todennakoisyydella 1 O(N 1) mikaan paketti ei vieta jonossa
pitempaan kuin 4n, eli kokonaisaika on korkeintaan 5n.
Kun e = (v1; v2) on kaari, olkoon P (e) se kolmen kaaren joukko, johon kuuluvat e ja kaksi solmuun v1 tulevaa kaarta.
Vaiheen I analysoimiseksi sanotaan, etta jono kaaria e1; : : : ; en on mahdollinen viivejono jos kaikilla i patee ei 2 P (ei+1). Toisin sanoen kysymyksessa on suunnattu polku, johon voi myos kuulua pysahdyksia.
Jono on viivejono jos lisaksi aina ei on joukon P (ei+1) viimeinen kaari (tai eras viimeisista) joka lahettaa paketin prioriteetilla i (tai alle).
Tarkastellaan nyt jotain vaiheen I suoritusta ja siina viivejonoa (e1; : : : ; en).
Olkoon ti niiden pakettien lukumaara, jotka menevat kaaren ei lapi prioriteetilla i. Olkoon Ti ajanhetki jona ei lahettaa viimeisen paketin prioriteetilla korkeintaan i. Siis erityisesti Tn on se ajanhetki, jona vaihe I paattyy kaaren en osalta.
Maaritelmista seuraa erityisesti, etta hetkella Ti kaari ei+1 on jo lahettanyt kaikki prioriteetin i paketit ja
vastaanottanut kaikki paketit jotka se lahettaa prioriteetilla i + 1.
Siis
Ti+1 Ti + ti+1; ja koska T1 = t1, induktiolla saadaan
T
Xn
t :
Edellisen perusteella siis jos on annettu kaareen e paattyva viivejono, tasta saadaan ylaraja kaaren e tarvitsemalle ajalle.
Toisaalta oletetaan, etta kaari e lahetti viimeisen pakettinsa ajanhetkella T . Muodostetaan viivejono rekursiivisesti:
en = e ja
ei 1 on se joukon P (ei) kaari, joka viimeisena lahettaa prioriteetilla i 1 tai alle.
Siis saadaan laillinen viivejono, ja sille patee edella todetun mukaisesti Xn
i=1
ti T:
Kun on annettu mahdollinen viivejono e1; : : : ; en, olkoon ti niiden pakettien lukumaara jotka menevat kaaren ei yli prioriteetilla i, ja T = Pn
i=1 ti. Edella esitetyn perusteella jos T 40n kaikilla (e1; : : : ; en), niin vaiheen I suoritusaika on korkeintaan 40n. Osoitetaan, etta tama patee suurella todennakoisyydella.
Tarkastellaan ensin jotain kiinteaa (e1; : : : ; en). Kaaren ei = (v; v0) lapi
prioriteetilla i kulkevat paketit lahtevat liikkeelle solmuista, joiden etaisyys solmusta v on tasan i. Naita solmuja on 2i kappaletta. Kun paketti lahtee vaiheessa 1 tallaisesta solmusta satunnaiseen valitavoitteeseen, se kulkee kaaren ei kautta todennakoisyydella 2 i 1. Siis
E[ti] = 2i2 i 1 = 1
2 ja E[T ] = n 2:
Kun j = 1; : : : ; N, olkoon Hj = 1 jos solmusta j lahtenyt paketti lasketaan summaan T ainakin kerran; muuten Hj = 0.
Muuttujat Hj ovat riippumattomia, H =
XN j=1
Hj T ja E[H] E[T ] = n 2: Chernon raja (lause 4.7) antaa
Pr(H 5n) 2 5n:
Tarkastellaan nyt sita, kuinka paljon T voi olla suurempi kuin H, eli kuinka monta kertaa sama paketti voi tulla lasketuksi.
Olkoon u paketti, joka lasketaan termiin ti. Erotamme kaksi mahdollisuutta:
ei+1 = ei: Koska paketin j siirtyma prioriteetilla i + 1 tapahtuu seuraavassa sarakkeessa, j ei tule mukaan termiin ti+i. Samoin nahdaan, ettei se tule muihinkaan termeihin tj, j > i.
ei+1 6= ei: Todennakoisyys, etta u kulkee myos kaarta ei+1, on
korkeintaan 1=2. Jos u ei kulje kaarta ei+1, se ei myohemminkaan enaa kohtaa tata polkua.
Siis kun u on tullut lasketuksi kerran, tuleminen lasketuksi uudestaan
edellyttaa "onnistumista" kokeessa, jonka todennakoisyys on korkeintaan 1=2.
Jatko sujuu kuten hyperkuution tapauksessa.
Etta 5n polulle tulevaa pakettia tuottaisi yhteensa 40n kaarenkayntia, tarvitaan korkeintaan 5n epaonnistumista 40n toistossa, kun yksittainen epaonnistumistodennakoisyys on ainakin 1=2. Chernon rajasta saadaan arvio
Pr(T 40n j H 5n) exp( 20n(3=4)2=2) 2 5n: Johtopaatos on, etta
Pr(T 40n) Pr(T 40n j H 5n) + Pr(H 5n) 2 5n+1:
Tama patee kun mahdollinen viivejono on kiinnitetty. Mahdollisia viivejonoja kaikkiaan on korkeintaan 2N3n 1 n2n3n kappaletta. Siis todennakoisyys etta jollakin viivejonolla patee T 40n on korkeintaan
n2n3n2 5n+1 = O(N 1):
Siis todennakoisyydella 1 O(N 1) vaiheessa I kaikilla viivejonoilla T 40n, jolloin myos reitityksen suoritusaika on korkeintaan 40n.
Vaihe III on taysin symmetrinen taman kanssa, ja kuten totesimme kaytetty priorisointi takaa, etteivat myohemmat vaiheet sotke aiempia.
Koska myos vaiheen II todettiin menevan ajassa O(n) todennakoisyydella 1 O(N 1), sama koskee koko algoritmia.
5. Pallot ja lokerot
Tarkastelemme m pallon sijoittamista toisistaan riippumatta n lokeroon, kun kunkin lokeron todennakoisyys on sama. Olemme erityisesti kiinnostuneet rajasta kun n ! 1 s.e. suhde m=n pysyy vakiona.
Kysymyksia:
Kuinka monta palloa annettuun lokeroon tulee?
Mika on suurin maara palloja yhdessa lokerossa?
Sovelluksia: tietorakenteet (hashing), kuormien tasapainotus.
Laskujen yksinkertaistamiseen kaytamme Poisson-approksimaatiota.