Kursplan

Spara favorit

Hämta kursplan
Kursplan för:

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

Computer Engineering BA (B), Data Structures and Algorithms, 7.5 credits


Allmänna data om kursen

Kurskod: DT046G
Ämne huvudområde: Datateknik
Nivå: Grundnivå
Progression: (B)
Namn (inriktning): Datastrukturer och algoritmer
Högskolepoäng: 7,5
Fördjupning vs. Examen: G1F - Kursen ligger på grundnivå och fordrar mindre än 60 hp kurs(er) på grundnivå som förkunskapskrav.
Utbildningsområde: Teknik 100%
Ansvarig avdelning: Avdelningen för informations- och kommunikationssystem
Ansvarig fakultet: Fakulteten för naturvetenskap, teknik och medier
Inrättad: 2007-03-15
Fastställd: 2007-12-07
Senast ändrad: 2013-07-11
Giltig fr.o.m: 2013-08-15

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 enkla algoritmer, uppskatta deras komplexitet och tillämpa detta i din egen programmering,
- veta vilka faktorer att utvärdera för att välja vilken algoritm och datastruktur som lämpar sig bäst för ett givet problem,
- kunna testa och jämföra egenskaper hos obekanta algoritmer genom att laborativt mäta realtidsprestanda och räkna instruktioner, och
- ta hänsyn till komplexitetsfrågor när du konstruerar egna algoritmer

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), 22,5 hp, inkluderande Objektbaserad programmering i C++ 7,5 hp, Matematik GR (A), Analys 7,5 hp

Rekommenderas:
Matematik GR (A), Diskret Matematik, 7,5 hp, Matematik GR (A), Algebra, 7,5 hp.

Urvalsregler

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

Undervisning

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

Examination

3.0 hp, L102: Laborationer
Betyg: Underkänd (F) eller Godkänd (P)

4.5 hp, T101: Skriftlig tentamen
Betyg: 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.

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.

Litteratur

Obligatorisk litteratur

Sedgewick, Algorithms in C++, Addison-Wesley, (Ny upplaga, om möjligt), 0-201-51059-6

Kommentar: alternativt: M. Goodrich and R. Tamassia Data Structures and Algorithms in Java, Second edition Wiley, ISBN: 0-471-38367-8

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

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