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: Arkiv
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
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 - 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 i august er en mundtlig eksamen, der bedømmes med karakter efter 7-trinsskalaen og ekstern censur.
Vejledende antal undervisningstimer
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
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.