Vær opmærksom på at dette website indeholder et arkiv med historiske data. Det aktuelle kursuskatalog findes på kursuskatalog.au.dk

AU kursuskatalog arkiv

[Forside] [Hovedområder] [Perioder] [Udannelser] [Alle kurser på en side]

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

Rammer for udbud

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

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.