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
· 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.
Forelæsninger 3 timer (2+1).
Øvelser 4 timer
Obligatorisk program
6 opgaver
Anders Møller
Mundtlig, ekstern censur, 13-skalaen
4. kvarter
5 ECTS