DM517: Beregnelighed (5 ECTS)

STADS: 15001701

Niveau
Bachelorkursus

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

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

• opskrive en endelig automat for et givet regulært udtryk og omvendt
• anvende teknikker som f.eks. lukningsegenskaber og pumpelemmaer for regulære (kontekstfrie) sprog til at demonstrere, at et givet sprog ikke er regulært (kontekstfrit)
• gøre rede for de skridt der indgår i beviser for at et givet sprog ikker er regulært/kontekstfrit, når man anvender de tilsvarende pumpelemmaer
• transformere en given non-deterministisk endelig automat til en ækvivalent deterministisk endelig automat
• opskrive kontekstfrie grammatikker og push-down automater for simple kontekstfrie sprog, samt opskrive en push-down automat for et vilkårligt kontekstfrit sprog som er givet via en kontekstfri grammatik
• beskrive Turing-maskiner i ord eller på diagramform
• opskrive Turing maskiner der afgør/accepterer typiske sprog som er afgørlige/accepterbare
• at vælge den blandt flere Turing-maskine modeller, som passer bedst til et givet afgørligt sprog og begrunde dette valg
• give simple beviser for uafgørlighed af sprog og egenskaber ved sprog for Turing-maskiner
• anvende Rice's sætning til at vise uafgørlighed af sprog

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:
4 timers skriftlig eksamen med alle hjælpemidler (lærebog, noter og lommeregner). Ekstern censur. Karakter efter 7-skalaen. Der er kun eksamen, når faget har kørt. Eksamen i øvrige terminer kun efter ansøgning til studienævnet.

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

Forelæsninger (22 timer) og eksaminatorier/laboratorier (20 timer).
Aktiviteter i studiefasen

Sprog
Der er ikke registreret nogle oplysninger om undervisningssproget.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. september 2006 til 31. august 2008.