Effektiva algoritmer och problemkomplexitet, 7,5 hp

Innehåll

Moment 1, 4,5 högskolepoäng, behandlar centrala begrepp och resultat kring effektiva algoritmiska tekniker å ena sidan och problemkomplexitet å andra sidan. Algoritmiska tekniker som behandlas omfattar divide-and-conquer, greedy methods och dynamic programming samt deras analys med avseende på effektivitet. I samband med begreppet problemkomplexitet diskuteras i första hand klasserna P och NP samt reduktion och NP-fullständighet. Kursens huvudfokus ligger på värsta-fall-analyser och algoritmernas tidseffektivitet, men även genomsnittlig effektivitet och algoritmers eller problems krav på minnesutrymme diskuteras kortfattat.

Moment 2, 3 högskolepoäng, består av ett antal påbyggnadsområden som studenten får välja emellan. Utbudet av dessa områden kan variera. Typiska exempel omfattar
* analys av konkreta program med hjälp av så kallad profiling software,
* effektiva algoritmer och problemkomplexitet inom området Automater och formella språk,
* effektiva parallella algoritmer och relaterade komplexitetsklasser.

Förväntade studieresultat

Efter avslutad kurs ska studenten kunna
* förklara centrala algoritmiska tekniker såsom divide-and-conquer, greedy methods och dynamic programming, analysera dem med avseende på effektivitet och redogöra för typiska problem de kan appliceras på
* redogöra för, diskutera och exemplifiera klasserna P och NP samt begreppen tidskomplexitet, reduktion och NP-fullständighet
* diskutera skillnaden mellan värsta och genomsnittliga fall och mellan komplexitetsmåtten tids- och minnesutrymme
* visa förmåga att självständigt både fördjupa och bredda sina kunskaper genom att läsa in sig i ett relaterat område som inte tas upp på föreläsningarna.

Behörighetskrav

Univ:För tillträde till kursen krävs 60 hp i huvudområdet datavetenskap eller 2 års avklarade studier, i båda fallen inkluderande kurserna Introduktion till diskret matematik (5MA008), Datastrukturer och Algoritmer (5DV108, 5DV127, 5DV128), Datavetenskapens grunder (5DV037) samt antingen Grundläggande analys (5MA016) eller Envariabelanalys 2 (5MA011) eller motsvarande kunskaper. Engelska A och svenska för grundläggande behörighet för högskolestudier (om kursen ges på svenska).

Undervisningens upplägg

Moment 1: Undervisningen bedrivs i form av föreläsningar som även innehåller schemalagda tider för frågor och återkoppling mellan lärare och studenter. Utöver schemalagda aktiviteter krävs även individuellt arbete med materialet.

Moment 2: Undervisningen bedrivs i form av självstudier där studenten arbetar med litteraturen eller material och uppgifter som ställs till förfogande via internet. Studenten får även tillgång till handledning.

Examination

Båda moment examineras genom obligatoriska inlämningsuppgifter. På Moment 1 ges enbart betygen Underkänd (U) eller Godkänd (G). På Moment 2 och 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). För att bli godkänd på hela kursen krävs minst betyget Godkänd på samtliga obligatoriska inlämningsuppgifter. Betyget utgör en sammanfattande bedömning av resultaten och sätts först när alla obligatoriska moment är godkända. Studerande som godkänts i ett prov får inte undergå förnyat prov för att få ett högre betyg.

För studerande som inte godkänns vid ordinarie provtillfälle anordnas ytterligare provtillfälle. 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 vid Institutionen för datavetenskap.

TILLGODORÄKNANDE
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.

Speciellt gäller att denna kurs kan ej ingå fullt ut i en examen samtidigt som någon av kurserna Algoritmanalys (5DV022), Komplexitetsteori (5DV018) eller Formella språk (5DV023)

Tillgodoräknande av studier prövas individuellt (se universitetets regelsamling och tillgodoräknandeordning). Ansökan om tillgodoräknande görs på speciell blankett och ställs till den Teknisk-naturvetenskapliga fakultetsnämnden, Umeå universitet.