DM507: Algoritmer og Datastrukturer

Det Naturvidenskabelige Studienævn

Undervisningssprog: På dansk eller engelsk afhængigt af underviser
EKA: N330068112, N330068102
Censur: Intern prøve, en bedømmer, Ekstern prøve
Bedømmelse: Bestået/Ikke bestået, 7-trinsskala
Udbudssteder: Odense
Udbudsterminer: Forår
Niveau: Bachelor

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

Godkendelsesdato: 21-10-2025


Varighed: 1 semester

Version: Godkendt - aktiv

Kommentar

Kurset samlæses med DM578 og DS814

Indgangskrav

Kurset kan ikke vælges hvis du har bestået, er tilmeldt, har fulgt DM578, DS814 eller DSK814, eller hvis en af disse indgår som obligatorisk i din studieordning.

Faglige forudsætninger

Studerende, der følger kurset, forventes at

  • have matematisk modenhed svarende til niveauet i DM549 og
  • have kendskab til programmering i Python på et niveau svarende til for eksempel DM574.

Formål

Kurset har til formål at sætte den studerende i stand til at anvende en lang række eksisterende algoritmer og datastrukturer for fundamentale problemer, anvende generelle metoder til udvikling af nye algoritmer, samt anvende matematiske værktøjer til analyse af algoritmers korrekthed og effektivitet. Dette er en helt central kompetence, når man skal udvikle effektiv software. Det giver desuden en vigtig forståelse for øvre og nedre grænser for beregningsproblemer.

Målbeskrivelse

For at opnå kursets formål er det læringsmålet for kurset, at den studerende demonstrerer evnen til at:
  • anvende algoritmerne og datastrukturerne fra kurset på konkrete problemer.
  • argumentere præcist for en algoritmes eller datastrukturs korrekthed eller mangel på samme.
  • bestemme en algoritmes eller datastrukturs asymptotiske køretid.
  • tilpasse kendte algoritmer og datastrukturer til specialtilfælde af kendte problemer og til nye problemer.
  • designe nye algoritmer og datastrukturer til at løse problemer, som i natur minder om problemer fra kurset, herunder give en præcis beskrivelse af algoritmen, f.eks. vha. pseudokode.
  • designe og implementere et større program, som anvender algoritmer og datastrukturer fra kurset.

Indhold

Kurset indeholder følgende faglige hovedområder:
  • Matematisk grundlag: rekursionsligninger, invarianter.
  • Algoritmer: korrekthed og kompleksitetsanalyse, del og hersk algoritmer (master teorem, Strassens algoritme), grådige algoritmer, dynamisk programmering, sorteringsalgoritmer (insertionsort, mergesort, heapsort, quicksort, countingsort, radixsort), graf-algoritmer (BFS, DFS, topologisk sortering af DAGs, sammenhængskomponenter, stærke sammenhængskomponenter, MST, SSSP, APSP), Huffman-kodning.
  • Datastrukturer: ordbøger (BSTs, rødsorte træer, hashing), prioritetskøer, disjunkte mængder.

Litteratur

Se itslearning for pensumlister og yderligere litteraturhenvisninger.

Eksamensbestemmelser

Eksamenselement a)

Tidsmæssig placering

Forår

Udprøvninger

Obligatorisk projektopgave

EKA

N330068112

Censur

Intern prøve, en bedømmer

Bedømmelse

Bestået/Ikke bestået

Identifikation

Fulde navn og SDU brugernavn

Sprog

Følger, som udgangspunkt, undervisningssprog

Hjælpemidler

Alle almindelige hjælpemidler undtagen generativ AI

ECTS-point

2.5

Uddybende information


Eksamenselement b)

Tidsmæssig placering

Juni

Udprøvninger

Skriftlig eksamen

EKA

N330068102

Censur

Ekstern prøve

Bedømmelse

7-trinsskala

Identifikation

Studiekort - Eksamensnummer

Sprog

Følger, som udgangspunkt, undervisningssprog

Varighed

3 timer

Hjælpemidler

Eksamen er med begrænset hjælpemidler. Det er kun følgende hjælpemidler som er tilladt:

  • lærebøger, noter, forelæsningspræsentationer, kompendier og formelsamlinger mv.
Internet er ikke tilladt. Du må dog gå ind på kursets hjemmeside i itslearning i forbindelse med åbning af system "DE – Digital Eksamen" og udfyldelse af evt. test i systemet. Noter fra kurset, som du ønsker at anvende som hjælpemidler, skal downloades til din computer senest dagen før eksamenen. Under eksamenen er det ikke sikkert at alt kursusmateriale er tilgængeligt for dig.

ECTS-point

7.5

Uddybende information

Reeksamen i august er en mundtlig eksamen, der bedømmes med karakter efter 7-trinsskalaen og ekstern censur.

Vejledende antal undervisningstimer

88 timer per semester

Undervisningsform

Skemalagte undervisningstimer:
Antal undervisningstimer i alt: 88
Heraf:
Fællestimer i klasselokale/auditorium: 44
Holdtimer i klasselokale: 44

I fællestimerne introducerer og gennemgår underviseren stoffet, med mulighed for spørgsmål fra deltagerne.

I holdtimerne arbejder deltagerne individuelt og i grupper med regneopgaver og programmeringsopgaver i stoffet. Der er mulighed for hjælp og feedback, mens løsninger præsenteres til sidst.

Andre planlagte undervisningsaktiviteter:


Efter fællestimerne og inden de tilsvarende holdtimer arbejder deltagerne individuelt og i grupper med stoffet og med tilhørende opgaver og programmeringsopgaver.

Ansvarlig underviser

Navn E-mail Institut
Rolf Fagerberg rolf@imada.sdu.dk Algoritmer

Skemaoplysninger

Administrationsenhed

Institut for Matematik og Datalogi (datalogi)

Team hos Registratur

NAT

Udbudssteder

Odense

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.