Kurset starter torsdag den 5. september. Der skal ikke købes nogen lærebog.
Pensum til eksamen er alt materiale (som regel slides) angivet på denne
webside under F-timer. Hvis der til et punkt 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 |
Torsdag 5/9 |
14-16 |
U23 |
Kursusintroduktion.
Repræsentation af tal (side
1-12). Programmet binexpand.py vist til
forelæsningen.
|
| 37 |
F |
Onsdag 11/9 |
08-10 |
U42 |
Afslutning af Repræsentation af tal (side
13-19). Programmet brugt til
forelæsningen til at vise bits i filer (ikke pensum).
|
| 37 |
F |
Fredag 13/9 |
12-14 |
U23
|
Boolsk algebra og gates.
|
| 37(-38) |
E |
|
|
|
Opgaver.
Løsninger (med nummerering fra E21).
|
| 38 |
F |
Tirsdag 17/9 |
08-10 |
U42 |
Afslutning af Boolsk algebra og gates. [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. CPU
simulator (Johan Fagerberg,
baseret på forlæg af J. Glenn Brookshear).
|
| 38 |
F |
Torsdag 19/9 |
10-12 |
U23 |
Afslutning af CPUer og maskinkode. 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.
|
| 38(-39) |
E |
|
|
|
Opgaver. Løsninger (med nummerering fra E21).
|
| 39 |
F |
Mandag 23/9 |
10-12 |
U42 |
Afslutning på algoritmer, asymptotisk notation,
invarianter, ved Lene Monrad Favrholdt.
|
| 39 |
F |
Onsdag 25/9 |
08-10 |
U48A |
Start på merging og hashing.
|
| 39(-40) |
E |
|
|
|
Opgaver. Løsninger (med nummerering fra E21).
|
| 40 |
F |
Mandag 30/9 |
14-16 |
U48A |
Første del (ud af seks) af eksamen i kurset: 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)). For evt. yderligere
materiale angivet i gråt og med betegnelsen "(ikke pensum)" er dette
naturligvis ikke med i pensum.
Mere om merging og hashing.
|
| 40 |
F |
Torsdag 3/10 |
14-16 |
U48A |
Afslutning af merging og hashing. [For yderligere detaljer (ikke pensum) om hashing
i Python, se her.
For Java, se her
og her.]
|
| 40(-41) |
E |
|
|
|
Opgaver. Løsninger (med nummerering fra E21).
|
| 41 | F | Mandag 7/10 | 10-12 | U55 |
Start på modeller for beregning:
DFA (slides ved Fabrizio
Montesi). [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 9/10 |
14-16 |
U55 |
Mere om modeller for beregning:
CFG (slides ved Fabrizio
Montesi) og regulære udtryk. [For yderligere materiale (ikke pensum) om CFG'er,
se f.eks. noter
11 af Sariel Har-Peled og Madhusudan Parthasarathy.]
|
| 41(-43) |
E |
|
|
|
Opgaver. Løsninger (med nummerering fra E21).
|
| 43 | F | Mandag 21/10 | 14-16 | U55 |
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)). For evt. yderligere materiale angivet i gråt og med
betegnelsen "(ikke pensum)" er dette naturligvis ikke med i pensum.
Mere om modeller for beregning: regulære udtryk.
|
| 43 | F | Onsdag 23/10 | 10-11 | U23 |
Mere om modeller for beregning: regulære
udtryk. 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(-44) |
E |
|
|
|
Opgaver. Løsninger (med nummerering fra E21).
|
| 44 | F | Onsdag 30/10 | 08-10 | U23 |
Afslutning af modeller for beregning:
beregnelighed, Turing maskiner, halting
problemet. 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 kan findes her. Læs mere om Turings
imponerende bedrifter på Wikipedia.]
|
| 44 | F | Fredag 1/11 | 10-12 | U23 |
Overblik og status for kursets
emner. Start på databaser. 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).
|
| 44(-45) |
E |
|
|
|
Opgaver. Løsninger (med nummerering fra E21).
|
| 45 | F | Mandag 4/11 | 14-16 | U23 |
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)). For evt. yderligere
materiale angivet i gråt og med betegnelsen "(ikke pensum)" er dette
naturligvis ikke med i pensum.
Afslutning på databaser. Et eksempel på et ER-diagram, dets oversættelse til den relationelle model og til SQL, samt nogle queries.
[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 7/11 | 10-12 | U23 |
Satisfiability (intro-slides samt
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 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 bag SAT-solvers, se Simon Prince og
Christopher Srinivasa's tutorial
og Inês Lynce's slides.]
|
| 45(-46) |
E |
|
|
|
Opgaver. Løsninger (med nummerering fra E21).
|
| 46 | F | Mandag 11/11 | 14-16 | U48A |
Start på korteste veje i grafer
(kode fra slides), materiale ved Daniel
Merkle.
|
| 46 | F | Onsdag 13/11 | 08-10 | U48A |
Mere om korteste veje i grafer,
materiale ved Daniel Merkle. Note med bevis
for den centrale sætning om min-plus matrix-multiplikation og korteste
veje.
|
| 46(-47) |
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), er her en
vejledning
for Linux.
|
| 47 | F | Mandag 18/11 | 12-14 | U55 |
Fjerde del (ud af seks) af eksamen i kurset: 30 minutters online
multiple-choice test i klassen. Pensum for denne del er materialerne
om regulære udtryk og materialerne om databaser. For begge emner
inkluderer materialet både slides og de tilhørende opgaver i
øvelsestimerne (opgaver uge 44(-45) og uge 45(-46)). For
evt. yderligere materiale angivet i gråt er dette ikke med i pensum.
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]
|
| 47 |
F |
Onsdag 20/11 |
08-10 |
U48A |
Start på kryptologi. Pythonprogram til brute-force attack
på Caesar cipher. [For yderligere materiale
(ikke pensum): Her er en side med
oversigt over krypteringsteknologier relevante for SSL/TLS-protokollen,
der bl.a. er grundlaget for de sikre webforbindelser
(HTTPS), som vi bruger dagligt. Her er en
side, som beskriver rekorder for faktorisering af
RSA-nøgler. Disse rekorder en noget af baggrunden for, at man for
RSA anbefaler nøgler N med mindst 2048 bits.]
|
| 47(-48) |
E |
|
|
|
Opgaver.
|