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 2011 - 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: 27072

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

Calculus 1+2, Introduktion til Programmering, Programmering 2

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.

Kursushjemmeside

http://www.cs.au.dk/dADS1

 

Skemaplacering (forelæsninger)

Mandag 14-16 + torsdag 12-14

Blokpar D:  http://science.au.dk/uddannelse/undervisning/blokpar/

Eksamensterminer

Eksamen: 3. kvarter

Placering: Onsdag d. 30. marts 2011, uge 13

Reeksamen august

http://science.au.dk/uddannelse/undervisning/eksamen/regler-for-tilmelding-til-kurser-med-fastlagt-eksamen/

Udbyder

Datalogisk Institut

Indgår i følgende studieordninger

Bacheloruddannelsen i Datalogi og IT

Tilmelding til undervisning

https://mit.au.dk/da/index.cfm

Bedømmelse

Skriftlig eksamen (2 timer), Alle sædvanlige hjælpemider dog uden PC,
7-skala bedømmelse, intern censur