Kursusbeskrivelse

for

Datastrukturer og algoritmer

ved

Keld Helsgaun

 

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

2. Mål

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

3. Indhold

Kursets indhold kan overordnet beskrives ved følgende punkter:

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

6. Forelæsninger

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

(11/9) Algoritmeanalyse (Kapitel 5: s. 107 - 141)
O-notation. Binær søgning.

(18/9) Datastrukturer I (Kapitel 6: s. 143 - 172)
Dataabstraktion. Elementære datastrukturer.

(25/9) Rekursion (Kapitel 7: s. 173 - 219)
Algoritmedesign.

(2/10) Sortering (Kapitel 8 og 9: s. 223 - 279)
Simple metoder. ShellSort, MergeSort og Quicksort. Randomisering.

(9/10) Anvendelser I (Kapitel 10 og 11: s. 283 - 330)
Rekursion og stakke: spiltræer, aritmetiske udtryk.

(16/10) Anvendelser II (Kapitel 12 og 13: s. 331 - 365)
Prioritetskøer: filkomprimering, simulering.

(23/10) Anvendelser III (Kapitel 14 : s. 367-410)
Grafer.

(30/10) Datastrukturer II (Kapitel 15, 16 og 17: s. 411 - 487)
Implementering af stakke, køer, hægtede lister og træer.

(6/11) Datastrukturer III (Kapitel 18: s.489 - 552)
Søgetræer.

(13/11) Datastrukturer IV (Kapitel 19 og 20: s. 553 - 613)
Hashing. Prioritetskøer.

(20/11) Kursusvaluering

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


August 2000 Keld Helsgaun