"False"
Hoppa direkt till innehållet
printicon
Huvudmenyn dold.

Beräkningskomplexitet

  • Antal högskolepoäng 7,5 hp
  • Nivå Avancerad nivå
  • Starttid Hösttermin 2023

Om kursen

Vissa algoritmer löser ett beräkningsproblem effektivare än andra. En viktig aspekt av datavetarens jobb är att hitta effektiva sätt att lösa ett givet problem. Ibland lyckas man väl med det, ibland inte. Men hur vet man om det i det senare fallet beror på ens egen oförmåga eller ligger i problemets natur, dvs om problemet överhuvud taget går att lösa effektivt? Varje problem har en inneboende beräkningskomplexitet som avgör om och i så fall hur effektivt det kan lösas. Detta leder till en kategorisering av problem i olika klasser med avseende på deras inneboende komplexitet. Att förstå sig på detta är viktigt eftersom det visar vilken effektivitet man rimligen kan förvänta sig, vilket å ena sidan leder till effektivare algoritmer i den utsträckning det är möjligt och å andra sidan förhindrar att energi läggs ner på att försöka åstadkomma det omöjliga.

Kursen behandlar och formaliserar denna inneboende komplexitet hos beräkningsproblem, som resulterar i kategoriseringen av problem i olika komplexitetsklasser, kända och okända samband mellan dessa klasser samt begreppet av fullständiga problem. Följande aspekter behandlas: Formalisering av beräkningskomplexitet (främst med avseende på tid och minnesutrymme) och dess praktiska betydelse, "speedup"-teoremet och den utvidgade Church-Turing-tesen, deterministiska och icke deterministiska komplexitetsklasser (främst (N)TIME(f(n)), (N)SPACE(f(n), P, NP, (N)EXPTIME, L, NL, PSPACE; komplementklasser till dessa) och vad man vet eller inte vet om deras inbördes relation, reduktion av ett problem till ett annat, fullständighet.

Anmälan och behörighet

Beräkningskomplexitet, 7,5 hp

Visa tillfällen för föregående termin Hösttermin 2023 Det finns inga senare terminer för kursen

Startar

31 oktober 2023

Slutar

14 januari 2024

Studieort

Umeå

Undervisningsspråk

Engelska

Studieform

Dagtid, 50%

Behörighetskrav

Minst 90 hp varav 60 hp datavetenskap. Minst 7,5 hp diskret matematik; 7,5 hp datastrukturer och algoritmer; 7,5 hp avancerade datastrukturer och algoritmer (t.ex. 5DV182); och 7,5 hp formella språk. Engelska för grundläggande behörighet för högskolestudier.

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-57234

Anmälan

Du kan inte anmäla dig ännu. Anmälan öppnar 15 mars 2023 klockan 13:00. Sista anmälningsdag är den 17 april 2023.

Kontaktformulär

Kontaktformulär

Tänk på att universitetet är en statlig myndighet och att det du skriver här kan bli en allmän handling. Var därför försiktig med att skriva känsliga eller personliga frågor här i kontaktformuläret. Alla uppgifter behandlas enligt dataskyddsförordningen (GDPR)