Regularitet og automater

Regularitet og automater

 

Målbeskrivelse

Målet med kurset er at give den studerende et grundlæggende kendskab til begrebet regularitet, dvs. egenskaber som generelt kendetegner beregningsprocesser i it-systemer med begrænset mange tilstande. Den studerende introduceres til en abstrakt beregningsmodel (endelige automater) dækkende alle sådanne systemer, og den studerende vil blive bekendt med metoder til at konstruere og ræsonnere omkring automater

Indholdbeskrivelse

· formelle modeller for regularitet, herunder endelige automater, regulære udtryk og regulære grammatikker,

· sammenhæng mellem disse modeller, karakterisationer af udtrykskraft og begrænsninger, samt tilhørende bevisteknikker (f.eks. invarians, strukturel induktion),

· en række eksempler på anvendelser af modellerne i datalogi,

· relationer til mere generelle modeller for problemløsning.

Undervisning

Forelæsninger 3 timer (2+1).
Øvelser 4 timer

Obligatorisk program
6 opgaver

Bemanding

Anders Møller

Eksamensform

Mundtlig, ekstern censur, 13-skalaen

Placering

4. kvarter

Omfang

5 ECTS