IN2080 – Beregninger og kompleksitet

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

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.

Tilrettelagt eksamen, kildebruk, begrunnelse og klage

Se mer om eksamen ved UiO

Sist hentet fra Felles Studentsystem (FS) 11. des. 2019 06:17:37

Fakta om emnet

Studiepoeng
10
Nivå
Bachelor
Undervisning
Vår
Eksamen
Vår
Undervisningsspråk
Norsk