Kursplan - Datastrukturer och algoritmer, fortsättningskurs
Omfattning
7.5 hp
Kurskod
DVA246
Giltig från
Hösttermin 2020
Utbildningsnivå
Grundnivå
Successiv fördjupning
G1F (Grundnivå, har mindre än 60 hp kurs/er på grundnivå som förkunskapskrav).
Huvudområde(n)
Datavetenskap
Akademi
Akademin för innovation, design och teknik
Fastställd
2020-01-24
Litteraturlistor
Kurslitteraturen är preliminär till 8 veckor innan kursstart. Kurslitteratur kan vara giltig över flera terminer.
-
Böcker
Introduction to algorithms
3. ed. : Cambridge, Mass. : MIT Press, cop 2009 - xix, 1292 s.
ISBN: 9780262033848 LIBRIS-ID: 11571492
Syfte
Kursen ger en fördjupad inblick i vanliga datastrukturer med tillhörande algoritmer och några utvalda viktiga algoritmklasser. Därtill ger kursen fördjupade kunskaper om metoder för analys av algoritmers komplexitet och introducerar begreppet komplexitetsklasser. Tillsammans ger detta en god grund för att lösa mer avancerade problem genom att kombinera användandet av existerande datastrukturer och algoritmer och att skapa egna. Dessutom ger kursen den viktiga förmågan att känna igen fundamentalt svåra problem.
Lärandemål
Efter avslutad kurs ska studenten kunna:
1. förstå och använda grundläggande datastrukturer med tillhörande algoritmer, bland annat prioritetsköer, balanserade sökträd och grafer,
2. förstå, använda och utveckla algoritmer av olika typ såsom giriga algoritmer, divide and conquer algoritmer och dynamisk programmering,
3. göra välgrundade val mellan olika datastrukturer och algoritmer för olika tillämpningar,
4. analysera algoritmers effektivitet och identifiera deras komplexitet,
5. redogöra för olika komplexitetsklasser och förklara deras egenskaper.
Innehåll
Kursen innehåller tre relaterade spår:
1. Datastrukturer och algoritmer: prioritetsköer, heapar, balanserade sökträd och grafer med tillhörande grundläggande algoritmer.
2. Algoritmdesign: giriga algoritmer, divide and conquer samt dynamisk programmering.
3. Algoritmanalys: komplexitetsanalys av rekursiva funktioner, komplexitetsklasser, relation mellan P, NP och NPC.
Särskild behörighet
Datastrukturer, algoritmer och programkonstruktion 7,5 hp, Objektorienterad programmering, 7,5 hp samt Diskret matematik, 7,5 hp eller motsvarande.
Examination
Laboration (LAB1), Laborationsserie som kontinuerligt redovisas enligt instruktioner, 4 hp, examinerar lärandemål 1-3, betyg Underkänd (U) eller Godkänd (G)
Tentamen (TEN1), Salstentamen, 3,5 hp, examinerar lärandemål 1-5, betyg Underkänd (U), 3, 4 eller 5
En student som har ett intyg från MDU avseende sin funktionsnedsättning har möjlighet att anmäla önskemål om anpassning vid salstentamina eller annan examinationsform i enlighet med Regler och anvisningar för examination på grundnivå och avancerad nivå vid Mälardalens högskola (2020/1655). Det är examinator som, utifrån det intyg som utfärdats, beslutar om eventuell anpassning och i så fall vilken anpassning som ska gälla.
Misstankar om vilseledande vid examination (fusk) anmäls, enligt högskoleförordningen, till universitetets rektor och prövas av universitetets disciplinnämnd. Om disciplinnämnden anser att en student gjort sig skyldig till en disciplinförseelse fattar nämnden beslut om en disciplinär åtgärd, vilket är varning eller avstängning.
Betyg
Med beröm godkänd, icke utan beröm godkänd, godkänd, underkänd