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

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

    1. Kuinka monta lehteä voi (i) enintään, (ii) vähintään olla n-solmuisessa puussa? (Pelkkä vastaus riittää, ei tarvitse todistaa.)
    2. Piirrä kaikki keskenään ei-isomorfiset nelilehtiset, enintään 7-solmuiset puut.
  1. Olkoon G = (V,E) (suuntaamaton) verkko, jonka jokaisen solmun asteluku on parillinen. Osoita, että G:n kaaret voidaan suunnata niin, että syntyvässä suhteikossa ovat kunkin solmun tulo- ja lähtöaste (= tulevien ja lähtevien kaarien määrä) keskenään yhtä suuret.
    1. Olkoon G = (V,E) vähintään 3-solmuinen yhtenäinen tasoverkko, jonka kaikki syklit ovat vähintään neljän pituisia (so. verkko ei sisällä tex2html_wrap_inline50 -muotoista indusoitua aliverkkoa eli on kolmioton). Osoita, että G:n kaarien määrää rajoittaa tällöin epäyhtälö tex2html_wrap_inline54 . (Kuten luennolla esitettiin, ilman kolmiottomuusoletusta saadaan heikompi epäyhtälö tex2html_wrap_inline56 .)
    2. Osoita edellisen tuloksen nojalla, että verkko tex2html_wrap_inline58 ei ole planaarinen.
  2. Tarkastellaan 15-bittistä Hamming-koodia tex2html_wrap_inline60 (11 viestibittiä, 4 pariteettibittiä, 1 virheen korjaus).
    1. Esitä koodin tarkistusmatriisi, jonka sarakkeet on lueteltu luonnollisessa järjestyksessä.
    2. Montako koodisanaa koodissa on?
    3. Määritä koodin teho (engl. rate).
    4. Osoita, että missään 15-bittisessä, 1 virheen korjaavassa koodissa ei voi olla enempää koodisanoja kuin koodissa tex2html_wrap_inline60 , ja se on siten tässä koodiluokassa maksimaalisen tehokas.
    5. Anna jokin kelvollinen koodisana tex2html_wrap_inline64 ja vahvista, että todella on tex2html_wrap_inline66 .
    6. Määritä yhden bittivirheen sisältävää jonoa 011101110011011 vastaava kelvollinen koodisana.

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



Pekka Orponen
Thu Nov 18 00:30:01 EET 1999