Tämä on moniosainen pähkinä, jolla saavutetaan kaunis todistus. Lukijalla tulisi olla lukiotason kokemusta matematiikasta, esim. termit 'vektori' ja 'skalaaritulo' (pistetulo) pitäisi tuntea. Ratkaisut itse pähkinöihin ovat lyhyitä, enintään parin rivin mittaisia. Selvennyksiä saa pyytää!
Tietokone lähettää nettiin kirjaimen. Serveri vastaanottaa kirjaimen, mutta häiriöiden takia se saatetaan lukea jonakin toisena kirjaimena.
Voimme kuvata tilannetta häiriögraafilla G:
1) Jokaista kirjainta edustaa erillinen piste.
2) Kaksi pistettä on yhdistetty kaarella, jos ne saattavat mennä sekaisin.
alpha(G) olkoon luku, joka kertoo suurimman ristiriidattoman osa-aakkoston koon. Etsimme siis suurinta G:n pisteiden osajoukkoa, josta puuttuu kaaret.
Entä jos lähetämme pidemmän viestin samalle tietokoneelle ja pohdimme mihin muihin viesteihin se saattaa sekaantua? Pohdimme asiaa ensin kahden kirjaimen pituisille viesteille. Saamme häiriögraafin G^2, jossa ab yhdistyy cd:hen täsmälleen silloin kun:
(a on eri kuin c) => (ac on kaari G:ssä) JA
(b on eri kuin d) => (bd on kaari G:ssä)
PÄHKINÄ 1: Osoita, että alpha(G^2) >= alpha(G)^2.
Mikä oli kirjainparien lähettämisen etu? Huomaa, että (alpha(G^2))^(1/2) kertoo ristiriidattoman aakkoston suhteutetun maksimikoon kirjainpareja lähettäessä. Pähkinä 1 osoittaa, että tilanne ei ainakaan mennyt huonompaan suuntaan.
Entä jos lähetetään n kirjainta kerralla? Tällöin raja-arvo c(G) = lim(alpha(G^n))^(1/n) on olemassa ja se on teoreettinen (suhteutettu) maksimi ristiriidattomalle aakkostokoolle. Pähkinästä 1 seuraa, että c(G^2) = c(G)^2.
Arvo c(G) tunnetaan vain hyvin harvalle graafille G. Paras tarkasti tunnettu epätriviaali arvo on c(C_5), missä C_5 on viiden pisteen sykli 'abcdea', missä peräkkäiset kirjaimet on yhdistetty kaarella. Eli esim. e ja a saattavat mennä sekaisin. Tavoitteenamme on määrittää arvo c(C_5).
PÄHKINÄ 2: Osoita, että c(C_5) >= njuuri(5). (Lämmittelytehtävä: Määritä alpha(C_5).)
Valitaan sopiva luonnollinen luku k ja muodostetaan 1-1 vastaavuus G:n pisteiden ja joidenkin k-ulottuvuuksisten reaalivektorien välille, niin että jokaista yhdistämätöntä pisteparia vastaava vektoripari on kohtisuorassa. Jos {u_i} on sellainen joukko vektoreita, kutsumme sitä G:n edustukseksi. (Jos G:ssä on n pistettä, otamme 1
Tietokone lähettää nettiin kirjaimen. Serveri vastaanottaa kirjaimen, mutta häiriöiden takia se saatetaan lukea jonakin toisena kirjaimena.
Voimme kuvata tilannetta häiriögraafilla G:
1) Jokaista kirjainta edustaa erillinen piste.
2) Kaksi pistettä on yhdistetty kaarella, jos ne saattavat mennä sekaisin.
alpha(G) olkoon luku, joka kertoo suurimman ristiriidattoman osa-aakkoston koon. Etsimme siis suurinta G:n pisteiden osajoukkoa, josta puuttuu kaaret.
Entä jos lähetämme pidemmän viestin samalle tietokoneelle ja pohdimme mihin muihin viesteihin se saattaa sekaantua? Pohdimme asiaa ensin kahden kirjaimen pituisille viesteille. Saamme häiriögraafin G^2, jossa ab yhdistyy cd:hen täsmälleen silloin kun:
(a on eri kuin c) => (ac on kaari G:ssä) JA
(b on eri kuin d) => (bd on kaari G:ssä)
PÄHKINÄ 1: Osoita, että alpha(G^2) >= alpha(G)^2.
Mikä oli kirjainparien lähettämisen etu? Huomaa, että (alpha(G^2))^(1/2) kertoo ristiriidattoman aakkoston suhteutetun maksimikoon kirjainpareja lähettäessä. Pähkinä 1 osoittaa, että tilanne ei ainakaan mennyt huonompaan suuntaan.
Entä jos lähetetään n kirjainta kerralla? Tällöin raja-arvo c(G) = lim(alpha(G^n))^(1/n) on olemassa ja se on teoreettinen (suhteutettu) maksimi ristiriidattomalle aakkostokoolle. Pähkinästä 1 seuraa, että c(G^2) = c(G)^2.
Arvo c(G) tunnetaan vain hyvin harvalle graafille G. Paras tarkasti tunnettu epätriviaali arvo on c(C_5), missä C_5 on viiden pisteen sykli 'abcdea', missä peräkkäiset kirjaimet on yhdistetty kaarella. Eli esim. e ja a saattavat mennä sekaisin. Tavoitteenamme on määrittää arvo c(C_5).
PÄHKINÄ 2: Osoita, että c(C_5) >= njuuri(5). (Lämmittelytehtävä: Määritä alpha(C_5).)
Valitaan sopiva luonnollinen luku k ja muodostetaan 1-1 vastaavuus G:n pisteiden ja joidenkin k-ulottuvuuksisten reaalivektorien välille, niin että jokaista yhdistämätöntä pisteparia vastaava vektoripari on kohtisuorassa. Jos {u_i} on sellainen joukko vektoreita, kutsumme sitä G:n edustukseksi. (Jos G:ssä on n pistettä, otamme 1
Vastaukset 7
Vanhimmat
Käytännössä sanomien merkkejä ei tuolla tavalla "sekoiteta", koska ne lähetetään binäärisinä ja siellä ongelmana on pääasiassa bittien kääntyminen. Yhden taikka useamman.
Tietokoneissa lähetetyn bittivirran perään laitetaan tarkistussumma (CRC = Cyclic Redundance Check) ja jos se ei täsmää lasketun kanssa, niin jossain on vikaa. Tällöin yleensä joko konsultoidaan virheenkorjausalgoritmia (jos sellainen on) taikka pyydetään lähettämään uudestaan.
http://fi.wikipedia.org/wiki/CRC
Toinen menetelmä on yksinkertainen tarkastussumma, jossa kaikki lähetteen tavut lasketaan yhteen ja ylivuodosta ei välitetä. Tarkistussumma lisätään lähetteen loppuun (yksi ylimääräinen tavu) ja se lasketaan aina tarvittaessa uudelleen sekä alkuperäistä verrataan laskettuun.
Esimerkkinä vastaavasta tarkistusummasta on esim. henkilötunnuksen viimeinen merkki, jonka avulla voi tarkistaa, onko koko tunnus muodollisesti oikein annettu.
Merkit talletetaan tietokoneissa binäärisinä, joten niiden sekoittuminen esittämälläsi tavalla ei ole mahdollista. Tai jos sekoittumista haluttaisiin esittää tuolla tavalla, niin kaikista pisteistä tulisi kaaret kaikkiin pisteisiin (1 tavu, eli 8 bittiä voi saada arvon välillä 0..255 ja jokaista vastaa jokin merkki ibm:n laajennetussa ascii-taulukossa). Käytännössä sekoittuminen on siis mahdollista kaikilla mahdollisilla tavoilla (luku voi muuttua miksi tahansa toiseksi luvuksi alueella 0..255).
http://www.mindworkshop.com/alchemy/crc.html
... kyseessä oli puhtaasti teoreettinen malli, yksi alkeellisimmista Shannonin kommunikaatioteoriassa. En kai minä nyt ole mikään idiootti, joka oikeasti luulee, että tämä olisi tarkka kuvaus nettiteknologiasta? Minulle ongelma on lähinnä esimerkki graafiteorian kauneudesta.
Nielenkiintoinen vastaus, mutta en näe 'kritiikki'-sanan käytölle mitään ideaa.
... tilanteesta, joissa malli on realistinen:
1) Halutaan välttää samannäköisten kirjainten käyttöä salasanan antamisessa käyttäjälle. Aakkosilla a,b,...,ö,A,B,...,Ö ei koskaan käytetä molempia l ja I kirjaimista.
2) Näkövikaisille on olemassa audioversio salasanasta, joten d/D ja t/T eivät esiinny yhtä aikaa, kuin myöskään b/B ja p/P tai å/Å ja o/O. Käyttäjälle kerrotaan nämä valinnat etukäteen.
:D:D,mitä jengiä,keep going on dudes!
kokonaisuudessaan
Sattumoisin näissä yksinkertaisissa klassisissa ideoissa oli siemenet, joilla Shannon mullisti kommunikaatioteorian. Maailma olisi varsin erinäköinen paikka, jos sitä ei olisi tapahtunut.
... sanottuna Shannon loi kommunikaatioteorian, lähestulkoon omakätisesti.