Kursen behandlar grundläggande abstrakta datatyper, grundläggande algoritmer, komplexitetsanalys, tillämpningsexempel och olika problemlösningsansatser. Under kursen används programspråket C.
Grundläggande abstrakta datatyper som behandlas är bland andra lista, stack, kö, träd, mängd, graf och tabell. 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 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 och man lär sig beskriva resultatet av en sådan analys med hjälp av Ordo-notation. Grundläggande problemlösningsstrategier behandlas, till exempel divide and conquer, brute force, greedy och dynamisk programmering.
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 enkla algoritmer undersöks.
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 grundläggande begrepp relaterade till datastrukturer och algoritmer,
- beskriva vanliga abstrakta datatyper och algoritmer,
- förklara jämlöpande exekvering med delat minne som koncept och med det redogöra för innebörden av synkronisering och trådsäkra datatyper.
Färdighet och förmåga
- formulera lösningar till enkla problem i form av algoritmer inklusive att identifiera och använda lämpliga datatyper,
- implementera lösningen i form av ett program i programspråket C,
- tillämpa dynamisk minnesallokering,
- använda sig av grundläggande problemlösningsstrategier,
- experimentellt och teoretiskt undersöka en mjukvaras tids- och minneskomplexitet, samt redogöra för och dokumentera utfallet enligt givna riktlinjer,
- visa att en komponent i ett program fungerar korrekt med hjälp av testning,
- använda sig av en debugger för att hitta fel i program.
Värdering och förhållningssätt
- visa förståelse för hur struktur-, tids- och minnesaspekter påverkar kvalitet hos program.
Behörighetskrav
Univ: För tillträde till kursen krävs en grundläggande kurs i programmeringsmetodik i programspråket C (tex 5DV104 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.
Speciellt gäller att denna kurs kan ej ingå fullt ut i en examen samtidigt som någon av kurserna Datastrukturer och algoritmer (5DV108, 5DV041, 5DV043) eller Datastrukturer och algoritmer (Python) (5DV128).
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.
