INF9135 – Algoritmer: design og effektivitet
Beskrivelse av emnet
Timeplan, pensum og eksamensdato
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.
In addition, each PhD candidate will be given an extended curriculum within the field/research area of the course. The syllabus must be approved by the lecturer so that the student can be admitted to the final exam.
Opptak og adgangsregulering
Ph.d.-kandidater ved UiO s?ker plass p? undervisningen og melder seg til eksamen i Studentweb.
Hvis emnet har begrenset kapasitet, vil ph.d.-kandidater som har emnet i sin utdanningsplan ved UiO bli prioritert. Noen nasjonale forskerskoler kan ha egne regler for rangering av s?kere til emner med begrenset kapasitet.
Ph.d.-kandidater som har opptak ved andre utdanningsinstitusjoner m? innen angitt frist s?ke om hospitantplass.
Forkunnskaper
Anbefalte forkunnskaper
Emnet bygger p? INF1010 – Objektorientert programmering (videref?rt) og det anbefales sterkt ? ha tattINF2220 – Algoritmer og datastrukturer (videref?rt)/INF 110/HUMIT2720MN – Datalingvistikk 1 (nedlagt)/HUMIT2720 – Datalingvistikk 1 (nedlagt).
Overlappende emner
- 10 studiepoeng overlapp mot INF3130 – Algoritmer: Design og effektivitet (nedlagt)
- 3 studiepoeng overlapp mot INF4200 – Algoritmer og effektivitet (nedlagt)
- 10 studiepoeng overlapp mot INF4130 – Algoritmer: Design 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, som er st?rre enn i INF4130.
Eksamen
3 timers skriftlig eksamen.
Note that the exam in INF9135 will be more extensive than the one in INF4130.
Karakterskala
Emnet bruker karakterskala best?tt/ikke best?tt. Les mer om karakterskalaen.
Begrunnelse og klage
Adgang til ny eller utsatt eksamen
Studenter som dokumenterer gyldig frav?r fra ordin?r eksamen, kan ta utsatt eksamen i starten av neste semester.
Det tilbys ikke ny eksamen til studenter som har trukket seg under ordin?r eksamen, eller som ikke har best?tt.
Annet
Det er obligatorisk oppm?te p? f?rste forelesning. Ved praktisering av 3-gangers regelen skal emnet sees i sammenheng med INF3130 – Algoritmer: Design og effektivitet (nedlagt).