Datateknik GR (B), Datastrukturer och algoritmer, 6 hp

Syfte

Kursen presenterar, både teoretiskt och praktiskt, ett urval av algoritmer och datastrukturer lämpade för vanligt förekommande problem hos programvarutillämpningar, samt metoder för att undersöka egenskaperna hos detta urval. Kursen syftar till att bilda ett kritiskt förhållningssätt till samspelet mellan programkod, representation och lösningsförfaranden.

Lärandemål

Efter godkänd kurs ska du kunna:
- analysera algoritmer, uppskatta deras komplexitet och tillämpa detta,
- utvärdera faktorer för vilken algoritm och datastruktur som lämpar sig bäst för ett givet problem,
- jämföra egenskaper hos obekanta algoritmer genom att mäta realtidsprestanda och räkna instruktioner,
- värdera egna skapade algoritmers komplexitet.

Innehåll

- Introduktion till algoritmer exemplifierat med graf-relaterade problem.
- Analys av algoritmers effektivitet.
- Enkla och komplexa datastrukturer: fält, länkade listor, dynamiska strukturer, kö, stack, sammansatta strukturer; uppbyggnad av abstrakta datatyper (ADT).
- Rekursiva algoritmer och ”divide-and-conquer”-ansatser.
- Introduktion till dynamisk programmering.
- Träd, grafer och traverseringsalgoritmer.
- Elementära sorteringsalgoritmer.
- Quicksort, mergesort, heapsort, m fl.
- Sökning och symboltabeller, binära träd och dess balansering.
- Hashtabeller, sökning och algoritmer.

Behörighet

Datateknik GR (A), 18 hp, inklusive Objektbaserad programmering, 6 hp. Matematik GR (A) 9 hp inklusive Diskret Matematik, 6 hp.

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örberelser för laboration, inlämningsuppgift och tentamensförberedelser. Vid förändrad resurstillgång kan fördelningen ändras.

Examination

L108: Laborationer, med redovisning, 3 hp
Betygsskala: Underkänd (U) eller Godkänd (G)

M108: Muntlig examination, 3 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 beslut 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

Kursen är språkoberoende så tillvida att du får välja programspråk på laborationer. Handledning kan dock endast garanteras i C++.

Rekommenderas: Matematik GR (A), Algebra, 6 hp.

Denna kurs kan inte ingå i samma examen som kurs med kod DTAB04, DTAB50 eller DT0046G.