DM517: Beregnelighed (5 ECTS)

STADS: 15000001

Niveau
Bachelorkursus

Undervisningsperiode
Kurset er placeret i efterårssemesteret.

Ansvarlige undervisere
Email: jbj@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal.

Indgangskrav:
Ingen

Faglige forudsætninger:
Stoffet fra Algoritmer og Datastrukturer skal være kendt.

Kursusintroduktion
At introducere teorien for endelige automater, formalismer for formelle sprog, samt afgørlighedsbegrebet.

Kompetencer
De studerende vil opnå detaljeret indsigt i formalismer for formelle sprog 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.

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 ikke er kontekstfrie vha. f.eks. lukningsegenskaber og pumpelemmaer
• Konstruere deterministiske Turing maskiner som afgør et givet sprog eller beregner en givet funktion
• Bevise uafgørligheden af visse sprog vha. Rices sætning og reduktioner

Emneoversigt
Endelige automater, push-down automater, Turing-maskiner, regulære sprog, kontekstfrie sprog, grammatikker, afgørlighed.

Litteratur

Meddeles ved kursets start.

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

Forudsætningsprøver
Obligatoriske opgaver der bedømmes med bestået/ikke bestået og intern bedømmelse ved underviser. Opgaverne skal være godkendt af underviser, for at man kan gå op til den skriftlige eksamen. (15000012)

Eksamen- og censurform:
4 timers skriftlig eksamen der bedømmes med karakter efter 7-trinsskalaen og ekstern censur. (15000002)

Reeksamen i samme eksamenstermin eller i umiddelbar forlængelse heraf. Reeksamen er en mundtlig eksamen, der bedømmes med karakter efter 7-trinsskalaen og ekstern censur.

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

Aktiviteter i studiefasen Studiefase: 10 timer

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