Moment 1, teoridel, 4.5 högskolepoäng
Kursens mål är att ge förtrogenhet med programbyggnadskonstens grundläggande verktyg, material och konstruktioner. Detta inbegriper grundläggande abstrakta datatyper, grundläggande algoritmer, komplexitetsanalys, tillämpningsexempel och olika programmeringsansatser. Under kursen används programspråket C.
Moment behandlar abstrakta datatyper såsom lista, stack, kö, träd, mängd, graf och tabell samt deras informella och formella karakteriseringar, egenskaper och användningsområden. Några tillämpningsexempel, olika implementationsmöjligheter och deras egenskaper ingår i kursen. Dessutom behandlas grundläggande algoritmer, deras komplexitet och karakteristiska egenskaper för typiska problem (till exempel sökning, sortering och traversering) förknippade med olika abstrakta datatyper.
Den objektorienterade programmeringsansatsen introduceras och relationen mellan datatyper och klasser förklaras. Komplexitetsanalys introduceras.
Moment 2, laborationsdelt, 3 högskolepoäng
Delmomentet utgörs av en laborationskurs med ett antal obligatoriska inlämningsuppgifter.
Förväntade studieresultat
Efter avslutad kurs ska studenten:
- känna till grundläggande begrepp relaterade till datastrukturer och algoritmer
- känna till grundläggande abstrakta datatyper såsom lista, stack, kö, träd, mängd, graf och tabell
- kunna välja lämpliga datatyper för ett givet problem
- kunna välja implementation av datatyper
- känna till grundläggande algoritmer, deras komplexitet och karakteristiska egenskaper för typiska problem
- kunna analysera algoritmer praktiskt och teoretiskt med avseende på prestanda
- kunna använda sig av grundläggande problemlösningsstrategier, som till exempel divide and conquer, brute force, greedy, dynamisk programmering, på nya problem
- kunna dokumentera algoritmer och datatyper på ett struktuerat sätt
Behörighetskrav
Univ:För tillträde till kursen krävs, förutom grundläggande behörighet, kurserna Programmeringsteknik för ingenjörer (5DV042), Grundläggande analys (5MA016) och Grundläggande linjär algebra (5MA017) 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 en skriftlig tentamen dels genom ett laborationsmoment. På en skriftlig tentamen 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å laborationsmomentet 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.
För studerande som inte godkänns vid ordinarie provtillfälle anordnas ytterligare provtillfälle.
Studerande som två gånger underkänts i prov, har rätt att hos styrelsen för institutionen för datavetenskap begära att annan lärare utses för att sätta betyg på honom/henne. Den som godkänts i ett prov får ej undergå förnyat prov för högre betyg
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 35
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
