Algoritmedesign
med internetanvendelser
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
Form
Undervisningen foregår ved forelæsninger og øvelser.
Forelæsningerne afholdes mandage 930-1200.
Øvelserne afholdes mandage1300-1530.
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
Januar 2008 Keld Helsgaun