DM507: Algoritmer og Datastrukturer (10 ECTS)

STADS: 15016701

Niveau
Bachelorkursus

Undervisningsperiode
Kurset er placeret i forårssemesteret.

Ansvarlige undervisere

Email: rolf@imada.sdu.dk

Skemaoplysninger

Hold	Type	Dag	Tidsrum	Lokale	Uger
Fælles	I	Mandag	12-14	U140	5-7,9-11,14-19
Fælles	I	Tirsdag	14-16	U48A	13
Fælles	I	Tirsdag	14-16	U140	19
Fælles	I	Onsdag	14-16	U140	6
Fælles	I	Torsdag	08-10	U140	5,13,15,17,20
Fælles	I	Fredag	12-15	U48A	22
D2	TE	Tirsdag	14-16	U155	5,9-10,14-15,17
D2	TE	Tirsdag	14-16	U27A	6-7,11
D2	TE	Tirsdag	16-18	U152	16,19
D2	TE	Tirsdag	14-16	U156	18
D2	TE	Tirsdag	10-12	U14	21
D2	TE	Onsdag	14-16	U27A	13
D2	TE	Torsdag	10-12	U155	6,9,11,14,16,20
D2	TE	Fredag	14-16	U14	18
D3	TE	Mandag	08-10	U31	6,9,11,14,18
D3	TE	Mandag	16-18	U14	16
D3	TE	Tirsdag	08-10	U26A	5-7,9-11,13-15
D3	TE	Tirsdag	08-10	U14	18,21
D3	TE	Onsdag	16-18	U152	16-17,19-20
O1	TE	Mandag	08-10	U10	21
O1	TE	Tirsdag	10-12	U146	5-7,9-11,13-19
O1	TE	Onsdag	14-16	U141	9
O1	TE	Torsdag	08-10	U154	6,16
O1	TE	Torsdag	14-16	U56	11,14
O1	TE	Fredag	10-12	U10	18,20
T1	TE	Mandag	14-16	U14	16,19
T1	TE	Mandag	12-14	U154	21
T1	TE	Tirsdag	12-14	U146	5-6
T1	TE	Tirsdag	12-14	U14	7,10
T1	TE	Tirsdag	12-14	U31	9,13-15
T1	TE	Tirsdag	12-14	U26A	11,16
T1	TE	Tirsdag	12-14	U56	17
T1	TE	Tirsdag	12-14	U50A	18
T1	TE	Fredag	12-14	U74	6
T1	TE	Fredag	12-14	U56	9,11
T1	TE	Fredag	12-14	U51	14,18
T1	TE	Fredag	12-14	U31	20

Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal.

Indgangskrav:
Ingen

Faglige forudsætninger:
Stoffet fra DM550 Introduktion til programmering forudsættes kendt. Stoffet fra DM549 Diskrete metoder til datalogi anbefales kendt.

Kursusintroduktion
Kursets formål er at give kendskab til en bred vifte af fundamentale algoritmer og datastrukturer. Endvidere introduceres generelle metoder til udvikling af algoritmer, samt matematiske 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 formålstjenlige 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 de 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: træer, ordbøger, prioritetskøer, disjunkte mængder.

Litteratur

Meddeles ved kursets start.

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

Forudsætningsprøver
Obligatorisk projektopgave. Intern censur ved én underviser. Bestået/ikke bestået. Projektopgaven skal være bestået, for at man kan deltage i eksamen. (15016712)

Eksamen- og censurform:
4 timers skriftlig eksamen. Ekstern censur. Karakter efter 7-trinsskalaen. (15016702)

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.
Introfase: 44 timer
Træningsfase: 40 timer, heraf:
- Eksaminatorie: 40 timer

Aktiviteter i studiefasen Studiefase: 14 timer

Sprog
Dette kursus undervises på dansk eller engelsk, afhængigt af underviseren.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. februar 2015 til 31. januar 2017.