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) och en grundläggande kurs i programmeringsmetodik (tex 5DV104, 5DV105, 5DV106 eller 5DV114) 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 provtillfä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 prefekten 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 och/eller programansvarig för sitt program.
Tillgodoräknande av studier prövas individuellt (se universitetets regelsamling och tillgodoräknandeordning). Ansökan om tillgodoräknande görs på speciell blankett och ställs till den Teknisk-naturvetenskapliga fakultetsnämnden, Umeå universitet.
Linz Peter An introduction to formal languages and automata 5th ed. : Sudbury, MA : Jones & Bartlett Learning : c2012 : xiii, 437 p. : ISBN: 978-1-4496-3739-2 (hft.) Obligatorisk Se Umeå UB:s söktjänst
Linz Peter An introduction to formal languages and automata 5th ed. : Sudbury, MA : Jones & Bartlett Learning : c2012 : xiii, 437 p. : ISBN: 978-1-4496-3739-2 (hft.) Obligatorisk Se Umeå UB:s söktjänst
