Diskret matematikk

Innføring i elementær kombinatorikk og mengdelære, tallsystemer, induksjon og rekursjon og grafteori. Metoder for å analysere effektiviteten av algoritmer, splitt- og hersk-teknikker, rekursive løsningsmetoder. Metoder for ordning, søking i og sortering av datamengder. Datastrukturer for effektiv gjenfinning av data, dynamisk programmering og grådighetsalgoritmer. Datastrukturer for etablering av grafer og nettverk, samt metoder for gjennomløping og leting. Algoritmer for å finne beste vei(er) og koplinger (matchinger) og spenntrær. Teori for problemkompleksitet.

1. Kunnskap:
Studenten har grunnleggende kunnskaper innen mengdelære og kombinatoriske tellemetoder. Studenten har kunnskaper om rekursjon og induksjon, samt om grafer og trær. Studenten har kunnskap om et bredt spekter av etablerte algoritmer og datastrukturer med nytteverdi på tvers av mange fagområder. Klassiske algoritmiske problemer med kjente effektive løsninger. Komplekse problemer uten kjente effektive løsninger.

2. Ferdigheter:
Studenten skal kunne:
- Gjøre praktisk bruk av elementær mengdelære, føre enkle induksjonsbevis, anvende kombinatoriske tellemetoder til å løse praktiske problemer.
- Analysere algoritmers effektivitet for å oppnå best mulig løsning på et gitt problem.
- Formulere et problem så det rasjonelt kan løses av en algoritme.
- Bruke kjente designmetoder for å konstruere nye effektive algoritmer.

3. Generell kompetanse:
Kandidaten skal være i stand til:
- Å gjenkjenne, forstå og bruke begreper som grafer og trær i anvendelser, f.eks. innen informasjonsteknologi.
- Å bruke kjente algoritmer og tilgjengelige programmoduler på nye problemstillinger.
- Utvikle og realisere nye datatekniske løsninger på komplekse problemstillinger med rot i en praktisk virkelighet.

Forelesninger og obligatoriske øvinger. Karakter basert på avsluttende skriftlig eksamen. Ved utsatt eksamen (kontinuasjonseksamen) kan skriftlig eksamen bli endret til muntlig eksamen.