1. Formål

Studiet af algoritmer, algoritmik, er en central del af datalogien. Ved udvikling af et program er det vigtigt, at datalogen har et solidt kendskab til egnede algoritmer og kan foretage et kvalificeret valg imellem disse. Han eller hun skal endvidere være i stand til at designe nye algoritmer, kunne vurdere deres effektivitet og kunne argumentere for deres korrekthed.

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:

• Algoritmedesign: rekursion, del-og-hersk, baksporing
• Datastrukturer og abstrakte datatyper: arrays, hægtede lister, køer, stakke, træer, grafer
• Algoritmer: sortering, søgning, strengsøgning, syntaksanalyse, grafalgoritmer
• Kompleksitet: algoritmekompleksitet
• Korrekthed: bevisførelse 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 "Algorithms in C++" af Robert Sedgewick (Addison Wesley 1992). Som supplement til lærebogen anbefales "Algoritmer i Java" (3. udgave) af Keld Helsgaun (Datalogiske Noter, RUC 1999).

6. Forelæsninger

Til stofgennemgang er afsat 10 forelæsningsgange. Forelæsningerne finder sted i teorilokalet i hus 43.2 på torsdage fra 9⁴⁵ til 12⁰⁰. Første forelæsningsgang er torsdag den 16. september 1999. Sidste forelæsningsgang er torsdag den 18. november 1999.

En foreløbig plan for forelæsningerne er vist nedenfor.

En udførlig beskrivelse af de enkelte forelæsninger kan ses her. Det bemærkes, at kun de 10 første af de 12 beskrevne forelæsninger afholdes i dette semester. Ret til ændringer forbeholdes.

6. Arbejdsbelastning

Den forventede arbejdsbelastning for den studerende er cirka 10 timer per uge i kursusperioden.

Tilbage til hovedsiden