DV3: Beräkningar och språk, 7,5 hp

Innehåll

Formella språk är grundläggande för vår förståelse av hur datorer utför beräkningar och oumbärliga redskap för att praktiskt programmera datorer. Kursen belyser både teoretiska aspekter på och praktiska tillämpningar av formella språk. Till att börja med fördjupas studiet av reguljära och kontextfria språk, samt deras olika representationer. Dessa kunskaper omsätts i praktisk kompetens inom textmatchning samt lexikalisk och syntaktisk analys av programspråk.

Kursen introducerar också Turingmaskiner, en av de viktigaste beräkningsmodellerna i datavetenskapens historia. Dessa används dels för att undersöka gränserna för vad datorer kan beräkna och dels för en introduktion till komplexitetsteori. Vi studerar komplexitetsklasserna P och NP, vars relation till varandra är ett av de viktigaste öppna problemen inom datavetenskapen. Under kursens gång kommer en mängd aktuella forskningsfrågor inom området att beskrivas och diskuteras.

Kursen består av två moment:
Moment 1, teori, 4.5 högskolepoäng
Moment 2, problemlösning, 3 högskolepoäng

Förväntade studieresultat

Efter avslutad kurs ska studenten kunna:
Kunskap och förståelse

• redogöra för pumpningslemmat för kontextfria språk (FSR 1),
• återge och exemplifiera definitionerna av LALR-, LR-, LA-, och deterministiska kontextfria språk (FSR 2),
• återge definitionen av Turingmaskin samt konstruera Turingmaskiner för enkla beräkningsproblem (FSR 3),
• definiera begreppen avgörbarhet, igenkännbarhet, uppräkningsbarhet och beräkningsbarhet samt sätta dem i relation till varandra (FSR 4),
• definiera komplexitetsklasserna P och NP (FSR 5),
• ge exempel på aktuella forskningsfrågor inom området (FSR 6),
• diskutera för- och nackdelar med olika representationer av reguljära språk (FSR 7),

Färdighet och förmåga

• konstruera och tolka pushdown-automater (FSR 8),
• använda reguljära uttryck för textmatchning, speciellt lexikalisk analys (FSR 9),
• tillämpa syntaxstyrd översättning på enklare kontextfria grammatiker (FSR 10),
• använda verktyg för lexikal- och syntaxanalys för att skapa en parser (FSR 11),
• konstruera algoritmer för att bevisa medlemskap i klasserna P och NP, samt använda reduktioner för att bevisa svårighet för klassen NP (FSR 12),

Värderingsförmåga och förhållningsätt

• diskutera förhållandet mellan teoretisk och praktisk beräkningsbarhet (FSR 13).

Behörighetskrav

För tillträde till kursen krävs kursen DV2: Algoritmer och problemlösning (5DV161) eller motsvarande kunskaper.

Undervisningens upplägg

Undervisningen bedrivs i form av föreläsningar, arbete i datorlabb och övningar i mindre grupper. Utöver schemalagda aktiviteter krävs även individuellt arbete med materialet.

Examination

Examinationen på Moment 1 (FSR 1-10, 12-13) sker dels genom ett antal mindre delprov samt en skriftlig tentamen. Momentet bedöms med något av betygen Väl godkänd (VG), Godkänd (G) eller Underkänd (U).

Moment 2 (FSR 7-13) examineras genom ett antal obligatoriska uppgifter. På moment 2 ges betygen Underkänd (U) eller Godkänd (G).

På hela kursen ges något av betygen Väl godkänd (VG), Godkänd (G) eller Underkänd (U). 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 vid Institutionen för datavetenskap

Övriga föreskrifter

TILLGODORÄKNANDE
Student har rätt att få prövat om tidigare utbildning eller motsvarande kunskaper och färdigheter förvärvade i yrkesverksamhet kan tillgodoräknas för motsvarande utbildning vid Umeå universitet. Ansökan om tillgodoräknande skickas in till Studentcentrum/Examina. Mer information om tillgodoräknande finns på Umeå universitets studentwebb, www.student.umu.se, och i högskoleförordningen (6 kap). Ett avslag på ansökan om tillgodoräknande kan överklagas (Högskoleförordningen 12 kap) till Överklagandenämnden för högskolan. Detta gäller såväl om hela som delar av ansökan om tillgodoräknande avslås.

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.

Speciellt gäller att denna kurs kan ej ingå fullt ut i en examen samtidigt som kursen Datavetenskapens grunder (5DV037).

Överlappet mellan denna och kurserna uppräknade ovan motsvarar ca 5hp. Om man läst kursen ovan och vill tillgodoräkna de kunskaperna till denna så måste man komplettera med examinerande delar som motsvarar FSR 6 och 13.