itf10705---matematikk-for-it---15-12-2017

EKSAMEN

Emnekode:

ITF10705

Emnenavn:

Matematikk for IT Dato:

15. desember 2017

Eksamenstid:

09.00 – 13.00 Hjelpemidler:

- To A4-ark med valgfritt innhold på begge sider.

Kalkulator er ikke tillatt.

Faglærer:

Christian F Heide

Om eksamensoppgaven og poengberegning:

Oppgavesettet består av 8 sider inklusiv denne forsiden og to sider med vedlegg.

Kontroller at oppgavesettet er komplett.

Oppgavesettet består av 13 oppgaver. Ved sensur vil alle oppgaver telle like mye.

Der det er mulig skal du:

 Vise utregninger og hvordan du kommer fram til svarene.

 Begrunne dine svar, selv om dette ikke er eksplisitt sagt i hvert spørsmål.

Sensurfrist:

15. januar 2018

Karakterene er tilgjengelige for studenter på Studentweb senest 2 virkedager etter oppgitt sensurfrist. www.hiof.no/studentweb

ITF10705 Matematikk for IT, desember 2017 Side 2 av 8 Gitt følgende binære tall:

1011011 og

1101

Utfør en multiplikasjon av disse tallene på binær form (altså uten å konvertere dem til et annet tallsystem).

Skriv svaret både på binær form og heksadesimal form.

Oppgave 2

Gitt følgende mengder

A = {1, 3, 5, 7}, B = {2, 3, 5} og C = {1, 5, 7}.

og universet

U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Finn følgende mengder og skriv dem på listeform:

a) CA b) (AB)C

Oppgave 3 Gitt mengden

A = {2, 4, 5, 10, 12, 20}

En relasjon på A er gitt ved





R ( , ) |

altså at (a,b)R dersom a deler b.

a) Skriv mengden R på listeform.

b) Begrunn at relasjonen er en delvis ordning.

c) Tegn hassediagrammet for den delvis ordnede mengden (A, R).

d) Er denne relasjonen en totalordning? Begrunn svaret.

ITF10705 Matematikk for IT, desember 2017 Side 3 av 8 Bruk sannhetstabeller til å undersøke om følgende logiske utsagn er logisk ekvivalente:

i) (pq)r ii) (pr)(qr)

Oppgave 5

Gitt følgende sammensatte logiske utsagn:



 



Benytt lovene i logikk gitt i vedlegget til å forenkle dette utsagnet for å finne hvilket av følgende utsagn det er logisk ekvivalent med:

i) pq ii) pr iii) pq iv) pq

v) p

Bruk kun én lov i hvert trinn, og angi for hvert trinn hvilken lov du bruker.

Oppgave 6 Gitt to mengder:

A = {1, 2, 3, …, 99, 100}

B = {1, 2, 3, …, 99, 100, 101}

Gitt en funksjon B A f : 

a) Hva betyr det at en funksjon er injektiv? Kan funksjonen f :AB være injektiv? Begrunn svaret.

b) Hva betyr det at en funksjon er surjektiv? Kan funksjonen f :AB være surjektiv? Begrunn svaret.

c) Kan funksjonen f :AB ha en invers funksjon? Begrunn svaret.

ITF10705 Matematikk for IT, desember 2017 Side 4 av 8 Bruk induksjonsbevis til å bevise følgende formel for n1:

) 7 3 ( ) 2 3 ( 11

8

5   n ₂¹ n² n

Oppgave 8

a) Finn den generelle løsningen av følgende differensligning:

0 6 ₂

1 

 _{n n}

n y y

y

b) Gitt følgende differensligning:

n n

n

n y y

y  _16 _2 52

Finn løsningen av denne når følgende startbetingelser er gitt:

0 3 y

110 y

Oppgave 9

Lag en aksepterende automat med alfabet {0, 1} som gjenkjenner alle bitstrenger som

inneholder nøyaktig tre enere. Det er ikke noe krav at enerne skal komme rett etter hverandre for at automaten skal akseptere strengen.

Oppgave 10

Gitt følgende vektede graf:

Bruk Kruskals algoritme til å finne et minimalt spenntre for grafen. Vis hvert trinn i algoritmen.

2 2

3 1

3

1 3

4

b a

c

d e

ITF10705 Matematikk for IT, desember 2017 Side 5 av 8 Nedenfor er grafene G₁ (V₁,E₁) og G₂ (V₂,E₂) tegnet.

G₁ (V₁,E₁) G₂ (V₂,E₂)

Er G1 og G2 isomorfe?

Dersom de er isomorfe må du angi en funksjon f :V₁ V₂ og vise at denne funksjonen oppfyller kravene til en isomorfi.

Dersom de ikke er isomorfe må du forklare hvorfor de ikke er det.

Oppgave 12

En turingmaskin er definert ved følgende fem-tupler:

1. (s0, 0, s1, 0, R) 2. (s0, 1, s1, 1, R) 3. (s1, 0, s0, 1, R) 4. (s1, 1, s1, 0, R) 5. (s0, B, s2, 0, L) 6. (s1, B, s2, 1, L)

Anta nå at vi kjører turingmaskinen med en tape som ved oppstart ser slik ut:

Vis hvert trinn i kjøringen av denne turingmaskinen. Angi hvordan tapen ser ut etter kjøringen (altså hvilke symboler som står i de ulike cellene), og hvilken tilstand turingmaskinen er i etter kjøringen.

6 f

b

a c

d

e

1 2

3 4

5

… B 1 0 B …

ITF10705 Matematikk for IT, desember 2017 Side 6 av 8 Gitt en grammatikk med startsymbol s, hvor mengden av ikke-avslutningssymboler er

N = {s, t, u} og mengden av avslutningssymboler er T = {0, 1}. Grammatikken har følgende produksjonsregler:

1. sstu 2. u0t1 3. t 1 4. st

Er denne grammatikken kontekstfri, regulær eller ingen av delene? Begrunn svaret.

ITF10705 Matematikk for IT, desember 2017 Side 7 av 8

ITF10705 Matematikk for IT, desember 2017 Side 8 av 8

Lover for logikk og mengder

Lov Logikk Mengder

1. Assosiative lover (pq)r  p(qr) (A  B)  C = A  (B  C) )

( )

(pq r  p qr (A  B)  C = A  (B  C)

2. Kommutative lover pqq p A  B = B  A

p q q

p   A  B = B  A

3.Distributive lover p(qr)(pq)(pr) A  (B  C) = (A  B)  (A  C) )

( ) ( )

(q r p q p r

p      A  (B  C) = (A  B)  (A  C)

4. De Morgans lover (pq)pq ABA B q

p q

p  

( ) ABA B

5. Idempotenslover pp p _{A  A = A}

p p

p  _{A  A = A}

6.Absorpsjonslover p(pq) p A  (A  B) = A p

q p

p(  ) A  (A  B) = A 7. Dobbel negasjon /

Involusjonslov

 ( p)  p _{A  A}

8. Inverslover pp S AA U

F p

p  AA 

9. Identitetslover pS p AU  A

p F

p  A A

10. Dominanslover pF F A   = 

S S

p  A  U = U

11. Implikasjon pq pq 12. Kontrapositive pq qp

utsagn

Inklusjons- og eksklusjonsprinsippet

|A  B  C| = |A| + |B| + |C| – | A  B| – |A  C| – |B  C| + |A  B  C|