Kurset starter mandag den 1. september. Der skal ikke købes nogen
lærebog.
Pensum til eksamen i DM573 er materialet (som regel slides) angivet på
denne webside under de relevante 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 |
Mandag 1/9 |
12-14 |
U55 |
DM500: Mød din studiegruppe. Introduktion til SDUs systemer, ved Søren
Sten Hansen. Se Itslearning for materialer.
|
| 36 |
F |
Tirsdag 2/9 |
12-14 |
U23 |
Kursusintroduktion (slides med
overlays/uden overlays).
Repræsentation af tal (side 1-9 i slides med
overlays/uden overlays).
|
| 36 |
F |
Torsdag 4/9 |
10-12 |
U1 |
Afslutning af repræsentation af tal (side 10-19 i slides
med
overlays/uden overlays).
Programmet brugt til forelæsningen til at vise
bits i filer (ikke pensum).
|
| 37 |
F |
Tirsdag 9/9 |
12-14 |
U23
|
Boolsk algebra og gates (side 1-18 i slides med
overlays/uden overlays).
Programmet binexpand.py vist til forelæsningen.
|
| 37 |
F |
Torsdag 11/9 |
08-10 |
U23 |
Afslutning af Boolsk algebra og gates (resten af 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 indeholder indeholder over 1010 transistorer - se en
oversigt over den vilde udvikling i antallet her.
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. Se evt. også
denne artikel.]
Start på CPUer og maskinkode (side 1-11 i slides
med
overlays/uden overlays).
|
| 37 |
F |
Torsdag 11/9 |
10-12 |
U140 |
DM500: Studiegrupper, studiegruppekontrakter. Se Itslearning for
materialer.
|
| 37(-38) |
E |
|
|
|
Opgaver.
Løsninger (med nummerering
fra E21).
|
| 38 |
F |
Tirsdag 16/9 |
12-14 |
U23 |
Afslutning af CPUer og maskinkode (resten af 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.
[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.]
Start på algoritmer, asymptotisk notation,
invarianter, ved Lene Monrad Favrholdt. 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 |
Torsdag 18/9 |
08-10 |
U23 |
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.
|
| 38 |
F |
Torsdag 18/9 |
10-12 |
U1 |
DM500: Studievejlederne, ved Peter Mertz. Se Itslearning for
materialer.
|
| 38(-39) |
E |
|
|
|
Opgaver.
Løsninger (med nummerering
fra E21).
|
| 39 |
F |
Tirsdag 23/9 |
10-12 |
U1 |
Afslutning af algoritmer, asymptotisk notation,
invarianter, ved Lene Monrad Favrholdt.
[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).]
|
| 39 |
F |
Torsdag 25/9 |
08-10 |
U23 |
Start på merging og hashing (side 1-14 i slides
med
overlays/uden overlays)
|
| 39 |
F |
Torsdag 25/9 |
10-12 |
|
DM500: Studiestrategi, tidstyring, noteteknikker. Se Itslearning for
materialer.
|
| 39(-40) |
E |
|
|
|
Opgaver.
Løsninger (med nummerering fra E21).
|
| 40 |
F |
Tirsdag 30/9 |
12-14 |
U23 |
Første del (ud af seks) af eksamen i DM573: 30 minutters online
multiple-choice test i klassen. 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.
Mere om merging og hashing (side 15-17 i slides
med
overlays/uden overlays)
|
| 40 |
F |
Torsdag 2/10 |
08-10 |
U23 |
Afslutning af merging og hashing (sidste del af slides
med
overlays/uden overlays).
[For yderligere detaljer (ikke pensum) om
hashing i Python, se her.
For Java, se her
og her.]
|
| 40 |
F |
Torsdag 2/10 |
10-12 |
U23 |
DM500: IMADAs fagråd. Se Itslearning for materialer.
|
| 40(-41) |
E |
|
|
|
Opgaver.
Løsninger (med nummerering fra E21).
|
| 41 | F | Mandag 6/10 | 10-12 | U150 |
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 |
Torsdag 9/10 |
08-10 |
U42 |
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 |
F |
Torsdag 9/10 |
10-12 |
|
DM500: Introduktion til LaTeX. Se Itslearning for materialer.
|
| 41(-43) |
E |
|
|
|
Opgaver. Løsninger (med nummerering fra E21).
|
| 43 | F | Tirsdag 21/10 | 10-12 | U23 |
Anden del (ud af seks) af eksamen i kurset: 30 minutters online
multiple-choice test i klassen. 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: regulære udtryk (slides
med
overlays/uden overlays).
Info om eksamen i DM500.
|
| 43 | F | Torsdag 23/10 | 08-10 | U23 |
Mere om modeller for beregning: afslutning af regulære udtryk (slides
med
overlays/uden overlays).
Eksempelprogram vist til forelæsning
og tilhørende datafil med
godkendte personnavne (data kommer fra
Familieretshuset,
version fra 2024.09.16).
[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 |
Torsdag 23/10 |
10-12 |
U23 |
DM500: 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 | Tirsdag 28/10 | 10-12 | U23 |
Afslutning af modeller for beregning: beregnelighed, Turing maskiner,
halting problemet (slides med
overlays/uden overlays).
Dette sæt slides er ikke eksamenspensum, dvs. vil ikke danne baggrund
for eksamensspørgsmål.
Start på satisfiability: intro (slides med
overlays/uden overlays).
[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 kan findes her. Læs mere om Turings
imponerende bedrifter på Wikipedia.]
|
| 44 | F | Torsdag 30/10 | 10-12 | U1 |
Afslutning af 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.
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.]
|
| 44 |
F |
Torsdag 30/10 |
12-14 |
|
DM500: Introduktion til Git. Se Itslearning for materialer.
|
| 44(-45) |
E |
|
|
|
Opgaver.
Løsninger (med
nummerering fra E21).
|
| 45 | F | Tirsdag 4/11 | 10-12 | U1 |
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.
Start på databaser.
|
| 45 | F | Torsdag 6/11 | 10-12 | U23 |
Afslutning på databaser. Et
eksempel på et ER-diagram, dets oversættelse
til den relationelle model og til SQL, samt nogle queries. Linket til
sitet
vist til forelæsningen, hvor man kan udføre SQL. En samling
eksempler på SQL-søgninger på data i dette
link, også vist til forelæsningen. Hvis man gerne vil installere en
relationel database selv, er
PostgreSQL og
MySQL to veludbyggede open-source
muligheder.
[For yderligere materiale (ikke pensum) om
ER-modellen, relational algebra og SQL, se f.eks. Christopher
Painter‑Wakefields online bog
A Practical Introduction to Databases, Johannes
Gehrkes slides, Tutorialspoints,
w3school, Khan
Academy, Phil Spectors
slides, PostgreSQLs
dokumentation.]
|
| 45 |
F |
Torsdag 6/11 |
12-13 |
U23 |
DM500: Introduktion til kompetenceportfolio. Se Itslearning for
beskrivelse.
|
| 45(-46) |
E |
|
|
|
Opgaver.
Løsninger (med nummerering
fra E21) og tilhørende
Python-programmer. 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), er her en
vejledning
for Linux.
|
| 46 | F | Tirsdag 11/11 | 10-12 | U23 |
Start på kryptologi.
|
| 46 |
F |
Onsdag 12/11 |
09-10 |
U55 |
DM500: Orientering om kursustilmelding.
|
| 46 | F | Torsdag 13/11 | 10-12 | U1 |
Mere om på kryptologi.
|
| 46 |
F |
Torsdag 13/11 |
12-14 |
|
DM500: Introduktion til kommandolinjen. Se Itslearning for materialer.
|
| 46(-47) |
E |
|
|
|
Opgaver.
|
| 47 | F | Tirsdag 18/11 | 10-12 | U23 |
Fjerde del (ud af seks) af eksamen i kurset: 25 minutters online
multiple-choice test i klassen. Pensum for denne test er materialerne
om regulære udtryk og materialerne om satisfiability. For alle emner
inkluderer materialet både slides og de tilhørende opgaver i
øvelsestimerne (opgaver uge 44(-45) og uge 45(-46)). Evt. yderligere
materiale angivet i gråt og med betegnelsen "(ikke pensum)" er
naturligvis ikke med i pensum.
Afslutning af kryptologi. Emnerne fra dele af
slides kan også læses i dette notesæt om de
algoritmiske aspekter af RSA (er en del af pensum).
[For yderligere materiale (ikke pensum):
Keith Conrad har mange velskrevne noter om
dette emne (og meget andet), se f.eks. hans noter om Fermats
lille sætning, Fermat-testen,
Carmichael-tal,
og Miller-Rabin-testen.]
|
| 47 | F | Torsdag 20/11 | 10-12 | U1 |
Online algoritmer, ved Kim Skak Larsen.
|
| 47 |
F |
Torsdag 20/11 |
12-14 |
U23 |
DM500: Studiehjælpstilbud på IMADA, ved Peter Bækgaard Von Lehnsburg.
|
| 47(-48) |
E |
|
|
|
Opgaver.
|
| 48 | F | Tirsdag 25/11 | 10-12 | U1 |
Start på korteste veje i grafer,
materiale ved
Daniel Merkle.
|
| 48 | F | Torsdag 27/11 | 10-12 | U1 |
Afslutning af korteste veje i grafer,
materiale ved Daniel Merkle. I nogle af figurerne på slides er
molekyler vist som skeletal formulas, hvor C-atomer og H-atomer ikke
skrives direkte - principperne for dette kan man f.eks. finde
her.
[For yderligere materiale (ikke pensum) om
alkaner, se f.eks. kapitel
7 i denne online lærebog fra Western Oregon University]
|
| 48 |
F |
Torsdag 27/11 |
12-14 |
|
DM500: Kommandolinje-scripts.
|
| 48(-49) |
E |
|
|
|
Opgaver.
|