AU kursuskatalog arkiv

IO-algoritmer (Q3+Q4) ( forår 2011 - 10 ECTS )

Rammer for udbud

• Uddannelsessprog: engelsk
• Niveau: Kandidatkursus
• Semester/kvarter: Q3+Q4
• Timer per uge: 3
• Deltagerbegrænsning: Ingen
• Undervisningssted: Århus
• Hovedområde: Det Naturvidenskabelige Fakultet
• Udbud ID: 28584

Formål

Deltagerne vil efter kurset have detaljeret kendskab til I/O-effective algoritmer og datastrukturer for fundamentale graf og geometri problemer (samt teknikker til at udvikle sådanne algoritmer), samt praktisk erfaring med implementation af I/O-effektive algoritmer. Kursets arbejdsform vil også træne deltagernes evne til at planlægge og gennemføre projekter og til at læse og forstå videnskabelige artikler.

Obligatorisk program

Tre projekter

Indhold

I/O-kommunikation mellem internt og eksternt lager er ofte flaskehalsen i moderne beregninger, der involverer store datamængder. Grunden til dette er den store hastighedsforskel mellem hurtig intern og langsom ekstern hukommelse, såsom diske. For at amortisere den lange læse/skrive tid, læser og skriver moderne diske typisk store blokke af data på en gang. Dette betyder, at det er vigtig at udvikle algoritmer med stor lokalitet i den måde de læser og skriver på disken, altså algoritmer, hvor data der bliver brugt tæt i tid også er lokaliseret tæt på disken. Sådanne algoritmer drager fordel af blokflytninger ved at amortisere den store læse-/skrivetid over mange disk-læsninger/-skrivninger. Hovedformålet i I/O-algoritme området er at udvikle algoritmer, der minimaliserer antallet af blok flytninger, der bruges til at løse et givent problem. Dette kursus vil omhandle I/O-algoritmer og datastrukturer for fundamentale problemer. Kurset vil for eksempel dække: * Hierarkiske hukommelsesmodeller og fundamentale grænser .* Søgning og sortering (for eksempel, merge og distribution sort, B-trees, og buffer trees). * Geometriske søgningsproblemer (for eksempel, interval-trees, point location, priority search trees, range trees, kdB-trees, O-trees, og R-trees). * Batched geometriske problemer (for eksempel, distribution sweeping, batched filtering, line segment intersection). * Grafproblemer (for eksempel, list ranking, MST, SSSP, plane graf problemer, graf blocking). * Cache-oblivious algoritmer.

Læringsmål

Deltagerne skal ved afslutningen af kurset kunne:

• forklare og analysere kendte fundamentale I/O-effektive algoritmer og data strukturer.
• konstruere og analysere I/O-effektive algoritmer og data strukturer for simple problemer.
• implementere simple I/O-effektive algoritmer og data strukturer.
• diskutere mulige I/O-effektive algoritmer og data strukturer for konkrete problemer.

Faglige forudsætninger

Optimering og Kombinatorisk søgning (kan følges sideløbende)

Underviser

Lars Arge

Undervisnings- og arbejdsform

Forelæsninger (3t/uge)

Engelsk

Litteratur

Artikler og noter

Kursushjemmeside

http://www.daimi.au.dk/~large/ioS09/

Eksamensterminer

Juni/juli, reeksamen august

Udbyder

Datalogisk Institut

Tilmelding til undervisning

http://mit.au.dk

Bedømmelse

Mundtlig eksamen uden forberedelse (20 min)
7-skala, intern censur