Stærðfræðimynstur í tölvunarfræði
09.12.14


Lokapróf 19. desember 1991


Allar spurningarnar hafa sama vægi. Einungis þarf að svara 6 spurningum af 7. Bestu 6 svörin gilda.
Öll skrifleg hjálpargögn leyfileg.



1. Fyrir hverja eftirtalinna yrðinga í umsagnarökfræði sýnið eina túlkun (óðal, útskýring á umsögnum og gildi fasta) þar sem yrðingin er sönn og aðra þar sem hún er ósönn.

a) (Ex)P(x) -> (Ax)P(x)
b) (Ax)(Ey)P(x, y) -> (Ex)(Ay)P(x, y)
c) (Ex)[P(x) -> Q(x)] -> [(Ex)P(x) -> (Ex)Q(x)]
d) (Ax)[P(x) -> Q(x)] -> [P(a) -> (Ax)Q(x)]

Hvað segir það okkur um þessar yrðingar að við skulum geta fundið tvær slíkar andstæðar túlkanir?



2. Hanna á rökrás sem tekur inn tvíundarform eins tölustafs frá 0 til 9 og skilar út tvíundarformi tölunnar eftir að búið er að leggja 1 við hana (segjum að 9+1 = 0). Inntakið samanstendur af 4 bitum b1, b2, b3, b4 og úttakið er bitarnir c1, c2, c3, c4. Sem dæmi, þá verður inntakið 0101 að úttakinu 0110.


Búið til Boolesegðina fyrir c2, einfaldið hana með Karnaugh korti og sýnið rökrásina fyrir c2, sem kemur út úr því.



3. Við höfum n beinar óendanlegar línur sem liggja þannig í sléttunni (planinu) að engar tvær eru samsíða og engar þrjár skerast í sama punkti. Hvað skipta n línurnar sléttunni upp í mörg svæði? Hér að neðan sést að 4 línur skipta sléttunni upp í 11 svæði.



(Vísbending: Reynið að giska á almennu formúluna og sannið hana með þrepun.)



4. Á prófi í Efnafræðimynstur í tölvunarfræði eru 12 spurningar. Aðeins á að svara 9 af þeim. Hve margir möguleikar eru á að svara þessum 9 spurningum ...
a) ef alltaf þarf að svara spurningum 1 og 7?
b) ef ekki má svara bæði spurningum 2 og 3?
c) ef svara þarf a.m.k. 5 spurningum af fyrstu 6?
d) ef spurningarnar sem sleppt er mega ekki allar vera oddatöluspurningar?



5. Við skilgreinum innri lengd (internal path length) tvíundartrés sem summu lengdar allra vega frá rót til allra hnúta sem eru ekki lauf. Ytri lengd (external path length) er summa lengdar allra vega frá rót til allra laufa. Ef allir hnútar í tvíundartrénu hafa annað hvort tvö börn eða ekkert sýnið þá að ytri lengd = innri lengd + 2k, þar sem k er fjöldi innri hnúta (þ.e., ekki lauf) í trénu.



6. Lát M vera mengi þeirra bitastrengja sem, ef túlkaðir sem tvíundartölur, tákna tölur sem 3 gengur uppí. M = {0, 11, 110, 1001, 1100, 1111, ... }
a) Búið til endanlega stöðuvél sem ber kennsl á M. Gerið ráð fyrir að strengurinn sé lesinn inn vinstra megin frá. (Vísbending: Látið stöðuvélina vera í ákveðinni stöðu ef bitastrengurinn sem lesinn hefur verið inn hingað til mod 3 = i, fyrir i=0,1,2)
b) Sýnið reglulega málfræði sem skilgreinir málið M.
c) Sýnið reglulega segð fyrir M.



7. Ef um hálfgrúpuna [S, +] gildir að ef x+y = x+z þá er y=z, þá er hún sögð styttin frá vinstri.
a)Sýnið að algebran með mengið S* (mengi allra strengja með táknum úr S) og aðgerðina samtenging strengja er styttin frá vinstri.
b) Sýnið að víxlna hálfgrúpan [{0, 1, 2, 3}, max] er ekki styttin frá vinstri.
c) Sýnið dæmi um hálfgrúpu sem er ekki víxlin og er ekki styttin frá vinstri.
d) Sýnið að ef hálfgrúpa er styttin frá vinstri og hægri (þ.e., ef y+x = z+x þá er y=z) þá er hún grúpa.