INF3130 – Algoritmer: Design og effektivitet
Beskrivelse av emnet
Kort om emnet
Gjennomgang av generelle algoritme-klasser (så som dynamisk programmering, heuristiske algoritmer, probabilistiske algoritmer etc.) samt av et representativt utvalg enkelt-algoritmer som løser aktuelle problemer. Vekt på effektivitetsvurdering. Videre gjennomgåes den grunnleggende teorien for NP-kompletthet (hvilke problemer kan ikke løses i ”rimelig” tid), og for uavgjørbarhet (hvilke problemer har ingen løsningsalgoritme).
Hva lærer du?
Studentene skal få en oversikt over algoritmer og klasser av algoritmer, og hva slags problemer disse kan løse. Dessuten gis studentene teori og verktøy til å avgjøre om det for et gitt problem ikke finnes noen effektiv algoritme, eller ikke noen algoritme i det hele tatt.
Opptak og adgangsregulering
Studenter må hvert semester søke og få plass på undervisningen og melde seg til eksamen i Studentweb.
Dersom du ikke allerede har studieplass ved UiO, kan du søke opptak til våre studieprogrammer, eller søke om å bli enkeltemnestudent.
Forkunnskaper
Obligatoriske forkunnskaper
I tillegg til generell studiekompetanse eller realkompetanse må du dekke spesielle opptakskrav:
- Matematikk R1 eller Matematikk (S1+S2)
De spesielle opptakskravene kan også dekkes med fag fra videregående opplæring før Kunnskapsløftet, eller på andre måter. Les mer om spesielle opptakskrav.
Emnet forutsetter INF1020 – Algoritmer og datastrukturer (nedlagt)/INF 110/HUMIT2720MN – Datalingvistikk 1 (nedlagt)/HUMIT2720 – Datalingvistikk 1 (nedlagt).
Anbefalte forkunnskaper
Emnet bygger på INF1010 – Objektorientert programmering (videreført).
Overlappende emner
10 studiepoeng mot INF4130 – Algoritmer: Design og effektivitet (nedlagt) og 3 studiepoeng mot INF4200 – Algoritmer og effektivitet (nedlagt).
Undervisning
2 timer forelesning og 2 timer gruppeøvelser pr uke. Det kreves gjennomføring av obligatoriske oppgaver for å kunne gå opp til eksamen.
Eksamen
3 timers skriftlig eksamen. Bokstavkarakter (A - F).
Adgang til ny eller utsatt eksamen
Dette emnet tilbyr ikke ny eksamen i begynnelsen av påfølgende semester til kandidater som stryker eller trekker seg under ordinær eksamen. For generelle opplysninger om ny og utsatt eksamen, se /studier/admin/eksamen/sykdom-utsatt/mn/index.html
Annet
Det er obligatorisk oppmøte på første forelesning. Ved praktisering av 3-gangers regelen skal emnet sees i sammenheng med INF4130 – Algoritmer: Design og effektivitet (nedlagt).
Tilsynssensor for emnet er: Fredrik Manne