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 ett antal skriftliga inlämningsuppgifter 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.

Stöd på grund av funktionsnedsättning
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.

Byte av examinator
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.

Ö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.

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.