Hoppa direkt till innehållet

Information till studenter och medarbetare med anledning av covid-19 (Uppdaterad: 15 april 2021)

printicon
Kursplan:

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

Engelskt namn: CS2: Algorithms and problemsolving

Denna kursplan gäller: 2018-01-01 och tillsvidare

Kurskod: 5DV204

Högskolepoäng: 7,5

Utbildningsnivå: Grundnivå

Huvudområden och successiv fördjupning: Datavetenskap: Grundnivå, har mindre än 60 hp kurs/er på grundnivå som förkunskapskrav

Betygsskala: För denna kurs ges betygen VG Väl godkänd, G Godkänd, U Underkänd

Ansvarig institution: Institutionen för datavetenskap

Beslutad av: Teknisk-naturvetenskapliga fakultetsnämnden, 2017-09-29

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 och graf. 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 språk med hjälp av reguljära uttryck och finita automater. 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 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),
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 9).

Behörighetskrav

För tillträde till kursen krävs kurserna DV1: Datavetenskaps byggstenar (5DV160) och Algebra och analys för datavetare (5MA186) 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) sker genom ett antal mindre digitala delprov. Antalet delprov beror på deras omfattning men är aldrig mer än fem. 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 (med obligatorisk närvaro). Antalet uppgifter beror på deras omfattning men är aldrig mer än fem. 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 de tidigare kurserna DV2: Algoritmer och problemlösning  (5DV161 eller 5DV169), och kan inte tas med i examen tillsammans med dessa. Överlappet mellan dessa kurser och denna är 7.5hp.

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.

Om man har läst kursen 5DV169 DV2: Algoritmer och problemlösning och klarat av Moment 1 eller Moment 2 där så kan detta tillgodoräknas till denna kurs utan ytterligare examination.

Litteratur

  • Giltig från: 2019 vecka 4

    Datatyper och algoritmer
    Janlert Lars-Erik, Wiberg Torbjörn
    2., [rev.] uppl. : Lund : Studentlitteratur : 2000 : x, 387 s. :
    ISBN: 91-44-01364-7
    Obligatorisk
    Se bibliotekets söktjänst

    Linz Peter
    Introduction to formal languages and automata
    Jones And Bartlett Publishers : 2016 : 450 sidor :
    ISBN: 9781284077247
    Se bibliotekets söktjänst

  • Giltig från: 2019 vecka 3

    Datatyper och algoritmer
    Janlert Lars-Erik, Wiberg Torbjörn
    2., [rev.] uppl. : Lund : Studentlitteratur : 2000 : x, 387 s. :
    ISBN: 91-44-01364-7
    Obligatorisk
    Se bibliotekets söktjänst

    Linz Peter
    An introduction to formal languages and automata
    5th ed. : Sudbury, MA : Jones & Bartlett Learning : c2012 : xiii, 437 p. :
    ISBN: 978-1-4496-3739-2 (hft.)
    Se bibliotekets söktjänst
    Läsanvisning: 6:e upplagan med ISBN 9781284077247 fungerar också bra.

  • Giltig från: 2019 vecka 1

    Datatyper och algoritmer
    Janlert Lars-Erik, Wiberg Torbjörn
    2., [rev.] uppl. : Lund : Studentlitteratur : 2000 : x, 387 s. :
    ISBN: 91-44-01364-7
    Obligatorisk
    Se bibliotekets söktjänst

    Linz Peter
    An introduction to formal languages and automata
    5th ed. : Sudbury, MA : Jones & Bartlett Learning : c2012 : xiii, 437 p. :
    ISBN: 978-1-4496-3739-2 (hft.)
    Se bibliotekets söktjänst

  • Giltig från: 2018 vecka 1

    Datatyper och algoritmer
    Janlert Lars-Erik, Wiberg Torbjörn
    2., [rev.] uppl. : Lund : Studentlitteratur : 2000 : x, 387 s. :
    ISBN: 91-44-01364-7
    Obligatorisk
    Se bibliotekets söktjänst

    Sipser Michael
    Introduction to the theory of computation
    Third edition. : Australia : Cengage Learning : [2012?] : xxii, 458 pages :
    ISBN: 9781133187813 (paperback) :
    Obligatorisk
    Se bibliotekets söktjänst