IN2080 – Beregninger og kompleksitet
Beskrivelse av emnet
Kort om emnet
I dette emnet lærer du om sammenhengene mellom ulike beregningsmodeller, formelle språk, deres begrensinger og kompleksitet.
Hva lærer du?
Etter å ha fullført IN2080:
- forstår du beregningsmodellene: endelige automater, pushdown-automater og turingmaskiner
- kan du forklare sammenhengen mellom automater/turingmaskiner og de ulike språkklassene og oversette mellom ekvivalente modeller
- kan du forklare begrensningene til språk- og modellklassene
- kan du gi en formell definisjon for viktige begrep, som for eksempel «algoritme»
- forstår du kompleksitetsklassene L, NL, P, NP og PSPACE
Opptak til emnet
Studenter ved UiO søker plass på undervisning og melder seg til eksamen i Studentweb.
Spesielle opptakskrav
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.
Obligatoriske forkunnskaper
Emnet forutsetter IN1150 – Logiske metoder/INF1080 – Logiske metoder for informatikk (videreført)
Overlappende emner
- 5 studiepoeng overlapp med INF2080 – Logikk og beregninger (videreført).
Undervisning
4 timer forelesning og 2 timer gruppeøvelser per uke. Det kreves innlevering av obligatoriske oppgaver. Les mer om krav til innlevering av oppgaver, gruppearbeid og lovlig samarbeid under retningslinjer for obligatoriske oppgaver.
Eksamen
4 timers avsluttende skriftlig digital eksamen. Alle obligatoriske oppgaver må være godkjente for å kunne gå opp til eksamen.
Hjelpemidler til eksamen
Ingen hjelpemidler er tillatt.
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.