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 et af kurserne ≥Datastrukturer og algoritmer≤ og ≥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.

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.

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

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

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

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

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

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

(21/3) Internetalgoritmer II
Kryptografi.

(28/3) Internetalgoritmer III
Netværksalgoritmer.

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

(11/4) Kursusafrunding

Tilbage til hovedsiden