INF2080 – Logikk og beregninger
Beskrivelse av emnet
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.
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.