AARHUS UNIVERSITET
DATALOGISK INSTITUT

Algoritmer og Datastrukturer (dADS)

Kursusbeskrivelse

Formål:

Målet med kurset er at give deltagerne kendskab til algoritmer og datastrukturer samt erfaring i systematisk udvikling og analyse heraf.

Indhold:

Datastrukturer: lister, træer, hashtabeller, skip-lister

Dataabstraktioner: stakke, køer, prioritetskøer, ordbøger, mængder

Algoritmer: søgning, sortering, selektion, fletning, mønstergenkendelse

Grafalgoritmer: grafgennemløb, sammenhængsegenskaber, topologisk sortering, udspændende træer, korteste veje, transitiv lukning

Paradigmer: del-og-kombiner, dynamisk programmering, grådighed

Analyse og syntese: worstcase, amortiseret og forventet udførelsestid; udsagn, invarianter, gyldighed, terminering og korrekthed

Underviser:

Gerth Stølting Brodal

Eksamensform:

4-timers skriftlig eksamen, som bedømmes efter 13-skalaen. Ekstern censur.

Sprog:

Dansk

ECTS point:

10 point

Denne side vedligeholdes af Gerth Stølting Brodal <gerth@cs.au.dk>.