DM507: Algoritmer og Datastrukturer (10 ECTS)

STADS: 15000701

Niveau
Bachelorkursus

Undervisningsperiode
Kurset er placeret i efterårssemesteret.
1. og 2. kvartal.

Ansvarlige undervisere
Email: lenem@imada.sdu.dk

Skemaoplysninger
Hold Type Dag Tidsrum Lokale Uger Kommentar
Fælles I Mandag 12-14 U20 36,38-41,45-51
Fælles I Mandag 12-14 U9 37
Fælles I Torsdag 08-10 U26 36-38
S1 TE Tirsdag 08-10 U24 36-41, 45-51
S1 TE Fredag 08-10 U24 36-38
S2 TE Mandag 14-16 U24 36-41,45-51
S2 TE Fredag 12-14 U17 36-38
Vis hele skemaet
Vis personligt skema for dette kursus.

Indgangskrav:
Ingen

Faglige forudsætninger:
Stoffet fra Programmering A og B (DM502 og DM503) skal være kendt. Diskrete Strukturer (DM504) anbefales.

Kursusintroduktion
Kursets formål er at give kendskab til fundamentale klasser af algoritmer samt til hvorledes disse realiseres ved hjælp af datastrukturer. Endvidere introduceres basale værktøjer til analyse af algoritmers korrekthed og effektivitet.

Kompetencer
De studerende vil blive i stand til at
  • designe algoritmer

  • vælge og implementere passende datastrukturer

  • analysere algoritmer mht. korrekthed og køretid



Forventet læringsudbytte
Ved kursets afslutning forventes den studerende at kunne

• 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 fornuftige valg af datastruktur
• designe nye datastrukturer baseret på kendte datastrukturer
• designe og implementere et større program, som bl.a. anvender algoritmer og datastrukturer fra kurset
• argumentere præcist for de valg, der foretages i forbindelse med foregående 4 punkter


Emneoversigt
Matematisk grundlag:
  • rekursionsligninger


Algoritmer:
  • korrekthed og kompleksitetsanalyse

  • del og hersk algoritmer

  • grådige algoritmer

  • dynamisk programmering
  • sortering

  • graf-algoritmer

  • Huffman-kodning


Datastrukturer:
  • abstrakte datatyper

  • træer

  • ordbøger

  • prioritetskøer

  • disjunkte mængder



Litteratur
    Meddeles ved kursets start


Pensum
Se pensumbeskrivelse.

Kursets hjemmeside
Dette kursus benytter e-learn (blackboard).

Forudsætningsprøver
Ingen

Eksamen- og censurform:
a) 4 timers skriftlig eksamen med alle hjælpemidler (lærebog, noter, lommeregner). Ekstern censur. Karakter efter 7-skalaen.

b) Obligatorisk projektopgave som tæller 3 ECTS ud af kurset samlede omfang på 10 ECTS. Intern censur ved én underviser. Bestået/ikke bestået. Projektopgaven skal være bestået, for at man kan deltage i eksamen.

Der er eksamen når kurset har kørt. Eksamen udenfor disse terminer kun efter ansøgning til studienævnet.

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.

Forelæsninger (32 timer) og eksaminatorier (32 timer).
Aktiviteter i studiefasen

Sprog
Dette kursus undervises på dansk.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. september 2006 til 31. januar 2008.