DV3: Beräkningar och språk (5DV162)

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 studiet av reguljära och kontextfria språk, samt 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.