Introduktion til algoritmik og datastructurer

Efterår 2002


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 m.m. udleveres. Der vil være et antal mindre og større obligatoriske opgaver, hvor besvarelsen skal godkendes for at kunne gå til 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 fredag kl. 9.15-17 på IT-højskolen. Forelæsninger er i lokale 2.59 fra kl. 12.59. Øvelserne er i lokalerne 2.59, 3.08 og 3.09. Se iøvrigt lektionsplanen.

Litteratur

Cormen, Leiserson, Rivest, and Stein: Intruduction to Algorithms, Second Edition, The MIT Press.
Som supplerende litteatur anbefaler vi at kikke på sider webkursus. Endvidere har mange studerende været glade for at se algoritmerne implementeret i JAVA og ekstra matematik forklaringer i bogen Data Structures and algorithms in Java", af M.T. Goodrich and R. Tamassia. På dansk findes der en bog som hedder "Grundlæggende matematik for dataloger" som man benytter sig af på DTU, den kan måske ligeledes være nyttig. På nettet findes ligeledes en anvendelig note. De sidste to noter/bøger er ikke læst grundigt af lærerne på kurset, men på overfladen ser de gode ud.

Programmerinssprog

Kurset vil indeholde et antal programmeringsopgaver, som I kan vælge at løse. I princippet kan et vilkårligt imperativt programmeringsprog benyttes til at løse opgaverne, hjælp vil dog primært kunne gives i Java og C/C++.

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.

Undervisere

Stephen Alstrup (stephen@it-c.dk), lokale 0.30
Theis Rauhe (theis@it-c.dk), lokale 0.30

Instruktorer

Jacob Borella(jborella@it-c.dk)

Eksamen

 Skriftlig. Det er en forudsætning for at bestå eksamen, at alle obligatoriske opgaver er godkendt. De ugentlige obligatoriske opgaver kan hver give op til et minus point. De store ugeopgaver kan hver give op til tre minus point. For at få lov til at gå til eksamen må man maksimalt have 3 minus point.
 


Stephen Alstrup (stephen@it-c.dk) August 2002