DV2: Algoritmer och problemlösning, 7,5 hp

Innehåll

Kursen behandlar abstrakta datatyper, algoritmer, en introduktion till formella språk och grammatiker, automatteori samt tillämpningsexempel. Kursen ger också en introduktion och praktiskt arbete med att utforma en frågeställning och utifrån denna formulera kriterier för att bedöma lämpligheten hos en lösning. Studenterna får sedan värdera olika lösningsförslag utifrån dessa kriterier. Under kursen används programspråket C och där introduceras bland annat funktionspekare och hur man använder kommandoradsparametrar.

Abstrakta datatyper som behandlas är bland andra träd, trie, heap, graf 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 förknippade med dessa abstrakta datatyper, deras komplexitet och karakteristiska egenskaper. På kursen gås ett antal problemlösningsstrategier som tex brute force, greedy, divide and conquer och dynamisk programmering igenom.

Kursen ger en introduktion till formella språk och grammatiker där studenterna får arbeta med reguljära och kontextfria språk med hjälp av reguljära uttryck, finita automater och en algoritm för att avgöra medlemsskap i ett språk definierat av en kontextfri grammatik. Under kursen kommer studenterna få praktiskt använda de abstrakta datatyper och algoritmer vi gått igenom för att skapa egna finita automater.

Teoridelarna i kursen tillämpas genom problemlösning (att konstruera algoritmer) och programmering (att överföra algoritmer till källkod i ett programspråk) där ett större programmeringsprojekt kommer behandla formella språk och automater.

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

Förväntade studieresultat

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

• beskriva och använda sig av abstrakta datatyper och algoritmer (FSR 1),
• definiera begreppen alfabet och formellt språk (FSR 2),
• återge och redogöra för grundläggande begrepp och definitioner rörande reguljära språk, kontextfria grammatiker och automater (FSR 3),

Färdighet och förmåga

• förklara hur en given problemlösningsstrategi tillämpas på ett givet problem (FSR 4)
• skriva program i programspråket C som tillämpar funktionspekare och kommandoradsparametrar (FSR5),
• utifrån en beskrivning av ett problem identifiera och formulera en datavetenskaplig frågeställning (FSR 6),
• implementera lösningen på ett problem i form av ett program i programspråket C inklusive att välja en lämplig representation för de ingående abstrakta datatyperna (FSR 7),
• definiera, konstruera och tolka olika representationer av reguljära språk samt översätta mellan dem (FSR 8),
• använda en algoritm för att avgöra medlemskap i ett språk definierat av en kontextfri grammatik (FSR 9),

Värderingsförmåga och förhållningssätt

• utifrån en frågeställning göra relevanta designbeslut under arbetet med att lösa ett problem utifrån sin kunskap om hur struktur-, tids- och rumsaspekter påverkar kvalitet hos program (FSR 10).

Behörighetskrav

För tillträde till kursen krävs kurserna DV1: Datavetenskaps byggstenar (5DV160) och Matematik för datavetare (5MA150) 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-5, 8-9) sker dels genom ett antal mindre elektroniska delprov. Momentet bedöms med något av betygen Godkänd (G) eller Underkänd (U). Var och en av delproven bedöms som avklarad eller ej avklarad. När samtliga delprov är bedömda som avklarade ges betyget G på momentet. För student som deltagit i examinationen men inte fått samtliga delprov bedömda som avklarade vid kursen slut sätts betyget U på momentet.

Moment 2 (FSR 1, 5-7, 9-10) examineras genom ett antal obligatoriska uppgifter varav minst en uppgift genomförs i seminarieform. På Moment 2 ges betygen Väl godkänd (VG), Godkänd (G) eller Underkänd (U). Var och en av de obligatoriska uppgifterna bedöms som avklarad eller ej avklarad samt ges ett övergripande omdöme i form av poäng. Betyget på momentet utgör en sammanfattande bedömning av resultaten av examinationens olika delar och sätts först när alla uppgifter är bedömda som avklarade. Om student deltagit i examination 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ällen. 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

Kursen ersätter den tidigare DV2: Algoritmer och problemlösning  (5DV161), och kan inte tas med i examen tillsammans med den.

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), Datastrukturer och algoritmer (Python) (5DV128, 5DV150), Datavetenskapens grunder (5DV037) eller DV3: Kompilatorns första faser - automater och grammatik (5DV156).

Överlappet mellan denna och en kurs i Datastrukturer och algoritmer (5DV108, 5DV041, 5DV043, 5DV127, 5DV149, 5DV128, 5DV150) motsvarar ca 2.5 hp.

Överlappet mellan denna och kurserna 5DV037 och 5DV156 motsvarar ca 3 hp.

Om man läst en kurs i Datastrukturer och algoritmer (5DV108, 5DV041, 5DV043, 5DV127, 5DV149, 5DV128, 5DV150) och vill tillgodoräkna de kunskaperna till denna så måste man komplettera med examinerande delar som motsvarar FSR 2-3, 6-10.

Om man läst någon av kurserna 5DV037 eller 5DV156 och vill tillgodoräkna de kunskaperna till denna så måste man komplettera med examinerande delar som motsvarar FSR 1,5-7,10.

Har man både läst en kurs i datastrukturer och algoritmer och någon av kurserna 5DV037/5DV156 och vill tillgodoräkna de kunskaperna till denna kurs måste man komplettera med examinerande delar som motsvarar FSR 6 och 10.

Om man har läst kursen 5DV161 DV2: Algoritmer och problemlösning och klarat av Moment 1 där och vill tillgodoräkna det till denna kurs så måste man komplettera med examinerande delar motsvarade FSR4. Moment 2 kan tillgodoräknas utan ytterligare examination.