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
Written exam.
Other information
- - -
