Datateknik GR (B), Datastrukturer och algoritmer, 7,5 hp

Syfte

Kursens målsättning är att göra studenten bekant med relevanta teoretiska koncept med praktisk tillämpning gällande skapande, lagring, åtkomst samt manipulering av datastrukturer, abstrakta datatyper (ADT's) tillsammans med grunder i algoritmanalys. Vidare avser kursen stärka ett kritiskt förhållningssätt gentemot grundläggande datastrukturer såsom listor, länkade listor, hashtabeller, binära trädstrukturer, heaps samt grafer.

Lärandemål

Efter godkänd kurs ska studenten kunna:
- analysera och jämföra såväl effektivitet som komplexitet mellan olika algoritmer.
- beskriva egenskaper gällande abstrakta datatyper samt implementera olika datastrukturer,
- beskriva och implementera tillhörande operationer för olika datastrukturer,
- beskriva användningsområden samt begränsningar kring olika datastrukturer samt tillämpa lämpliga strukturer för problemlösning,
- beakta komplexitetsaspekter vid utformning och implementering av algoritmer.

Innehåll

- Introduktion till komplexitetsteori (tids-/ minneskomplexitet) och kravanalys för datastrukturer samt tillhörande algoritmer med hjälp av Asymptotisk notation. Identifiering av Best / Average / Worst fallscenarios.
- Introduktion till grundläggande abstrakta datatyper (ADT) såsom Stacks ADT, Queues ADT och List ADT samt tillhörande algoritmer.
- Introduktion till rekursiva algoritmer samt angreppssätt enligt s.k. divide-and-conquer.
- Introduktion till grundläggande sorteringsalgoritmer.
- Introduktion samt implementering av komplexa datastrukturer såsom Stacks, Queues, Lists, Trees, Heaps, Hashes, Graphs.
- Fastställande av datastrukturers lämplighet i förhållande till givna problemområden.

Behörighet

Datateknik GR (A), 22,5 hp, inkluderande 15 hp objektorienterad programmering.

Urvalsregler

Urval sker i enlighet med Högskoleförordningen och den lokala antagningsordningen.

Undervisning

Undervisningen består av ca 17% föreläsningar, 6% laborationer, 77% självstudier. Självstudier skall ägnas åt inläsning av litteratur, förberedelser för laboration, inlämningsuppgift och tentamensförberedelser. Vid förändrad resurstillgång kan fördelningen ändras.

Examination

L101: Laborationer, 3,5 hp
Betygsskala: Underkänd (U) eller Godkänd (G)

Q101: Webbexamination, 4 hp
Betygsskala: På kursen ges något av betygen A, B, C, D, E, Fx och F. A - E är Godkänt, Fx och F är underkänt.

Betygskriterier för ämnet finns på www.miun.se/betygskriterier.

Om en student har ett besked från samordnaren vid Mittuniversitetet om pedagogiskt stöd vid funktionsnedsättning, har examinator rätt att ge anpassad examination för studenten.

Begränsning av examination

Studenter registrerade på denna version av kursplan har rätt att examineras 3 gånger inom loppet av 1 år enligt angivna examinationsformer. Därefter gäller examinationsform enligt senast gällande version av kursplan.

Betygsskala

På kursen ges något av betygen A, B, C, D, E, Fx och F. A - E är Godkänt, Fx och F är underkänt.

Övrig information

Denna kurs kan inte ingå i samma examen som kurs med kod DT046G eller DT064G.