Timeplan, pensum og eksamensdato

Velg semester

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

Forkunnskaper

Obligatoriske forkunnskaper

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.

Emnet forutsetter IN1150 – Logiske metoder/INF1080 – Logiske metoder for informatikk (videreført)

Overlappende emner

5 studiepoeng overlapp mot 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

Ingen hjelpemidler er 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.

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.

Tilrettelagt eksamen

Søknadskjema, krav og frist for tilrettelagt eksamen.

Fakta om emnet

Studiepoeng

10

Nivå

Bachelor

Undervisning

Hver vår

Dette emnet går for første gang våren 2019.

Eksamen

Hver vår

Undervisningsspråk

Norsk