Kursen behandlar en introduktion till beräkningsteorin, som omfattar områdena (a) formella språk, (b) beräkningsbarhet och (c) komplexitet. Inom dessa områden behandlas centrala begrepp och resultat såsom
(a) ändliga automater och reguljära uttryck, kontextfria grammatiker och parsning (syntaxträd, flertydighet), pumpinglemmana för reguljära och kontextfria språk
(b) Turing-maskinen som en universell beräkningsmodell, avgörbarhet och relaterade begrepp, Church-Turing-tesen, haltproblemet och dess oavgörbarhet, reduktion
(c) tidskomplexitet, klasserna P och NP, polynomtidsreduktion, P=NP-frågan
I kursen ingår även ett antal obligatoriska inlämningsuppgifter.
Förväntade studieresultat
Efter avslutad kurs ska studenten kunna:
definiera, skapa och tolka olika representationer av reguljära och kontextfria språk samt översätta mellan dem
bevisa och använda pumpinglemmat för reguljära språk och känna till pumpinglemmat för kontextfria språk
diskutera Church-Turing tesen
definiera begreppen avgörbarhet, igenkännbarhet, uppräkningsbarhet och beräkningsbarhet samt sätta dem i relation till varandra
definiera haltproblemet och bevisa dess oavgörbarhet
definiera och förklara klasserna P och NP samt begreppet NP-komplett
redogöra för problemet SAT och Cooks teorem
definiera begreppen reduktion och polynomtidsreduktion samt förklara vad som är syftena med dessa
Behörighetskrav
För tillträde till kursen krävs Introduktion till diskret matematik (5MA008) eller Algebra (MATA96) och en grundläggande programmeringskurs på universitetsnivå eller motsvarande kunskaper.
Undervisningens upplägg
Undervisningen bedrivs i form av föreläsningar och övningar i mindre grupper. Utöver schemalagda aktiviteter krävs även individuellt arbete med materialet.
Examination
Examinationen sker dels genom skriftlig tentamen dels genom obligatoriska uppgifter. På en skriftlig tentamen sätts något av betygen Underkänd (U), Godkänd (3), Icke utan beröm godkänd (4) eller Med beröm godkänd (5). På obligatoriska uppgifter ges endast betygen Underkänd (U) eller Godkänd (G). På hela kursen ges något av betygen Underkänd (U), Godkänd (3), Icke utan beröm godkänd (4) eller Med beröm godkänd (5). För att bli godkänd på hela kursen krävs att samtliga prov och obligatoriska moment är godkända. Betyget utgör en sammanfattande bedömning av resultaten vid examinationens olika delar och sätts först när alla obligatoriska moment är godkända.
För studerande som inte godkänns vid ordinarie provtillfälle anordnas ytterligare prov¬tillfälle. En student som utan godkänt resultat har genomgått två prov för en kurs eller en del av en kurs, har rätt att få en annan examinator utsedd, om inte särskilda skäl talar emot det (HF 6 kap. 22 §). Begäran om ny examinator ställs till styrelsen för Institutionen för datavetenskap.
Tillgodoräknande
I en examen får denna kurs ej ingå, helt eller delvis, samtidigt med en annan kurs med likartat innehåll. Vid tveksamheter bör den studerande rådfråga studievägledare vid Institutionen för datavetenskap.
Sipser Michael Introduction to the theory of computation 2. ed. : Boston, Mass. : Thomson Course Technology : 2006 : 437 s. : ISBN: 0-619-21764-2 (int. ed.) Se Umeå UB:s söktjänst