Kursen behandlar tekniker för att konstruera effektiva algoritmer och typiska datastrukturer som används i dessa. Speciell hänsyn tas till faktumet 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, 4.5 högskolepoäng, behandlar centrala begrepp och resultat kring effektiva algoritmiska tekniker och datastrukturer samt tränar studentens förmåga att använda sig av denna kunskap för 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.
Moment 2, Problemlösning och algoritmanalys, 3 högskolepoäng, utgörs av att studenten, baserat på inlämningsuppgifterna som ingår i Moment 1, skriver en rapport om ett algoritmiskt problem och dess lösning som täcker hela vägen från det initiala, vanligen otydligt specificerade problemet till den färdiga algoritmen och dess analys. Här kan experimentella utvärderingar baserade på implementationer framtagna av studenten ingå.
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
kritiskt redogöra för de viktigaste teknikerna för att skapa effektiva algoritmer.
Färdighet och förmåga Efter avslutad kurs ska studenten kunna
analysera en algoritm med avseende på effektivitet
välja en lämplig algoritmisk teknik för att lösa ett konkret problem
anpassa en algoritmisk teknik eller datastruktur till ett specifikt problem för att öka effektiviteten
konkretisera ett otydligt formulerat problem på ett sätt som gör det möjligt att behandla problemet algoritmiskt.
beskriva ett problem och dess effektiva lösning i en skriftlig rapport på ett vetenskapligt sätt.
Värderingar och förhållningssätt Efter avslutad kurs ska studenten kunna
vetenskapligt värdera olika problemlösningars för- och nackdelar
värdera praktiska resultat kritiskt och jämföra dem med teoretiska förväntningar.
Behörighetskrav
Univ: För tillträde till kursen krävs följande (eller motsvarande): 60 hp i huvudområdet datavetenskap eller 2 års avklarade studier (120hp), i båda fallen inkluderande minst 7.5hp kurser som behandlar diskret matematik (tex Introduktion till diskret matematik) samt minst 7.5hp datastrukturer och algoritmer (tex Datastrukturer och algoritmer (C), eller DV2: Algoritmer och problemlösning).
Engelska A/5 och svenska för grundläggande behörighet för högskolestudier (om kursen ges på svenska).
Undervisningens upplägg
Undervisningen bedrivs i dels i form av lärarledda lektioner och gruppdiskussioner där studenterna diskuterar (utkast till) problemlösningar de har arbetat fram. Utöver schemalagda aktiviteter krävs även individuellt arbete med materialet och med inlämningsuppgifter där mindre implementationer och datorexperiment kan ingå.
Examination
Moment 1 examineras genom obligatoriska inlämningsuppgifter samt deltagande i grupparbeten. På detta moment ges enbart betygen Underkänd (U) eller Godkänd (G).
Moment 2 examineras genom en rapport studenten lämnar in på slutet av kursen och som helt eller delvis baseras på inlämningsuppgifterna från Moment 1. 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. Notera att när det gäller examinerande grupparbeten så anordnas ett "uppsamlingsgrupparbete" vid anslutning till kursens slut. Om student fortfarande inte blivit godkänd på grupparbetsuppgiften efter detta tillfälle är nästa möjlighet till komplettering i samband med att kursen ges nästa gång.
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.
Litteratur
Litteraturlistan är inte tillgänglig via den webbaserade utbildningskatalogen.
Kontakta aktuell institution.
