Strfrimynstur tlvunarfri
09.12.14


Lokaprf 14. desember 1993


Allar spurningarnar hafa sama vgi. Einungis arf a svara 6 spurningum af 7. Bestu 6 svrin gilda.
ll skrifleg hjlparggn leyfileg.



1. Hfum riggja manna nefnd sem arf a kjsa um tillgu. Hanna rkrs sem skilar 1 aa melimir nefndarinnar kjsa ekki allir eins.
a) Setji upp Boole-seg eunar-staalformi (DNF) sem lsir essu sannfalli og einfaldi hana me Karnaugh-korti.
b) Setji upp Boole-seg ogunar-staalformi (CNF), sem lsir sannfallinu og einfaldi.
c) Teikni rkrsina fyrir einfaldari segina 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 tlurnar eru skilgreindar eftirfarandi htt:
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 mrg mismunandi full hs eru pker? Fullt hs pker er 5 spil, ar sem rj hafa eitt gildi og hin tv anna gildi, t.d. hjarta ta, laufa ta, tgul ta, laufa fimma og spaa fimma.

b) Hsmir hefur baka 4 gerir af jlasmkkum. Vi megum f okkur 10 smkkur. Hva getum vi vali r marga vegu?



5. Vi hfum eftirfarandi vensl nttrulegu tlurnar:
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 smu frumtlur sem frumtti }
a)Hvaa vensl eru sjlfhverf?
b)Hvaa vensl eru samhverf?
c)Hvaa vensl eru andsamhverf?
d)Hvaa vensl eru gegnvirk?

Rkstyji svrin hverju tilfelli.i



6.
a) Er til einfalt graf 5 hntum ar sem allir hntarnir hafa gruna 3? Ef svo er, teikni grafi, annars sanni a slkt graf s ekki til.

b) rjr ftur rma 10, 7 og 3 ltra hver. upphafi er 10 ltra fatan full og hinar tmar. Skipta vatninu tvennt annig a tvr strri fturnar hafi hvor um sig nkvmlega 5 ltra. Aeins m hella r einni ftu ara ar til fyrri fatan er tm ea s seinni full. Sni hvernig er hgt a lsa essu vandamli me stefnugrafi ar sem leyfilegar stur eru hntarnir og rvarnar tkna leyfilegar agerir. Teikni upp stefnugrafi og finni lausnina vandamlinu t fr v.



7. Gefi er mli L sem inniheldur alla strengi sem byrja einhverjum fjlda 0-bita, hafa san tvo 1-bita og geta enda einhverjum bitastreng. nnur lsing L vri {0}*{11}{0, 1}*.
a) Sni reglulega mlfri fyrir L.
b) Sni briggenga stuvl sem ber kennsla L.
c) Sni lggenga stuvl sem samykkir L.