høst 2019

MAT-1005 Diskret matematikk - 10 stp

Sist endret: 20.09.2019

Ansvarlig fakultet

Fakultet for naturvitenskap og teknologi

Studiested

Tromsø |

Søknadsfrist

1. juni for emner som tilbys i høstsemesteret. 1. desember for emner som tilbys i vårsemesteret.

Emnetype

Emnet er obligatorisk i studieprogrammene Informatikk - bachelor og Informatikk - master (5-årig), sivilingeniør samt studiretningen Matematikk - Lektorutdanning for trinn 8-13 - master (5-årig). Det kan også tas som enkeltemne.

Opptakskrav

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.

Innhold

Kurset er et introduksjonskurs i matematikk som spesielt dekker matematiske strukturer som har anvendelser i informatikk. Det gis en introduksjon til fundamentale begreper i matematikk som mengder og funksjoner og inkluderer logikk og ulike bevisteknikker. Andre emner som vektlegges er kombinatorikk med sannsynlighetsregning og grafteori. Det gis en innføring i bruk av Mathematica som numerisk, symbolsk og grafisk verktøy, og for enkel programmering.

Hva lærer du

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.

Undervisnings- og eksamensspråk

Norsk

Undervisning

Forelesninger: 40 t
Øvelser: 30 t

Eksamen

En skriftlig eksamen av 4 timers varighet som teller 100 %.

Karakterskala: Bokstavkarakterer A-F.

Kontinuasjonseksamen: Studenter som ikke har bestått siste ordinære eksamen tilbys kontinuasjonseksamen tidlig i påfølgende semester, dersom emnet inngår som obligatorisk i studieprogrammet.

Utsatt eksamen: Studenter med gyldig forfall tilbys utsatt eksamen tidlig i påfølgende semester.

Arbeidskrav: Obligatoriske øvelser kreves godkjent for adgang til å avlegge eksamen.

For mer informasjon, se forøvrig:
- Utfyllende bestemmelser for eksamener ved Fakultet for naturvitenskap og teknologi
- Forskrift for eksamener i Tromsø

Eksamensdato

Skriftlig prø
ve 29.11.2019

Eksamensdato er foreløpig og vil kunne bli endret. Endelig eksamensdato kunngjøres på uit.no/eksamen og i studentweb primo mai for vårsemesteret og primo november for høstsemesteret

Timeplan



Kontakt
Instituttleder-Ragnar-Soleng

Ragnar Soleng


Førsteamanuensis
Telefon: +4777644014 ragnar.soleng@uit.no