MAT-1005 Diskret matematikk - 10 stp

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

• 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 9336 - enkeltemner i realfag.

Emnet er en introduksjon i matematikken som spesielt dekker diskrete matematiske strukturer som har anvendelser i informatikk og elektronikk. Etter fullført kurs skal studentene:

• Kunne lese og forstå matematiske argumenter og selv kunne skrive enkle bevis, herunder også induksjonsbeviser.
• Beherske matematikkens basale strukturer som mengder og funksjoner mellom disse.
• Kunne forstå betydningen av uendelige følger og summasjoner og spesielt beherske aritmetiske og geometriske følger.
• Beherske tallteoretiske algoritmer som Euklids algoritme og rask eksponentiering, og også forstå viktigheten i disse for offentlig nøkkel kryptering.
• Kjenne til offentlig nøkkel krypteringsmetoden RSA.
• Beherske basale kombinatoriske telleteknikker som produkt- og summeregel og ha god forståelse av når disse kan brukes.
• Anvende dueslagsprinippet for å løse oppgaver i en rekke sammenhenger.
• Kunne bruke rekursjonsligninger til å løse avanserte telleproblemer.
• Kunne bruke inklusjons-eksklusjons prinsippet i konkrete oppgaver.
• Kjenne til hvordan diskrete strukturer som mengder, permutasjoner, relasjoner, matriser, grafer, trær og endelige tilstandsmaskiner brukes til modellering.
• Kjenne til begreper og problemer som korteste veg på grafer, utspenningstrær og fargetall for grafer.
• Kunne besvare hvorvidt en gitt graf har Euler eller Hamilton sti og veg.
• Beherske Huffmankoding til å finne effektiv koding av alfabeter.
• Beherske Dijkstras algoritme for å finne korteste veg på vektede grafer og Prims og Kruskals algoritme for å finne minimale utspenningstrær.
• Beherske boolsk algebra og kunne designe enkle boolske funksjoner med gitt output til bruk i elektroniske kretser.
• Beherske Karnaugh map og Quine-McCluskeys metode for minimalisering av kretser.
• Forstå hvordan endelige tilstandsmaskiner kan brukes til språkgjenkjenning.

Eksamensdato er foreløpig og vil kunne bli endret. Endelig eksamensdato kunngjøres ved oppslag på det enkelte fakultet primo mai for vårsemesteret og primo november for høstsemesteret.