Effektiva algoritmer, 7,5 hp

Innehåll

Kursen behandlar tekniker för att konstruera effektiva algoritmer och typiska datastrukturer som används i dessa. Speciell hänsyn tas till att effektivitet inte bara beror på algoritmens inneboende asymptotiska beteende utan också på de specifika probleminstanser den appliceras på. Standardalgoritmer och -datastrukturer behöver därför ofta väljas ut och anpassas för att lösa problemet så effektivt som möjligt.

Moment 1, Algoritmiska tekniker och datastrukturer, 3 högskolepoäng, behandlar effektiva algoritmiska tekniker (divide-and-conquer, greedy, dynamic programming) deras användningsområden och för- och nackdelar, illustrerar dessa med hjälp av centrala algoritmer, och diskuterar exempel på effektiva datatyper (t.ex. heaps, red-black trees, union-find) och deras implementation.

Moment 2, Problemlösning och algoritmanalys, 4,5 högskolepoäng,
utgörs av att studenten både teoretiskt och empiriskt undersöker varianter av en känd algoritm med avseende på effektivitet och skriver en rapport om detta. Hela kedjan från initiala, vanligen otydligt specificerade frågeställningar till den färdiga algoritmiska lösningen och dess teoretisk och empirisk analys ingår. Momentet tränar studentens förmåga att gå från en otydlig formulerad problemspecifikation till en exakt formulering, ta fram en lämplig algoritmisk lösning, om möjligt förbättra den genom att anpassa den till problemets säregenheter, samt analysera och diskutera dess effektivitet.

Förväntade studieresultat

Kunskap och förståelse
Efter avslutad kurs ska studenten kunna

• förklara och analysera olika avancerade datastrukturer och redogöra för deras för- och nackdelar med avseende på effektivitet (FSR 1)
• kritiskt redogöra för de viktigaste teknikerna för att skapa effektiva algoritmer. (FSR 2)

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

• analysera en algoritm med avseende på effektivitet (FSR 3)
• välja en lämplig algoritmisk teknik för att lösa ett konkret problem (FSR 4)
• anpassa en algoritmisk teknik eller datastruktur till ett specifikt problem för att öka effektiviteten (FSR 5)
• konkretisera ett informellt formulerat problem på ett sätt som gör det möjligt att behandla problemet algoritmiskt. (FSR 6)
• beskriva ett problem och dess effektiva lösning i en skriftlig rapport på ett vetenskapligt sätt. (FSR 7)

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

• vetenskapligt värdera olika problemlösningars för- och nackdelar (FSR 8)
• värdera praktiska resultat kritiskt och jämföra dem med teoretiska förväntningar. (FSR 9)

Behörighetskrav

För behörighet krävs antingen en kandidatexamen i datavetenskap eller minst 90 hp varav minst 60 hp i huvudområdet datavetenskap.

Följande kurser (eller motsvarande) krävs:
- Introduktion till diskret matematik, 7,5 hp
- minst 7,5 hp inom formella språk (t.ex. DV3: Beräkningar och språk eller Datavetenskapens grunder)
- minst 7,5 hp inom datastrukturer och algoritmer

Engelska B/6 och svenska för grundläggande behörighet för högskolestudier om utbildningen ges på svenska.

Undervisningens upplägg

Undervisningen består av tre olika element: Lärarledda lektioner, handledningsmöten där problemställningar och av studenterna föreslagna lösningar eller identifierade problem diskuteras, samt feedback på rapportutkast som lämnas in vid i förväg definierade tillfällen. Utöver schemalagda aktiviteter krävs även individuellt arbete med materialet. Det är studentens ansvar att i tid sätta sig in i materialet och förbereda eventuella frågor för att kunna få lämplig feedback.

Examination

Moment 1 examineras genom ett muntligt prov. På detta moment ges enbart betygen Underkänd (U) eller Godkänd (G).

Moment 2 examineras genom en skriftlig rapport studenten lämnar in på slutet av kursen.

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 delar. Betyget utgör en sammanfattande bedömning av resultaten och sätts först när alla obligatoriska moment är godkända.

För studerande som inte godkänns vid ordinarie provtillfälle anordnas ytterligare provtillfälle. Studerande som godkänts i ett prov får inte undergå förnyat prov för att få ett högre 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.

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. Speciellt gäller att denna kurs inte kan, helt eller delvis, användas i en examen tillsammans med kursen 5DV170 Effektiva algoritmer.

Kursens kopplingar till program och examina
Kursen är baskurs på masterprogrammet i Datavetenskap.
Kursen kan användas som en del i uppfyllandet av kravet på 45 poäng med inriktning mot datalogi (varav minst 37,5 högskolepoäng på avancerad nivå) som krävs för specialiseringen Datalogi inom ramen för en Teknologie masterexamen i datavetenskap.