Avanceret Algoritmik : Datastrukturer (Q1+2) ( efterår 2007 - 10 ECTS )
Rammer for udbud
-
Uddannelsessprog:
(se under Undervisnings- og arbejdsform)
-
Niveau:
Valgfrit overbygningskursus
-
Semester/kvarter:
Q1+Q2 i 2007
-
Timer per uge:
-
Deltagerbegrænsning:
-
Undervisningssted:
Århus
-
Hovedområde:
Det Naturvidenskabelige Fakultet
-
Udbud ID:
7774
Formål
Deltagerne vil efter kurset have detaljeret kendskab til mange avancerede datastrukturer og generelle designteknikker til konstruktion af datastrukturer og praktisk erfaring med implementation, evaluering og sammenligning af komplekse datastrukturer. Kursets arbejdsform vil også træne deltagernes evne til at læse og forstå videnskabelige artikler.
Obligatorisk program
3 projekter
Indhold
Udvalgte emner inden for datastruktur. Mulige emner: Fractional cascading. Persistens: Delvis persistence, fuld persistence, rent funktionelle datastrukturer (konkatenerbare lister). Dearmortiseringsteknikker. Dynamiseringsteknikker. Sortering vs. Prioritetskøer. RAM datastrukturer. Ordbøger. Prioritetskøer. Vedligeholdelse af listeorder. Interpolationssøgning. Mindste fælles forfader datastrukturer. Finger søgetræer. Succinte datastrukturer. Koncise datastrukturer. Implicitte datastrukturer. Deterministisk hashing. Prioritetskøer: Binomialkøer, Fibonaccikøer, Skew heaps. van Emde Boas datastrukturer. Union-split-find datastrukturer. Union-find datastrukturer. Selektion i heaps. Planare separatorer.
Læringsmål
Deltagerne skal ved afslutningen af kurset kunne:
-
implementere
og
evaluere
avancerede datastrukturer,
-
beskrive
og
analysere
avancerede datastrukturer,
-
sammenligne
avancerede datastrukturer i forskellige beregningsmodeller.
Faglige forudsætninger
dADS 1+2
Underviser
Gerth Stølting Brodal
Undervisnings- og arbejdsform
Forelæsninger (3t/uge)
Litteratur
Forskningsartikler
Litteratur
Research papers
Kursushjemmeside
http://www.daimi.au.dk/~gerth/aa07/index.html
Udbyder
Datalogisk Institut
Tilmelding til undervisning
https://mit.au.dk/da/index.cfm
Studieordning og bedømmelse
-
Mundtlig, bedømt efter 7-skala med intern censur
Projekt og mundtlig eksamen
7-skala, intern censur
