Beregnbarhets- og kompleksitetsteori

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.

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.

Forelesninger og øvinger. Undervisningen vil kunne bli gitt på engelsk. Dersom kurset foreleses på engelsk vil eksamen bli gitt kun på engelsk. Ved utsatt eksamen (kontinuasjonseksamen) kan skriftlig eksamen bli endret til muntlig eksamen.