DM803: Avancerede Datastrukturer

Kommentar

Kurset udbydes efter behov og udbydes ikke nødvendigvis hvert år. Eksamensforsøg for DM803 udbydes efter følgende plan, når kurset udbydes: Forår (kursusstart februar): ordinær eksamen (juni), første reeksamen (august) og 2. reeksamen i (januar eller marts).

Indgangskrav

Ingen

Faglige forudsætninger

Der forudsættes kendskab til algoritmer og datastrukturer og analyse af disse, herunder algoritmedesignteknikker som del-og-hersk, balancerede binære søgetræer som rød-sorte træer, prioritetskøer via heap-implementation, disjunkte mængder, tids- og pladsanalyse, herunder asymptotisk notation og rekursionsligninger, nedre grænser for sortering, samt et basalt kendskab til sandsynlighedsteori. Forudsætningerne kan erhverves gennem algoritmekurser og kurser i diskret matematik på en bacheloruddannelse i datalogi.

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 algoritmekurser på en datalogisk bacheloruddannelse 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

ECTS-point

Uddybende information

Eksamen består af en mundtlig eksamen og et projekt med en samlet evaluering.

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	Algoritmer

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

Overgangsordninger

Overgangsordninger beskriver, hvordan et kursus erstatter et andet kursus, når der ændres i et studieforløb.

Hvis der er lavet en overgangsordning for et kursus vil den fremgå af oversigten.
Se overgangsordninger for alle kurser på Det Naturvidenskabelige Fakultet.