Kenneth H. Rosen, Discrete Mathematics and Its Applications, fifth edition, McGraw-Hill 2003. Kan købes i centerboghandlen (ca. 500 kr.). Bogens hjemmeside.
Den gren af matematikken der i mange tilfælde anvendes indenfor datalogi, er diskret matematik. Diskret matematik er et stort emne indenfor matematikken, og i dette kursus vil vi studere aspekter af den diskrete matematik, der er relevante for datalogi.
For at være i stand til at forstå samt anvende matematik (i forskellige sammenhænge) er det nødvendigt at kunne udtrykke sig matematisk korrekt, hvilket bl.a. indebærer at kunne bevise matematiske påstande. I kurset vil vi derfor studere hvorledes man egentlig konstruerer et korrekt matematisk bevis, og vi vil specielt se på bevisteknikker, der er relevante for den diskrete matematik. Vi vil nøje studere begrebet induktion, der er en bevisteknik der er særdeles anvendelig i mange sammenhænge i den teoretiske datalogi.
I datalogien spiller algortimer en fundamental rolle. I kurset vil vi studere og konstruere forskellige algoritmer til løsning af konkrete problemer. Vi vil undersøge, hvordan man måler effektiviteten af en algoritme, og desuden hvordan man matematisk beviser, at en algoritme faktisk gør det, som det påstås, at den gør! For at gøre dette må man altså konstruere et matematisk bevis. Vi vil endvidere stifte bekendtskab med rekursivt definerede algoritmer og analysere kompleksiteten af sådanne.
Udover disse emner behandles forskellige matematiske strukturer, som er velegnede til modellering af algoritmiske problemer. Særlig fokus vil der være på grafteori. En graf kan opfattes som en matematisk abstraktion over diskrete objekter og relationerne mellem disse objekter. Et træ eller træstruktur er et vigtigt eksempel på en graf, der har mange anvendelser i datalogien. Vi forventer at genemgå dele af bogens kapitel 1, 2,3,4,6,8 og 9.
Hver enkelt kursusgang består af en blanding af forelæsning og opgaveregning. Opgaveregningen foregår i projektgrupperne under vejledning af kursusholderen. For at få et fornuftigt udbytte af kurset er det væsentligt, at opgaveregningstiden udnyttes til at diskutere det relevante stof dels indbyrdes i gruppen og dels med kursusholderen.
En enkelt kursusgang forløber typisk på følgende måde:
| Dato: | |
| Onsdag 1/12 | Lektion 1 |
| Torsdag 2/12 | Lektion 2 |
| Fredag 3/12 | Lektion 3 |
| Mandag 6/12 | Lektion 4 |
| Tirsdag 7/12 | Lektion 5 |
| Onsdag 8/12 | Lektion 6 |
| Fredag 10/12 | Lektion 7 |
| Mandag 13/12 | Lektion 8 |
| Tirsdag 14/12 | Lektion 9 |
| Onsdag 15/12 | Lektion 10 |
| Torsdag 16/12 | Lektion 11 |
| Fredag 17/12 | Lektion 12 |