INF4130 – Algoritmer: Design og effektivitet

Timeplan, pensum og eksamensdato

Velg semester

Kort om emnet

Gjennomgang av generelle algoritme-klasser som dynamisk programmering, heuristiske algoritmer, probabilistiske algoritmer med mer, 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?

Etter å ha tatt INF4130 kan du

  • kjenne og kunne programmere viktige algoritmer innen flere sentrale andvendelsesområder.
  • kjenne og kunne anvende de viktigste prinsipper for design av effektive algoritmer.
  • vurdere hvor effektiv en gitt algoritme er, og kjenne begrepet «polynomiske algoritmer».
  • kunne kjenne igjen problemer som ikke kan løses ved noen algoritme.
  • kunne kjenne igjen problemer som kan løses algoritmisk, men ikke på noen effektiv måte.

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.

Overlappende emner

Undervisning

2 timer forelesning og 2 timer gruppeøvelser pr uke. Det kreves gjennomføring av obligatoriske oppgaver. Les mer om krav til innlevering av oppgaver, gruppearbeid og lovlig samarbeid under retningslinjer for obligatoriske oppgaver.

Eksamen

4 timer skriftlig eksamen. Alle obligatoriske oppgaver må være godkjente for å kunne gå opp til eksamen.

Karakterskala

Emnet bruker karakterskala fra A til F, der A er beste karakter og F er stryk. 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.

Trekk fra eksamen

Det er mulig å ta eksamen i emnet inntil tre ganger. Dersom du trekker deg fra eksamen etter fristen eller under eksamen, bruker du et eksamensforsøk.

Som eksamensforsøk i dette emnet teller også forsøk i følgende tilsvarende emner: INF3130 - Algoritmer: Design og effektivitet.

Annet

Det er sterkt anbefalt å møte på første forelesning fordi det vil bli gitt viktig informasjon.

Fakta om emnet

Studiepoeng

10

Nivå

Master

Undervisning

Hver høst

Eksamen

Hver høst

Undervisningsspråk

Norsk (engelsk på forespørsel)