DM507/DM578/DS814/SE4-DMAD Algoritmer og datastrukturer
Forår 2026
Rolf Fagerberg
Generel information
Kurset starter mandag den 2. februar og slutter fredag den
29. maj.
Timer
Hvis tid eller sted er angivet med rødt,
er det for at henlede opmærksomheden på, at placeringen afviger fra
det normale.
| Uge |
Type |
Dato |
Tid |
Lokale |
Indhold |
| 6 |
F |
Mandag 2/2 |
16-18 |
U55 |
Introduktion til kurset (slides med
overlays/uden overlays, kapitel 1
i lærebogen [3. udgave: kapitel 1]).
Om algoritmeanalyse (dele af afsnit 2.2 i lærebogen [3. udgave: dele af afsnit 2.2], slides
med
overlays/uden overlays).
Eksempel på en (meget detaljeret) algoritmeanalyse:
Ombytningspuslespil (slides med
overlays/uden overlays,
noter). Et
ombytningspuslespil
fra nettet.
|
| 7 |
F |
Tirsdag 10/2 |
08-10 |
U1 |
Lidt mere om algoritmeanalyse (dele af afsnit 2.2 i lærebogen [3. udgave: dele af afsnit 2.2], slides
med
overlays/uden overlays),
især om RAM-modellen (side 5 i slides).
Start på sorteringsalgoritmer: Insertionsort (side 157-160 i lærebogen
[3. udgave: side 147-150], afsnit 2.1-2.2
i lærebogen [3. udgave: afsnit 2.1-2.2],
side 1-6 i slides med
overlays/uden overlays). Vi
vender tilbage til begrebet "Invariant" lidt senere i kurset - de dele
af teksten i lærebogen, som snakker om dette, kan indtil videre læses
let.
|
| 7 |
F |
Torsdag 12/2 |
10-12 |
U55 |
Mere om sorteringsalgoritmer: Selectionsort, Mergesort (afsnit 2.3 i
lærebogen [3. udgave: afsnit 2.3], side
7-13 i slides med
overlays/uden overlays). Vi
vender tilbage til begrebet "Divide and Conquer" lidt senere i kurset
- de dele af teksten i lærebogen, som snakker om dette, kan indtil
videre læses let.
Noter om logaritmefunktionen. [Yderligere kommentarer (ikke pensum): Noterne om
logaritmefunktionen antager, at man kender begrebet omvendt
funktion. Man kan få genopfrisket dette i afsnit 7.1 og 7.3 af Benjamin
Teglbjærgs noter til Matematik B på HHX. ]
Asymptotisk analyse (afsnit 3.1-2 i lærebogen [3. udgave: afsnit 3.1], side 1-3 og 9-23 i slides
med
overlays/uden overlays,
Det kan være en fordel at orientere sig i afsnit 3.3 i lærebogen [3. udgave: afsnit 3.2], hvis der i kurset
bruges matematiske formler, definitioner og metoder, man har glemt.
|
| 7 |
E |
|
|
|
Opgaver.
|
| 8 |
F |
Torsdag 19/2 |
10-12 |
U1 |
Afslutning af asymptotisk analyse (afsnit 3.1-2 i lærebogen [3. udgave: afsnit 3.1], resten af siderne i
slides med
overlays/uden overlays).
Java-programmerne fra slides: Linear.java,
Quadratic.java, Cubic.java.
Et eksempel på at forskellige algoritmer for samme beregningsproblem
kan have meget forskellige køretider: the maximum sum sub-array
problem. (slides med
overlays/uden overlays,
wikipedia).
|
| 8 |
E |
|
|
|
Opgaver.
|
| 9 |
F |
Tirsdag 24/2 |
08-10 |
U1 |
Divide-and-conquer/rekursive algoritmer (side 34 i lærebogen [3. udgave: side 30], slides
med
overlays/uden
overlays, eksempel i Python
som illustrerer flow-of-control).
Mergesort formuleret rekursivt (afsnit 2.3 i lærebogen [3. udgave: afsnit 2.3], side 14-15 i slides
med
overlays/uden overlays).
Flere sorteringsalgoritmer: Quicksort (afsnit 7.1-3 i lærebogen [3. udgave: afsnit 7.1-3], side 16-22 i slides
med
overlays/uden overlays).
|
| 9 |
F |
Torsdag 26/2 |
10-12 |
U1 |
Flere sorteringsalgoritmer: Heapsort (afsnit 6.1-4 i lærebogen [3. udgave: afsnit 6.1-4], afsnit B.5.3 i
lærebogen [3. udgave: afsnit B.5.3],
sidste del af slides med
overlays/uden overlays).
|
| 9 |
E |
|
|
|
Opgaver.
|
| 10 |
F |
Torsdag 5/3 |
10-12 |
U1 |
Nedre grænser for sammenligningsbaseret sortering (afsnit 8.1 i
lærebogen [3. udgave: afsnit 8.1], første
del af slides med
overlays/uden
overlays, eksempler på decisiontrees for insertionsort
(n=1,2,3,4,5,6,7),
mergesort
(n=1,2,3,4,5,6,7))
og heapsort
(n=1,2,3,4,5,6,7),
eksempel i Python på at annotere en
sammenligningsbaseret sorteringsalgoritme med elementernes
startindekser).
|
| 10 |
E |
|
|
|
Opgaver.
|
| 11 |
F |
Mandag 9/3 |
12-14 |
U55 |
Flere sorteringsalgoritmer: sortering af heltal med Countingsort og
Radixsort (afsnit 8.2-3 i lærebogen [3. udgave:
afsnit 8.2-3], anden del af slides
med
overlays/uden
overlays). For at forstå sidste side af slides om Radixsort, skal man
kende det binære talsystem. Gør man ikke det, så check side 5-7 i
disse slides med
overlays/uden overlays.
[Det antages i dette kursus, at man allerede er bekendt med de
simple datastrukturer lænket liste, stak og kø,
f.eks. fra ens programmeringskursus. I modsat fald, læs afsnit 10.1-2
i lærebogen [3. udgave: afsnit 10.1-2].]
Prioritetskøer (afsnit 6.5 i lærebogen [3. udgave: afsnit 6.5], slides
med overlays/uden
overlays).
|
| 11 |
F |
Torsdag 12/3 |
10-12 |
U1 |
Dictionaries og deres implementation via binære søgetræer
(side 249-251 i lærebogen [3. udgave:
side 229-231], afsnit 10.3 (mest figur 10.6) i lærebogen [3. udgave: afsnit 10.4 (mest figur 10.9)],
afsnit 12.1-3 i lærebogen [3. udgave:
afsnit 12.1-3], første del af slides
med
overlays/uden overlays).
Rød-sorte træer (afsnit 13.1-4 i lærebogen [3. udgave: afsnit 13.1-4], næste del af slides
med
overlays/uden overlays).
Bemærk at lærebogen er ret tung læsning i kapitel 13. Det skyldes
dels, at dens pseudo-kode er fungerende kode (robust og gennemtænkt,
så den også virker i specialtilfælde, såsom tomme træer, etc.) med
alle detaljer, og dels at den udtrykker og beviser invarianter på
niveau 2 (mere om invarianter til en senere forelæsning), dvs. under
henvisning til denne kode. Det anbefales (for alle emner, men her
endnu mere end normalt) at læse lærerens slides før man nærlæser
lærebogen.
|
| 11 |
E |
|
|
|
Opgaver.
|
| 12 |
F |
Torsdag 19/3 |
10-12 |
U1 |
Afslutning af rød-sorte træer (afsnit 13.1-4 i lærebogen [3. udgave: afsnit 13.1-4], næste del af slides
med
overlays/uden overlays).
Udlevering og gennemgang af projektet, del I (kun
for DM507 og DS814). Redirection af standard input og output (relevant
viden for alle).
Implementation af dictionaries via hashing (afsnit 11.1-4 i lærebogen
(dog ikke: siderne 278-281, beviset for corollary 11.3, afsnit
11.3.3-1.3.5, siderne 297 (midten) til 300) [3. udgave: afsnit 11.1-4 (dog ikke: siderne 258-260,
266-268, 274-276)], slutningen af slides
med
overlays/uden overlays).
En god indføring i state-of-the-art hashing metoder, som både er
effektive i praksis og teoretisk gode, kan findes i disse
noter af Mikkel Thorup (ikke
pensum).
|
| 12 |
E |
|
|
|
Opgaver.
|
| 13 |
F |
Mandag 23/3 |
12-14 |
U55 |
Dekoration af binære søgetræer (afsnit 17.1-2 i lærebogen [3. udgave: afsnit 14.1-2], slides
med
overlays/uden overlays).
|
| 13 |
F |
Torsdag 26/3 |
08-10 |
U1 |
Invarianter (siderne 20-21, 167-168, 184 og 340-345 i lærebogen [3. udgave: siderne 18-20, 32-33, 157, 171-173 og
318-322], slides med
overlays/uden overlays).
Divide and Conquer algoritmer, rekursionsligninger, og analyse heraf
via rekursionstræer og via Master Theorem (afsnit 4.0, 4.4 og 4.5 i
lærebogen [3. udgave: afsnit 4.0, 4.4 og 4.5
(bemærk at i 3. udgave er case 2 i Master Theorem en smule mindre
generel end i 4. udgave)], side 1-23 i slides
med
overlays/uden
overlays).
|
| 13 |
E |
|
|
|
Opgaver.
|
Maintained by Rolf Fagerberg
(rolf@imada.sdu.dk)
|
|