Kursen behandlar grundläggande abstrakta datatyper, grundläggande algoritmer, komplexitets¬analys, tillämpningsexempel och olika problemlösningsansatser. Under kursen används program¬språket C och Python.
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, problemlösning, 3 högskolepoäng
Momentet utgörs av ett antal obligatoriska uppgifter. Teori från moment 1 tillämpas genom problemlösning och programmering i ett imperativt språk. Det innebär att studenterna dels tränar sig i att lösa problem men också hur man överför lösta problem (algoritmer) till färdig kod. Färdigheter som testning, felsökning 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
visa förmåga att testa, felsöka och dokumentera program och algoritmer
Behörighetskrav
För tillträde till kursen krävs En grundläggande kurs i programmeringsmetodik (tex 5DV104, 5DV105, 5DV106 eller 5DV114) eller motsvarande kunskaper.
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 (Moment 1, teori) dels genom ett antal obligatoriska uppgifter (Moment 2, problemlösning). Skriftlig tentamen bedöms med något av betygen Med beröm godkänd (5), Icke utan beröm godkänd (4), Godkänd (3), Underkänd (U). På moment 2 ges endast betygen Underkänd (U) eller Godkänd (G).
På hela kursen ges något av betygen Med beröm godkänd (5), Icke utan beröm godkänd (4), Godkänd (3), Underkänd (U). 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.
Studenter som underkänts på Moment 1 vid kursens slut erbjuds ytterligare två provtillfällen under året. För studenter som underkänts på Moment 2 vid kursens slut ges ytterligare ett provtillfälle under året.
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.
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.
Litteratur
Giltig från:
2011 vecka 24
Datatyper och algoritmer Janlert Lars-Erik, Wiberg Torbjörn 2., [rev.] uppl. : Lund : Studentlitteratur : 2000 : x, 387 s. : ISBN: 91-44-01364-7 Obligatorisk Se Umeå UB:s söktjänst
