Learning objectives
Mathematical foundations of computer science:
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.
Principles and paradigms of programming languages:
The interaction with computers takes place in several ways: when the sought behavior is simple or already encoded, simple and intuitive mechanisms can be used. For a more sophisticate communication the use of highly expressive formalisms is mandatory. Programming languages offer a wide range of notations for the specification of the behaviors that are required from a computer. The study of programming languages is important and fascinating. First, because the study of the fundamental principles (values, bindings, control, abstraction, encapsulation, objects, modules, nondeterminism, types, ...) and their realization in various languages (C, C++, Fortran, Pascal, OCaml, Java, Python, ...) makes one appreciate what really matters in the choice of a programming language, well beyond the "fashion" of the moment. Secondly, the comparative study of programming languages induces the gradual refinement of programming skills and styles independently from the programming languages that, in a given moment of an individual's professional life, are more frequently used. Finally, more often than a student could imagine, the proper solution of a problem in ICT requires the definition of a language and the realization of a "machine" that interprets it.
Prerequisites
Foundations of programming.
Course unit content
The course is composed of two distinct, complementary parts: one on the mathematical foundations of computer science, the other on the principles and paradigms of programming languages.
Full programme
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.
Principles and paradigms of programming languages:
* Description of programming languages.
* Names and environment.
* Memory handling.
* Control structures and abstraction.
* Data structures and abstraction.
Bibliography
* A. Dovier, R. Giacobazzi. Fondamenti dell'Informatica: Linguaggi Formali e Calcolabilità.
* A. M. Pitts. Regular Languages and Finite Automata.
* I. Mastroeni. Eserciziario per il corso ``Fondamenti dell'Informatica: Linguaggi Formali e Calcolabilità''.
* U. Solitro. Linguaggi Formali, Computabilità e Complessità: Esercizi risolti, 2006.
* A. Pettorossi. Automata Theory and Formal Languages, Aracne Editrice, 2006. ISBN: 88-548-0889-X.
* A. Pettorossi. Elements of Computability, Decidability, and Complexity, Aracne Editrice, 2006. ISBN: 88-548-0682-X.
* M. Gabbrielli e S. Martini. Linguaggi di programmazione: principi e paradigmi, Seconda edizione. McGraw-Hill Italia, 2011. ISBN 88-386-6573-8.
Teaching methods
Lectures and exercise sessions.
Assessment methods and criteria
Written, oral and practical examination (an individual or group project is realized on the parts about programming languages).
Other information
Mailing list: http://studenti.cs.unipr.it/mailman/listinfo/Fondamenti-Informatica
