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 2010 - 5 ECTS )

Rammer for udbud

Uddannelsessprog: dansk
Niveau: Grundkursus
Semester/kvarter: Q3
Timer per uge: 7
Deltagerbegrænsning: Ingen
Undervisningssted: Århus
Hovedområde: Det Naturvidenskabelige Fakultet
Udbud ID: 14671

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

Introduktion til Programmering

Underviser

Gerth Stølting Brodal

Undervisnings- og arbejdsform

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

Dansk

Litteratur

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