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.
Den här kursen innehåller tillfällen som är en del av ett program på Umeå universitet. Du kan bara söka kursen om du går det programmet. Information om ansökningstider och vad som gäller för dig får du från din institution.
