Dette emnet er nedlagt

INF3130 – Algoritmer: Design og effektivitet

Timeplan, pensum og eksamensdato

Velg semester

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).

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

Fakta om emnet

Studiepoeng

10

Undervisning

Høst 2007

Høst 2006

Høst 2005

Denne versjonen av emnet går for siste gang høsten 2007. INF4130 – Algoritmer: Design og effektivitet (nedlagt) vil videreføres.

Eksamen

Hver høst

Undervisningsspråk

Norsk