DM207: I/O-Effektive algoritmer og datastrukturer (10 ECTS)

STADS: 15017401

Niveau
PhD-kursus

Undervisningsperiode
Kurset udbydes efter behov.

Ansvarlige undervisere
Email: rolf@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal.

Indgangskrav:
Ingen

Faglige forudsætninger:
Ingen

Kursusintroduktion
I anvendelser der involverer beregninger på store datamængder, er den begrænsende faktor ofte dataoverførsel mellem computerens hukommelsesniveauer, snarere end CPU cykler. Dette skyldes at der er meget store forskelle i tilgangstid mellem de forskellige niveauer i det hukommelseshierarki (typisk bestående af registre, cache-niveauer, RAM og disk) som findes i moderne computere. I området I/O-effektive algoritmer studeres, hvordan man udvikle algoritmer, der minimerer antallet af dataoverførsler (I/Os) mellem hukommelsesniveauerne.

I dette kursus gennemgås I/O-effektive algoritmer for fundamentale problemer så som sortering, søgning og permutering, samt for en række problemer inden for områder som grafer, strenge og geometri. Kursets formål er dels at gennemgå generelle teknikker til design af I/O-effektive algoritmer og datastrukturer, dels at præsentere resultater fra områdets forskningsfront.

Forventet læringsudbytte
Efter kurset forventes den studerende at kunne:

• Beskrive de i kurset gennemgåede generelle metoder og resultater relevante for konstruktion af I/O-effektive algoritmer.
• Give beviser for korrekthed og effektivitet af algoritmer og datastrukturer gennemgået i kurset.
• Anvende præcist sprog og notation under udførelsen af ovenstående.
• Implementere algoritmer og datastrukturer gennemgået i kurset.
• Udføre eksperimenter med disse implementationer, samt reflektere over resultaterne heraf.
• Beskrive disse implementationer og det udførte eksperimentelle arbejde i et klart og præcist sprog, og på en struktureret måde.

Emneoversigt
Modeller for hukommelseshierarkier, øvre og nedre grænser for fundamentale problemer, algoritmer og datastrukturer for sortering og søgning (f.eks. merge- og distributionsort, B-trees, buffer-trees, string sorting, string B-trees), geometriske søgeproblemer (f.eks. interval trees, point location, priority search trees, range trees, kdB-trees, O-trees, R-trees), geometriske problemer af global type (f.eks. distribution sweeping, batched filtering, line segment intersection), grafalgoritmer (f.eks. list ranking, MST, SSSP, algoritmer for planare grafer), cache-oblivious algoritmer, samt implementation af I/O-effektive algoritmer and datastrukturer.

Litteratur

Meddeles ved kursets start.

Kursets hjemmeside
Dette kursus benytter e-learn (blackboard).

Forudsætningsprøver
Projektopgave, der bedømmes med B/IB og intern censur ved underviser. (15017412)

Eksamen- og censurform:
Mundtlig eksamen der bedømmes med karakter efter 7-skalaen og ekstern censur. 10 ECTS (15017402)

Reeksamen ifølge studienævnets regler.

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.

42 forelæsninger.
Aktiviteter i studiefasen

Sprog
Dette kursus undervises på dansk eller engelsk, afhængigt af underviseren. Dog altid på Engelsk ved deltagelse af internationale studerende.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Dette er den nyeste version af en kursusbeskrivelse, som trådte i kraft den 1. sep 2015.