DM507: Algoritmer og Datastrukturer (10 ECTS)

STADS: 15000701

Niveau
Bachelorkursus

Undervisningsperiode
Kurset er placeret i forårssemesteret.
3. og 4. kvartal.

Ansvarlige undervisere
Email: rolf@imada.sdu.dk

Skemaoplysninger
Hold Type Dag Tidsrum Lokale Uger Kommentar
Fælles I Mandag 10-12 U140 05-11, 15-20
Fælles I Onsdag 14-16 U140 05, 07, 09
Fælles I Onsdag 08-10 U140 20
Fælles I Fredag 14-16 U140 11
M1 TE Torsdag 10-12 U10 05-11, 15-18, 20-21
M1 TE Fredag 10-12 U49E 06, 08, 10
S7 TE Onsdag 14-16 U49B 06, 08, 10
S7 TE Torsdag 14-16 U27 05-11, 15-18, 20-21
Vis hele skemaet
Vis personligt skema for dette kursus.

Skemaændringer:
: Forelæsning onsdag uge 20 i U140.
: Forelæsning fredag uge 11 i U140.

Kommentar:
Obligatorisk på Mat.Øk 2.år.
Ubegrænset deltagerantal. 3. + 4. kvartal.

Indgangskrav:
Ingen

Faglige forudsætninger:
Stoffet fra Programmering A og B (DM502 og DM503) skal være kendt. Stoffet fra Matematiske Redskaber i Datalogi (DM527) anbefales kendt.

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.

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)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.
    b) 4 timers skriftlig eksamen med alle hjælpemidler (lærebog, noter, lommeregner). Ekstern censur. Karakter efter 7-trinsskalaen.


    Reeksamen efter 4. kvartal i august. Reeksamen er en mundtlig eksamen, der bedømmes med karakter efter 7-trinsskalaen og ekstern censur.

    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 eller engelsk, afhængigt af underviseren. Dog altid på Engelsk ved deltagelse af internationale studerende.

    Kursustilmelding
    Se tilmeldingsfrister.

    Pris for åben uddannelse
    Se priser for enkeltkurser.

    Denne kursusbeskrivelse var gyldig fra 1. februar 2009 til 31. januar 2012.