DM578: Algoritmer og datastrukturer

Det Naturvidenskabelige Studienævn

Undervisningssprog: På dansk eller engelsk afhængigt af underviser
EKA: N330063102
Censur: Ekstern prøve
Bedømmelse: 7-trinsskala
Udbudssteder: Odense
Udbudsterminer: Forår
Niveau: Bachelor

STADS ID (UVA): N330063101
ECTS-point: 7.5

Godkendelsesdato: 12-10-2022


Varighed: 1 semester

Version: Arkiv

Kommentar

Kurset kan ikke følges hvis DM507 er bestået, eller hvis DM507 indgår obligatorisk i din studieordning.

Indgangskrav

Ingen

Faglige forudsætninger

Studerende, der følger kurset, forventes at:

  • Have matematisk modenhed svarende til niveauet i kurset DM549 Diskrete metoder til datalogi.
  • Have kendskab til programmering i Java eller Python.

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.

Kurset bygger oven på den viden, der
er erhvervet i kurserne DM549 Diskrete metoder til datalogi og DM574 Introduktion til programmering, og giver et fagligt grundlag for at
studere algoritmiske og kompleksitetsteoretiske emner, der er placeret
senere i uddannelsen. I forhold til uddannelsens kompetenceprofil har
kurset eksplicit fokus på at:

  • Give kompetence til udvikle nye varianter af centrale algoritmer og datastrukturer udviklet inden for datalogi.
  • Give færdigheder i at analysere fordele og ulemper ved forskellige algoritmer, specielt med hensyn til ressourceforbrug.
  • Give viden om et stort udvalg af centrale algoritmer og datastrukturer udviklet inden for datalogi.

Målbeskrivelse

For at opnå kursets formål er det læringsmålet for kurset, at den studerende demonstrerer evnen til at:

  • anvende algoritmerne fra kurset på konkrete problemer.
  • argumentere præcist for en algoritmes korrekthed eller mangel på samme.
  • bestemme en algoritmes asymptotiske køretid.
  • tilpasse kendte algoritmer og datastrukturer til specialtilfælde af kendte problemer og til nye problemer.
  • designe
    nye algoritmer 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.

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

    Juni

    Udprøvninger

    Skriftlig eksamen

    EKA

    N330063102

    Censur

    Ekstern prøve

    Bedømmelse

    7-trinsskala

    Identifikation

    Studiekort - Eksamensnummer

    Sprog

    Følger, som udgangspunkt, undervisningssprog

    Varighed

    3 timer

    Hjælpemidler

    Alle almindelige hjælpemidler er tilladte fx lærebøger, egne noter, computerprogrammer som ikke benytter internettet m.v. 

    Internet er ikke tilladt. Du må dog gå ind på system DE-Digital Eksamen i forbindelse med udfyldelse af multiple choice testen. Noter fra kurset i itslearning, som du ønsker at anvende som hjælpemidler, skal downloades til din computer senest dagen før eksamenen. Under eksamenen må itslearning ikke anvendes.

    ECTS-point

    7.5

    Uddybende information

    Reeksamen afholdes som en mundtlig eksamen.

    Vejledende antal undervisningstimer

    88 timer per semester

    Undervisningsform

    Undervisningsaktiviteter udmønter sig i en anslået vejledende fordeling af arbejdsindsatsen hos en gennemsnitsstuderende på følgende måde:
    • Introfase (forelæsning, holdtimer) - Antal timer: 44
    • Træningsfase: Antal timer: 44

    Undervisningsform: Opgaver i studiegrupper.

    Ansvarlig underviser

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

    Skemaoplysninger

    Administrationsenhed

    Institut for Matematik og Datalogi (datalogi)

    Team hos Uddannelsesjura & Registratur

    NAT

    Udbudssteder

    Odense

    Anbefalede studieforløb

    Profil Uddannelse Semester Udbuds periode
    BA Centralt fag datalogi et-faglig særligt forløb for datamatikere - optag 1. september 2023 Bachelor i datalogi | Odense 2 E23
    BA Centralt fag datalogi et-faglig særligt forløb for datamatikere - optag 1. september 2023 Bachelor i datalogi | Odense 2 E22
    BA Centralt fag datalogi et-faglig særligt forløb for datamatikere - optag 1. september 2023 og 2024 Bachelor i datalogi | Odense 2 E24
    BA centralt fag i datalogi et-faglig - optag 1. september 2022 Bachelor i datalogi | Odense 2 E22
    BA centralt fag i datalogi et-faglig - optag 1. september 2022 og 2023 Bachelor i datalogi | Odense 2 E23
    BA centralt fag i datalogi et-faglig - optag 1. september 2022, 2023 og 2024 Bachelor i datalogi | Odense 2 E24
    BA centralt fag i datalogi to-faglig med sidefag - optag 1. september 2022 Bachelor i datalogi | Odense 2 E22
    BA centralt fag i datalogi to-faglig med sidefag - optag 1. september 2022 og 2023 Bachelor i datalogi | Odense 2 E23
    BA centralt fag i datalogi to-faglig med sidefag - optag 1. september 2022, 2023 og 2024 Bachelor i datalogi | Odense 2 E24
    BA centralt fag i datalogi to-faglig med sidefag i matematik - optag 1. september 2022 Bachelor i datalogi | Odense 2 E22
    BA centralt fag i datalogi to-faglig med sidefag i matematik - optag 1. september 2022 og 2023 Bachelor i datalogi | Odense 2 E23
    BA centralt fag i datalogi to-faglig med sidefag i matematik - optag 1. september 2022, 2023 og 2024 Bachelor i datalogi | Odense 2 E24
    BA centralt fag i kunstig intelligens et-faglig - Optag 2023 Bachelor i kunstig intelligens | Odense 2 E23
    BA centralt fag i kunstig intelligens et-faglig - Optag 2023 og 2024 Bachelor i kunstig intelligens | Odense 2 E24
    BA sidefag i Datalogi for central fag i Matematik - optag 1. september 2021 og 2022 Bachelor i datalogi | Odense 6 E22
    BA sidefag i Datalogi for central fag i Matematik - optag 1. september 2021, 2022 og 2023 Bachelor i datalogi | Odense 6 E23
    BA sidefag i Datalogi for central fag i Matematik - optag 1. september 2021, 2022, 2023 og 2024 Bachelor i datalogi | Odense 6 E24

    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.