Information till medarbetare med anledning av covid-19 (Uppdaterad: 29 oktober 2020)

Hoppa direkt till innehållet
printicon

Beräkningskomplexitet

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

Antagen till kursen

Här hittar du allt du behöver veta innan kursen startar.

Om kursen

Som studenten har lärt sig på kursen Effektiva algoritmer löser vissa algoritmer 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.

Moment 1, Begrepp och teorier, 3 högskolepoäng, 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.

Moment 2, Seminarer och reflektioner, 4,5 högskolepoäng, består av eget arbete och studentledda diskussioner av materialet. Momentet 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.

Anmälan och behörighet

Beräkningskomplexitet, 7,5 hp

Det finns inga tidigare terminer för kursen Hösttermin 2020 Det finns inga senare terminer för kursen

Startar

2 november 2020

Slutar

17 januari 2021

Studieort

Umeå

Undervisningsspråk

Engelska

Studieform

Dagtid, 50%

Behörighetskrav

Univ:För tillträde till kursen krävs 90 hp avklarade studier varav 60 hp i huvudområdet datavetenskap eller minst 2 års avklarade studier (120hp) inom ett studieprogram, i båda fallen inkluderande kursen Effektiva algoritmer (7.5hp) eller motsvarande.

Svenska för grundläggande behörighet för högskolestudier samt Engelska A/5. Krav på svenska gäller endast om utbildningen ges på svenska.

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.

Anmälningskod

UMU-57234

Anmälan

Sista anmälningsdag var den 15 april 2020. Du kan göra en sen anmälan via Antagning.se.

Studieavgifter

Anmälnings- och studieavgifter krävs för dig som inte har medborgarskap i EU, EES-länderna eller Schweiz. Läs mer på antagning.se

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)

Kontaktperson för kursen är:
Studentexpeditionen på datavetenskap