Mat - 1.135 Tietotekniikan matematiikka

Tentti 18.1.1995

Kirjoita, ensin alla mainitussa järjestyksessä koepapereihin selvästi

- Tietotekn. mat., tentti 18.1.1995

- Opiskelijatunnus (numero + kirjain),

TEKSTATEN sukunimi (alleviivattuna), kaikki etunimet

- Koulutusohjelma (Ke, Ko, M, Mk, P, R, S, Tf, Ti, Tu)

- Mahdolliset entiset nimet ja koulutusohjelmat

- Nimikirjoitus

1. Miten monta r - pituista 'sanaa' voidaan muodostaa sanan PUKUPUU kirjaimista, eri arvoilla r = 0, 1, ... 5 7?

2. Etsi seuraaville joukoille erilliset edustajat, tai osoita tehtävä mahdottomaksi, soveltaen ns. Hall'in algoritmia:

A={2,4,5,6,8}, B={1,2,3,7}, C={4,5,8},

D={l,2,3,7,9}, E={1,3,7,9}, F={2,3,7},

G={1,3,5,6,8}, H={1,2,7,9}, I={1,3,9}.

3. Olkoon p (erisuuri kuin) 2 alkuluku. Laske

a) (p - 3)! (mod p) , b) p(potenssiin 2) (mod 4).

4. Mitä tarkoitetaan pseudoalkuluvuilla ja vahvoilla pseudoalkuluvuilla? Selvitä lyhyesti, miksi nämä, ja kummat näistä erityisesti, ovat tärkeitä RSA - salakirjoituksen kannalta.

5. Hammingin (7, 4) - koodilla on generoiva matriisi

    1 0 0 0 1 1 1

G = 0 1	0 0 0 1 1

    0 0 1 0 1 1 0

    0 0 0 1 1 0 1

b) Analysoi ja tulkitse vastaanotetut sanat 1001010 ja 1010010 parillisuustarkistusmatriisin avulla.

c) Millä todennäköisyydellä yhden vastaanotetun sanan tulkinta johtaa oikeaan tulokseen, jos käytössä on symmetrinen binäärikanava, jolla virhetodennäköisyys yhden bitin välityksessä on p = 0.0002 ?