next up previous
Next: About this document Up: No Title Previous: No Title

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

    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ä)?

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

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

    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 , .)
  3. 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ä.


next up previous
Next: About this document Up: No Title Previous: No Title

Pekka Orponen
Wed Aug 16 16:42:45 EET DST 2000