Diskret matematik, algoritmer og datastrukturer

Studienævnet for uddannelserne ved Det Tekniske Fakultet

Undervisningssprog: Dansk. Såfremt studerende eller underviser er ikke-dansktalende, vil undervisningen foregå på engelsk.
EKA: T510040102
Censur: Ekstern prøve
Bedømmelse: 7-trinsskala
Udbudssteder: Odense
Udbudsterminer: Forår
Niveau: Bachelor

Fagnummer: T510040101
ECTS-point: 10

Godkendelsesdato: 03-11-2021


Varighed: 1 semester

Version: Arkiv

Fagnummer

T510040101

Fagtitel

Diskret matematik, algoritmer og datastrukturer

ECTS-point

10

Intern kursuskode

SE4-DMAD

Ansvarligt studienævn

Studienævnet for uddannelserne ved Det Tekniske Fakultet

Godkendelsesdato

03-11-2021

Fagansvarlige

Navn E-mail Institut
Mette Lind Johansen melj@tek.sdu.dk TEK Uddannelseskoordinering og -support
Mikkel Baun Kjærgaard mbkj@mmmi.sdu.dk SDU Software Engineering

Undervisere

Navn E-mail Institut By
Lene Monrad Favrholdt lenem@imada.sdu.dk Algorithms
Rolf Fagerberg rolf@imada.sdu.dk Algorithms

Undervisningssekretær

Navn E-mail Institut By
Anna Schollain avs@tek.sdu.dk TEK Uddannelseskoordinering og Support

Udbudssteder

Odense

Niveau

Bachelor

Udbudsterminer

Forår

Varighed

1 semester

Anbefalede forudsætninger

Studerende, der følger kurset, forventes at:

  • Besidde matematisk modenhed, som f.eks. opnået gennem kurset Calculus og Lineær Algebra.
  • Kunne programmere i Java.

Overordnet målbeskrivelse

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 værktøjer fra diskret matematik til beskrivelse, analyse og bevisførelse i 
relation til algoritmers korrekthed og effektivitet. 

Målbeskrivelse - viden

  • Definere og beskrive relevante koncepter indenfor diskret matematik, algoritmer og datastrukturer 

Målbeskrivelse - færdigheder

  • Arbejde med logiske udsagn, relationer og bevisteknikker, herunder induktion.
  • 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.

Indhold

Kurset indeholder følgende faglige hovedområder:

  • Diskret matematik: bevisteknikker (herunder induktion), logik, relationer, rekursionsligninger, invarianter. 
  • Algoritmer: korrekthed og kompleksitetsanalyse, del-og-hersk algoritmer (master teorem, Strassens algoritme), grådige algoritmer, dynamisk programmering, graf-algoritmer (BFS, DFS, topologisk sortering af DAGs, sammenhængskomponenter, stærke sammenhængskomponenter, minimum udspændende træ, korteste veje), Huffman-kodning. 
  • Datastrukturer: ordbøger (binære søgetræer, rødsorte træer, hashing), prioritetskøer, disjunkte mængder. 

URL til Skemaplan

Antal undervisningstimer

96 timer per semester

Undervisningssprog

Dansk. Såfremt studerende eller underviser er ikke-dansktalende, vil undervisningen foregå på engelsk.

Eksamensbestemmelser

Eksamensbestemmelser

Navn

Eksamensbestemmelser

Tidsmæssig placering

I slutningen af semestret.

Udprøvninger

Eksamen

EKA

T510040102

Navn

Eksamen

Beskrivelse

1) Formatet er Multiple Choice (MCQ)
2) Tilladte hjælpemidler: Laptop, bøger og noter må anvendes Adgang til internettet er ikke tilladt. Nærmerebeskrivelse af eksamensregler vil blive offentliggjort i itslearning.
3) Eksamen er individuel.

Prøveform

Skriftlig prøve

Censur

Ekstern prøve

Bedømmelse

7-trinsskala

Identifikation

Studiekort - Eksamensnummer

Sprog

Følger, som udgangspunkt, undervisningssprog

Varighed

3 timer og 45 minutter

ECTS-point

10

Fagudbud

Udbuds periode Udbudstype Profil Uddannelse Semester

Studieforløb

Profil Uddannelse Semester Udbuds periode