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.