DM508: Algoritmer og kompleksitet (5 ECTS)

STADS: 15005801

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.

Skemaændringer:
: Eksaminatorie tirsdag uge 10 flyttet til lokale U26.

Kommentar:
Valgfrit på Mat.Øk 3.år.
Ubegrænset deltagerantal. 3. kvartal.

Indgangskrav:
Ingen

Faglige forudsætninger:
Stoffet fra DM507 Algoritmer og Datastrukturer og DM528 Kombinatorik, Sandsynlighed og Randomiserede Algoritmer 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:

• 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
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) Obligatoriske projektopgaver. Intern censur ved én underviser. Bestået/ikke bestået. Projektopgaverne skal være bestået for at man kan deltage i eksamen.
(b) Mundtlig eksamen af ca. 30 min. varighed, og med 30 min. forberedelse med alle hjælpemidler. Ekstern censur. Karakter efter 7-trinsskalaen.

Reeksamen efter 4. kvartal.

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.

Forelæsninger (18 timer) og eksaminatorier (18 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. august 2012.