Kursen behandlar grundläggande abstrakta datatyper, grundläggande algoritmer, komplexitetsanalys, tillämpningsexempel och olika problemlösningsansatser. Under kursen används programspråket Java.
Moment 1, teori, 4.5 högskolepoäng
Momentet behandlar grundläggande abstrakta datatyper såsom lista, stack, kö, träd, mängd, graf och tabell. Det behandlas deras informella och formella specifikationer, generella egenskaper och användningsområden liksom olika implementationsmöjligheter och deras specifika egenskaper. Vidare behandlas grundläggande algoritmer förknippade med olika abstrakta datatyper, deras komplexitet och karakteristiska egenskaper för typiska problem (till exempel sökning, sortering och traversering). Komplexitetsanalys av algoritmer introduceras (Ordo-notationen). Grundläggande problemlösningsstrategier diskuteras som till exempel divide and conquer, brute force, greedy och dynamisk programmering.
Moment 2, färdighetsträning, 3 högskolepoäng
Momentet utgörs av ett antal obligatoriska uppgifter. Teori från moment 1 tillämpas under grundläggande färdighetsträning: val, konstruktion och användande av datastrukturer och algoritmer vid programmering i ett objektorienterat språk. Färdigheter som (delar av) projektplanering, testning, debuggning och dokumentation övas. Komplexitet av enkla algoritmer undersökes.
Förväntade studieresultat
Efter avslutad kurs ska studenten kunna:
redogöra för grundläggande begrepp relaterade till datastrukturer och algoritmer
redogöra för organisation och specifikation för grundläggande abstrakta datatyper såsom lista, stack, kö, träd, mängd, graf och tabell
redogöra för grundläggande algoritmer, deras komplexitet och karakteristiska egenskaper
välja lämpliga datatyper och algoritmer för ett givet problem
välja och utföra lämpliga implementationer (konstruktioner) av de valda datatyperna och algoritmerna
analysera enklare algoritmer praktiskt och teoretiskt med avseende på prestanda
använda sig av grundläggande problemlösningsstrategier (som till exempel divide and conquer, brute force, greedy och dynamisk programmering) på nya problem
tillämpa de teoretiska kunskaperna och objektorienteringsparadigmen praktiskt på ett programmeringsprojekt, dvs. konstruera en komplett programvara inklusive dokumentation (med systembeskrivning och webbaserad API) utifrån givna riktlinjer
utforma en enkel arbetsplan för ett programmeringsprojekt som utförs i grupp samt dokumentera, följa upp och skriftligt utvärdera den gjorda planeringen.
Behörighetskrav
Univ: För tillträde till kursen krävs kurserna Objektorienterad programmeringsmetodik (5DV081) eller Objektorienterad programmeringsmetodik för Öppen ingång (5DV090) eller motsvarande kunskaper.
Dessutom är det en stark rekommendation att man läst Diskret matematik (5MA008).
Undervisningens upplägg
Undervisningen bedrivs i form av föreläsningar, arbete i datorlabb och övningar i mindre grupper. Utöver schemalagda aktiviteter krävs även individuellt arbete med materialet.
Examination
Examinationen sker dels genom skriftlig tentamen (på moment 1) dels genom ett antal obligatoriska uppgifter (på moment 2). På moment 1 sätts något av betygen Underkänd (U), Godkänd (3), Icke utan beröm godkänd (4) eller Med beröm godkänd (5). På moment 2 ges endast betygen Underkänd (U) eller Godkänd (G). På hela kursen 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 att samtliga prov och obligatoriska moment är godkända. Betyget utgör en sammanfattande bedömning av resultaten vid examinationens olika delar 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 styrelsen för 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.
Litteratur
Giltig från:
2009 vecka 4
Datatyper och algoritmer Janlert Lars-Erik, Wiberg Torbjörn 2., [rev.] uppl. : Lund : Studentlitteratur : 2000 : x, 387 s. : ISBN: 91-44-01364-7 Se Umeå UB:s söktjänst
