DM534/DM558 Introduktion til Datalogi

Efterår 2021
Rolf Fagerberg

• Officiel kursusbeskrivelse
• Instruktorer
• Skema

Kurset starter mandag den 6. 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).

Vi forsøger i år at optage alle forelæsninger. Kvaliteten vil være moderat, og optagelsen er alene ment som en service, der tillader at man kan gennemse forelæsningen igen bagefter. Det kan ikke anbefales som et alternativ til at være til stede fysisk ved selve forelæsningen.

Timer

Uge	Type	Dato	Tid	Lokale	Indhold
36	F	Mandag 6/9	12-14	U20	Kursusintroduktion. Repræsentation af tal (optagelse fra forelæsning), ved Rolf Fagerberg.
36	F	Onsdag 8/9	10-12	U50A	Boolsk algebra og gates (optagelse fra forelæsning), ved Rolf Fagerberg.
36(-37)	E				Opgaver
37	F	Onsdag 15/9	10-12	U53	CPUer og maskinkode (optagelse fra forelæsning), 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.]
37(-38)	E				Opgaver
38	F	Mandag 20/9	12-14	U20	Start på algoritmer, asymptotisk notation, invarianter (optagelse fra forelæsning), ved Lene Monrad Favrholdt.
38	F	Onsdag 22/9	10-12	U21	Afslutning af algoritmer, asymptotisk notation, invarianter (optagelse fra forelæsning), ved Lene Monrad Favrholdt. [For yderligere materiale (ikke pensum) om asymptotisk notation, se f.eks. slides fra DM507 og forklaring fra Khan Academy. For yderligere materiale (ikke pensum) om invarianter, se f.eks. slides fra DM507 og side fra Stefan Nilsson.]
38(-39)	E				Opgaver
39	F	Mandag 27/9	12-14	U20	Start på merging og hashing (optagelse fra forelæsning), ved Rolf Fagerberg.
39	F	Onsdag 29/9	10-12	U1	Afslutning af merging og hashing (optagelse fra forelæsning [rettelse: alle ulighedstegn tegnet på tavlen mellem 10:10 og 11:00 skal vendes]), ved Rolf Fagerberg. Første 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 repræsentation af tal, Boolsk algebra og gates, samt CPUer og maskinkode. For alle emner inkluderer materialet både slides og de tilhørende opgaver i øvelsestimerne (ugerne 36(-37), 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.
39(-40)	E				Opgaver
40	F	Mandag 4/10	12-14	U20	Start på machine learning (optagelse fra forelæsning), ved Marco Chiarandini. Se også Marco's supplerende note om emnet (er en del af pensum).
40	F	Mandag 6/10	10-12	U47	Afslutning af machine learning, (optagelse fra forelæsning), ved Marco Chiarandini. Se også Marco's supplerende note om emnet (er en del af pensum).
40(-41)	E				Opgaver
41	F	Mandag 11/10	12-14	U20	Start på feature spaces and clustering (optagelse fra forelæsning), ved Melih Kandemir. [For yderligere materiale (ikke pensum) om Lp-normer, se f.eks. dette underafsnit af den engelske Wikipedia-side om Lp-rum..] 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 algoritmer, asymptotisk notation og invarianter (Lene Monrad Favrholdt) og om merging og hashing (Rolf Fagerberg). For alle emner inkluderer materialet både slides og de tilhørende opgaver i øvelsestimerne (ugerne 39(-40) og 40(-41)). For evt. yderligere materiale angivet i gråt og med betegnelsen "(ikke pensum)" er dette naturligvis ikke med i pensum.
41	F	Onsdag 13/10	10-12	U47	Slut på feature spaces and clustering (optagelse fra forelæsning), ved Melih Kandemir. [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].
41(-43)	E				Opgaver (løsninger).
43	F	Mandag 25/10	12-14	U20	Start på modeller for beregning (optagelse fra forelæsning), ved Fabrizio Montesi. [For yderligere materiale (ikke pensum) om DFA'er, se f.eks. slides af Henrik Nilsson.]
43	F	Onsdag 27/10	09-10	U51	Afslutning af modeller for beregning (optagelse fra forelæsning), 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.]
43(-44)	E				Opgaver.
44	F	Mandag 1/11	12-14	U20	Online algoritmer (optagelse fra forelæsning, desværre med meget lav lyd, optagelse af den tilsvarende forelæsning (på Zoom) fra efterår 2020), ved Kim Skak Larsen.
44(-45)	E				Opgaver (svar).
45	F	Mandag 8/11	12-14	U20	Satisfiability (ingen optagelse af forelæsningen pga. tekniske problemer, optagelse af den tilsvarende forelæsning fra efterår 2020), ved Peter Schneider-Kamp. Eksamensrelevant indhold: side 3-23 og 35-36.
45	F	Onsdag 10/11	10-12	U55	Datalogiens historie (audio på optagelse af forelæsningen desværre ubrugelig pga. højttalerlyden i lokalet, optagelse af den tilsvarende forelæsning (på Zoom) fra efterår 2020), ved Rolf Fagerberg. Dette emne er ikke eksamenspensum, dvs. vil ikke danne baggrund for eksamensspørgsmål. For nogle danskere med indflydelse datalogiens historie, se denne artikel på dr.dk. 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 machine learning (Marco Chiarandini) og feature spaces and clustering (Melih Kandemir). For alle emner inkluderer materialet både slides og de tilhørende opgaver i øvelsestimerne (ugerne 41(-43) og 43(-44)). Også Marcos noter er pensum. For evt. yderligere materiale angivet i gråt og med betegnelsen "(ikke pensum)" er dette naturligvis ikke med i pensum.
45(-46)	E				Opgaver (svar).
46	F	Mandag 15/11	12-14	U20	Start på databaser (optagelse af videoundervisning), ved Rolf Fagerberg.
46	F	Onsdag 17/11	10-12	U180	Slut på databaser (optagelse af videoundervisning), 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.]
46(-47)	E				Opgaver (svar).
47	F	Mandag 22/11	12-14	Zoom mødelink	Start på kryptologi (optagelse af videoundervisning), ved Ruben Niederhagen. Side 1-22 blev gennemgået.
47	F	Onsdag 24/11	10-12	Zoom mødelink	Fortsættelse af kryptologi (optagelse af videoundervisning), ved Ruben Niederhagen. Denne del foregår på Zoom 10:15 til 11:00. Side 23-33 blev gennemgået. Fjerde del (ud af seks) af eksamen i kurset: 45 minutters online multiple-choice test. Da ugens forelæsninger er på Zoom, skal denne test ikke tages i klassen (man kan sidde hvor som helst). Testen vil være åben 11:15 til 12:00. Pensum for denne test vil være materialerne om modeller for beregning (Fabrizio Montesi) og online multiple-choice (Kim Skak Larsen). For alle emner inkluderer materialet 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 (svar).
48	F	Mandag 29/11	12-14	Zoom mødelink	Afslutning af kryptologi (optagelse af videoundervisning, svar på spørgsmål fra slides), ved Ruben Niederhagen. Emnerne fra dele af slides kan også læses i dette notesæt om de algoritmiske aspekter af RSA. [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.]
48	F	Onsdag 1/11	10-12	U55	Start på korteste veje i grafer (Java kode fra slides, optagelse af videoundervisning) ved Daniel Merkle. Side 1-44 blev gennemgået.
48(-49)	E				Opgaver.
49	F	Onsdag 8/11	10-12	U55	Afslutning af korteste veje i grafer (Java kode fra slides, optagelse af videoundervisning) ved Daniel Merkle. Femte del (ud af seks) af eksamen i kurset: 45 minutters online multiple-choice test i klassen. Testen vil finde sted i klassen 10:15 til 11:00. Pensum for denne eksamen vil være materialerne om satisfiability (Peter Schneider-Kamp) og databaser (Rolf Fagerberg). For alle emner inkluderer materialet både slides og de tilhørende opgaver i øvelsestimerne (ugerne 46(-47) og 47(-48)). For evt. yderligere materiale angivet i gråt og med betegnelsen "(ikke pensum)" er dette naturligvis ikke med i pensum.
49(-50)	E				Opgaver.
50	F	Mandag 13/12	12-14	U20	3D-grafik (optagelse af videoundervisning), ved Rolf Fagerberg. [Dette er ikke eksamenspensum, dvs. vil ikke danne baggrund for eksamensspørgsmål.]
50	E				Opgaver.
51	F	Mandag 20/12	12-14	U45	Sjette del (ud af seks) af eksamen i kurset: 50 minutters online multiple-choice test i klassen. Testen vil være åben 12:15 til 13:05. Pensum for testen er materialet om kryptologi (Ruben Niederhagen) og korteste veje i grafer (Daniel Merkle). For begge emner inkluderer materialet både slides, noter og de tilhørende opgaver i øvelsestimerne (ugerne 48(-49), 49(-50) og 50). For evt. yderligere materiale angivet i gråt og med betegnelsen "(ikke pensum)" er dette naturligvis ikke med i pensum. Kursusevaluering.