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
Opptakskrav
Søkeren må oppfylle opptakskravet til et av studieprogrammene som emnet er åpent for.
Emneevaluering
Fakultetet avgjør om det skal gjennomføres tidligdialog i alle emner eller i utvalgte grupper av emner. Formålet er å få tilbakemeldinger fra studentene for forbedringer i semesteret. I tillegg skal det gjennomføres en digital emneevaluering minst hvert tredje år for å innhente studentenes erfaringer.