Algoritmeteori (DAT600)
Emnet gir innsikt i teorien om algoritmer og deres ytelse. Det inkluderer et matematisk grunnlag for å analysere egenskapene av algoritmer. Emnet introduserer vanlige beregningsproblemer og ulike algoritmer for å løse dem. Emnet introduserer også problemet P=NP.
Dette er emnebeskrivelsen for studieåret 2025-2026. Merk at det kan komme endringer.
Fakta
Emnekode
DAT600
Versjon
1
Vekting (stp)
10
Semester undervisningsstart
Vår
Antall semestre
1
Vurderingssemester
Vår
Undervisningsspråk
Engelsk
Timeplan
Innhold
Emnet tar opp igjen noen matematiske begreper som vekst av funksjoner, standard notasjoner for tids kompleksitet, noen bevis teknikker og andre grunnlag fra tidligere fag. I løpet av emnet vil vi besøke problemer som sortering, trær, grafer og deres anvendelser, og multiplisering av matriser. Vi vil utvikle løsninger på disse problemene ved å anvende noen metoder som del og hersk, dynamiske og grådige algoritmer, og optimalisering.
Læringsutbytte
Etter å ha tatt dette emnet skal studenten:
- Være kjent med viktige prinsipper for å designe av avanserte algoritmer og vurdere deres ytelse.
- Være kjent med viktige problemer og algoritmer som løser dem.
- Kunne velge og anvende forskjellige typer algoritmer avhengig av hva informasjonssystemene krever.
- Være kjent med klassene av problemer P, NP, NP-Hard, NP-Complete.
- Kunne transformere et gitt problem til et optimaliserings problem og kunne løse det i praksis.
Forkunnskapskrav
Ingen
Anbefalte forkunnskaper
DAT200 Algoritmer og datastrukturer
Eksamen / vurdering
| Vurderingsform | Vekting | Varighet | Karakter | Hjelpemiddel |
|---|---|---|---|---|
| Skriftlig eksamen | 1/1 | 4 Timer | Bokstavkarakterer | Ingen trykte eller håndskrevne hjelpemidler tillatt. Godkjent, enkel kalkulator tillatt |
Digital eksamen.
Vilkår for å gå opp til eksamen/vurdering
Obligatoriske øvinger
4 obligatoriske innleveringsoppgaver.
Fagperson(er)
Emneansvarlig:
Nejm SaadallahInstituttleder:
Tom RyenArbeidsformer
4 timer forelesninger og 2 timer øvinger.
Overlapping
| Emne | Reduksjon (SP) |
|---|---|
| Algoritmeteori (MID290_1) | 10 |
Åpent for
Utveksling ved Det teknisk- naturvitenskapelige fakultet
Emneevaluering
Det skal være en tidligdialog mellom emneansvarlig, studenttillitsvalgt og studentene. Formålet er tilbakemelding fra studentene for endringer og justering i emnet inneværende semester.I tillegg skal det gjennomføres en digital emneevaluering minimum hvert tredje år. Den har som formål å innhente studentenes erfaringer med emnet.