EVU - Regularitet & Automater
Efterår 2010, 5 ECTS
Indhold
Kurset vil dække følgende emner:
- endelige automater, regulære udtryk og regulære grammatikker
- egenskaber ved disse, bl.a. ækvivalens og begrænsninger
- relation til mere generelle beregningsmodeller som kontekst-fri grammatikker og Turingmaskiner
- bevisteknikker
- eksempler på praktiske anvendelser
Læringsmål
Deltagerne skal ved afslutningen af kurset kunne:
- definere den basale terminologi (strenge, sprog, klasser af sprog, samt basale operationer på disse).
- beskrive basale abstrakte sprogformalismer (regulære udtryk, endelige automater, regulære grammatikker, kontekstfri grammatikker) - fra intuitivt niveau og konkrete eksempler til formel notation og generelle definitioner.
- beskrive egenskaber ved formalismerne, bl.a. ækvivalens, begrænsninger og beslutningsprocedurer.
- forklare og udføre algoritmer, der oversætter mellem formalismerne eller afgør beslutningsproblemer - fra konkrete eksempler til generelle og formelle beskrivelser.
- bevise og analysere egenskaber ved formalismerne (ved hjælp af konstruktive beviser og induktionsbeviser) - fra intuitivt niveau til formelle detaljer.
Eksamen vil vurdere i hvor høj grad kursisten besidder disse kompetencer.
Forudsætning
Enkeltfaget forudsætter at kursisten har fulgt faget ”Diskret matematik”.
Tid og sted
Seminarer
Undervisningen vil foregå som heldagsseminarer som vil indeholde en blanding af forelæsning, opgaveløsning og diskussion.
- Fredag 28/8 2010 kl. 9-16
- Fredag 10/9 2010 kl. 9-16
- Fredag 1/10 2010 kl. 9-16
Desuden vil der blive stillet en ugentlig opgave.
Alle gange i Incuba science park (5520.112)
Bemanding
Forelæser: Sigurd Meldgaard <stm@cs.au.dk>
Kursussekretær: Marianne Dammand Iversen <dammand@cs.au.dk>
Kursusplan
| Uge nr. | Dato | Seminar | Emner, slides og opgaver |
|---|---|---|---|
| 34 | 27/8 2010 | Introduktion, Regulære udtryk [Martin, kap. 1.5, 3.1-3.5] (Læs desuden [Martin kap. 1-2] efter behov i løbet af de første uger af kurset.) |
Slides til print slides til skærm Opgaver |
| 35 | |||
| 36 | 10/9 2010 | Nondeterminisme, Kleenes sætning, minimering [Martin: kap. 4.1-4.3, 5.1-5.2] |
Slides til print slides til skærm Opgaver |
| 37 | |||
| 38 | |||
| 39 | 1/10 2010 | Lukketheds- og afgørlighedsegenskaber, Konteksfri gramatikker, Afrunding
[Martin: kap. 5.3-5.5, 6.1-6.2] |
Slides til print slides til skærm opgaver |
Materiale
Kurset tager udgangspunkt i bogen
 |
John Martin |
| Introduction to Languages and the Theory of Computation | |
| 3. udgave, McGraw-Hill, 2002 | |
| ISBN: 0071198547 eller 0072322004 |
En liste af trykfejl.
Bogen kan købes i Stakbogladen Naturfag (kr. 560,- minus 10% studierabat).
Vi vil i løbet af kurset udvikle en software-pakke i Java. Pakken stiller en samling operationer til rådighed, som er begrundet af praktiske anvendelser og samtidig baseret på de teoretiske resultater, der præsenteres på kurset.
Nyheder
Nyheder om kurset annonceres på vores mailingliste. som også kan benyttes til diskussioner om opgaver og lignende.
Man kan tilmelde sig mailing-listen på: denne side
Eksamen
Mundtlig, ekstern censur, 7-trinsskala, 20 min. per person, uden forberedelsestid.
For at kunne indstilles til eksamen skal man have godkendt besvarelser af de obligatoriske opgaver.