MAT4630 – Beregnbarhetsteori
Kort om emnet
Innføring i klassisk beregnbarhetsteori med vekt på relativ beregnbarhet, grader av uavgjørbarhet og på anvendelser innen beregnbar analyse og teoretisk informatikk.
Hva lærer du?
Med utgangspunkt i de primitivt rekursive funksjonene og µ-operatoren innføres de beregnbare funksjonene og relasjonene over de naturlige tallene. Grunnleggende resultater vedrørende de partielle beregnbare funksjonene og de beregnbare og semiberegnbare mengdene blir vist.
Deretter ser man på forskjellige klassiske tilnærminger til gradering av de ikke-beregnbare funksjonene og mengdene. Avslutningsvis vil man se på hvordan den klassiske beregnbarhetsteorien brukes til å studere beregnbarhetsfenomener i analyse og topologi, og på hvordan alternative tilnærminger til beregnbarhet har anvendelser innen teoretisk informatikk.
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
Anbefalte forkunnskaper
Ingen spesielle anbefalte forkunnskaper.
Overlappende emner
*Informasjon om overlapp mot nedlagte emner kan være ufullstendig. Ta kontakt med instituttet ved spørsmål.
Undervisning
3 timer forelesning/regneøvelse hver uke hele semesteret.
Ved fremmøte av tre eller færre studenter kan faglærer, sammen med undervisningsleder, gjøre emnet om til selvstudiumsemne med veiledning.
Eksamen
Muntlig eksamen.
Hjelpemidler
Ingen hjelpemidler er tillatt.
Eksamensspråk
Dersom emnet undervises på engelsk vil det bare tilbys eksamensoppgavetekst på engelsk.
Du kan besvare eksamen på norsk, svensk, dansk eller engelsk.
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.
Evaluering av emnet
Vi gjennomfører fortløpende evaluering av emnet, og med jevne mellomrom ber vi studentene delta i en mer omfattende evaluering.