RUC, foråret 2004

Sidste nyt
 7. juni 2004

Formål

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


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
  

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

Forudsætninger

Kurset forudsætter fortrolighed med datastrukturer og algoritmer svarende til gennemførelse af kurset “Datalogi C”. 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


Deltagere

Deltagerliste

Yderligere information

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

Projektforslag

• Forslag til datalogiprojekter (38 forslag) [pdf]
• Ti forslag til datalogiske projekter inden for kunstig intelligens [pdf]