DM553: Kompleksitet og beregnelighed (10 ECTS)

STADS: 15016101

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 DM508 Algoritmer og datastrukturer.

Indgangskrav:
Ingen

Faglige forudsætninger:
Stoffet fra Algoritmer & Datastrukturer og Algoritmer & Sandsynlighed forudsættes kendt.

Kursusintroduktion
At introducere teorien for endelige automater, formalismer for formelle sprog, afgørlighedsbegrebet, udviklingen og analysen af approksimationsalgoritmer, samt kompleksiteten af algoritmer og den dertil knyttede teori

Kompetencer
De studerende vil opnå detaljeret indsigt i formalismer for formelle sprog, kompleksitiet af problemer, herunder approximation muligheder for optimeringsproblemer, og afgørlighedsbegrebet og skal kunne anvende den opnåede viden i relevante sammenhænge til:

• at opskrive en endelig automat for et givet regulært udtryk og omvendt.
• at demonstrere, at et givet sprog ikke er regulært (kontekstfrit) ved hjælp af teknikker som f.eks. lukningsegenskaber og pumpelemmaer for regulære (kontekstfrie) sprog.
• at transformere en given non-deterministisk endelig automat til en ækvivalent deterministisk endelig automat.
• at afgøre, om en given grammatik er kontekstfri, opskrive kontekstfrie grammatikker for simple kontekstfrie sprog, samt opskrive en push-down automat for et givet kontekstfrit sprog.
• at arbejde med Turing-maskine begrebet og beskrive Turing-maskiner i ord eller på diagramform.
• at vælge den blandt flere Turing-maskine modeller, som passer bedst til et givet afgørligt sprog.
• at arbejde med uafgørlighedsbegrebet og kunne give simple beviser for uafgørlighed af sprog og egenskaber ved sprog for Turing-maskiner.
• at bevise uafgørligheden af visse sprog vha. Rices sætning og reduktioner.
• 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 definitioner af kompleksitetsklasserne P og NP formelt, at forklare hvad NP-Complete betyder og Cook's Sætning, og at bevise at problemer er NP-Complete.
• at forklare og analysere approksimationsalgoritmer.

Forventet læringsudbytte
Efter kurset forventes den studerende at kunne:

• Konstruere endelige automater og regulære udtryk for simple sprog
• Konstruere stakautomater og kontekstfrie grammatikker for simple sprog
• Anvende sætninger og algoritmer til regulære eller kontekstfrie sprog inden for kursets pensum
• Bevise at visse sprog ikker er kontektsfrie vha. fx lukningsegenskaber og pumpelemmaer
• Konstruere deterministiske og ikke deterministiske Turing maskiner som afgør et givet sprog eller beregner en given funktion
• Bevise uafgørligheden af visse sprog vha. Rices sætning og reduktioner
• Bevise nedre grænser for kompleksitet af algoritmer vha. informationsteoretiske argumenter
• Bevise nedre grænser på kompleksitet af algoritmer vha. modstander argumenter
• Tilpasse kendte algoritmer og datastrukturer til specialtilfælde af kendte problemer og til ny problemer
• Forklare og analysere approksimationsalgoritmer fra kurset
• Designe og analysere nye approksimationsalgoritmer 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
Endelige automater, push-down automater, Turing-maskiner, regulære sprog, kontekstfrie sprog, grammatikker, afgørlighed, nedre grænser (informationsteoretiske og modstanderargumenter), kompleksitetsklasserne P og NP, teorien for NP-fuldstændighed, approksimationsalgoritmer.

Litteratur

Meddeles ved kursets start.

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

Forudsætningsprøver
Obligatoriske projektopgaver. Bedømmes efter bestået/ikke bestået ved intern censur ved underviser. (15016112)

Eksamen- og censurform:

1. Mundtlig eksamen af ca. 30 minutters varighed, samt 30 minutters forberedelse med alle hjælpemidler. Bedømmes efter 7-trinsskalaen ved ekstern censur (10 ECTS). (15016102)

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
Introfase: 38 timer
Træningsfase: 38 timer, heraf:
 - Eksaminatorie: 38 timer

Aktiviteter i studiefasen Studiefase: 30 timer

Sprog
Dette kursus undervises på dansk eller engelsk, afhængigt af underviseren. Dog altid på Engelsk ved deltagelse af internationale studerende.

Bemærkninger
Kurset samlæses med DM508 Algoritmer og kompleksitet

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. februar 2015 til 31. januar 2016.