DM508: Algoritmer og kompleksitet (5 ECTS)

STADS: 15016801

Niveau
Bachelorkursus

Undervisningsperiode
Kurset er placeret i forårssemesteret.

Ansvarlige undervisere
Email: joan@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal. Fælles med DM553 Kompleksitet og beregnelighed.

Indgangskrav:
Ingen

Faglige forudsætninger:
Stoffet fra DM507 Algoritmer og Datastrukturer og DM538 Algoritmer og sandsynlighed ELLER DM528 Kombinatorik, Sandsynlighed og Randomiserede Algoritmer forudsættes 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 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 forklare hvad NP-Complete betyder og bevise at problemer er NP-Complete
• at forklare og analysere approksimationsalgoritmer

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
• tilpasse kendte algoritmer og datastrukturer til specialtilfælde af kendte problemer og til nye problemer
• designe og analysere nye approksamationsalgoritmer 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
• forklare og analysere approksimationsalgoritmer

Emneoversigt
Nedre grænser (informationsteoretiske og modstanderargumenter), teorien for NP-fuldstændighed, approksimationsalgoritmer.

Litteratur

Meddeles ved kursets start.

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

Forudsætningsprøver
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. (15016812)

Eksamen- og censurform:
Mundtlig eksamen af ca. 30 min. varighed, og med 30 min. forberedelse med alle hjælpemidler. Ekstern censur. Karakter efter 7-trinsskalaen (5 ECTS). (15016802)

Reeksamen efter 4. kvartal.

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
Introfase: 18 timer
Træningsfase: 18 timer, heraf:
 - Eksaminatorie: 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.

Dette er den nyeste version af en kursusbeskrivelse, som trådte i kraft den 1. feb 2015.