Kursusbeskrivelse
for
Datalogi C
ved
Keld Helsgaun
1. Formål
Studiet af datastrukturer og algoritmer er en central del af datalogien. Ved udvikling af et program er det vigtigt, at man har et solidt kendskab til egnede datastrukturer og algoritmer og kan foretage et kvalificeret valg imellem disse.
Kursets formål er at give den studerende
2. Indhold
Kursets indhold kan overordnet beskrives ved følgende punkter:
Som programmeringssprog anvendes Java.
3. Forudsætninger
Datalogi A eller tilsvarende kendskab til programmering.
4. Undervisningsform
Undervisningen foregår ved forelæsninger (33 timer) og øvelser (33 timer).
Forelæsningerne afholdes på tirsdage fra 930-1200 i teorirummet i hus 42.2. Øvelserne afholdes på fredage fra 1300-1530 i datastuen og møderummet i hus 42.1.
5. Evalueringskriterier
Der vil i kursusperioden løbende blive stillet et antal øvelsesopgaver. For hver tilfredsstillende opgaveløsning gives et på forhånd angivet antal point. For at bestå kurset skal der opnås en pointsum, der udgør mindst 80% af pointsummen for samtlige obligatoriske opgaver.
Opgaveløsninger afleveres til kursuslæreren, enten individuelt eller af grupper på 2 personer. Afleveringsfrister skal overholdes, og der er ikke mulighed for genaflevering.
6. Undervisningsmaterialer
Mark Allen Weiss,
Data Structures & Problem Solving Using Java,
Addison Wesley, 2nd edition, 2001.
7. Forelæsninger
Til stofgennemgang er afsat 12 forelæsningsgange. En foreløbig plan er vist nedenfor. Ret til ændringer forbeholdes.
| (18/9) Objektorienteret programmering I (Kapitel 1, 2 og 3) Typer. Sætninger. Referencer. Undtagelser. Klasser. Pakker. |
|||||||||||||||||
| (25/9) Objektorienteret programmering II (Kapitel 4) Nedarvnning. Grænseflader. |
|||||||||||||||||
| (2/10) Algoritmeanalyse (Kapitel 5) Data- og algoritmebegebet. O-notation. Binær søgning. |
|||||||||||||||||
| (9/10) Datastrukturer I (Kapitel 6) Dataabstraktion. Elementære datastrukturer. |
|||||||||||||||||
| (16/10) Rekursion (Kapitel 7) Algoritmedesign. |
|||||||||||||||||
| (23/10) Sortering (Kapitel 8 og 9) Simple metoder. ShellSort, MergeSort og Quicksort. Randomisering. |
|||||||||||||||||
| (30/10) Anvendelser I (Kapitel 10 og 11) Rekursion og stakke: spiltræer, aritmetiske udtryk. |
|||||||||||||||||
| (6/11) Anvendelser II (Kapitel 12 og 13) Prioritetskøer: filkomprimering, simulering. |
|||||||||||||||||
| (13/11) Anvendelser III (Kapitel 14) Grafer. |
|||||||||||||||||
| (20/11) Datastrukturer II (Kapitel 15, 16, 17 og 18) Implementering af stakke, køer, hægtede lister og træer. |
|||||||||||||||||
| (27/11) Datastrukturer III (Kapitel 19) Søgetræer. |
|||||||||||||||||
| (4/12) Datastrukturer IV (Kapitel 20 og 21) Hashing. Prioritetskøer. |
|||||||||||||||||
8. Øvelser
Der afholdes øvelser følgende fredage:
28/9, 5/10, 12/10, 19/10, 26/10, 2/11, 9/11, 16/11, 23/11 og 7/12.
9. Kursusafrunding og -evaluering
Kursusafrunding tirsdag den 8/1 2002.
Kursusevaluering fredag den 11/1 2002.