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

Innehåll

Kursen ger en introduktion till formella språk och beräkningsteori.

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 programmera datorer. Kursen belyser både teoretiska aspekter på och praktiska tillämpningar av formella språk. Vi studerar reguljära och kontextfria språk, deras representationer, egenskaper, och algoritmer för att arbeta med dem. Detta förankras med praktiska uppgifter inom textmatchning och parsning.

Vi behandlar sedan beräkningsteori med Turingmaskinen som en universell beräkningsmodell för att definiera och diskutera avgörbarhet, stopproblemet, och relaterade begrepp. Vi diskuterar Church-Turing-tesen, tidskomplexitet, och hur komplexitetsklasserna P och NP används.

Under kursens gång kommer aktuella forskningsfrågor inom området att beskrivas och diskuteras.

Förväntade studieresultat

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

• (FSR 1) förstå hur reguljära språk och kontextfria språk kan representeras, hur olika representationer förhåller sig till varandra, och hur de kan transformeras
• (FSR 2) förstå Turingmaskinen som en modell för beräkning och dess relation till Church-Turing-tesen samt begreppen avgörbarhet, igenkännbarhet, och beräkningsbarhet
• (FSR 3) förstå definitionerna av tidskomplexitet och i synnerhet komplexitetsklasserna P och NP
• (FSR 4) redogöra för några aktuella forskningsfrågor inom formella språk och beräkningsteori

Färdighet och förmåga
Efter avslutad kurs ska studenten kunna:

• (FSR 5) konstruera Turingmaskiner för givna beräkningsproblem och analysera deras tidskomplexitet
• (FSR 6) bevisa egenskaper relaterade till reguljära språk och kontextfria språk, till exempel bevis för stängningsegenskaper och motbevis för språktillhörighet
• (FSR 7) använda reduktioner för att demonstrera förhållanden mellan beräkningsproblem, till exempel NP-svårighet
• (FSR 8) formalisera ett informellt beskrivet (reguljärt eller kontextfritt) språk och avgöra om (och hur) givna strängar tillhör språket genom att tillämpa algoritmer

Behörighetskrav

För behörighet krävs följande kurser (eller motsvarande):
- Introduktion till diskret matematik, 7,5 hp
- DV0: Datavetenskapligt tänkande, 7,5 hp
- DV1: Datatyper och datastrukturer, 7,5 hp
- DV2: Algoritmer och problemlösning, 7,5 hp

Undervisningens upplägg

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

Examination

Examinationen sker genom skriftliga inlämningsuppgifter, muntliga examinationer och en salstentamen. På kursen sätts något av betygen Underkänd (U), Godkänd (G), eller Väl godkänd (VG) efter en samlad bedömning av prestationerna på de examinerande momenten.

Anpassad examination
För student som har beslut om rekommenderat stöd på grund av funktionsnedsättning kan examinator besluta om avsteg från kursplanens examinationsform. Individuell anpassning av examinationsformen ska övervägas utifrån studentens behov och kursens förväntade studieresultat. För mer information se Handläggningsordning för stöd till studenter med funktionsnedsättning samt Regel för betyg och examination.

Övriga föreskrifter

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 inte kan ingå i en examen tillsammans med 5DV037 Datavetenskapens grunder.

Övergångsbestämmelser

Om kursplanen har upphört att gälla eller kursen slutat erbjudas garanteras en student som någon gång registrerats på kursen minst tre provtillfällen (inklusive ordinarie provtillfälle) enligt denna kursplan under en tid av maximalt två år från det att kursplanen upphört att gälla eller kursen slutat erbjudas.