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

STADS: 15006401

Niveau
PhD-kursus

Undervisningsperiode
Kurset er placeret i forårssemesteret.
Udbydes efter behov.

Ansvarlige undervisere
Email: rolf@imada.sdu.dk

Skemaoplysninger
Der er ingen skemaoplysninger for den valgte periode.

Kommentar:
Ubegrænset deltagerantal. 1. + 2. kvartal.

Indgangskrav:
Ingen

Faglige forudsætninger:
Bachelorgraden skal være bestået. Stoffet fra DM508 Algoritmer og kompleksitet skal være kendt.

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.

Pensum
Se pensumbeskrivelse.

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

Forudsætningsprøver
Ingen

Eksamen- og censurform:
(a) Projektopgave, der bedømmes med B/IB og intern censur ved underviser. Projektopgaven andrager 3 ECTS af kursets 10 ECTS. Det er en forudsætning for at kunne gå til mundtlig eksamen at projektopgaven er bestået.
(b) Mundtlig eksamen der bedømmes med karakter efter 7-skalaen og ekstern censur (7 ECTS).

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.

Denne kursusbeskrivelse var gyldig fra 1. februar 2009 til 31. august 2015.