RUC, foråret 2005

Sidste nyt
 31. maj 2005

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 torsdage 9³⁰-12⁰⁰.
Øvelserne afholdes torsdage13⁰⁰-15³⁰.

Forudsætninger

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

Evaluering

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

Underviser

Keld Helsgaun, lektor


Yderligere information

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