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 kunskaperna om reguljära språk och kontextfria språk introduceras tillsammans med 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å moduler:
Modul 1, teori, 4.5 högskolepoäng
Modul 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 för olika 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),

Färdighet och förmåga

• använda en algoritm för att avgöra medlemsskap i ett språk definierat av en kontextfri grammatik (FSR 7)
• konstruera och tolka pushdown-automater (FSR 8),
• använda reguljära uttryck för textmatchning, speciellt lexikalisk analys (FSR 9),
• skapa en parser för en given kontextfri grammatik (FSR 10),
• 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 11),

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

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

Behörighetskrav

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

Undervisningens upplägg

Undervisningen bedrivs i form av föreläsningar och arbete med obligatoriska uppgifter. Utöver schemalagda aktiviteter krävs även individuellt arbete med materialet.

Examination

Examinationen på Modul 1 (FSR 1-8, 11-12) sker genom en skriftlig tentamen. Modulen bedöms med något av betygen Väl godkänd (VG), Godkänd (G) eller Underkänd (U).

Modul 2 (FSR 1-3, 9-12) examineras genom ett antal obligatoriska uppgifter. Antalet beror på uppgifternas svårighetsgrad men är aldrig mer än 5. På modul 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 moduler ä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 moduler ä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

Examination baserad på denna kursplan garanteras under två år efter studentens förstagångsregistrering på kursen. Detta gäller även om kursen lagts ned och denna kursplan upphört gälla.

Avsteg från kursplanens examinationsform kan göras för en student som har beslut om pedagogiskt stöd på grund av funktionsnedsättning. Individuell anpassning av examinationsformen ska övervägas utifrån studentens behov. Examinationsformen anpassas inom ramen för kursplanens förväntade studieresultat. Efter begäran av studenten ska kursansvarig lärare, i samråd med examinator, skyndsamt besluta om anpassad examinationsform. Beslutet ska sedan meddelas studenten.

Ö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, överlapp ca 5hp) eller kursen 5DV162 med samma namn som denna kurs (överlapp ca 7.5hp).

Om man läst kursen 5DV037 och vill tillgodoräkna de kunskaperna till denna kurs så måste man komplettera med examinerande delar som motsvarar FSR 6 och 13.