Diskret matematikk

Emnet er obligatorisk i studieprogrammene Informatikk, sivilingeniør - master (5-årig), Informatikk datafag (Mo i Rana, Bodø), samt studieretningen Matematikk - Lektorutdanning for trinn 8-13 - master (5-årig). Det kan også tas som enkeltemne.

Emnet gir en introduksjon til grunnleggende diskrete strukturer i matematikk. Det starter med en innføring i grunnleggende mengdelære og utsagnslogikk, og bevisteknikker utforskes gjennom påstander om heltall. Videre bygges det på strukturer som relasjoner, funksjoner, partisjoner, grafer, strenger, følger og rekker. Modulær aritmetikk behandles grundig, med anvendelser innen kryptografi. Problemer knyttet til vandringer i grafer, med anvendelser i informatikk, undersøkes, og flere praktiske algoritmer presenteres. I tillegg introduseres grunnleggende kombinatorikk, inkludert telleprinsipper, permutasjoner og kombinasjoner (med og uten repetisjon), inklusjon-eksklusjon og dueslagprinsippet.

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.

Du vil få en reduksjon i antall studiepoeng (som oppgitt under), dersom du avlegger eksamen i dette emnet og har bestått følgende emne(r) fra før av:

• MAT-6053 Innføring i logikk, bevis, resonnering og argumentasjon med programmering 5 stp

Undervisnings- og eksamensspråk

Mer info om arbeidskrav

Det er mange aktiviteter gjennom semester som er poenggivende. En student trenger 60% eller mer av de totale tilgjengelige poeng for å framstille seg til eksamen. Aktivitetene inkluderer:

• 6 fysiske quizzer

• 12 digitale quizzer

• 2 to-timers fysiske midtveisprøver

Kontinuasjonseksamen