1. Formål

Kursets formål er at supplere den studerendes kendskab til analyse og design af
algoritmer.

2. Indhold

Kurset er et avanceret kursus i algoritmedesign. Anvendelser indenfor områderne internetalgoritmik og algoritmisk geometri vil blive behandlet.

Emner:

• Algoritmeanalyse
  Asymptotisk notation, amortisering, eksperimentel analyse
  
  
• Algoritmedesign
  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”. Desuden forudsættes matematik på B-niveau.

5. Evaluering

Mundtlig eksamen. Den studerende fremlægger en artikel, der udleveres 3 arbejdsdage inden eksamen. Der gives karakter efter 13-skalaen.

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.

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

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

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

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

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

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

(19/3) Internetalgoritmer II
Kryptografi.

(26/3) Internetalgoritmer III
Netværksalgoritmer.

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

(16/4) Kursusafrunding

Tilbage til hovedsiden