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.
Emnekode
DAT600
Versjon
1
Vekting (stp)
10
Semester undervisningsstart
Vår
Antall semestre
1
Vurderingssemester
Vår
Undervisningsspråk
Engelsk
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
Anbefalte forkunnskaper
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
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 |