course-details-portlet

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.

Kursmateriell

Oppgis ved semesterstart.

Studiepoengreduksjon

Emnekode Reduksjon Fra Til
MA2301 7.5
Flere sider om emnet

Ingen

Fakta om emnet

Versjon: 1
Studiepoeng:  7.5 SP
Studienivå: Høyere grads nivå

Undervisning

Termin nr.: 1
Undervises:  HØST 2012

Undervisningsspråk: -

-

Fagområde(r)
  • Informatikk
  • Matematikk
Kontaktinformasjon
Emneansvarlig/koordinator:

Ansvarlig enhet
Institutt for matematiske fag

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.
Eksamensinfo

For mer info om oppmelding til og gjennomføring av eksamen, se "Innsida - Eksamen"

Mer om eksamen ved NTNU