ͯÑÕÊÓƵ

±õ²Ô²Ô±ð³óÃ¥±ô±ô

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.

Ö±¹±ð°ù²µÃ¥²Ô²µ²õ²ú±ð²õ³Ùä³¾³¾±ð±ô²õ±ð°ù

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.