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