Behörighetskrav

15 hp informationssystem eller motsvarande

Mål

Vad gäller kunskap och förståelse förväntas studenten efter genomgången kurs kunna:

- förklara kopplingen mellan val av datastrukturer och effektiv problemlösning,

- beskriva grundläggande datastrukturer och algoritmer,

- förklara kopplingen mellan datastrukturer, algebraiska datatyper och abstrakta datastrukturer,

- beskriva några av de olika teknikerna som används inom algoritmdesign och utveckling.

Vad det gäller färdigheter och förmåga förväntas studenten efter genomgången kurs kunna:

- skapa domänspecifika datastrukturer genom användning av algebraiska datatyper,

- dölja detaljer i datastrukturer bakom interfaces,

- använda grundläggande datastrukturer och kunna implementera standardalgoritmer som använder olika tekniker för algoritmkonstruktion såsom rekursiv nedstigning, divide & conquer eller beskärning,

- tillämpa eller anpassa en ny eller tidigare osedd algoritm för att lösa ett givet problem.

Vad det gäller värderingsförmåga och förhållningssätt förväntas studenten efter genomgången kurs kunna:

- jämföra och utvärdera algoritmer med avseende på korrekt funktion och effektivitet.

Innehåll

Kursens fokus ligger på algoritmisk problemlösning, dvs. hur generella lösningar till problem kan framgångsrikt tillämpas på exempelvis sök- och sorteringsrelaterade problem inom programmering. Kursen inleder genom att behandla datarepresentation i form av datastrukturer. Grundläggande begrepp såsom sammansatta datatyper (composite datatypes) som skapas genom att kombinera enklare datatyper, såsom heltal, bokstäver och strängar, samt grundläggande datastrukturer, såsom enkla listor och träd, introduceras och definieras. Vidare diskuteras felhantering med avsikt att nå robusthet. Efter detta behandlas olika grundläggande algoritmer för sökning och sortering inom dessa datastrukturer. Vidare behandlas grundläggande tekniker för algoritmkonstruktion, inklusive rekursiv nedstigning, divide and conquer, dynamisk programmering, "greedy" algoritmer, beskärning och min-max algoritmer. Slutligen introduceras metoder för att bedöma korrektheten, fullständigheten och komplexiteten hos olika algoritmer. Vid utgången av kursen har studenten fått en förståelse för hur datarepresentation och algoritmer används för att söka ut och sortera data och kan tillämpa detta i praktiken.

Undervisning

Föreläsningar, lektioner och laborationer

Examination

Kursen examineras genom inlämningsuppgifter och tentamen.

Om särskilda skäl finns får examinator göra undantag från det angivna examinationssättet och medge att en student examineras på annat sätt. Särskilda skäl kan t.ex. vara besked om särskilt pedagogiskt stöd från universitetets samordnare eller beslut om undantag som fattats av institutionens arbetsgrupp för studieärenden.