Kurset starter tirsdag den 1. september. Der skal ikke købes nogen
lærebog.
Pensum til eksamen i DM595 er materialet (som regel slides) angivet på
denne webside under de relevante forelæsninger (F-timer). Hvis der til
et emne er angivet yderligere materiale, som ikke er pensum, er dette
ikke nødvendigt at læse for at kunne regne opgaverne eller gå til
eksamen (dette ekstramateriale er blot ment som en service for
personer, der efterspørger noget sådant).
| Uge |
Type |
Dato |
Tid |
Lokale |
Indhold |
| 36 |
F |
Tirsdag 1/9 |
10‑12 |
U55 |
Introduktion til SDUs systemer, ved Søren Sten Hansen. Se Itslearning
plan for materialer.
|
| 36 |
F |
Onsdag 2/9 |
10-12 |
U20 |
Kursusintroduktion (slides med
overlays/uden overlays).
Repræsentation af tal (side 1-9 i slides med
overlays/uden overlays).
|
| 36 |
F |
Fredag 4/9 |
08-10 |
U20 |
Afslutning af repræsentation af tal (resten af slides
med
overlays/uden overlays).
Programmet brugt til forelæsningen til at vise
bits i filer (ikke pensum).
|
| 37 |
F |
Mandag 7/9 |
12-14 |
U47
|
Boolsk algebra og gates (slides med
overlays/uden overlays).
[Yderligere kommentarer (ikke pensum): For en
gennemgang af opbygningen af en af de første CPU'er på én chip, Intels
8008 (1972), se her. Moderne
CPU'er kan indeholde over 1011 transistorer - se en
oversigt over den vilde udvikling i antallet her. Her er
en side med
flere billeder af indmaden af integrerede kredse.
Bemærk, at selv om Boolsk algebra på CPU'er implementeres via strøm og
elektronik, er dette ikke en nødvendighed. Enhver teknologi, som kan
implementere logiske gates, kan i princippet bruges. F.eks. blev der i
1964 bygget en computer
baseret på luftstrømme i stedet for elektrisk strøm.]
|
| 37 |
F |
Onsdag 9/9 |
08-10 |
U20 |
CPUer og maskinkode (slides med
overlays/uden overlays). CPU
simulator (Johan Fagerberg,
baseret på forlæg af J. Glenn Brookshear). De to eksempelprogrammer
fra slides om CPU: bytOmPåToTal.txt og
udskrivStigendeSekvens.txt.
[Første abstraktionslag, som man (på vej til
programmerinssprog såsom Python) lægger ovenpå ren maskinkode, er assembly
language (ikke pensum). I assembly language er kommandoer angivet
med korte navne i stedet for bitstrings, og positioner i koden (brugt
under jumps) kan angives med symbolske navne (labels), således at man
under programmering ikke behøver kende kodens konkrete placering i
hukommelsen. Når et program i assembly language oversættes og placeres
i hukommelsen (af en simpel compiler kaldet en assembler), bliver
disse labels automatisk konverteret til hukommelsesadresser, som
passer med programmets endelige placering. Pelle Schäfer Domela har
lavet et
assembly language for maskinsproget i vores simulator og en tilhørende
assembler. ]
[For yderligere materiale (ikke pensum) om
Boolean algebra, gates og CPUer/maskinkode se f.eks. slides fra Alvin
Lebeck's kursus, specielt disse,
disse
og delvist disse.]
|
| 37 |
F |
Onsdag 9/9 |
10-12 |
U20 |
Studiegrupper og studiegruppekontrakter, ved instruktorerne. Se
Itslearning plan for materialer.
|
| 37 |
F |
Torsdag 10/9 |
10-12 |
U23 |
Kompetenceportfolio, ved Benjamin Jäger. Se Itslearning plan for
materialer.
|
| 37(-38) |
E |
|
|
|
Opgaver.
Løsninger (med nummerering
fra E21).
|
| 38 |
F |
Mandag 14/9 |
12-14 |
U47 |
Start på algoritmer, asymptotisk notation, invarianter, ved Lene
Monrad Favrholdt (slides,
algoritmer fra slides med engelske
keywords). 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. ]
|
| 38 |
F |
Onsdag 16/9 |
08-10 |
U20 |
Afslutning af algoritmer, asymptotisk notation, invarianter, ved Lene
Monrad Favrholdt (slides,
algoritmer fra slides med engelske
keywords). De tre sidste sider i slides om rekursive versioner af
algoritmerne er ikke pensum.
[For yderligere materiale (ikke pensum) om
asymptotisk notation og invarianter, se disse slides fra DM578: med
overlays/uden
overlays (algoritmeanalyse), med
overlays/uden
overlays (asymptotisk notation), med
overlays/uden
overlays (invarianter).]
|
| 38 |
F |
Onsdag 16/9 |
10-12 |
U20 |
Studievejlederne, ved Simone Louise Nothlev Sørensen.
|
| 38(-39) |
E |
|
|
|
Opgaver.
Løsninger (med nummerering
fra E21).
|
| 39 |
F |
Mandag 21/9 |
14-16 |
U20 |
Start på merging og hashing (side 1-15 i slides
med
overlays/uden overlays)
|
| 39 |
F |
Onsdag 23/9 |
08-10 |
U20 |
Mere om merging og hashing (side 16-18 i slides
med
overlays/uden overlays).
[For yderligere detaljer (ikke pensum) om
hashing i Python, se her.
For Java, se her.
]
|
| 39 |
F |
Onsdag 23/9 |
10-12 |
U20 |
Studiestrategi, tidstyring, noteteknikker. Se Itslearning for
materialer.
|
| 39(-40) |
E |
|
|
|
Opgaver.
Løsninger (med nummerering fra E21).
|
| 40 |
F |
Mandag 28/9 |
12-14 |
U47 |
Første del (ud af seks) af eksamen i DM595: 30 minutters online
multiple-choice test i klassen. Bemærk at lokalet er U47. Pensum for
denne del er materialerne om repræsentation af tal, Boolsk algebra og
gates. For alle emner inkluderer materialerne både slides og de
tilhørende opgaver i øvelsestimerne (uge 37(-38) og uge
38(-39)). Evt. yderligere materiale angivet i gråt og med betegnelsen
"(ikke pensum)" er naturligvis ikke med i pensum.
Datalogiens historie (slides med
overlays/uden overlays). Disse
emner er ikke eksamenspensum, dvs. vil ikke danne baggrund for
eksamensspørgsmål. For nogle danskere med indflydelse på datalogiens
historie, se
denne
artikel på dr.dk. For mere om Charles Babbage, se
Computer History
Museum.
|
| 40 |
F |
Onsdag 30/9 |
08-10 |
U20 |
Afslutning af merging og hashing (resten af slides
med
overlays/uden overlays)
|
| 40 |
F |
Onsdag 30/9 |
10-12 |
U20 |
IMADAs fagråd.
|
| 40(-41) |
E |
|
|
|
Opgaver.
Løsninger (med nummerering fra E21).
|
| 41 |
F |
Mandag 5/10 |
12-14 |
U20 |
Start på modeller for beregning: DFA (side 1-75 i
slides af Fabrizio Montesi).
Programmet vist til forelæsningen, som tester, om en
given streng bliver accepteret af en DFA.
[For yderligere materiale (ikke pensum) om
DFA'er, se f.eks. noter
2 og noter
3 af Sariel Har-Peled og Madhusudan Parthasarathy.]
|
| 41 |
F |
Onsdag 7/10 |
08-10 |
U20 |
Mere om modeller for beregning: CFG (resten af
slides af Fabrizio Montesi).
[For yderligere materiale (ikke pensum) om
CFG'er, se f.eks. noter
11 af Sariel Har-Peled og Madhusudan Parthasarathy.
En vigtig anvendelse af CFG'er er at definere syntaksen for
programmeringssprog, ofte med notationen kaldet (extended) Backus–Naur
form. Navnet "Naur" refererer i øvrigt her til Peter
Naur, som er den eneste dansker, der har modtaget Turing
prisen (også kaldet datalogiens Nobelpris).]
|
| 41(-43) |
E |
|
|
|
Opgaver.
Løsninger (med nummerering fra E21).
|
| 43 |
F |
Mandag 19/10 |
12-14 |
U47 |
Anden del (ud af seks) af eksamen i kurset: 30 minutters online
multiple-choice test i klassen. Bemærk at lokalet er U47. Pensum for
denne del er materialerne om CPUer og maskinkode og materialerne om
algoritmer, asymptotisk notation og invarianter. For alle emner
inkluderer materialerne både slides og de tilhørende opgaver i
øvelsestimerne (uge 39(-40) og uge 40(-41)). Evt. yderligere materiale
angivet i gråt og med betegnelsen "(ikke pensum)" er naturligvis ikke
med i pensum.
Mere om modeller for beregning: CFG vs. DFA (resten af
slides af Fabrizio Montesi).
|
| 43 |
F |
Onsdag 21/10 |
08-10 |
U20 |
Mere om modeller for beregning: regulære udtryk (side 1-16 samt 24 i
slides med
overlays/uden overlays).
Eksempelprogram vist til forelæsning og
tilhørende datafil med
godkendte personnavne
(data
kommer fra
Familieretshuset,
version fra 2026.10.20).
[Yderligere materiale (ikke pensum): For de
fulde detaljer om regulære udtryk i Python, se dokumentationen for
modulet re og Regular Expression
Howto for Python. For et hurtigt og velstruktureret overblik (og
meget andet) over regulære udtryk, se f.eks. dette Regex
Cheat Sheet. Hvis man vil vide mere om effektiv implementation af
søgning med regulære udtryk og sammenhængen med forskellige typer
endelige automater, se denne webside
af Russ Cox.]
|
| 43 |
F |
Onsdag 21/10 |
10-12 |
U20 |
God akademisk praksis og eksamensformer, ved Søren Sten Hansen. Se
Itslearning for materialer og instruktioner om forberedelse til
timen.
|
| 43(-44) |
E |
|
|
|
Opgaver.
Løsninger (med nummerering fra E21).
|
| 44 | F | Mandag 26/10 |
12-14 |
U47 |
Mere om modeller for beregning: afslutning af regulære udtryk (resten
af slides med
overlays/uden overlays).
Afrunding af modeller for beregning: start på beregnelighed, Turing
maskiner, halting problemet (side 1-10 i slides
med
overlays/uden overlays).
Dette sæt slides er ikke eksamenspensum, dvs. vil ikke danne baggrund
for eksamensspørgsmål.
|
| 44 | F | Onsdag 28/10 |
08-10 |
U20 |
Afrunding af modeller for beregning: afslutning af beregnelighed,
Turing maskiner, halting problemet (resten af slides
med
overlays/uden overlays).
Dette sæt slides er ikke eksamenspensum, dvs. vil ikke danne baggrund
for eksamensspørgsmål.
[For yderligere materiale (ikke pensum) om
modeller for beregning og om beregnelighed, se f.eks. samlingen af
lecture notes fra Sariel
Har-Peleds og Madhusudan Parthasarathys kursus eller Jeff
Ericksons notesæt. En
online simulator for Turing maskiner, inkl. mange eksempler på
konkrete maskiner, kan findes her. Læs mere om Turings
imponerende bedrifter på Wikipedia.]
Start på satisfiability: intro (slides med
overlays/uden overlays).
|
| 44 |
F |
Onsdag 28/10 |
10-12 |
U20 |
Studiehjælpstilbud på IMADA, ved Peter Bækgaard Von Lehnsburg.
|
| 44(-45) |
E |
|
|
|
Opgaver.
|
| 45 | F | Mandag 2/11 | 14-16 | U20 |
Tredie del (ud af seks) af eksamen i kurset: 35 minutters online
multiple-choice test i klassen. Pensum for denne del er materialerne
om merging og hashing og materialerne om DFA'er og om CFG'er. For alle
emner inkluderer materialerne både slides og de tilhørende opgaver i
øvelsestimerne (uge 41(-43) og uge 43(-44)). Evt. yderligere materiale
angivet i gråt og med betegnelsen "(ikke pensum)" er naturligvis ikke
med i pensum.
Mere om satisfiability: slides fra
Peter Schneider-Kamp. Eksamensrelevant indhold af Peters slides: side
3-23 og 35-36. Bemærk, at i Peters slides bruges ordene "conjunction"
for AND og "disjunction" for OR. For en beskrivelse af inputformatet
til SAT solvers, se afsnit 4.1 i
dette
svar på StackExchange.
|
| 45 | F | Onsdag 4/11 | 10-12 | U20 |
Afslutning af satisfiability: slides
fra Peter Schneider-Kamp. Eksamensrelevant indhold af Peters slides:
side 3-23 og 35-36. For en beskrivelse af inputformatet til SAT
solvers, se afsnit 4.1 i
dette
svar på StackExchange.
Lidt om kompleksitet og P vs. NP problemet: side 27-31 i
slides fra
UNF
foredrag april 2023 (dette sæt slides er ikke eksamenspensum,
dvs. vil ikke danne baggrund for eksamensspørgsmål).
[For yderligere materiale (ikke pensum) om
Satisfiability, SAT-solvers, og brugen til modellering og løsning af
kombinatoriske problemer, se f.eks. Işıl
Dilligs slides og Simon Prince's tutorial.
For indsigt i algoritmerne inden i SAT-solvers, se Simon Prince og
Christopher Srinivasa's tutorial
og Inês Lynce's slides. For mere
om udviklingen af SAT-solvers evner, se denne artikel. For
en liste over SAT-solvers (og mange andre relaterede ressourcer), se
Matt
Gibsons oversigt.]
|
| 45(-46) |
E |
|
|
|
Opgaver.
For at afprøve ens CNF-programmer kan man bruge
dette
web-interface til SAT-solveren MiniSat. Her er
et CNF-program for 2x2 tower, som man kan bruge
som test. Hvis man gerne vil installere Lingeling på egen computer (et
alternativ foreslået i opgaverne), kan man downloade og kompilere
source eller
f.eks. installere den via
Devbox.
|