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