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.

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, 2.5 högskolepoäng
Moment 2, problemlösning, 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 exemplifiera pumpnings-lemmat för reguljära språk (FSR 3),
• definiera och konstruera kontextfria grammatiker (FSR 4),

Färdighet och förmåga

• använda sig av grundläggande problemlösningsstrategier (FSR 5),
• 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 genom ett antal mindre delprov. Momentet bedöms när samtliga delprov är godkända med något av betygen Godkänd (G) eller Underkänd (U).

Moment 2 (FSR 1-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).

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 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.

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 komplettering i samband med att kursen ges nästa gång.

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
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.

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

Överlappet mellan denna och kurserna i Datastrukturer och algoritmer uppräknade ovan motsvarar ca 2.5 hp. Om man läst någon av dessa kurser och vill tillgodoräkna de kunskaperna till denna så måste man komplettera med examinerande delar som motsvarar FSR 2-4, 6-10.

Överlappet mellan denna och kurserna 5DV037 och 5DV156 uppräknade ovan motsvarar ca 3 hp. Om man läst någon av dessa kurser 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.