Kursusbeskrivelse for

Algoritmedesign

1. Formål

Kursets formål er

• at supplere den studerendes kendskab til analyse og design af algoritmer
  
  
• at udbygge den studerendes evne til at tilegne sig algoritmeorienteret stof og at formidle dette til andre.
  

2. Indhold

Kurset er et avanceret kursus i algoritmedesign.

Emner:

• Algoritmeanalyse
  Asymptotisk notation, amortisering, eksperimentel analyse
  
  
• Algoritmiske designmønstre
  Grådige algoritmer, del-og-hersk, dynamisk programmering
  
  
• Grafalgoritmer
  Traversering, topologisk sortering, korteste vej,
  mindste udspændende træ, strømning i netværk
  
  
• Internetalgoritmer
  Strengsøgning, tekstkomprimering, kryptografi, netværksalgoritmer
  
  
• Geometriske algoritmer
  Flerdimensionale træer, konvekst hylster
  

3. Form

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

4. Deltagerforudsætninger

Kurset forudsætter fortrolighed med datastrukturer og algoritmer svarende til gennemførelse af kurset “Datalogi C” eller CSS.
Desuden forudsættes matematik på B-niveau.

5. Evaluering

Mundtlig eksamen. 30 minutters individuel prøve.
Den studerende fremlægger en artikel, der er udleveret 3 arbejdsdage inden eksamen.
Der gives karakter efter 7-trinsskalaen.

6. Lærebog

Som lærebog anvendes

7. Forelæsninger

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

(4/2) Fundamentale værktøjer I
Algoritmeanalyse. Prioritetskøer. Hashing.

(11/2) Fundamentale værktøjer II
Søgetræer og skiplister. Sortering.

(18/2) Fundamentale værktøjer III
Algoritmiske designmønstre.

(25/2) Grafalgoritmer I
Korteste veje. Mindste udspændende træ.

(3/3) Grafalgoritmer II
Strømning i netværk.

(10/3) Internetalgoritmer I
Strengsøgning. Tekstkomprimering.

(17/3) Internetalgoritmer II
Kryptografi.

(31/3) Internetalgoritmer III
Netværksalgoritmer.

(7/4) Geometriske algoritmer
Flerdimensionale søgetræer. Konvekst hylster.

(14/4) Kursusafrunding

Tilbage til hovedsiden