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: 29-10-2021
Varighed: 1 semester
Version: Godkendt - aktiv
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
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
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
10
Uddybende information
Eksamen består af en mundtlig eksamen og et projekt med en samlet evaluering.
Vejledende antal undervisningstimer
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
Skemaoplysninger
Administrationsenhed
Team hos Uddannelsesjura & Registratur
Udbudssteder
Anbefalede studieforløb
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.
Se overgangsordninger for alle kurser på Det Naturvidenskabelige Fakultet.