Kort om emnet

En fortsettelse av emnet INF1080 – Logiske metoder for informatikk (videref?rt). Om endelige tilstandautomater – deterministiske, ikke deterministiske og alternerende. Studentene l?rer om overganger mellom automatene og forhold til regul?re uttrykk og grammatikker. Pushdown automater, kontekstfrie spr?k og turing maskiner . Om sekventkalkyle og f?rste ordens logikk. Beskrive beregninger i logikk. Begrensninger av logikk og beregninger – pumpelemma for automater, stoppeproblemet for turing maskiner, ufullstendighet av f?rste ordens logikk. Kompleksitetsklasser som P, NP og PSPACE.

Hva l?rer du?

Etter ? ha tatt INF2080 kan du

  • Gi beregninger med automater og turing maskiner
  • Gi sammenheng mellom automater og grammatikker
  • Beskrive beregninger med logikk
  • Forst? fullstendighet og ufullstendighet av f?rste ordens logikk
  • Vise begrensninger av logikk og beregninger
  • Forst? kompleksitetsklasser som 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.

INF1080 – Logiske metoder for informatikk (videref?rt)/INF1800 – Logikk og beregninger (nedlagt)/MAT1030 – Diskret matematikk (nedlagt)

Overlappende emner

5 studiepoeng overlapp mot INF1800 – Logikk og beregninger (nedlagt)

Undervisning

2 timer forelesning og 4 timer ?velse hver uke.

Det kreves gjennomf?ring av obligatoriske oppgaver som m? v?re godkjent for ? kunne g? opp til eksamen.

Krav til innlevering av oppgaver, gruppearbeid og lovlig 澳门葡京手机版app下载 under retningslinjer for obligatoriske oppgaver

Eksamen

4 timers skriftlig digital eksamen. Obligatoriske oppgaver m? v?re godkjent for ? kunne g? opp til eksamen.

 

Hjelpemidler

Ingen hjelpemidler er tillatt.

Eksamensspr?k

Du kan besvare eksamen p? norsk, svensk, dansk eller engelsk. S?knad om engelsk oppgavetekst sender du til kontaktpunktet for emnet.

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.

Annet

Det er sterkt anbefalt ? m?te p? f?rste forelesning fordi det vil bli gitt viktig informasjon.

Fakta om emnet

Studiepoeng
10
Niv?
Bachelor
Undervisning
Hver v?r
Eksamen
Hver v?r

Arrangeres v?r 2019 og v?r 2020

 

Undervisningsspr?k
Norsk (engelsk p? foresp?rsel)