AU kursuskatalog arkiv

Avanceret Algoritmik: Datastrukturer (Q1+Q2) ( efterår 2011 - 10 ECTS )

Rammer for udbud

• Uddannelsessprog: engelsk (eller dansk)
• Niveau: Valgfrit kandidatkursus
• Semester/kvarter: Q1+Q2
• Timer per uge: 3
• Deltagerbegrænsning: Ingen
• Undervisningssted: Århus
• Hovedområde: Det Naturvidenskabelige Fakultet
• Udbud ID: 32403

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. 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

Algoritmer og Datastrukturer 1+2

Underviser

Gerth Stølting Brodal

Undervisnings- og arbejdsform

Forelæsninger (3t/uge)

Litteratur

Forskningsartikler

Litteratur

Research papers

Kursushjemmeside

http://www.cs.au.dk/~gerth/aa11/index.html

Eksamensterminer

December/januar, reeksamen foregår efter aftale med underviseren

Udbyder

Datalogisk Institut

Tilmelding til undervisning

https://mit.au.dk/

Studieordning og bedømmelse

Tilvalgsfag: Datalogi

• Mundtlig, bedømt efter 7-skala med intern censur

Projekt og mundtlig eksamen
7-skala, intern censur