Kurset starter mandag den 4. 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 |
Mandag 4/9 |
12-14 |
U1 |
Kursusintroduktion.
Repræsentation af tal ved Rolf Fagerberg.
|
| 36 |
F |
Tirsdag 5/9 |
14-16 |
U55 |
Afslutning af Repræsentation af tal.
|
| 37 |
F |
Tirsdag 12/9 |
12-14 |
U23
|
Boolsk algebra og gates ved Rolf Fagerberg.
|
| 37 |
F |
Onsdag 13/9 |
14-16 |
U1 |
Afslutning af Boolsk algebra og gates. [Yderligere kommentarer (ikke pensum): Moderne CPU'er
indeholder indeholder over 10^10 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 . Se også
denne artikel.]
Start på CPUer og maskinkode, ved Rolf
Fagerberg.
|
| 37(-38) |
E |
|
|
|
Opgaver. Løsninger
(med nummerering fra E21).
|
| 38 |
F |
Tirsdag 19/9 |
12-14 |
U23
|
Afslutning af CPUer og maskinkode, ved Rolf
Fagerberg. 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.
|
| 38 |
F |
Onsdag 20/9 |
08-10 |
U170
|
Afslutning på algoritmer, asymptotisk notation,
invarianter, ved Lene Monrad Favrholdt.
|
| 38(-39) |
E |
|
|
|
Opgaver. Løsninger
(med nummerering fra E21).
|
| 39 |
F |
Tirsdag 26/9 |
12-14 |
U23
|
Start på merging og hashing, ved Rolf
Fagerberg.
|
| 39 |
F |
Onsdag 27/9 |
14-16 |
U1 |
Afslutning af merging og hashing, ved Rolf
Fagerberg.
|
| 39(-40) |
E |
|
|
|
Opgaver. Løsninger (med nummerering fra E21).
|
| 40 |
F |
|
|
|
Bemærk at der ikke er nogen forelæsninger i denne uge.
|
| 40(-41) |
E |
|
|
|
Opgaver. Løsninger (med nummerering fra E21).
|
| 41 |
F |
Tirsdag 10/10 |
12-14 |
U23 |
Start på databaser, ved Rolf Fagerberg.
|
| 41 |
F |
Onsdag 11/10 |
14-16 |
U1 |
Første del (ud af seks) af eksamen i kurset: 30 minutters online
multiple-choice test i klassen. Pensum for denne eksamen vil være
materialerne om repræsentation af tal, Boolsk algebra og gates. For
alle emner inkluderer materialet både slides og de tilhørende opgaver
i øvelsestimerne (ugerne 37(-38) og 38(-39)). For evt. yderligere
materiale angivet i gråt og med betegnelsen "(ikke pensum)" er dette
naturligvis ikke med i pensum.
Slut på databaser, ved Rolf Fagerberg.
[For yderligere materiale (ikke pensum) om
relational algebra og om SQL, se f.eks. Johannes
Gehrke's slides, Tutorialspoints,
w3school, Khan
Academy, Phil Spector's
slides, PostgreSQL's
dokumentation.]
|
| 41(-43) |
E |
|
|
|
Opgaver. Løsninger (med nummerering fra E21).
|
| 43 |
F |
Mandag 23/10 |
16-18 |
U42 |
Satisfiability (intro-slides samt
slides fra Peter Schneider-Kamp), ved
Rolf Fagerberg. 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.
|
| 43 |
F |
Onsdag 25/10 |
16-18 |
U1 |
Afslutning af Satisfiability (intro-slides
samt slides fra Peter
Schneider-Kamp), ved Rolf Fagerberg. Eksamensrelevant indhold af
Peters slides: side 3-23 og 35-36. [For
yderligere materiale (ikke pensum) om Satisfiability og dets brug
til modellering og løsning af kombinatoriske problemer, se
f.eks. slides fra Işıl
Dilligs kursus]
|
| 43(-44) |
E |
|
|
|
Opgaver. Løsninger
(med nummerering fra E21).
|
| 44 |
F |
Tirsdag 31/10 |
12-14 |
U23 |
Supervised Learning and
Clustering, ved Melih Kandemir. Eksamensrelevant indhold: side 32-45.
|
| 44 |
F |
Fredag 3/11 |
12-14 |
U55 |
Mere om Supervised Learning
and Clustering, ved Melih Kandemir. Eksamensrelevant indhold: side
32-45.
Anden del (ud af seks) af eksamen i kurset: 40 minutters online
multiple-choice test i klassen. Pensum for denne eksamen vil være
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
(ugerne 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.
|
| 44(-45) |
E |
|
|
|
Opgaver. Løsninger
(med nummerering fra E21) og tilhørende
Python-programmer. For at afprøve ens
CNF-programmer kan man bruge følgende web-interface til
SAT-solveren MiniSat (den virker bedre end
web-interfacet
til CryptoMiniSat nævnt i opgaverne). Her er et
CNF-program for 2x2 tower, 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.
|
| 45 |
F |
Tirsdag 7/11 |
12-14 |
U23 |
Afslutning af Supervised
Learning and Clustering, ved Melih Kandemir. Eksamensrelevant
indhold: side 32-45. [For yderligere materiale
(ikke pensum), se f.eks. side 1-10 af Zijun Zhangs slides
om k-means og side 1-28 af David Sontags
slides om k-means].
Start på modeller for
beregning, ved Rolf Fagerberg (slides ved Fabrizio Montesi). [For yderligere materiale (ikke pensum) om DFA'er,
se f.eks. slides
af Henrik Nilsson.]
|
| 45 |
F |
Fredag 10/11 |
12-14 |
U1 |
Mere om modeller for beregning,
ved Rolf Fagerberg (slides ved Fabrizio Montesi). [For yderligere materiale (ikke pensum) om CFG'er,
se f.eks. slides
1 (et sprog er regulært, hvis der findes en DFA som genkender
strengene i sproget) og slides
2 af Henrik Nilsson.]
Tredie del (ud af seks) af eksamen i kurset: 40 minutters online
multiple-choice test i klassen. Pensum for denne eksamen vil være
materialerne om merging og hashing og materialerne om databaser. For
alle emner inkluderer materialerne både slides og de tilhørende
opgaver i øvelsestimerne (ugerne 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.
|
| 45(-46) |
E |
|
|
|
Opgaver. Løsninger
(med nummerering fra E21).
|
| 46 |
F |
Tirsdag 14/11 |
12-14 |
U23 |
Start på regulære udtryk, ved Rolf Fagerberg.
Midtvejsevaluering af kurset.
|
| 46 |
F |
Onsdag 15/11 |
08-10 |
U23 |
Afslutning af regulære udtryk, ved Rolf
Fagerberg. Eksempelprogram vist til
forelæsning og tilhørende datafil med
godkendte personnavne (data kommer fra
Familieretshuset).
[For de fulde detaljer om regulære udtryk i
Python, se dokumentationen for
modulet re og Regular Expression
HOWTO. 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 (ikke pensum).]
|
| 46(-47) |
E |
|
|
|
Opgaver.
Løsninger (med
nummerering fra E21).
|
| 47 |
F |
Tirsdag 21/11 |
12-14 |
U23 |
Start på korteste veje i grafer
(kode fra slides), ved Daniel Merkle.
|
| 47 |
F |
Onsdag 22/11 |
14-16 |
U1 |
Afslutning af korteste veje i grafer
(kode fra slides), ved Daniel Merkle.
Fjerde del (ud af seks) af eksamen i kurset: 35 minutters online
multiple-choice test i klassen. Pensum for denne eksamen vil være
materialerne om Satisfiability og materialerne om Clustering (mens
Supervised Learning er ikke en del af eksamenpensum). For alle emner
inkluderer materialerne både slides og de tilhørende opgaver i
øvelsestimerne (ugerne 44(-45) og 45(-46)). For evt. yderligere
materiale angivet i gråt og med betegnelsen "(ikke pensum)" er dette
naturligvis ikke med i pensum.
|
| 47(-48) |
E |
|
|
|
Opgaver. Løsninger
(med nummerering fra E21).
|
| 48 |
F |
Mandag 27/11 |
08-10 |
U1 |
Online algoritmer, ved Kim
Skak Larsen.
|
| 48 |
F |
Onsdag 29/11 |
14-16 |
U1 |
Datalogiens historie, ved Rolf
Fagerberg. Dette emne 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.
|
| 48(-49) |
E |
|
|
|
Opgaver. Løsninger
(med nummerering fra E21).
|
| 49 |
F |
Tirsdag 5/12 |
12-14 |
U23 |
Start på kryptologi, ved Rolf Fagerberg. 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.]
|
| 49 |
F |
Onsdag 6/12 |
14-16 |
U1 |
Afslutning på kryptologi, ved Rolf Fagerberg. 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 Rabin-Miller-testen.]
Femte del (ud af seks) af eksamen i kurset: 50 minutters online
multiple-choice test i klassen. Pensum for denne eksamen vil være
materialerne om modeller for beregning, regulære udtryk og korteste
veje. For alle emner inkluderer materialerne både slides og de
tilhørende opgaver i øvelsestimerne (uge 46(-47), 47(-48) og
48(-49)). For evt. yderligere materiale angivet i gråt og med
betegnelsen "(ikke pensum)" er dette naturligvis ikke med i pensum.
|
| 49(-50) |
E |
|
|
|
Opgaver. Løsninger
(med nummerering fra E21).
|
| 50 |
F |
Tirsdag 12/12 |
12-14 |
U23 |
3D-grafik, ved Rolf Fagerberg. [Dette er ikke
eksamenspensum, dvs. vil ikke danne baggrund for eksamensspørgsmål.]
|
| 50 |
E |
|
|
|
Opgaver.
Løsninger del 1 og
del 2 (med nummerering fra
E21 og med svar på flere opgaver end her i E23).
|
| 51 |
F |
Tirsdag 19/12 |
12-13 |
U23 |
Sjette del (ud af seks) af eksamen i kurset: 45 minutters online
multiple-choice test i klassen. Pensum for denne eksamen vil være
materialerne om online algoritmer og om kryptologi. For alle emner
inkluderer materialerne både slides og de tilhørende opgaver i
øvelsestimerne (uge 49-50 og uge 50). Også notesættet om de
algoritmiske aspekter af RSA er pensum. For evt. yderligere materiale
angivet i gråt og med betegnelsen "(ikke pensum)" er dette naturligvis
ikke med i pensum.
|