FOUNDATIONS OF COMPUTER SCIENCE
cod. 07581

Academic year 2024/25
2° year of course - Second semester
Professor
Enea ZAFFANELLA
Academic discipline
Informatica (INF/01)
Field
Discipline informatiche
Type of training activity
Characterising
72 hours
of face-to-face activities
9 credits
hub:
course unit
in ITALIAN

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

- - -

2030 agenda goals for sustainable development

- - -