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


Haustpróf 19. ágúst 1992


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.
a) Sıniğ og einfaldiğ neitun eftirfarandi setninga:
"Til er rakari sem rakar alla şá sem ekki raka sig sjálfir"
"Ef enginn er reykurinn şá er enginn eldur"
"Fyrir allar náttúrulegar tölur k er til N, şannig ağ fyrir öll n>N er n^k > logn"

b) Hver eru veikustu skilyrğin sem mengin A, B og C verğa ağ uppfylla til ağ jafnan

A \ (B \ C) = (A \ B) \ C

gildi? Athugiğ ağ hér er \ ağgerğin mengjamunur.



2. Til er stağalform fyrir Boolesegğir sem heitir ogunar stağalform (conjunctive normal form). Til dæmis er segğin (x'+y)(x+y') á şessu stağalformi. Í şví er einn liğur fyrir hvert 0 í sanntöflunni og öfugt viğ eğunar stağalform er notağ x' ef breytan x er 1 í şeirri línu sanntöflunnar. Şessu stağalformi er meğal annars lıst í dæmi 8 í kafla 6.1 í kennslubókinni. Sıniğ hvernig hægt er ağ nota Karnaugh kort til ağ einfalda segğir á ogunar stağalformi. Finniğ ogunar stağalform fyrir eftirfarandi sanntöflur, einfaldiğ şağ meğ Karnaugh korti og reyniğ síğan ağ einfalda meğ grunnreglum.

   a)   x   y   f(x, y)         b)   x   y   z   f(x, y, z)
       -----------------            ------------------------
        1   1      0                 1   1   1        0  
        1   0      0                 1   1   0        1
        0   1      1                 1   0   1        1
        0   0      0                 1   0   0        0          
                                     0   1   1        0          
                                     0   1   0        1
                                     0   0   1        1          
                                     0   0   0        0



3. Meğ şví ağ nota ağeins frumsetningarnar

1. (P -> (Q -> P)
2. (P -> (Q -> R)) -> ((P -> Q) -> (P -> R))
3. (Q' -> P') -> (P -> Q)

auk reglnanna (P v Q) <-> (P'-> Q) og (P ^ Q) <-> (P -> Q')' sanniğ eftirfarandi setningar meğ şví ağ sına hvert skref fyrir sig:

a) P -> (Q -> (P ^ Q))
b) (Q -> (P -> R)) -> (P -> (Q -> R))
c) (P ^ Q) -> (P v Q)



4. Şríliğustuğullinn C(n, k, j) er fjöldi möguleika á ağ velja k og j stök úr n staka mengi, şannig ağ ef viğ skiptum menginu upp í şrennt şá hefur einn hópur k stök, annar hefur j stök og sá şriğji n-k-j stök.
a) Sıniğ ağ eftirfarandi regla gildi



b) Regla Pascals [C(n, k) = C(n-1, k) + C(n-1, k-1) ] var notuğ til ağ búa til Şríhyrning Pascals. Sıniğ samsvarandi reglu fyrir şríliğustuğla og notiğ hana til ağ útvíkka Şríhyrning Pascals.



5. Ef R eru tvístæğ vensl á mengiğ S, şá skilgreinum viğ gagnstæğu venslin R' şannig ağ

(x, y) stak í R' şşaa (y, x) stak í R.

a) Ef venslin R eru samhverf gildir şá hiğ sama um R'? Hvağ meğ andsamhverfni?

b) Gegnvirk lokun vensla R eru minnstu venslR* şannig ağ (R* hlutmengi í R) og R* eru gegnvirk. Sanniğ eğa afsanniğ eftirfarandi:

(R')* = (R*)'




6. Gefin er reglulega málfræğin fyrir máliğ L:

S -> 0 | 0A | 0B
A -> 1C | 1A
B -> 0D | 1A
C -> 1 | 0
D -> 1A

a) Búiğ til brigğgenga stöğuvél sem ber kennsl á máliğ L.
b) Sıniğ reglulega segğ sem lısir L.
c) Búiğ til löggenga stöğuvél sem ber kennsl á L, annağ hvort út frá a)-liğ eğa frá grunni.



7. Leysiğ eftirfarandi mismunajöfnur meğ şví ağ skoğa fyrstu liğina, giska á lausn og sına ağ hún sé rétt:
a) T(1) = 1, T(n) = T(n-1) + n
b) T(1) = 1, T(n) = T(n/2) + logn, hér er n = 2^k.
c) T(1) = 1, T(n) = 2T(n/2) + logn, hér er n = 2^k.