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.