Vær opmærksom på at dette website indeholder et arkiv med historiske data. Det aktuelle kursuskatalog findes på kursuskatalog.au.dk

AU kursuskatalog arkiv

[Forside] [Hovedområder] [Perioder] [Udannelser] [Alle kurser på en side]

Algoritmer og Datastrukturer 1 (Q3) ( forår 2008 - 5 ECTS )

Rammer for udbud

Uddannelsessprog: (se under Undervisnings- og arbejdsform)
Niveau: Obligatorisk grundkursus
Semester/kvarter: Q3 i 2007/2008
Timer per uge: 6
Deltagerbegrænsning:
Undervisningssted: Århus
Hovedområde: Det Naturvidenskabelige Fakultet
Udbud ID: 7821

Formål

Deltagerne vil efter kurset have indsigt i algoritmer som model for sekventielle beregningsprocesser og som basis for formelle korrekthedsbeviser og analyse af ressourceforbrug ved beregningerne, samt detaljeret kendskab til adskillige konkrete implementationer af fundamentale datastrukturer.

Obligatorisk program

6 opgaver

Indhold

Datastrukturer Lister, træer, hashtabeller Dataabstraktioner Stakke, køer, prioritetskøer, ordbøger, mængder Algoritmer Søgning, sortering, selektion, fletning Analyse og syntese Worst-case, amortiseret og forventet udførelsestid, udsagn, invarianter, gyldighed, terminering og korrekthed.

Læringsmål

Deltagerne skal ved afslutningen af kurset kunne:

formulere og udføre algoritmer og datastrukturer i pseudo code.
analysere og sammenligne tid og pladsforbruget af algoritmer.
identificere gyldige invarianter for en algoritme.
bevise korrektheden af simple programmer og transitionssystemer.

Faglige forudsætninger

dIntProg

Underviser

Gerth Stølting Brodal

Undervisnings- og arbejdsform

Forelæsninger (2+1t/uge), holdøvelser (3t/uge) Dansk

Litteratur

Introduction to Algorithms (Second Edition), Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein. MIT Press and McGraw-Hill, 2001.