Learning objectives
The course provides the formal tools and the notions that are fundamental to study the problems that are or are not solvable by means of computers. The course begins with the presentation of the theory of automata and formal languages: this is the foundation of the description and implementation of programming languages. This is followed by the illustration of the concepts and the nature of the problems that admit effective solution, that is, of those problem that can be solved by computers.
Prerequisites
Foundations of programming. Calculus. Algebra and geometry.
Course unit content
Mathematical foundations of computer science:
* Introduction to the concept of algorithm, the representation of information, and the computer architecture.
* Formal languages.
* Regular expressions.
* Finite state automata.
* Generative grammars.
* Context-free languages.
* Turing machines.
* Computable and non computable functions.
* Computability and programming languages.
* Introduction to recursive and recursively enumerable sets.
Full programme
- - -
Bibliography
Text book:
A. Dovier, R. Giacobazzi. Fondamenti dell'Informatica Bollati-Boringhieri, 2020.
Other useful books:
I. Mastroeni. Eserciziario per il corso ``Fondamenti dell'Informatica: Linguaggi Formali e Calcolabilità''.
U. Solitro. Linguaggi Formali, Computabilità e Complessità: Esercizi risolti, 2006.
Teaching methods
Lectures and exercise sessions.
Assessment methods and criteria
The exam consists of a written test and an optional oral interview.
The written test is composed of exercises and open questions on the course contents; the oral interview consists in further questions on the
course contents. The oral
interview, if any, must occur in the same exam slot as the written test.
Students with a grade between 18 and 26 in the written test will pass the
exam (without the oral interview); the oral interview is reserved to
students with a grade greater than 26 or between 16 and 17 in the
written test.
Other information
- - -
