Learning objectives
Provide the basic elements and formal tools for studying problems that can and cannot be dealt with using a computer.
Prerequisites
Functions of one variable A, Programming 1.
Course unit content
<br /> Introductory notes on the algorithm concept, on the representation<br />of information, and on computer architecture.<br />Formal languages.<br />Regular expressions.<br />Finite state automata.<br />Generative grammars.<br />Context-free languages.<br />Turing machines.<br />Computable and non-computable functions.
Full programme
- - -
Bibliography
A. Dovier, R. Giacobazzi. Fondamenti dell'Informatica: Linguaggi Formali e Calcolabilita.<br />A. M. Pitts. Regular Languages and Finite Automata.<br />I. Mastroeni. Collection of exercises for the ``Fundamentals of Computer Science: Formal Languages and Computability'' course.
Teaching methods
- - -
Assessment methods and criteria
- - -
Other information
- - -