| TDDD86 |
Datastrukturer, algoritmer och programmeringsparadigm, 11 hp
/Data Structures, Algorithms and Programming Paradigms/
För:
D
U
|
| |
Prel. schemalagd
tid: 90
Rek. självstudietid: 203
|
| |
Utbildningsområde: Teknik
Huvudområde: Datateknik, Datavetenskap Nivå (G1,G2,A): G1
|
| |
Mål:
IUAE-matris
Kursens syfte är att ge studenten verktyg att självständigt kunna konstruera datorprogram som effektivt utnyttjar tid och minne. Dessutom ger kursen fördjupade kunskaper i programmering, särskilt procedurell och objektorienterad programmering i programspråket C++, samt en introduktion till programmeringsparadigm som ett bredare perspektiv på programmering. Kursen ger även en introduktion till hur effektiva datorprogram kan hjälpa oss förstå och hantera problem relaterade till hållbar utveckling.
Efter genomgången kurs skall den studerande:
- ha god förmåga att analysera tids- och rumskomplexitet hos iterativa och enkla rekursiva algoritmer.
- kunna redogöra för och använda de vanligaste abstrakta datatyperna och sorteringsalgoritmerna.
- kunna implementera de vanligaste abstrakta datatyperna med olika datastrukturer och algoritmer.
- kunna beskriva etablerade metoder för design (och analys) av algoritmer i allmänhet.
- kunna implementera procedur- och objektorienterade program i programspråket C++.
- kunna använda olika komponenter från C++ standardbibliotek i kombination för att lösa icke-triviala beräkningsproblem.
- kunna beskriva de vanligaste programmeringsparadigmen.
- kunna tillämpa effektiva algoritmer för att bättre förstå samhälleliga problem kopplade till hållbar utveckling.
|
| |
Förkunskaper: (gäller studerande antagna till program som kursen ges inom, se 'För:' ovan)
Diskret matematik, Grundläggande funktionell, imperativ och objektorienterad programmering.
OBS! Tillträdeskrav för icke programstudenter omfattar vanligen också tillträdeskrav för programmet och ev. tröskelkrav för progression inom programmet, eller motsvarande.
|
| |
Påbyggnadskurser
Konstruktion och analys av algoritmer, Komplexitetsteori, Logikprogrammering, Programmeringsteori, Data- och programstrukturer, Processprogrammering och operativsystem, Kompilatorkonstruktion, Avancerad programmering i C++
|
| |
Organisation:
Föreläsningar används för att presentera teori som sedan övas under laborationer. Föreläsningarna om datastrukturer och algoritmer introducerar nya koncept och håller en översiktlig nivå, varvid studenterna förväntas inhämta detaljkunskaperna genom läsning och övning i en kursspecifik version av det öppna, interaktiva, läromedlet OpenDSA.
Kursen pågår hela höstterminen.
|
| |
Kursinnehåll:
- Grundläggande begrepp
- Matematiska grunder för algoritmanalys
- Grundläggande abstrakta datatyper och datastrukturer, såsom listor, stackar, köer, sökträd, heapar, hashtabeller och grafer
- Resursanalys av algoritmer
- Strängalgoritmer
- Algoritmer för sortering och urval
- Grafalgoritmer
- Paradigmer för design av algoritmer (dynamisk programmering, giriga algoritmer, rekursiv nedbrytning, totalsökning)
- Procedurell programmering i C++ (variabler, konstanter, deklarationer, uttryck, satser, funktioner, grundläggande datatyper och datastrukturer)
- Pekare och dynamisk minneshantering i C++
- Klasser i C++ (deklaration, datamedlemmar och medlemsfunktioner, åtkomstspecifikation av klassmedlemmar, konstruktorer, destruktorer, arv, polymorfi, vänner)
- Användning av C++ standardbibliotek (in- och utmatning, tecken och stänghantering, containrar, iteratorer, algoritmer, funktionsobjekt, lambdauttryck)
- Mallar i C++
- Introduktion till programmeringsparadigm
- Introduktion till effektiva algoritmers betydelser för samhällets mål med en hållbar utveckling
|
| |
Kurslitteratur:
Lippman, Lajolie, Moo, "C++ Primer", fifth edition, Addison Wesley,2012
Kursspecifik version av OpenDSA.
Laborationskompendium, stilguider för C++ och annat material finns på kursens webbsidor.
|
| |
Examination: |
DAT1
LAB1
UPG1
UPG2
|
Datortentamen (U,3,4,5)
Laborationskurs (U,3,4,5)
Datorbaserade inlämningsuppgifter (U,G)
Inlämningsuppggift (U,G)
|
3 hp
5 hp
2 hp
1 hp
|
| |
|
UPG1 är instuderingsuppgifter i datastrukturer och algoritmer som utförs i en kursspecifik version av det öppna, interaktiva, läromedlet OpenDSA.
Tentamen prövar studentens kunskaper om datastrukturer och algoritmer. Första delen av tentamen består av liknande uppgifter som i UPG1 och godkänt på den delen ger betyg 3 på tentamen. För högre betyg krävs lösta uppgifter på tentamens andra del.
Laborationskursen LAB1 övar och prövar studentens kunskaper och färdigheter i programmering i C++ och datastrukturer och algoritmer. Genom att utföra uppgifter utöver de obligatoriska i laborationskursen kan ett högre betyg än 3 erhållas på momentet.
Inlämningsuppgiften UPG2 övar och prövar studentens kunskaper och färdigheter i programmeringsparadigm.
Slutbetyget på kursen bestäms av det poängviktade medelbetyget av DAT1 och LAB1 avrundat till närmsta heltal. |
|