Introduktion til algoritmik og datastructurer

Efterår 1999


Generel information

Hvorfor dette kursus?

I softwareudvikling er det vigtigt at vide, hvordan problemer, der kan løses på en computer, løses effektivt. Algoritmik handler om de metoder, der benyttes til løsning af problemer under forskellige ressourcemål. Ofte er det ønskværdigt, at computeren beregner en løsning så hurtigt og med så lidt brug af plads som muligt. For at løse et problem effektivt kan det være nødvendigt at benytte en datastruktur, der er specielt velegnet til netop dette problem. En datastrukturer er en bestemt måde at organisere data på, hvortil der er knyttet en række af operationer. Der findes f.eks. datastrukturer, hvor det er hurtigt at indsætte og genfinde data.

Målsætning

Kursets målsætning er at give en grundlæggende forståelse af, hvordan almindelige datalogiske problemer kan løses effektivt på en computer.

Indhold

Analyse af algoritmers effektivitet
Algoritmer til søgning, sortering og selektion
Datastrukturer (stakke, lister, køer og prioritetskøer, træer, søgetræer og balancerede søgetræer, mængder)
Hashing
Dynamisk programmering
Grådige algoritmer
Grafer og grafalgoritmer

Kursusform

Hver kursusgang vil bestå af en forelæsning samt øvelser med øvelsesvejleder. En ugentlig plan med pensum og øvelser mm. udleveres. Der vil være et antal mindre og større obligatoriske opgaver, hvor besvarelsen skal godkendes for at kunne bestå eksamen.

Belastning

Kursets belastning er 7.5 ECTS, det svarer til 1/3 af et fuldtidsstudie i den periode kurset afholdes.

Hvor og hvornår

Forelæsningerne og øvelserne holdes fredage kl. 9-17 på IT-højskolen i lokale 251. Første forelæsningsdag er fredag 3. september. Se iøvrigt lektionsplanen.

Litteratur

Cormen, Leiserson & Rivest: Intruduction to Algorithms, McGraw-Hill. Kan købes i Polyteknisk Boghandel eller Universitetssbogladen.

Programmerinssprog

I princippet kan et vilkårligt imperativt programmeringsprog benyttes til at løse kursets programmeringsopgaver. Hjælp til opgaverne vil dog primært kunne gives i Java og C/C++. Det anbefales, at opgaverne løses i Java.

En dansk introduktion til Java kan ses her og den officielle Sun tutorial her. Java til Windows 95/NT, Linux og andre platforme kan hentes fra denne hjemmeside.

Hjemmeside for kurset

Kursets hjemmeside findes på http://www.itu.dk/courses/swue99iads. I forventes regelmæssigt at kigge på hjemmesiden.

Undervisere

Stephen Alstrup (stephen@itu.dk), lokale 0.30
Theis Rauhe (theis@itu.dk), lokale 0.30
Jens Chr. Godskesen (jcg@itu.dk), lokale 2.28

Eksamen

 Skriftlig. Det er en forudsætning for at bestå eksamen, at alle obligatoriske opgaver er godkendt.

Pensum

Meddeles senere.


Jens Christian Godskesen (jcg@itu.dk) 1. oktober 1999