Regularitet og Automater (Q4) ( forår 2011 - 5 ECTS )
Rammer for udbud
-
Uddannelsessprog:
dansk
-
Niveau:
Grundkursus
-
Semester/kvarter:
Q4
-
Timer per uge:
7
-
Deltagerbegrænsning:
Ingen
-
Undervisningssted:
Århus
-
Hovedområde:
Det Naturvidenskabelige Fakultet
-
Udbud ID:
27074
Formål
Deltagerne vil efter kurset have indsigt i teori om formelle sprog.
Obligatorisk program
6 obligatoriske opgaver
Indhold
Kurset dækker følgende emner indenfor teori om formelle sprog: Endelige automater, regulære udtryk og regulære grammatikker; egenskaber ved disse, bl.a. ækvivalens og begrænsninger; eksempler på praktiske anvendelser; bevisteknikker, f.eks. induktion; relation til mere generelle beregningsmodeller som kontekstfri grammatikker og Turing-maskiner.
Læringsmål
Deltagerne skal ved afslutningen af kurset kunne:
-
referere
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.
Faglige forudsætninger
Calculus 1+2, Introduktion til Programmering, Programmering 2
Underviser
Anders Møller
Undervisnings- og arbejdsform
Forelæsninger (3t/uge), øvelser (2t/uge), studiecafe (2t/uge)
Dansk
Litteratur
John Martin, Introduction to Languages and the Theory of Computation, 4. udgave, McGraw-Hill, 2010
Kursushjemmeside
http://www.cs.au.dk/dRegAut
Skemaplacering (forelæsninger)
Onsdag 14-17
Blokpar F:
http://science.au.dk/uddannelse/undervisning/blokpar/
Eksamensterminer
Eksamen: 4. kvarter
Placering: Uge 22 0g 23
Reeksamen: August
http://science.au.dk/uddannelse/undervisning/eksamen/regler-for-tilmelding-til-kurser-med-fastlagt-eksamen/
Udbyder
Datalogisk Institut
Indgår i følgende studieordninger
Bacheloruddannelsen i Datalogi
Tilmelding til undervisning
https://mit.au.dk/da/index.cfm
Bedømmelse
Mundtlig eksamen uden forberedelse (20 min)
7-skala, ekstern censur
