CS3: Computations and languages

Education facts

Code: 5DV208

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.

Entry requirements

null

Education offerings

Each offering has its own dates and conditions. Closed offerings are retained as history and do not mean that a new application is open.

• CS3: Computations and languages

  Umeå University

  Start date: 31 August 2026

  End date: 1 November 2026

  Pace of study: 50 %