Faglig innhold

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), spenntrær, maksimal flyt og optimal sirkulasjon i nettverk. Metoder for søking i tekst. Teori for problemkompleksitet. Algoritmene uttrykkes mest mulig språkuavhengig.

Læringsutbytte

Å gi studentene nært kjennskap til et bredt spekter av etablerte algoritmer med nytteverdi på tvers av mange fagområder. Studentene skal bli i stand til å analysere algoritmers effektivitet for å oppnå best mulig løsning på et gitt problem, og de skal gis trening i hvordan problemer best formuleres for å kunne bli rasjonelt angrepet av en algoritme. Studentene skal videre lære å bruke kjente algoritmer og tilgjengelige programmoduler på nye problemstillinger, samt kunne utvikle og realisere nye datatekniske løsninger på komplekse problemstillinger med rot i en praktisk virkelighet.

Læringsformer og aktiviteter

Forelesninger og individuelle øvinger. Ved utsatt eksamen (kontinuasjonseksamen) kan skriftlig eksamen bli endret til muntlig eksamen.

Obligatoriske aktiviteter

• Øvinger

Anbefalte forkunnskaper

Studentene forutsettes å kunne programmere, for eksempel ved å ha tatt TDT4100 Objektorientert programmering. Studentene forutsettes også å ha kunnskaper om funksjoner, logaritmer, grensebetraktninger, mengder, relasjoner, induksjonsbevis, rekker og elementær sannsynlighetsregning.

Kursmateriell

Cormen, Leiserson, Rivest: Introduction to Algorithms, The MIT Press. (Det tas forbehold om endringer.)

Studiepoengreduksjon