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 欧洲杯在线买球_欧洲杯投注网站推荐@ 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.