TDRK12 - Datastrukturer>

Kurskod:	TDRK12
Fastställd av:	VD 2021-03-01
Reviderad av:	Utbildningschef 2021-11-08
Gäller fr.o.m.:	2022-01-01
Version:	2

Utbildningsnivå:	Grundnivå
Utbildningsområde:	Tekniska området
Ämnesgrupp:	DT1
Fördjupning:	G1F
Huvudområde:	Datavetenskap

Lärandemål

Efter genomgången kurs skall studenten:

Kunskap och förståelse

- visa förståelse för koncepten inkapsling, abstrakta datatyper och programmering mot gränssnitt
- visa kunskap om de datastrukturer och abstrakta datatyper som kursen behandlar
- visa kunskap om standardoperationer på de abstrakta datatyper som kursen behandlar

Färdighet och förmåga

- visa förmåga att använda och designa abstrakta datatyper för att erhålla en god programdesign
- visa färdighet i att använda och implementera de datastrukturer och abstrakta datatyper som kursen behandlar
- visa färdighet i att genomföra enklare komplexitetsanalys av operationer på datastrukturer
- visa förmåga att använda avancerade konstruktioner i språket C för att hantera abstrakta datatyper

Värderingsförmåga och förhållningssätt

- visa förmåga att välja och utnyttja lämpliga abstrakta datatyper vid programkonstruktion
- visa förmåga att välja en lämplig konkret representation för en given abstrakt datatyp.

Innehåll

Kursen behandlar de vanligast förekommande abstrakta datatyperna, samt deras implementering och användning i strukturerad programmering.

Kursent innehåller följande moment:
- Grundläggande datastrukturer i språket C: Vektorer, matriser, strängar och structar
- Avancerade konstruktioner i språket C och tillämpningar av dessa: pekare och dynamisk minnesallokering, funktionspekare och unioner
- Abstrakta datatyper (ADT:er) och användning av ADT:er för att skapa applikationer
- Analys av komplexitet för operationer på olika datastrukturer
- Linjära datastrukturer: Stack, kö, prioritetskö, länkad lista, samt operationer på dessa
- Rekursiva datastrukturer: lista, hög (heap), träd (särskilt sökträd), samt operationer på dessa
- Grafer och enklare grafalgoritmer

Undervisningsformer

Föreläsningar, övningar och handledning av laborationer.

Undervisningen bedrivs normalt på svenska men undervisning på engelska kan förekomma.

Förkunskapskrav

Grundläggande behörighet samt genomgånga kurser i Diskret matematik 7,5 hp, Funktionell programmering 7,5 hp och Programmeringsteknik 7,5 hp (eller motsvarande kunskaper).

Examination och betyg

Kursen bedöms med betygen 5, 4, 3 eller Underkänd.

Poängregistrering av examinationen för kursen sker enligt följande system:

Examinationsmoment	Omfattning	Betyg
Tentamen¹	4,5 hp	5/4/3/U
Laborationer	3 hp	U/G

¹ Bestämmer kursens slutbetyg vilket utfärdas först när samtliga moment godkänts.

Kurslitteratur

Kurslitteraturen fastställs 8 månader innan kursstart.

Titel: Data Structures Using C, 2nd edition
Författare; Reema Thareja
Förlag: Oxford University Press, 2014
ISBN-13: 978-0198099307