Beräkningskomplexitet, 7,5 hp

Innehåll

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, Koncept, resultat och bevis, 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, Fördjupning, reflexion och diskussion, 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.
 

Förväntade studieresultat

Kunskap och förståelse
Efter avslutad kurs ska studenten med matematisk noggrannhet kunna definiera, förklara och diskutera

• begreppet beräkningskomplexitet med avseende på exekveringstid, minnesutrymme och sambanden mellan dem (FSR 1)
• de mest centrala komplexitetsklasserna samt hur de är relaterade (FSR 2)
• de viktigaste öppna problem gällande sambanden mellan dessa komplexitetsklasser (FSR 3)
• återkommande metoder som används för att bevisa samband mellan komplexitetsklasser, i synnerhet ”nåbarhetsmetoden”, eller specifika problem, i synnerhet reduktioner mellan problem (FSR 4).

Färdighet och förmåga
Efter avslutad kurs ska studenten kunna

• självständigt läsa en matematisk-formell text (kursboken) samt presentera den för andra och diskutera både den vunna kunskapen och eventuella svårigheter (FSR 5)
• med matematisk noggrannhet resonera kring innebörd, formalisering och användning av begreppen beräkningsproblem, beräkningskomplexitet, fullständighet och sambanden mellan dem (FSR 6)
• utifrån givna exempel ta fram och skriftligt formulera liknande reduktioner mellan problem samt använda sig av dessa för att bevisa ett givet problems fullständighet för en given komplexitetsklass (FSR 7).

Värderingar och förhållningssätt
Efter avslutad kurs ska studenten kunna

• kritiskt och på ett kunskapsbaserat sätt muntligt diskutera de teoretiska resultatens praktiska betydelse och begränsningar med personer på samma kunskapsnivå (FSR 8).

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.

Undervisningens upplägg

Undervisningen sker som beskrivet under innehåll och består av både lärarledda lektioner och studentledda presentationer och diskussioner av materialet.
 

Examination

Moment 1 (FSR 1-4, 6-8) examineras genom en skriftlig tentamen. På detta moment ges något av betygen Underkänd (U), Godkänd (3), Icke utan beröm godkänd (4) eller Med beröm godkänd (5). För studerande som inte godkänns vid ordinarie provtillfälle anordnas ytterligare provtillfällen.

Moment 2 (FSR 1-8) examineras genom studentens inlämnade sammanfattningar och presentationer. På Moment 2 ges något av betygen Underkänd (U) eller Godkänd (G). För betyget G krävs att samtliga utom max 3 sammanfattningar lämnas in i tid och får omdömet avklarad, och att samtliga presentationer studenten ger blir bedömda som avklarade. Antalet sammanfattningar som skrivs under kursen beror på deras omfattning och är normalt 12 och aldrig mer än 14.

För att en sammanfattning eller presentation ska bedömas som avklarad ska den tydligt visa att studenten har ägnat sig åt innehållet och med viss framgång reflekterat över både det och sin egen nivå av förståelse. Förutsättningen för omdömet avklarad är därmed inte att studenten redan vid det tillfället har lyckats visa en korrekt förståelse av hela det diskuterade innehållet. Det ska dock bli tydligt att materialet har behandlats och reflekterats på en för en avancerad kurs lämplig nivå.

En student som vid ordinarie provtillfälle får betyget U på Moment 2 kan vid ett senare tillfälle efter kursens slut komplettera momentet. Detta sker genom att på ett noggrant sätt behandla samtliga deluppgifter som fick betyget "Ej avklarad" och lämna in en skriftlig redogörelse. I det här fallet ställs alltså högre krav på fullständighet och korrekthet än vid ordinarie provtillfället. Detta eftersom studenten måste kompensera examinationen av den efterföljande diskussion som ingår i ordinarie examination. Om en student varit helt inaktiv på moment 2 under kursens gång får denne inte komplettera utan få istället delta i examinationen vid nästa kurstillfälle.Detta eftersom studenten inte deltagit i en enda diskussion under kursens gång och därmed inte kan uppfylla FSR 8 genom att skriva rapporter på papper.
 
För att bli godkänd på hela kursen krävs minst betyget Godkänd på båda momenten. På kursen i sin helhet ges något av betygen Underkänd (U), Godkänd (3), Icke utan beröm godkänd (4) eller Med beröm godkänd (5). Betyget, som utgör en sammanfattande bedömning av resultaten och som därmed först sätts när alla obligatoriska moment är godkända, styrs i normalfallet av betyget på Moment 1. Om betyget ligger strax under gränsen till ett högre betyg kan dock en särskild bra prestation på Moment 2 motivera ett höjt betyg.

En student som utan godkänt resultat har genomgått två prov för en kurs eller en del av en kurs, har rätt att få en annan examinator utsedd, om inte särskilda skäl talar emot det (HF 6 kap. 22 §). Begäran om ny examinator ställs till prefekten för Institutionen för datavetenskap.

Den som godkänts i ett prov får ej undergå förnyat prov för högre betyg.

Examination baserad på denna kursplan garanteras under två år efter studentens förstagångsregistrering på kursen. Detta gäller även om kursen lagts ned och denna kursplan upphört gälla.

TILLGODORÄKNANDE
Student har rätt att få prövat om tidigare utbildning eller motsvarande kunskaper och färdigheter förvärvade i yrkesverksamhet kan tillgodoräknas för motsvarande utbildning vid Umeå universitet. Ansökan om tillgodoräknande skickas in till Studentcentrum/Examina. Mer information om tillgodoräknande finns på Umeå universitets studentwebb, www.student.umu.se, och i högskoleförordningen (6 kap). Ett avslag på ansökan om tillgodoräknande kan överklagas (Högskoleförordningen 12 kap) till Överklagandenämnden för högskolan. Detta gäller såväl om hela som delar av ansökan om tillgodoräknande avslås.

Övriga föreskrifter

I en examen får denna kurs ej ingå, helt eller delvis, samtidigt med en annan kurs med likartat innehåll. Vid tveksamheter bör den studerande rådfråga studievägledare vid Institutionen för datavetenskap och/eller programansvarig för sitt program.