DM508: Algoritmer og kompleksitet (5 ECTS)

STADS: 15000801

Niveau
Bachelorkursus

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

Ansvarlige undervisere
Email: joan@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

Indgangskrav:
Ingen

Faglige forudsætninger:
Stoffet fra DM507 Algoritmer og Datastrukturer og DM504 Diskrete Strukturer skal være kendt.

Kursusintroduktion
Formålet med kurset er

• at give kendskab til udviklingen af effektive algoritmer


• at give kendskab til kompleksitet af algoritmer og den dertil knyttede teori

Kompetencer
De studerende vil opnår indsigt i flere teknikker til design af effektive algoritmer og i teorien for kompleksitet af algoritmer. De skal kunne anvende den opnåede viden i relevante sammenhænge til

• at designe og analysere randomiserede algoritmer


• at bevise nedre grænser for kompleksitet af algoritmer med brug af informationsteoretiske argumenter


• at bevise nedre grænser for kompleksitet af algoritmer med brug af modstander argumenter


• at lave amortiserede analyser


• at forklare Fibonacci heaps


• at forklare algoritmer til string matching


• at forklare hvad NP-Complete betyder og bevise at problemer er NP-Complete

Forventet læringsudbytte


Emneoversigt
Randomiserede algoritmer, nedre grænser (informationsteoretiske og modstanderargumenter), amortiseret analyse, Fibonacci heaps, string-matching, teorien for NP-fuldstændighed.

Litteratur

Meddeles ved kursets start.

Pensum
Se pensumbeskrivelse.

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

Forudsætningsprøver
Ingen

Eksamen- og censurform:
(a) Mundtlig eksamen af ca. 30 min. varighed, og med 30 min. forberedelse med alle hjælpemidler. Ekstern censur. Karakter efter 13-skalaen.
(b) Obligatoriske projektopgaver som tilsammen tæller 1 ECTS ud af kursets samlede omfang på 5 ECTS. Intern censur ved én underviser. Bestået/ikke bestået. Projektopgaverne skal være bestået for at man kan deltage i eksamen.

Der er kun eksamen, når faget har kørt. Eksamen i øvrige 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 (21 timer) og eksaminatorier (21 timer).
Aktiviteter i studiefasen

Sprog
Der er ikke registreret nogle oplysninger om undervisningssproget.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

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