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
Fagtitel
ECTS-point
10
Intern kursuskode
Ansvarligt studienævn
Godkendelsesdato
Fagansvarlige
Navn | 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 | Institut | By | |
---|---|---|---|
Lene Monrad Favrholdt | lenem@imada.sdu.dk | Algorithms | |
Rolf Fagerberg | rolf@imada.sdu.dk | Algorithms |
Undervisningssekretær
Udbudssteder
Niveau
Udbudsterminer
Varighed
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