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: 28-10-2022


Varighed: 1 semester

Version: Godkendt - aktiv

Indgangskrav

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

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 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 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

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

Oplyses på kurset

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

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 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) - 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 2019, 2020, 2021 og 2022 Bachelor i datalogi | Odense 2 E22
BA Centralt fag datalogi et-faglig særligt forløb for datamatikere - optag 1. september 2020, 2021 og 2022 Bachelor i datalogi | Odense 2 E23
BA centralt fag i datalogi et-faglig - optag 1. september 2019 Bachelor i datalogi | Odense 2 E22
BA centralt fag i datalogi et-faglig - optag 1. september 2020 og 2021 Bachelor i datalogi | Odense 2 E23
BA centralt fag i datalogi et-faglig - optag 1. september 2020 og 2021 Bachelor i datalogi | Odense 2 E22
BA centralt fag i datalogi to-faglig med sidefag - optag 1. september 2019 Bachelor i datalogi | Odense 2 E22
BA centralt fag i datalogi to-faglig med sidefag - optag 1. september 2020 og 2021 Bachelor i datalogi | Odense 2 E23
BA centralt fag i datalogi to-faglig med sidefag - optag 1. september 2020 og 2021 Bachelor i datalogi | Odense 2 E22
BA centralt fag i datalogi to-faglig med sidefag i matematik - optag 1. september 2020 og 2021 Bachelor i datalogi | Odense 2 E22
BA centralt fag i datalogi to-faglig med sidefag i matematik - optag 1. september 2020 og 2021 Bachelor i datalogi | Odense 2 E23
Ikke længere gældende pr. 31.aug 2020 - BA centralt fag i datalogi to-faglig med sidefag - optag 1. september 2019 Bachelor i datalogi | Odense 2 E22
Ikke længere gældende pr. 31.august 2020: BA centralt fag i datalogi et-faglig - optag 1. september 2019 Bachelor i datalogi | Odense 2 E22
Ikke længere gældende pr. 31.august 2020: BA centralt fag i datalogi to-faglig med sidefag - optag 1. september 2019 Bachelor i datalogi | Odense 2 E22
BA Centralt fag i anvendt matematik et-faglig - optag 1. september 2019 Bachelor i anvendt matematik | Bachelor i anvendt matematik | Odense 4 E22
BA Centralt fag i anvendt matematik et-faglig - optag 1.september 2021 Bachelor i anvendt matematik | Bachelor i anvendt matematik | Odense 4 E23
BA Centralt fag i anvendt matematik et-faglig - optag 1.september 2021 Bachelor i anvendt matematik | Bachelor i anvendt matematik | Odense 4 E22
BA Centralt fag i anvendt matematik et-faglig - optag 1.september 2022 Bachelor i anvendt matematik | Bachelor i anvendt matematik | Odense 4 E22
BA Centralt fag i anvendt matematik et-faglig - optag 1.september 2022 og 2023 Bachelor i anvendt matematik | Bachelor i anvendt matematik | Odense 4 E23
Bacheloruddannelsen i Matematik-Økonomi, Odense, gældende fra 1. september 2020 BSc.scient.oecon - 2022 | Bachelor i matematik-økonomi | Odense 4 E22
Ikke længere gældende pr. 31.august 2021 BA Centralt fag i anvendt matematik et-faglig - optag 1.september 2020 Bachelor i anvendt matematik | Bachelor i anvendt matematik | Odense 4 E22
Ikke længere gældende pr. 31.august 2021 BA Centralt fag i anvendt matematik et-faglig - optag 1.september 2020 Bachelor i anvendt matematik | Bachelor i anvendt matematik | Odense 4 E23
Ikke længere gældende pr. 31.august 2022: BA Centralt fag i anvendt matematik et-faglig - optag 1.september 2021 Bachelor i anvendt matematik | Bachelor i anvendt matematik | Odense 4 E23
Ikke længere gældende pr. 31.august 2022: BA Centralt fag i anvendt matematik et-faglig - optag 1.september 2021 Bachelor i anvendt matematik | Bachelor i anvendt matematik | Odense 4 E22
BA Sidefag i datalogi for central fag i matematik - optag 1. september 2019 og 2020 Bachelor i datalogi | Odense 6 E22
BA Sidefag i datalogi for central fag i matematik - optag 1. september 2020 Bachelor i datalogi | Odense 6 E23
BA Centralt fag i anvendt matematik et-faglig - optag 1.september 2020 Bachelor i anvendt matematik | Bachelor i anvendt matematik | Odense 6 E22
BA Centralt fag i anvendt matematik et-faglig - optag 1.september 2020 Bachelor i anvendt matematik | Bachelor i anvendt matematik | Odense 6 E23
BA Sidefag i Informatik for central fag uden for naturvidenskab - optag 1. september 2022 Bachelor i datalogi | Odense 6 E22
BA Sidefag i Informatik for central fag uden for naturvidenskab - optag 1. september 2022 og 2023 Bachelor i datalogi | Odense 6 E23
BA Sidefag i datalogi for central fag i biologi eller kemi - optag 1. september 2020, 2021 og 2022 Bachelor i datalogi | Odense 6 E22
BA Sidefag i datalogi for central fag i biologi eller kemi - optag 1. september 2020, 2021, 2022 og 2023 Bachelor i datalogi | Odense 6 E23
BA Sidefag i datalogi for central fag i biologi, kemi og uden for naturvidenskab - optag 1. september 2019 Bachelor i datalogi | Odense 6 E22
BA Sidefag i datalogi for centralfag fysik - optag 1. september 2019 Bachelor i datalogi | Odense 6 E22
BA sidefag i datalogi for centralfag fysik - optag 1. september 2020, 2021 og 2022 Bachelor i datalogi | Odense 6 E22
BA sidefag i datalogi for centralfag fysik - optag 1. september 2020, 2021, 2022 og 2023 Bachelor i datalogi | Odense 6 E23
Ikke længere gældende per. 31. august 2021: BA Sidefag i datalogi for centralfag fysik - optag 1. september 2019 og 2020 Bachelor i datalogi | Odense 6 E22
Ikke længere gældende per. 31. august 2021: BA Sidefag i datalogi for centralfag fysik - optag 1. september 2020 Bachelor i datalogi | Odense 6 E23
Ikke længere gældende pr 31.august 2020. BA Sidefag i datalogi for central fag i matematik - optag 1. september 2019 og 2020 Bachelor i datalogi | Odense 6 E22
Ikke længere gældende pr 31.august 2020. BA Sidefag i datalogi for central fag i matematik - optag 1. september 2020 Bachelor i datalogi | Odense 6 E23
Ikke længere gældende pr. 31.august 2022: BA Sidefag i datalogi for central fag i matematik - optag 1. september 2019, 2020 og 2021 Bachelor i datalogi | Odense 6 E22
Ikke længere gældende pr. 31.august 2022: BA Sidefag i datalogi for central fag i matematik - optag 1. september 2020 og 2021 Bachelor i datalogi | Odense 6 E23
Ikke længere gældende pr. 31.august 2022: BA Sidefag i datalogi for central fag i biologi, kemi og uden for naturvidenskab - optag 1. september 2019, 2020 og 2021 Bachelor i datalogi | Odense 6 E22
Ikke længere gældende pr. 31.august 2022: BA Sidefag i datalogi for central fag i biologi, kemi og uden for naturvidenskab - optag 1. september 2020 og 2021 Bachelor i datalogi | Odense 6 E23

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.