1. Formål

Studiet af datastrukturer og algoritmer er en central del af datalogien. Ved udvikling af et program er det vigtigt, at udvikleren har et solidt kendskab til egnede datastrukturer og algoritmer og kan foretage et kvalificeret valg imellem disse.

Kursets formål er

• at opøve evnen til at designe algoritmer
• at give viden om centrale algoritmer og datastrukturer
• at give kendskab til analyse og verifikation af algoritmer

2. Mål

Målet er, at den studerende efter gennemførelse af kurset

• kender til de vigtigste principper for algoritmedesign og er i stand til at anvende dem i praksis
• kender til elementære datastrukturer og deres anvendelse i forbindelse med implementering af abstrakte datatyper
• kender til en række vigtige algoritmer inden for datalogien, bl.a. algoritmer til sortering og søgning
• i simple tilfælde kan bestemme kompleksiteten af en forelagt algoritme og udtrykke den ved O-notation
• har et rudimentært kendskab til bevisførelse for algoritmers korrekthed.

3. Indhold

Kursets indhold kan overordnet beskrives ved følgende punkter:

• Datastrukturer og abstrakte datatyper: Stakke, køer, hægtede lister, træer, hashtabeller og prioritetskøer
• Algoritmer: sortering og søgning
• Algoritmedesign: rekursion, del-og-hersk, dynamisk programmering, baksporing
• Algoritmeanalyse: eksempler på algoritmeanalyse, O-notation
• Algoritmeverifikation: eksempler på beviser for algoritmers korrekthed

Hovedvægten lægges på de tre første punkter.

4. Form

Undervisningen foregår ved forelæsninger og øvelser.

5. Lærebog

Som lærebog anvendes

Mark Allen Weiss,
Data Structures & Problem Solving Using Java,
Addison Wesley, 1998.

6. Forelæsninger

Til stofgennemgang er afsat 10 forelæsningsgange. En foreløbig plan er vist nedenfor. Ret til ændringer forbeholdes.

7. Anbefalede forudsætninger

De anbefalede forudsætninger er som beskrevet i studieordningens §5, stk. 2. Det er en fordel at have et basalt kendskab til objektorienteret programmering i Java. For deltagere uden et sådant kendskab etableres i kursets start et kort undervisningsforløb baseret på lærebogens kapitel 2-4.

8. Arbejdsbelastning

Den forventede arbejdsbelastning er cirka 12 timer per uge i kursusperioden.

9. Eksamen

Der afholdes en skriftlig prøve med ekstern censur. Prøven varer 2 timer og foregår ved brug af alle sædvanlige hjælpemidler.

Tilbage til hovedsiden