RUC, foråret 2008

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.
  

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
  

Lærebog

Som grundbog anvendes

Michael T. Goodrich og Roberto Tamassia:
Algorithm Design: Foundations, Analysis, and Internet Examples,
John Wiley & Sons, Inc., 2002.


Form

Undervisningen foregår ved forelæsninger og øvelser.
Forelæsningerne afholdes mandage 9³⁰-12⁰⁰.
Øvelserne afholdes mandage13⁰⁰-15³⁰.

Forudsæ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.

Evaluering

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

Underviser

Keld Helsgaun, lektor


Yderligere information

• Kursusbeskrivelse
• Slides
• Ugesedler
• Artikler
  
  
• Dictionary of Algorithms, Data Structures, and Problems
• The Algorithm Design Manual
• Algorithms