Målbeskrivelse:
Målet med kurset er at give deltagerne
- erfaring i løsning, beskrivelse og programmering af mindre opgaver
- kendskab til et sædvanligt programmeringssprog og de dertil hørende programmeringssprogsbegreber, og
- kendskab til algoritmer og datastrukturer samt erfaring i systematisk udvikling og analyse heraf.
Indhold:
Kurset er en begrebsorienteret introduktion til emneområderne algoritmik, programmering og programmeringssprog. Fællesnævneren er en programmeringsmetodologi, hvor der lægges vægt på specifikation, korrekthed og analyse af algoritmer.
Programmering 1 (dProg 1) (efteråret)
Basale programmeringsbegreber: variabel, værdi, udtryk, objekt, kontrolstruktur, procedure, rekursion, nedarvning, beskyttelse, datatype, polymorfi, kommunikation.
Systematisk udvikling af mindre programmer: trinvis forfinelse, modularisering, udsagn, afprøvning.
Typer: tegn, heltal, sandhedsværdier, klasser, lister, rekursive typer.
Konkret semantik: tilstandsbeskrivelser og -ændringer, programmers tids- og pladsforbrug.
Algoritmer og Datastrukturer 1 (dADS) (foråret)
Basale algoritmer og datastrukturer: søgning, fletning, sortering, lister, køer, stakke, træer.
Elementær teori: algoritmers korrekthed og
effektivitet.
Fundamentale paradigmer: del-og-kombiner, dynamisk programmering, kombinatorisk søgning.
Dataabstraktioner: prioritetskøer, ordbøger, ækvivalensrelationer.
Grafalgoritmer: gennemløb, sammenhængsegenskaber, udspændende træer, korteste veje.
Maskinaritmetik: regler for fornuftig adfærd ved regning med pseudo-reelle maskintal.
Undervisningsform:
Forelæsninger: 3-4 timer pr. uge.
Øvelser: 3 timer pr. uge.
Obligatoriske opgaver: I efteråret stilles ca. 7 mindre afleveringsopgaver og i foråret en lidt større opgave af ca. 3 ugers omfang. Efterårets forløb afsluttes af en programmeringsprøve. Samlet godkendelse af de to obligatoriske forløb er en forudsætning for at kunne indstille sig til eksamen.
Evaluering:
En skriftlig 4 timers prøve og en mundtlig prøve uden forberedelse.
Bemanding:
Gudmund S. Frandsen og Erik Meineche Schmidt.
Belastning:
4 point.