Datastrukturer
Om utbildningen
Datastrukturer och algoritmer utgör grundläggande byggstenar i nästan alla programvaror. Kunskaper och färdigheter i dataabstraktion, datastrukturer och algoritmer är nödvändiga vid konstruktion, användning och underhåll av förändringsbara, återanvändbara, korrekta och effektiva programkomponenter.
Kursen ger kunskaper och färdigheter i konstruktion och användning av algoritmer och datastrukturer, introduktion till algoritmanalys och dataabstraktion, samt insikter i fördelarna med dataabstraktion vid programutveckling.
Följande ämnen täcks av kursen:
• abstrakta datatyper
• datastrukturer och algoritmer, med fokus både på imperativa, objektorienterade, och funktionella programmeringsspråk
• skillnader mellan lat och strikt evaluering av funktionella datastrukturer
• vanliga datastrukturer, såsom fält (arrayer), länkade listor, obalanserade och balanserade träd, heapar och hashtabeller
• hur dessa kan användas för att implementera abstrakta datatyper, såsom stackar, köer, prioritetsköer, avbildningar, mängder och grafer
• standardalgoritmer för dessa datastrukturer, inklusive deras resurskrav
• söknings- och sorteringsalgoritmer
• att använda olika bibliotek för datastrukturer och algoritmer
• grundläggande komplexitetsanalys av datastrukturer och algoritmer
Behörigheter och urval
Behörighet
Förkunskapskraven är:
- godkänd kurs i imperativ eller objektorienterad programmering, 7,5 hp (t.ex. DIT012 Imperativ programmering med grundläggande objektorientering, eller motsvarande)
- godkänd kurs i funktionell programmering, 7,5 hp (t.ex. DIT440 Introduktion till funktionell programmering, eller motsvarande)
- godkänd kurs eller delkurs i diskret matematik, 7,5 hp (t.ex. DIT980 Diskret matematik för Datavetare, delkursen Inledande algebra i MMGD200 Matematik 1, eller motsvarande)
Urval
Högskolepoäng, max 165 hp.