Datavetenskapens grunder, 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.

Utöver detta behandlas ett urval av mer avancerade ämnen, antingen i fördjupning av ovanstående, eller som behandling av aktuella forskningsfrågor.

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) skriftligt diskutera en teoretisk fördjupning av någon del av innehållet

Behörighetskrav

För behörighet krävs följande kurser (eller motsvarande):
- Introduktion till diskret matematik, 7,5 hp
- Datastrukturer och algoritmer, 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 (3), Icke utan beröm godkänd (4) eller Med beröm godkänd (5) efter en samlad bedömning av prestationerna på de examinerande momenten.

Examinator kan besluta om avsteg från kursplanens examinationsform. Individuell anpassning av examinationsformen ska övervägas utifrån studentens behov. Examinationsformen anpassas inom ramen för kursplanens förväntade studieresultat. Student som har behov av en anpassad examination ska senast 10 dagar innan examinationen begära anpassning hos Institutionen för datavetenskap. Examinator beslutar om anpassad examination som sedan meddelas studenten.

Ö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 samtidigt som DV3: Beräkningar och språk.

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.