Behörighetskrav

Algebra MN1 och Analys MN1.

Syfte

Kursen skall ge en introduktion till och

grundläggande kunskaper i den matematiska teorin

för beräkningar av betydelse för datavetenskap

Innehåll

Automatateori: deterministiska och

ickedeterministiska ändliga automater, reguljära

språk, Kleenes sats, pushdownautomater,

sammanhangsfria språk, pumpsatser. Chomskys

språkhierarki. Turingmaskiner: universalmaskinen

och stopproblemet. Orientering om

komplexitetsteori (kompexitetsklasserna P och NP).

Rekursiva funktioner. Rices sats och andra

oavgörbarhetsresultat. Church-Turings tes.

Logik: sats- och predikatlogik samt

semantiken för dessa.

Undervisning

Undervisningen sker i form av föreläsningar,

lektioner och räkneövningar.

Examination

Skriftligt och eventuellt muntligt prov vid

kursens slut. Dessutom förekommer obligatoriska

inlämningsuppgifter eller ett teoriprov som

redovisas i skriftlig och/eller muntlig form.