MAT-1005 Diskret matematikk - 10 stp

Generell studiekompetanse og følgende spesielle opptakskrav: Matematikk R1 og i tillegg enten:

• Matematikk R2

• Fysikk 1 + 2 eller

• Kjemi 1+ 2 eller

• Biologi 1 + 2 eller

• Informasjonsteknologi 1 +2 eller

• Geofag 1 + 2 eller

• Teknologi og forskningslære 1 + 2

Søknadskode 9197 (kravkode REALFA): Enkeltemner i realfag, lavere grad.

Kunnskap

Etter emnet er fullført har studenten:

• Kunnskap om grunnleggende mengdelære, utsagnslogikk og predikatlogikk, samt sentrale bevisteknikker.

• Kunnskap om definisjoner og egenskaper ved sentrale diskrete strukturer: relasjoner, funksjoner, partielle og totale ordninger, ekvivalensrelasjoner, strenger og tupler; samt begrepene injektiv, surjektiv og bijektiv.

• Kunnskap om tallteori: aksiomer for de naturlige tallene og heltallene; divisjon, største felles divisor (sfd) og Euklids algoritme; modulær aritmetikk og lineære kongruenser, med tilknytning til diofantiske likninger; det kinesiske restteoremet og Fermats lille teorem; oversikt over RSA-metoden.

• Kunnskap om grunnleggende kombinatorikk: telleprinsippene, permutasjoner og kombinasjoner; dueslagsprinsippet og inklusjons-eksklusjonsprinsippet.

• Kunnskap om grafer: enkle, rettede, sammenhengende og vektede grafer; trær; grafisomorfi; Eulers teorem om Euler-veier og -kretser; kjennskap til Hamilton-stier og -kretser, handelsreisendeproblemet og det kinesiske postbudproblemet; Dijkstras algoritme.

Ferdigheter

Etter emnet er fullført kan studenten:

• Beherske standard matematisk notasjon (mengdeoperasjoner, implikasjonspiler, kvantorer, summetegn, binomialkoeffisienter).

• Anvende og manipulere mengder, relasjoner og funksjoner; identifisere injektive, surjektive og bijektive funksjoner.

• Utføre induksjonsbevis og anvende grunnleggende bevismetoder i enkle resonnementer.

• Utføre beregninger i tallteori: finne største felles divisor med Euklids algoritme, bruke rask eksponentiering, løse lineære kongruenser og systemer av lineære kongruenser ved hjelp av det kinesiske restteoremet; kryptere og dekryptere enkle meldinger med RSA-metoden.

• Analysere og tolke utsagnslogiske og predikatlogiske formler: oversette predikatlogiske formler til og fra naturlig språk, avgjøre om to utsagnslogiske formler er logisk ekvivalente, og minimalisere utsagnslogiske formler ved hjelp av Karnaugh-diagrammer.

• Løse telleproblemer med produkt- og summeregel, permutasjoner og kombinasjoner (med og uten repetisjon), samt bruke dueslagsprinsippet og inklusjons-eksklusjonsprinsippet.

• Analysere grafer: avgjøre om en graf har Euler-vei eller -krets eller Hamilton-sti eller -krets; finne korteste vei i vektede grafer med Dijkstras algoritme; avgjøre om to grafer er isomorfe.

Generell kompetanse

Etter emnet er fullført kan studenten:

• Utforme egne matematiske resonnementer, presentere dem i et presist matematisk språk og begrunne gyldigheten.

• Tolke, bearbeide, vurdere og diskutere matematisk innhold i skriftlige, muntlige og grafiske framstillinger.

• Modellere diskrete problemstillinger og velge hensiktsmessige metoder og algoritmer; vurdere forutsetninger, korrekthet og begrensninger.