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.

Kommentar:
Ubegrænset deltagerantal.

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 og analysen 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
Ved kursets afslutning forventes den studerende at kunne:

• designe og analysere randomiserede algoritmer
• bevise nedre grænser for kompleksitet af algoritmer ved hjælp af informationsteoretiske argumenter
• bevise nedre grænser på kompleksitet af algoritmer ved hjælp af modstander argumenter
• lave amortiserede analyser
• forklare Fibonacci heaps og redegøre for køretiden af deres operationer
• forklare algoritmer til string matching og redegøre for køretiden af disse
• tilpasse kendte algoritmer og datastrukturer til specialtilfælde af kendte problemer og til nye problemer
• designe og analysere nye algoritmer til at løse problemer, som i natur minder om problemer fra kurset
• definere klasserne P og NP formelt
• forklare Cook's sætning, der viser at SAT er NP-fuldstændigt • give flere eksempler på NP-fuldstændighedsbeviser

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 7-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.

Reeksamen efter 4. kvartal.

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
Dette kursus undervises på dansk.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

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