Datavetenskapens grunder

Kursen behandlar en introduktion till beräkningsteorin, som omfattar områdena (a) formella språk, (b) beräkningsbarhet och (c) komplexitet. Inom dessa områden behandlas centrala begrepp och resultat såsom (a) ändliga automater och reguljära uttryck, kontextfria grammatiker och parsning (syntaxträd, flertydighet), pumpinglemmana för reguljära och kontextfria språk (b) Turing-maskinen som en universell beräkningsmodell, avgörbarhet och relaterade begrepp, Church-Turing-tesen, haltproblemet och dess oavgörbarhet, reduktion (c) tidskomplexitet, klasserna P och NP, polynomtidsreduktion, P=NP-frågan