DM517: Beregnelighed (5 ECTS)

STADS: 15011201

Niveau
Bachelorkursus

Undervisningsperiode
Kurset er placeret i efterårssemesteret.
1. kvartal.

Ansvarlige undervisere
Email: jbj@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal. Kurset kører i 1. kvartal.

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.

Pensum
Se pensumbeskrivelse.

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

Forudsætningsprøver
Ingen

Eksamen- og censurform:
(a) Obligatoriske opgaver der bedømmes med bestået/ikke bestået og intern bedømmelse ved underviser. (15011212) Opgaverne skal være bestået, for at man kan gå op til den skriftlige eksamen.
(b) 4 timers skriftlig eksamen der bedømmes med karakter efter 7-trinsskalaen og ekstern censur. (15011202)

Reeksamen efter 2. kvartal. 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.

Forelæsninger: 22 timer
Eksaminatorier/laboratorier 20 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. september 2011 til 31. august 2013.