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
Du kan inte anmäla dig ännu. Anmälan öppnar 16 september 2024 klockan 13:00.
Sista anmälningsdag är den
15 oktober 2024.
