DM507/DM578/DS814/SE4-DMAD Algoritmer og datastrukturer
Forår 2025
Rolf Fagerberg
Generel information
Kurset starter tirsdag den 4. februar og slutter fredag den
30. 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 |
Tirsdag 4/2 |
08-10 |
U55 |
Introduktion til kurset (slides med
overlays/uden overlays, kapitel 1
i lærebogen [3. udgave: kapitel 1]).
Eksempel på en (meget detaljeret) algoritmeanalyse:
Ombytningspuslespil (slides med
overlays/uden overlays,
noter). Et
ombytningspuslespil
fra nettet.
|
| 7 |
F |
Tirsdag 11/2 |
08-10 |
U55 |
Om algoritmeanalyse (dele af afsnit 2.2 i lærebogen [3. udgave: dele af afsnit 2.2], slides
med
overlays/uden overlays,
tidsTabelBeregninger.py).
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 13/2 |
10-12 |
U1 |
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.
Asymptotisk analyse (afsnit 3.1-2 i lærebogen [3. udgave: afsnit 3.1], side 1-23 i slides
med
overlays/uden overlays,
Java-programmerne fra slides: Linear.java,
Quadratic.java, Cubic.java).
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 |
Tirsdag 18/2 |
|
Video |
Afslutning af asymptotisk analyse
(videoforelæsning,
afsnit 3.1-2 i lærebogen [3. udgave:
afsnit 3.1], slides med
overlays/uden overlays).
Et eksempel på at forskellige algoritmer for samme beregningsproblem
kan have meget forskellige køretider: the maximum sum sub-array
problem (videoforelæsning, slides
med
overlays/uden overlays,
wikipedia).
Implementationer af de tre algoritmer for maximum sum sub-array:
MaxSum1.py, MaxSum1.java,
MaxSum2.py, MaxSum2.java,
MaxSum3.py, MaxSum3.java.
|
| 8 |
E |
|
|
|
Opgaver.
|
| 9 |
F |
Tirsdag 25/2 |
08-10 |
U55 |
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 27/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 |
Tirsdag 4/3 |
08-10 |
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).
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.
|
| 10 |
E |
|
|
|
Opgaver.
|
| 11 |
F |
Tirsdag 11/3 |
08-10 |
U1 |
[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).
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).
|
| 11 |
F |
Torsdag 13/3 |
10-12 |
U1 |
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 af projektet, del I (kun for DM507 og
DS814).
|
| 11 |
E |
|
|
|
Opgaver.
|
Maintained by Rolf Fagerberg
(rolf@imada.sdu.dk)
|
|