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, Cooks teorem, eksempler. Emnet foreleses annet hvert år, neste gang høsten 2012.

Etter fullført kurs skal studenten kunne gjenkjenne, forstå og anvende begreper fra det teoretiske grunnlaget for informatikkfaget, som spesifisert under "Faglig innhold". Studenten skal være fortrolig med matematisk tankegang i forbindelse med datateknologi og programmering.

Forelesninger og øvinger. Ved utsatt eksamen (kontinuasjonseksamen) kan skriftlig eksamen bli endret til muntlig eksamen.