DM507: Algoritmer og Datastrukturer

Det Naturvidenskabelige Studienævn

Undervisningssprog: På dansk eller engelsk afhængigt af underviser
EKA: N330046112, N330046102
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): N330046101
ECTS-point: 10

Godkendelsesdato: 02-10-2019


Varighed: 1 semester

Version: Arkiv

Kommentar

15016701(tidligere UVA) er identisk med denne kursusbeskrivelse.

Indgangskrav

Ingen

Faglige forudsætninger

Studerende, der følger kurset, forventes at:

  • Have kendskab til stoffet fra DM549 Diskrete metoder til datalogi. Specielt forudsættes en hvis mængde matematisk modenhed.
  • Kunne anvende metoderne fra DM550 Introduktion til programmering. Specielt forudsættes fortrolighed med programmering i Java.

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, samt generelle metoder til udvikling af nye algoritmer og
matematiske værktøjer til analyse af algoritmers korrekthed og
effektivitet. Dette er helt centralt i forhold til at kunne udvikle
effektiv software, og er vigtigt for forståelsen 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 DM550
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.
  • foretage formålstjenlige valg af datastruktur.
  • designe nye datastrukturer baseret på kendte datastrukturer.
  • designe og implementere et større program, som anvender algoritmer og datastrukturer fra kurset.
  • argumentere præcist for de valg, der foretages i forbindelse med de foregående fire punkter.

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

    N330046112

    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

    Oplyses på kurset

    ECTS-point

    2

    Uddybende information


    Eksamenselement b)

    Tidsmæssig placering

    Juni

    Udprøvninger

    Skriftlig eksamen

    EKA

    N330046102

    Censur

    Ekstern prøve

    Bedømmelse

    7-trinsskala

    Identifikation

    Studiekort

    Sprog

    Følger, som udgangspunkt, undervisningssprog

    Varighed

    3 timer

    Hjælpemidler

    Laptop, bøger og noter må anvendes. Adgang til internettet er ikke tilladt.
    Nærmere beskrivelse af eksamensreglerne vil blive offentliggjort i itslearning.

    ECTS-point

    8

    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

    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
    • Studiefase: Antal timer: 14

    Undervisningsform: Opgaver i studiegrupper.

    Ansvarlig underviser

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

    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 2018 og 2019 Bachelor i datalogi | Odense 2 E19
    BA Centralt fag datalogi et-faglig særligt forløb for datamatikere - optag 1. september 2018, 2019 og 2020 Bachelor i datalogi | Odense 2 E20
    BA centralt fag i datalogi et-faglig - optag 1. september 2016 Bachelor i datalogi | Odense 2 E20
    BA centralt fag i datalogi et-faglig - optag 1. september 2016 Bachelor i datalogi | Odense 2 E19
    BA centralt fag i datalogi et-faglig - optag 1. september 2017 Bachelor i datalogi | Odense 2 E20
    BA centralt fag i datalogi et-faglig - optag 1. september 2017 Bachelor i datalogi | Odense 2 E19
    BA centralt fag i datalogi et-faglig - optag 1. september 2018 Bachelor i datalogi | Odense 2 E20
    BA centralt fag i datalogi et-faglig - optag 1. september 2018 og 2019 Bachelor i datalogi | Odense 2 E19
    BA centralt fag i datalogi et-faglig - optag 1. september 2019 Bachelor i datalogi | Odense 2 E20
    BA centralt fag i datalogi et-faglig - optag 1. september 2020 Bachelor i datalogi | Odense 2 E20
    BA centralt fag i datalogi to-faglig med sidefag - optag 1. september 2018 Bachelor i datalogi | Odense 2 E20
    BA centralt fag i datalogi to-faglig med sidefag - optag 1. september 2018 og 2019 Bachelor i datalogi | Odense 2 E19
    BA centralt fag i datalogi to-faglig med sidefag - optag 1. september 2019 Bachelor i datalogi | Odense 2 E20
    BA centralt fag i datalogi to-faglig med sidefag - optag 1. september 2020 Bachelor i datalogi | Odense 2 E20
    BA centralt fag i datalogi to-faglig med sidefag i kemi eller matematik - optag 1. september 2016 Bachelor i datalogi | Odense 2 E20
    BA centralt fag i datalogi to-faglig med sidefag i kemi eller matematik - optag 1. september 2016 Bachelor i datalogi | Odense 2 E19
    BA centralt fag i datalogi to-faglig med sidefag i matematik - optag 1. september 2017 Bachelor i datalogi | Odense 2 E19
    BA centralt fag i datalogi to-faglig med sidefag i matematik - optag 1. september 2017 Bachelor i datalogi | Odense 2 E20
    BA centralt fag i datalogi to-faglig med sidefag i matematik - optag 1. september 2020 Bachelor i datalogi | Odense 2 E20
    Ikke længere gældende per 31. august 2019 - BA centralt fag i datalogi to-faglig med sidefag i matematik - optag 1. september 2018 Bachelor i datalogi | Odense 2 E19
    Ikke længere gældende per 31. august 2019 - BA centralt fag i datalogi to-faglig med sidefag i matematik - optag 1. september 2018 Bachelor i datalogi | Odense 2 E20
    Ikke længere gældende per 31. august 2019: BA centralt fag i datalogi et-faglig - optag 1. september 2018 Bachelor i datalogi | Odense 2 E20
    Ikke længere gældende per 31. august 2019: BA centralt fag i datalogi et-faglig - optag 1. september 2018 Bachelor i datalogi | Odense 2 E19
    Ikke længere gældende pr. 31.aug 2020 - BA centralt fag i datalogi to-faglig med sidefag - optag 1. september 2018 og 2019 Bachelor i datalogi | Odense 2 E20
    Ikke længere gældende pr. 31.august 2020: BA centralt fag i datalogi et-faglig - optag 1. september 2018 og 2019 Bachelor i datalogi | Odense 2 E20
    Ikke længere gældende pr. 31.august 2020: BA centralt fag i datalogi to-faglig med sidefag - optag 1. september 2018 og 2019 Bachelor i datalogi | Odense 2 E20
    BA Centralt fag i anvendt matematik et-faglig - optag 1. september 2016 Bachelor i anvendt matematik | Bachelor i anvendt matematik | Odense 4 E20
    BA Centralt fag i anvendt matematik et-faglig - optag 1. september 2016 Bachelor i anvendt matematik | Bachelor i anvendt matematik | Odense 4 E19
    BA Centralt fag i anvendt matematik et-faglig - optag 1. september 2017 Bachelor i anvendt matematik | Bachelor i anvendt matematik | Odense 4 E20
    BA Centralt fag i anvendt matematik et-faglig - optag 1. september 2017 Bachelor i anvendt matematik | Bachelor i anvendt matematik | Odense 4 E19
    BA Centralt fag i anvendt matematik et-faglig - optag 1. september 2018 og 2019 Bachelor i anvendt matematik | Bachelor i anvendt matematik | Odense 4 E20
    BA Centralt fag i anvendt matematik et-faglig - optag 1. september 2018 og 2019 Bachelor i anvendt matematik | Bachelor i anvendt matematik | Odense 4 E19
    BA Centralt fag i anvendt matematik et-faglig - optag 1.september 2020 Bachelor i anvendt matematik | Bachelor i anvendt matematik | Odense 4 E20
    BSc.scient.oecon BSc.scient.oecon | Bachelor i matematik-økonomi | Odense 4 F20
    BSc.scient.oecon BSc.scient.oecon | Bachelor i matematik-økonomi | Odense 4 E20, F21
    Software Engineering Bachelor i Software Engineering | Odense 4 F20
    Software Engineering 2018 Bachelor i Software Engineering | Odense 4 E20
    BA Sidefag i datalogi for central fag i biologi, kemi og uden for naturvidenskab - optag 1. september 2016 og 2017 Bachelor i datalogi | Odense 6 E19
    BA Sidefag i datalogi for central fag i biologi, kemi og uden for naturvidenskab - optag 1. september 2016 og 2017 Bachelor i datalogi | Odense 6 E20
    BA Sidefag i datalogi for central fag i biologi, kemi og uden for naturvidenskab - optag 1. september 2018 og 2019 Bachelor i datalogi | Odense 6 E19
    BA Sidefag i datalogi for central fag i biologi, kemi og uden for naturvidenskab - optag 1. september 2018, 2019 og 2020 Bachelor i datalogi | Odense 6 E20
    BA Sidefag i datalogi for central fag i fysik - optag 1. september 2016 og 2017 Bachelor i datalogi | Odense 6 E20
    BA Sidefag i datalogi for central fag i fysik - optag 1. september 2016 og 2017 Bachelor i datalogi | Odense 6 E19
    BA Sidefag i datalogi for central fag i matematik - optag 1. september 2018 og 2019 Bachelor i datalogi | Odense 6 E19
    BA Sidefag i datalogi for central fag i matematik - optag 1. september 2018, 2019 og 2020 Bachelor i datalogi | Odense 6 E20
    BA Sidefag i datalogi for centralfag fysik - optag 1. september 2018 og 2019 Bachelor i datalogi | Odense 6 E19
    BA Sidefag i datalogi for centralfag fysik - optag 1. september 2018, 2019 og 2020 Bachelor i datalogi | Odense 6 E20
    Ikke længere gældende per 31. august 2019 - BA Sidefag i datalogi for central fag i biologi, kemi og uden for naturvidenskab - optag 1. september 2018 Bachelor i datalogi | Odense 6 E19
    Ikke længere gældende per 31. august 2019 - BA Sidefag i datalogi for central fag i biologi, kemi og uden for naturvidenskab - optag 1. september 2018 Bachelor i datalogi | Odense 6 E20
    Ikke længere gældende per 31. august 2019 - BA Sidefag i datalogi for central fag i fysik - optag 1. september 2018 Bachelor i datalogi | Odense 6 E20
    Ikke længere gældende per 31. august 2019 - BA Sidefag i datalogi for central fag i fysik - optag 1. september 2018 Bachelor i datalogi | Odense 6 E21
    Ikke længere gældende per 31. august 2019 - BA Sidefag i datalogi for central fag i fysik - optag 1. september 2018 Bachelor i datalogi | Odense 6 E19
    Ikke længere gældende pr 31.august 2020. BA Sidefag i datalogi for central fag i matematik - optag 1. september 2018, 2019 og 2020 Bachelor i datalogi | Odense 6 E20