DV1: Datavetenskapens byggstenar, 7,5 hp

Innehåll

Kursen behandlar grundläggande abstrakta datatyper och tillhörande algoritmer, komplexitetsanalys och tillämpningsexempel. Kursen ger också en introduktion till vetenskapligt skrivande och experimentell metodik. Under kursen används programspråket C.

Grundläggande abstrakta datatyper som behandlas är bland andra fält, lista, stack, kö, mängd, tabell och hashtabell. Datatypernas informella och formella specifikationer, generella egenskaper och användningsområden liksom olika implementationsmöjligheter och deras specifika egenskaper behandlas. Vidare behandlas grundläggande algoritmer (till exempel sökning, sortering och traversering) förknippade med dessa abstrakta datatyper, deras komplexitet och karakteristiska egenskaper. Komplexitetsanalys av algoritmer introduceras och studenten lär sig beskriva resultatet av en sådan analys matematiskt. Under kursens gång introduceras studenterna till experimentell metodik och vetenskapligt skrivande och får praktisk erfarenhet av att genomföra ett experiment och avrapportera detta i en skriftlig rapport. Studenterna får också träning att studera vetenskapliga artiklar inom kursens ämnesområde samt muntligt presentera och diskutera sitt arbete med artikeln.

Teoridelarna i kursen tillämpas genom problemlösning (att konstruera algoritmer) och programmering (att överföra algoritmer till källkod i ett programspråk). Färdigheter som testning, felsökning och dokumentation övas. Komplexitet hos algoritmer bestäms .

Kursen består av två moment:
Moment 1, teori, 4.5 högskolepoäng
Moment 2, problemlösning, 3 högskolepoäng

Förväntade studieresultat

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

• förklara begrepp relaterade till datastrukturer, abstrakta datatyper och algoritmer (FSR 1),
• beskriva grundläggande abstrakta datatyper, deras specifikationer, egenskaper samt algoritmer knutna till dessa (FSR2),
• definiera matematiska begrepp relaterade till rums- och tidskomplexitet (FSR 3),

Färdighet och förmåga

• formulera lösningar till enkla problem i form av algoritmer (FSR 4)
• implementera algoritmer och datatyper i programspråket C (FSR 5),
• tillämpa dynamisk minnesallokering i programspråket C (FSR 6),
• tillämpa experimentell metodik för att undersöka rums- och tidskomplexitet (FSR 7),
• teoretiskt undersöka en algoritms rums- och tidskomplexitet, samt redogöra för och dokumentera utfallet skriftligt (FSR 8)
• säkerställa kvaliteten hos ett program genom att systematiskt testa en komponent i ett program (FSR 9),
• använda sig av systematisk felsökning med hjälp av en debugger (FSR 10),
• studera en given artikel inom ämnesområdet och muntligt presentera och diskutera den med andra (FSR 11).

Behörighetskrav

För tillträde till kursen krävs kursen DV0: Komputationellt tänkande (5DV159) samt en grundläggande kurs om minst 7.5hp i programmeringsmetodik i programspråket C (tex 5DV157, 5DV158, 5DV104, 5DV114) eller motsvarande kunskaper.

Undervisningens upplägg

Undervisningen bedrivs i form av föreläsningar, seminarier, arbete i datorlabb och övningar i mindre grupper. Utöver schemalagda aktiviteter krävs även individuellt arbete med materialet. Obligatorisk närvaro krävs på examinerande seminarier.

Examination

Examinationen på Moment 1 (FSR 1-4, 6-8) sker dels genom ett antal mindre digitala delprov samt en skriftlig salstentamen. Antalet delprov beror på deras omfattning men är aldrig mer än fem. Momentet bedöms med något av betygen Väl godkänd (VG), Godkänd (G) eller Underkänd (U). Var och en av de digitala delproven bedöms som avklarad eller ej avklarad. Betyget på momentet utgör en sammanfattande bedömning av resultaten av examinationens olika delar och sätts först när alla delar är bedömda som avklarade. För student som deltagit i examinationen men inte fått samtliga uppgifter bedömda som avklarade vid kursen slut sätts betyget U på momentet.

Moment 2 (FSR 3-11) examineras genom ett antal obligatoriska uppgifter varav minst en uppgift genomförs i seminarieform (och kräver obligatorisk närvaro). Antalet uppgifter beror på deras omfattning men är aldrig mer än fem. På moment 2 ges betygen Underkänd (U) eller Godkänd (G). Var och en av de obligatoriska uppgifterna bedöms som avklarad eller ej avklarad. Betyget på momentet utgör en sammanfattande bedömning av resultaten av examinationens olika delar och sätts först när alla delar är bedömda som avklarade. För student som deltagit i examinationen men inte fått samtliga uppgifter bedömda som avklarade vid kursen slut sätts betyget U på momentet.

På hela kursen ges något av betygen Väl godkänd (VG), Godkänd (G) eller Underkänd (U). För att bli godkänd på hela kursen krävs att samtliga 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.

För studerande som inte godkänns vid ordinarie provtillfälle anordnas ytterligare provtillfälle. Notera att när det gäller examinerande seminarier så anordnas ett "uppsamlingsseminarium" vid anslutning till kursens slut. Om student fortfarande inte blivit godkänd på seminarieuppgiften efter detta tillfälle är nästa möjlighet till komplettering i samband med att kursen ges nästa gång.

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 vid Institutionen för datavetenskap.

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

Denna kurs kan ej ingå fullt ut i en examen samtidigt som någon av kurserna Datastrukturer och algoritmer (5DV108, 5DV041, 5DV043), Datastrukturer och algoritmer (C) (5DV127,5DV149) eller Datastrukturer och algoritmer (Python) (5DV128, 5DV150). Överlappet mellan denna och kurserna uppräknade motsvarar ca 5hp.

Kursens kopplingar till program och examina
Kursen är baskurs på Kandidatprogrammet i datavetenskap.

Om man läst någon av kurserna Datastrukturer och algoritmer (5DV108, 5DV041, 5DV043), Datastrukturer och algoritmer (C) (5DV127,5DV149) eller Datastrukturer och algoritmer (Python) (5DV128, 5DV150) och vill tillgodoräkna de kunskaperna till denna så måste man komplettera med examinerande delar som motsvarar FSR 11 (som saknas helt i kurserna ovan) samt de mindre delproven som ingår i moment 1.