Beräkningskomplexitet 7,5 hp

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.

Modul 1, Koncept, resultat och bevis, 3 hp, introducerar och diskuterar begrepp, resultat och bevismetoder enligt innehållsbeskrivningen ovan i lärarledda lektioner. Varje lektion är kopplad till ett eller flera avsnitt i kursboken. Lektionen ger en introduktion till innehållet utan att ge sig in på detaljer. Målet är att göra det lättare för studenten att fördjupa sig i respektive avsnitt genom eget arbete.

Modul 2, Fördjupning, reflexion och diskussion, 4,5 hp, består av eget arbete och studentledda diskussioner av materialet. utgörs av att studenten, efter att läraren introducerat ett tema, läser motsvarande avsnitt i kursboken och förbereder en enkel presentation av materialet som kan användas för att diskutera det med klasskamraterna. En sammanfattning av de väsentliga punkterna lämnas in skriftligt inför nästa lektion (ungefär en sida). Inlämningen ska i synnerhet ta upp aspekter studenten inte lyckades förstå eller är osäker på och även tankar kring eventuella övningsuppgifter specificerade av läraren. Studenter blir sedan i slumpmässig ordning utvalda för att presentera materialet baserat på den egna förståelsen och leda diskussionen med resten av klassen. Varje student behöver presentera minst en gång.

Visa kursplan

Anmäl dig

HT2025
- Beräkningskomplexitet
  
  HT2025 / Umeå / Engelska / På plats
  
  Gör en sen anmälan
  
  Visa mer Visa mindre
  
  Startar
  3 november 2025
  
  Slutar
  18 januari 2026
  
  Omfattning
  7,5 hp
  
  Undervisning
  På plats
  
  Studietakt
  50%
  
  Undervisningstid
  Dagtid
  
  Studieort
  Umeå
  
  Undervisningsspråk
  Engelska
  
  Anmälningskod
  UMU-57234
  
  Behörighet Minst 90 hp varav 60 hp datavetenskap. Minst 7,5 hp diskret matematik; 7,5 hp datastrukturer och algoritmer; 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)
  
  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älan
  Sista anmälningsdag var den 15 april 2025. Du kan göra en sen anmälan via Antagning.se.

Anmäl dig via antagning.se
Du anmäler dig till våra program och kurser på antagning.se. Där kan du sedan följa din anmälan och kontrollera att dina meriter registrerats. Det är även där du loggar in för att svara på ditt antagningsbesked.

Sen anmälan
Efter sista anmälningsdag stänger anmälan till alla utbildningar. De kurser och program som har platser kvar kan vara öppna för sen anmälan. Dessa utbildningar är då märkta ”Öppen för sen anmälan” på antagning.se.

Mer om anmälan och antagning

Lär känna Umeå universitet

Här finns utbildningar av hög kvalitet och forskning inom alla vetenskapsområden och det konstnärliga området. Gemensamt för alla våra utbildningar är hög kompetens bland lärarna och ett tätt samspel mellan forskning, utbildning, samverkan och innovation.

Flest pedagogiskt meriterade lärare i Sverige

Priset går till lärare som verkligen engagerar sig, använder uppskattade metoder eller inspirerar.
Ett universitet där hälsa får ta plats

Umeå universitet är certifierat som ett Healthy Campus med många initiativ och aktiviteter som främjar hälsa.

Frågor om utbildningen?

Kontakta oss

Rubrik

Beskriv ditt ärende eller ställ en fråga

Förnamn

Efternamn

E-postadress

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).