Algoritmer og Datastrukturer 1 (Q3) ( forår 2009 - 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:
13851
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)
Litteratur
Introduction to Algorithms (Second Edition), Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein. MIT Press and McGraw-Hill, 2001.
Kursushjemmeside
http://www.daimi.au.dk/dADS1
Skemaplacering (forelæsninger)
Endnu ikke fastlagt
Eksamensterminer
Marts/april, reeksamen august
Udbyder
Datalogisk Institut
Indgår i følgende studieordninger
Bacheloruddannelsen i Datalogi og IT
Indgår i følgende fagpakker
Programmering
Tilmelding til undervisning
https://mit.au.dk/
Studieordning og bedømmelse
-
Skriftlig, bedømt efter 7-skala med intern censur
-
Skriftlig, bedømt efter 7-skala med intern censur
-
Skriftlig, bedømt efter 7-skala med intern censur
-
Skriftlig, bedømt efter 7-skala med intern censur
-
Skriftlig, bedømt efter 7-skala med intern censur
-
Skriftlig, bedømt efter 7-skala med intern censur
-
Skriftlig, bedømt efter 7-skala med intern censur
-
Skriftlig, bedømt efter 7-skala med intern censur
-
Skriftlig, bedømt efter 7-skala med intern censur
-
Skriftlig, bedømt efter 7-skala med intern censur
-
Skriftlig, bedømt efter 7-skala med intern censur
-
Skriftlig, bedømt efter 7-skala med intern censur
Skriftlig eksamen (2 timer)
7-skala bedømmelse, intern censur