IO-algoritmer (Q3+Q4) ( forår 2008 - 10 ECTS )
Rammer for udbud
-
Uddannelsessprog:
(se under Undervisnings- og arbejdsform)
-
Niveau:
Valgfrit overbygningskursus
-
Semester/kvarter:
Q3+Q4 i 2007/2008
-
Timer per uge:
3
-
Deltagerbegrænsning:
-
Undervisningssted:
Århus
-
Hovedområde:
Det Naturvidenskabelige Fakultet
-
Udbud ID:
7862
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
dADS1 og dADS2, samt dOpt og DKombsøg (kan følges sideløbende)
Underviser
Lars Arge
Undervisnings- og arbejdsform
Forelæsninger (3t/uge)
Litteratur
Artikler og noter
Kursushjemmeside
http://www.daimi.au.dk/
Udbyder
Datalogisk Institut
Tilmelding til undervisning
http://www.brics.dk/~mis/enrollment.html
Studieordning og bedømmelse
-
Mundtlig, bedømt efter 7-skala med intern censur
Mundtlig eksamen uden forberedelse (20 min)
7-skala, intern censur
