Emne - Beregnbarhets- og kompleksitetsteori - MA3301
MA3301 - Beregnbarhets- og kompleksitetsteori
Om emnet
Nytt fra studieåret 2012/2013
Vurderingsordning
Vurderingsordning: Skriftlig eksamen
Karakter: Bokstavkarakterer
Vurdering | Vekting | Varighet | Delkarakter | Hjelpemidler |
---|---|---|---|---|
Skriftlig | 100/100 | 4 timer |
Faglig innhold
Emnet gir en innføring i deler av den teoretiske bakgrunnen for informatikkfaget, og vil blant annet omhandle formelle språk, endelige automater, Turing-maskiner, beregnbarhet, rekursjon, polynomiell reduksjon, kompleksitetsklasser og Cooks teorem. Emnet foreleses annethvert år, neste gang høsten 2012.
Læringsutbytte
1. Kunnskap. Studenten behersker de mest sentrale formelle metoder for beregninger, formelle språk, endelige automater og Turing-maskiner, og forstår beregnbarhetsbegrepet.
Studenten har oversikt over de mest sentrale kompleksitetsklasser av problemer, som P og NP, og kjenner til NP-komplette problemer og Cooks teorem.
2. Ferdigheter. Studenten kan gjøre beregninger med formelle språk, endelige automater og Turing-maskiner. Studenten kan, bl.a. ved hjelp av polynomiell reduksjon, gjøre beregninger og vurderinger angående kompleksitetsklassen til gitte problemer.
Læringsformer og aktiviteter
Forelesninger og øvinger. Ved utsatt eksamen (kontinuasjonseksamen) kan skriftlig eksamen bli endret til muntlig eksamen.
Anbefalte forkunnskaper
MA0301 Elementær diskret matematikk eller TMA4140 Diskret matematikk.
Kursmateriell
Oppgis ved semesterstart.
Studiepoengreduksjon
Emnekode | Reduksjon | Fra | Til |
---|---|---|---|
MA2301 | 7.5 |
Ingen
Versjon: 1
Studiepoeng:
7.5 SP
Studienivå: Høyere grads nivå
Termin nr.: 1
Undervises: HØST 2012
Undervisningsspråk: -
-
- Informatikk
- Matematikk
Eksamensinfo
Vurderingsordning: Skriftlig eksamen
- Termin Statuskode Vurdering Vekting Hjelpemidler Dato Tid Eksamens- system Rom *
- Høst ORD Skriftlig 100/100 12.12.2012 09:00
-
Rom Bygning Antall kandidater
- * Skriftlig eksamen plasseres på rom 3 dager før eksamensdato. Hvis mer enn ett rom er oppgitt, finner du ditt rom på Studentweb.
For mer info om oppmelding til og gjennomføring av eksamen, se "Innsida - Eksamen"