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.

Eksamensdato
Den ordinære eksamen finder sted den 26. marts 2008 og 27. marts 2008 og 2. juni 2008

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. February 2008 til 31. January 2009.