DM803: Avancerede Datastrukturer (10 ECTS)

STADS: 15015701

Niveau
Kandidatkursus forhåndsgodkendt som PhD-kursus

Undervisningsperiode
Kurset udbydes efter behov.

Ansvarlige undervisere
Email: kslarsen@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal.

Indgangskrav:
Ingen.

Faglige forudsætninger:
Studerende, der følger kurset, forventes at have kendskab til:

• emnerne i kurset DM553 og kurser forudsat af dette, herunder specielt
• datastrukturer som balancerede søgetræer, prioritetskøer via heap-implementation, disjunkte mængder
• tids- og pladsanalyse, herunder asymptotisk notation, rekursionsligninger, amortiseret analyse

Formål
Datastrukturer er et af de emner, der er helt centralt i både teoretisk såvel som mere anvendelsesorienteret datalogi. Algoritmen med den bedst mulige tidskompleksitet udvikles ofte i samspil med, at en datastruktur med præcis de rigtige egenskaber findes. Ligeledes er valg eller design af en passende datastruktur ofte det, som kan gøre forskellen mellem et stort program, der kører alt for langsomt, og et, der kan tilfredsstille brugernes behov. Formålet med kurset er at bibringe deltagerne et solidt kendskab til avancerede datastrukturer, sådan at disse fremover vil indgå som en naturlig del af kompliceret problemløsning og programmering.

Kurset bygger på færdigheder opnået i specielt DM553 Kompleksitet og beregnelighed og giver kompetencer til specialeskrivning indenfor området.

I forhold til uddannelsens kompetenceprofil har kurset fokus på

• viden om et udvalg af metoder udviklet inden for datalogi baseret på højeste internationale forskning
• analysere fordele og ulemper ved forskellige datalogiske metoder
• udvikle nye varianter af de lærte metoder, hvor det konkrete problem kræver det

Målbeskrivelse
Ved kursets afslutning forventes den studerende at kunne:

• gøre rede for funktionaliteten og korrektheden af de gennemgåede algoritmer og datastrukturer
• analysere de gennemgåede algoritmer og datastrukturer mht. tids- og pladskompleksitet
• designe effektive algoritmer og datastrukturer for varianter af de belyste problemstillinger
• gøre rede for problemstillinger omkring implementation af de gennemgåede algoritmer og datastrukturer i et standard programmeringssprog

Indhold
Kurset indeholder følgende faglige hovedområder: Prioritetskøer, højde- og vægtbalancerede søgetræer, ikke-binære træer, randomiserede søgestrukturer, disjunkte mængder med variationer, hashingmetoder, teknikker som global genopbygning, persistens, dynamisering og relaxed balance, mm.

Litteratur

Meddeles ved kursets start.

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

Forudsætningsprøver
Rapport. Bestået/ikke-bestået, intern bedømmelse ved underviser (15015712).

Eksamen- og censurform:
Mundtlig eksamen med ekstern censur og karakter efter 7-trinsskalaen (15015702).

Reeksamen følger terminerne vedtaget af studienævnet.

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
Introfase: 28 timer
Træningsfase: 28 timer, heraf:
 - Eksaminatorie: 28 timer

Aktiviteter i studiefasen

Undervisningsform
Aktiviteter i studiefasen:

• Løse opgaver
• Læse den tildelte literatur
• Øve at anvende den tilegnede viden

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. september 2016 til 31. august 2020.