IN3130 – Algoritmer: Design og effektivitet
Beskrivelse av emnet
Kort om emnet
Emnet gir en gjennomgang av generelle algoritme-klasser som dynamisk programmering, heuristiske algoritmer, probabilistiske algoritmer, samt et representativt utvalg av enkeltalgoritmer som løser aktuelle problemer. Det legges vekt på effektivitetsvurdering. Videre gjennomgås teorien for NP-kompletthet og for uavgjørbarhet - problemer uten en løsningsalgoritme.
Hva lærer du?
Etter å ha fullført IN3130:
- kjenner du til og vil kunne programmere viktige algoritmer innen flere sentrale anvendelsesområder
- kjenner du til og vil kunne anvende de viktigste prinsipper for design av effektive algoritmer
- kan du vurdere hvor effektivt en gitt algoritme er, og kjenner til begrepet «polynomiske algoritmer»
- kjenner du igjen problemer som ikke kan løses av noen algoritme
- kjenner du igjen problemer som kan løses algoritmisk, men ikke på noen effektiv måte
Opptak til emnet
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.
Spesielle opptakskrav
I tillegg til generell studiekompetanse eller realkompetanse må du dekke spesielle opptakskrav:
- Matematikk R1 (eller Matematikk S1 og 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.
Obligatoriske forkunnskaper
Emnet forutsetter IN2010 – Algoritmer og datastrukturer/INF2220 – Algoritmer og datastrukturer (videreført).
Overlappende emner
- 10 studiepoeng overlapp med INF4130 – Algoritmer: Design og effektivitet (nedlagt).
- 10 studiepoeng overlapp med INF3130 – Algoritmer: Design og effektivitet (nedlagt).
- 10 studiepoeng overlapp med INF9135 – Algoritmer: design og effektivitet (nedlagt).
Undervisning
2 timer forelesning og 2 timer gruppeøvelser per uke. Les mer om krav til innlevering av oppgaver, gruppearbeid og lovlig samarbeid under retningslinjer for obligatoriske oppgaver.
Eksamen
Muntlig eksamen. Alle obligatoriske oppgaver må være godkjente for å kunne gå opp til eksamen.
Som eksamensforsøk i dette emnet teller også forsøk i følgende tilsvarende emner: INF3130 – Algoritmer: Design og effektivitet (nedlagt) og INF4130 – Algoritmer: Design og effektivitet (nedlagt)
Hjelpemidler til eksamen
Alle trykte og skrevne hjelpemidler tillatt.
Eksamensspråk
Du kan besvare eksamen på norsk, svensk, dansk eller engelsk.
Karakterskala
Emnet bruker karakterskala fra A til F, der A er beste karakter og F er stryk. Les mer om karakterskalaen
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.
Mer om eksamen ved UiO
- Kildebruk og referanser
- Tilrettelegging på eksamen
- Trekk fra eksamen
- Syk på eksamen / utsatt eksamen
- Begrunnelse og klage
- Ta eksamen på nytt
- Fusk/forsøk på fusk
Andre veiledninger og ressurser finner du på fellessiden om eksamen ved UiO.