Datastrukturer och algoritmer (C), 7,5 hp

Innehåll

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ä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 filhantering och 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.
• 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.

Övriga föreskrifter

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), Datastrukturer och algoritmer (C) (5DV127) eller Datastrukturer och algoritmer (Python) (5DV128, 5DV150).

Tillgodoräknande av studier prövas individuellt (se http://www.umu.se/utbildning/antagning/tillgodoraknande/).

Denna kurs ersätter kursen 5DV127 Datastrukturer och algoritmer (C)  som läggs ned. Under 2014 och 2015 gäller detta för studenter som gått 5DV127 men inte klarat den:

• Om man inte klarat något av momenten på 5DV127 rekommenderar vi att man istället registrerar sig på denna kurs och examineras på denna i sin helhet.
• Om man klarat ett av momenten på 5DV127 kan man examineras på det andra momentet genom att delta i motsvarande moment på denna kurs.
• Om man vill kan man också tillgodoräkna sig avklarade moment från 5DV127 till denna kurs. Ansökan om detta sker via http://www.umu.se/utbildning/antagning/tillgodoraknande/.