Datastrukturer, algoritmer och programmeringsparadigm

Mål

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

Innehå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