Dette emnet er nedlagt

INF9135 – 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.

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.

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

 

Fakta om emnet

Studiepoeng

10

Nivå

Ph.d.

Undervisning

Hver høst

Eksamen

Hver høst

Undervisningsspråk

Norsk (engelsk på forespørsel)