DS814: Algoritmer og Datastrukturer

Det Naturvidenskabelige Studienævn

Undervisningssprog: På dansk eller engelsk afhængigt af underviser
EKA: N340127112, N340127102
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: Kandidat

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

Godkendelsesdato: 28-10-2022


Varighed: 1 semester

Version: Arkiv

Kommentar

Kurset samlæses med DM507.

Indgangskrav

Kurset kan ikke følges, hvis DM507 indgår som obligatorisk i din studieordning, eller hvis DM507 følges samtidig med eller tidligere er bestået som valgfrit.
Dette kursus kan ikke følges af kandidatstuderende på Datalogi.

Faglige forudsætninger

Studerende, der følger kurset, forventes at:

  • Have en hvis mængde matematisk modenhed.
  • Kunne anvende metoderne fra DS801 Introduktion til objektorienteret 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 kurset DS801 Introduktion til objektorienteret 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

N340127112

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

Eksamenselement b)

Tidsmæssig placering

Juni

Udprøvninger

Skriftlig eksamen

EKA

N340127102

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

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.