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


Lokapróf 14. desember 1993


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. Höfum þriggja manna nefnd sem þarf að kjósa um tillögu. Hanna á rökrás sem skilar 1 þþaa meðlimir nefndarinnar kjósa ekki allir eins.
a) Setjið upp Boole-segð á eðunar-staðalformi (DNF) sem lýsir þessu sannfalli og einfaldið hana með Karnaugh-korti.
b) Setjið upp Boole-segð á ogunar-staðalformi (CNF), sem lýsir sannfallinu og einfaldið.
c) Teiknið rökrásina fyrir einfaldari segðina úr a) og b)-lið.



2. Sannið að fallið f(x) = (x+2)log(x^2+1) + log(x^2+1) er O(xlog(x)).



3. Fibonacci tölurnar eru skilgreindar á eftirfarandi hátt:
F_1 = 1
F_2 = 1
F_n = F_n-2 + F_n-1 þegar n > 2

Sannið að F_n >= (3/2)^(n-2) fyrir n„>= 2.



4.
a) Hve mörg mismunandi full hús eru í póker? Fullt hús í póker er 5 spil, þar sem þrjú hafa eitt gildi og hin tvö annað gildi, t.d. hjarta tía, laufa tía, tígul tía, laufa fimma og spaða fimma.

b) Húsmóðir hefur bakað 4 gerðir af jólasmákökum. Við megum fá okkur 10 smákökur. Hvað getum við valið þær á marga vegu?



5. Við höfum eftirfarandi vensl á náttúrulegu tölurnar:
R1 = {(x, y) | x+y > 10}
R2 = {(x, y) | y gengur upp í x}
R3 = {(x, y) | GCD(x, y) = 1}
R4 = { (x, y) | x og y hafa sömu frumtölur sem frumþætti }
a)Hvaða vensl eru sjálfhverf?
b)Hvaða vensl eru samhverf?
c)Hvaða vensl eru andsamhverf?
d)Hvaða vensl eru gegnvirk?

Rökstyðjið svörin í hverju tilfelli.i



6.
a) Er til einfalt graf á 5 hnútum þar sem allir hnútarnir hafa gráðuna 3? Ef svo er, teiknið grafið, annars sannið að slíkt graf sé ekki til.

b) Þrjár fötur rúma 10, 7 og 3 lítra hver. Í upphafi er 10 lítra fatan full og hinar tómar. Skipta á vatninu í tvennt þannig að tvær stærri föturnar hafi hvor um sig nákvæmlega 5 lítra. Aðeins má hella úr einni fötu í aðra þar til fyrri fatan er tóm eða sú seinni full. Sýnið hvernig er hægt að lýsa þessu vandamáli með stefnugrafi þar sem leyfilegar stöður eru hnútarnir og örvarnar tákna leyfilegar aðgerðir. Teiknið upp stefnugrafið og finnið lausnina á vandamálinu út frá því.



7. Gefið er málið L sem inniheldur alla strengi sem byrja á einhverjum fjölda 0-bita, hafa síðan tvo 1-bita og geta endað á einhverjum bitastreng. Önnur lýsing á L væri {0}*{11}{0, 1}*.
a) Sýnið reglulega málfræði fyrir L.
b) Sýnið brigðgenga stöðuvél sem ber kennsla á L.
c) Sýnið löggenga stöðuvél sem samþykkir L.