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
För behörighet krävs följande kurser (eller motsvarande): - Introduktion till diskret matematik, 7,5 hp - Datastrukturer och algoritmer, 7,5 hp
Urval
Högskolepoäng avklarade per sista anmälningsdag (för utbildning på grundnivå 1-165 hp, för avancerad nivå 30-285 hp)
Sökande inom vissa program vid Umeå universitet har platsgaranti till denna kurs. Antalet platser för fristående kurs kan därför bli begränsat.
Studieavgift
Gäller endast medborgare utanför EU, ESS och Schweiz.
Anmälningsavgift: 900 kr.
Studieavgift, första inbetalningen: 19 038 kr.
Total studieavgift: 19 038 kr.
Anmälnings- och studieavgifter
Anmälningskod
UMU-57301
Anmälan
Du kan inte anmäla dig ännu. Anmälan öppnar 15 september 2025 klockan 09:00.
Sista anmälningsdag är den
15 oktober 2025.
