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


Bacheloruddannelsen i datalogi

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


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