Pähkinänurkka 3/2013

Tehtävät

Uolevi on koodannut ohjelman, jolla voi lähettää viestejä netin välityksellä. Jokainen lähetettävä viesti on bittijono eli muodostuu merkeistä 0 ja 1. Ikävä kyllä Uolevin ohjelmassa on bugi ja osa biteistä saattaa kadota matkan varrella. Kuitenkin kaikki perille tulleet bitit ovat samassa järjestyksessä kuin alkuperäisessä viestissä ja ainakin yksi bitti tulee perille.

Esimerkiksi jos Uolevi lähettää viestin 1101, vastaanottaja voi saada 9 erilaista viestiä: 0, 1, 01, 10, 11, 101, 110, 111 tai 1101. Uolevi haluaa tutkia ohjelmansa luotettavuutta laskemalla, montako erilaista viestiä voi syntyä eri tilanteissa. Voitko auttaa Uolevia?

1. Jos Uolevi lähettää viestin 0110001111, montako erilaista viestiä vastaanottaja voi saada?
2. Entä jos Uolevi lähettää viestin 011000111100000111111000000011111111000000000?
3. Vastaanottaja voi saada tarkalleen 123 erilaista viestiä. Kuinka pitkä on lyhin mahdollinen Uolevin lähettämä viesti?
4. Entä jos vastaanottaja voi saada tarkalleen 999999 erilaista viestiä?
5. Uolevi lähettää viestin, jossa on n bittiä. Mikä on odotusarvo sille, kuinka monta erilaista viestiä vastaanottaja voi saada, jos kaikki viestit ovat yhtä todennäköisiä?

Ratkaisut

Tehokas tapa ratkaista tehtävät 1 ja 2 on laskea jokaisesta bittijonon alkuosasta, montako erilaista viestiä siitä pystyy muodostamaan. Seuraava C++-funktio laskee vastauksen bittijonolle s:

int laske(string s) {
    int a = 0, b = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '0') a = a+b+1;
        else b = a+b+1;
    }
    return a+b;
}

Ideana on, että muuttuja a sisältää nollaan päättyvien viestien määrän ja muuttuja b ykköseen päättyvien viestien määrän. Esimerkiksi tehtävässä 1 muuttujien arvot muuttuvat näin:

Siis nollaan päättyviä viestejä on 16 ja ykköseen päättyviä viestejä on 72, joten viestejä on yhteensä 88.

Tehtävässä 2 viestien määrä on 1395545.

Tehtävissä 3 ja 4 voi soveltaa käänteisesti aiempaa päättelyä. Jos muuttujien a ja b lopulliset arvot ovat tiedossa, niitä vastaa yksikäsitteinen bittijono. Seuraava C++-funktio etsii lyhimmän tällaisen jonon pituuden viestien määrälle m:

int etsi(int m) {
    int t[m/2+1][2];
    for (int i = 0; i <= m/2; i++) {
        t[i][0] = i;
        t[i][1] = m-i;
    }
    int c = 0;
    while (true) {
        c++;
        for (int i = 0; i <= m/2; i++) {
            if (t[i][0] == t[i][1]) continue;
            if (t[i][0] < t[i][1]) t[i][1] -= t[i][0]+1;
            else t[i][0] -= t[i][1]+1;
            if (t[i][0] == 0 && t[i][1] == 0) return c;
        }
    }
}

Funktio käy läpi kaikki tavat, miten viestien määrän voi jakaa muuttujien a ja b summaksi. Se käy läpi kaikkia tapoja rinnakkain bitti bitiltä taulukon t avulla. Kussakin taulukon kohdassa indeksi 0 vastaa muuttujaa a ja indeksi 1 vastaa muuttujaa b.

Tehtävän 3 vastaus on 10 ja tehtävän 4 vastaus on 29.

Tehtävän 5 voi ratkaista niin ikään tehtävien 1 ja 2 päättelyllä. Ideana on laskea muuttujien a ja b odotusarvoa. Lopullinen odotusarvo on näiden odotusarvojen summa.

Joka vaiheessa todennäköisyydellä 1/2 muuttujan arvo säilyy samana ja todennäköisyydellä 1/2 arvoksi tulee a+b+1. Muuttujat a ja b ovat symmetriset, joten niiden odotusarvojen täytyy olla samat. Jos a:n ja b:n odotusarvoa silmukan kierroksella n merkitään k_n, saadaan seuraava yhtälö:

• k₁ = 1
• k_n = 1/2 · k_n-1 + 1/2 · (2 k_n-1 + 1), kun n > 1

Tätä vastaa seuraava geometrinen summa:

k_n = 1/2 + 3/2 · 1/2 + (3/2)² · 1/2 + ... + (3/2)^n-1 · 1/2 = (3/2)ⁿ - 1

Näin ollen kun bittijonon pituus on n, odotusarvo on 2 · (3/2)ⁿ - 2.

Tarkastellaan esimerkiksi tapausta n = 3. Bittijonot ja viestien määrät ovat:

Odotusarvo on (3+5+6+5+5+6+5+3)/8 = 19/4 eli 2 · (3/2)³ - 2.