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: 17 850 kr.
Total studieavgift: 17 850 kr.
Anmälnings- och studieavgifter
Anmälningskod
UMU-57301
Anmälan
Sista anmälningsdag var den
15 oktober 2024.
Du kan göra en sen anmälan
via Antagning.se.
