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

MAT282 Johdatus diskreettiin matematiikkaan
2. välikoe ke 24.11.1999 klo 8-11

  1. Tiedekunnassa on dekaani ja yhdeksän muuta professoria: biologit M, A ja T, fyysikot R ja P, kemistit V ja J sekä matemaatikot K ja O. Dekaanin pitää muodostaa professoreista kehittämiskeskusteluja varten ryhmiä. Kussakin ryhmässä voi olla useita professoreita, kuitenkin seuraavin rajoituksin: kahta saman oppiaineen professoria ei voi sijoittaa samaan ryhmään; professorit V ja T tulee sijoittaa eri ryhmiin, samoin kuin professorit R ja M; professori A on ainoa biologi jonka voi sijoittaa samaan ryhmään kummankaan matemaatikon kanssa. Kukin kehittämiskeskustelu kestää tunnin. Muodosta dekaanin avuksi jokin professoreiden ryhmittely, jota käyttäen hän selviää keskusteluista mahdollisimman nopeasti. Montako tuntia vähintään tarvitaan?
  2. Dominopelin nappula on kahteen neliöön jaettu suorakaide, jonka molemmissa puoliskoissa on nollasta kuuteen ``silmää''. Jos pelistä jätetään pois nappulat, joiden puoliskojen silmämäärä on sama, ja sovitaan että nappulan suunnistuksella ei ole väliä, huomataan että dominonappulat vastaavat täsmälleen kahden alkion joukkoja tex2html_wrap_inline57 , missä tex2html_wrap_inline59 , tex2html_wrap_inline61 . Osoita, että näin saatavat tex2html_wrap_inline63 dominonappulaa voidaan asettaa dominopelin sääntöjen mukaiseksi renkaaksi, jossa kahden toisiaan koskettavan nappulan vastinpuoliskoissa on aina sama silmäluku. Esimerkiksi oheisessa kuvassa on toistensa naapureiksi laillisesti asetetut dominonappulat tex2html_wrap_inline65 ja tex2html_wrap_inline67 . tex2html_wrap89

    (Vihje: Tarkastele verkkoa tex2html_wrap_inline69 .)

  3. Kaikkien 15 EU-maan pääministerit saapuvat Jyväskylään huippukokoukseen tapaamaan 15:ta Jyvässeudun merkittävää kunnallista vaikuttajaa. Kukin pääministeri saa nimetä kolme vaikuttajaa, joiden kanssa hän haluaisi neuvotella. Osoita, että mikäli kenellekään jyvässeutulaiselle ei tule enempää kuin kolme neuvottelupyyntöä (tällöin itse asiassa jokaiselle tulee tasan kolme), kaikki toivotut tapaamiset voidaan järjestää kolmessa peräkkäisessä vaiheessa, joissa kussakin käydään 15 pareittaista neuvottelua EU:n ja Jyvässeudun edustajien kesken.
  4. Tarkastellaan viisinkertaista toistokoodia tex2html_wrap_inline71 , jossa yksibittinen viesti tex2html_wrap_inline73 koodataan viisibittiseksi jonoksi c(b) = bbbbb.
    1. Muodosta koodin koodisanat ja tarkistusmatriisi. Montako virhettä koodi korjaa lähimmän naapurin periaatteella?
    2. Määritä koodin teho (engl. rate), ja osoita että koodi on itse asiassa täydellinen (engl. perfect), so. omassa luokassaan maksimaalisen tehokas.
    3. Määritä todennäköisyys, että koodia tex2html_wrap_inline77 käyttäen koodattu viestisana b = 0 välittyy virheettömästi kanavassa BSC(0.05), kun vastaanottaja käyttää lähimmän naapurin dekoodausmenetelmää. (Lisätieto niille, joiden todennäköisyyslaskennan taidot ovat ruosteessa: ns. binomijakauman mukainen todennäköisyys sille, että n-bittisessä viestissä sattuu tasan e virhettä on tex2html_wrap_inline85 , kun yksittäisen virheen todennäköisyys on p. Jos sinulla ei ole laskinta, myös symbolimuotoinen virhetodennäköisyyden kaava kelpaa vastaukseksi.)

Pisteytys: kukin tehtävä á 9 pistettä, yhteensä 36 pistettä.


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

Pekka Orponen
Wed Nov 24 18:15:30 EET 1999