MAT282 Johdatus diskreettiin matematiikkaan (3 ov)
Loppukoe ke 16.8.2000 klo 12-16

1. Piirrä kaikkien neljän alkion ei-isomorfisten osittainjärjestysten Hasse-kaaviot. (Alkiojoukon järjestykset ja ovat isomorfiset, jos on olemassa alkioiden permutaatio , jolla on kaikilla voimassa joss . Siten esimerkiksi kaavioiden #1#2#3#4#5@font#1#2pt#3#4#5

   kuvaamat järjestykset ovat keskenään isomorfiset permutaation kautta, ja niillä on ``yhteinen'' Hasse-kaavio

2. 1. Yatzy-noppapelissä pelaajat yrittävät viittä noppaa heittämällä saada aikaan tiettyjä säännönmukaisia silmälukuyhdistelmiä. Arvokkain yhdistelmä on ``yatzy'', jossa kaikilla viidellä nopalla on sama silmäluku. (Siis joko kaikissa viidessä nopassa 1, tai kaikissa 2, tai ..., tai kaikissa 6.) Mikä on todennäköisyys saada yatzy-yhdistelmä yhdellä noppien heittokerralla? (Todennäköisyyden lukuarvoa ei tarvitse laskea, kaava riittää.)
   2. Muita Yatzy-pelin yhdistelmiä ovat ``neliluku'', jossa neljässä nopassa viidestä on keskenään sama silmäluku, ja ``pieni suora'', jossa noppien silmäluvut ovat 1-2-3-4-5. Mitkä ovat näiden yhdistelmien todennäköisyydet yhdellä heittokerralla? (Kaavat riittävät.)
   3. Yatzy-pelissä kukin pelaaja saa vuorollaan yrittää parantaa tulostaan kahdella lisäheitolla, jättäen haluamansa osan nopista laudalle heittojen välillä. Oletetaan, että pelaaja on kahdella ensimmäisellä heitollaan saanut aikaan yhdistelmän 1-2-2-2-5. Kannattaako hänen kolmannella ja viimeisellä heitollaan ennemmin heittää uudelleen 1- ja 5-nopat saadakseen 2-yatzyn (arvo 50 pistettä) vai kaksi 2-noppaa saadakseen pienen suoran (arvo 30 pistettä)?

3. Ns. Lucasin luvut määritellään rekursioyhtälöllä:

   Ratkaise em. rekursioyhtälöstä luvuille esitys suljetussa muodossa.

4. 1. Yhtenäisen verkon G solmujen (``kärkien'') u ja v etäisyys d(u,v) on lyhimmän niitä yhdistävän polun pituus. Verkon G halkaisija d(G) on sen solmujen maksimaalinen etäisyys. Määritä verkkojen (n solmun täydellinen verkko), (n solmun sykli) ja (n solmun polku) halkaisijat.
   2. Osoita, että verkot ja ovat yhtenäisten n-solmuisten verkkojen joukossa yksikäsitteisesti halkaisijaltaan minimaalinen ja maksimaalinen verkko.
   3. Suunnittele verkkoperhe , jolla ei ole vakio, mutta kasvaa hitaammin kuin lineaarisesti solmujen määrän suhteen. (Siis , .)
5. Tarkastellaan kuusibittistä lineaarista koodia, jonka tarkistusmatriisi on
   1. Määritä koodin kaikki koodisanat.
   2. Esitä, miten tarkistusmatriisia H käyttäen määritetään yhden bittivirheen sisältävää jonoa 101101 vastaava kooodisana.

Pisteytys: Kukin tehtävä 12 pistettä, yhteensä 60 pistettä.