DM803: Avancerede Datastrukturer

Kommentar

15015701 (tidligere UVA) er identisk med denne kursusbeskrivelse.
Kurset udbydes efter behov om foråret.
Eksamensforsøg for DM803 (som en del af F20 udbud) udbydes: Ordinær eksamen juni 2020 og reeksamen i august 2020 og januar 2021.

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

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

Se itslearning for pensumlister og yderligere litteraturhenvisninger.

Eksamensbestemmelser

Eksamenselement a)

Tidsmæssig placering

Juni

Udprøvninger

Mundtlig eksamen

EKA

N340060102

Censur

Ekstern prøve

Bedømmelse

7-trinsskala

Identifikation

Studiekort

Sprog

Følger, som udgangspunkt, undervisningssprog

Hjælpemidler

Oplyses på kurset, nærmere beskrivelse af eksamensreglerne vil blive offentliggjort i itslearning.

ECTS-point

Uddybende information

Eksamen består af en mundtlig eksamen og et projekt med en samlet evaluering.
Eksamensformen ved reeksamen kan være en anden end eksamensformen ved den ordinære eksamen.

Vejledende antal undervisningstimer

56 timer per semester

Undervisningsform

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

Introfase: 28 timer
Træningsfase: 28 timer, heraf 28 timers eksaminatorier

Aktiviteter i studiefasen:

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

Ansvarlig underviser

Navn	E-mail	Institut
Kim Skak Larsen	kslarsen@imada.sdu.dk	Institut for Matematik og Datalogi

Skemaoplysninger

Odense

Vis fuldt skema

Administrationsenhed

Institut for Matematik og Datalogi (datalogi)

Team hos Uddannelsesjura & Registratur

NAT

Udbudssteder

Odense

Anbefalede studieforløb

Profil	Uddannelse	Semester	Udbuds periode