DM803: Avancerede Datastrukturer

Det Naturvidenskabelige Studienævn

Undervisningssprog: På dansk eller engelsk afhængigt af underviser, men engelsk ved internationale studerende
EKA: N340060102
Censur: Ekstern prøve
Bedømmelse: 7-trinsskala
Udbudssteder: Odense
Udbudsterminer: Forår
Niveau: Kandidatkursus forhåndsgodkendt som Ph.d.-kursus

STADS ID (UVA): N340060101
ECTS-point: 10

Godkendelsesdato: 02-10-2019


Varighed: 1 semester

Version: Godkendt - aktiv

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

10

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

Skemaoplysninger

Administrationsenhed

Institut for Matematik og Datalogi (datalogi, fiktiv)

Team hos Registrering & Legalitet

NAT

Anbefalede studieforløb

Profil Program Semester Periode