AIMS AND CONTENT

LEARNING OUTCOMES

The course introduces the concepts related to the main computation models for the treatment of formal languages ​​(finite state automata and regular grammars, push-down automata and context-free grammars, syntax-guided translation). The concept of Turing machine as a universal model of computation is also introduced and the theoretical aspects related to the computability and complexity of the algorithmic solution of problems on the Turing machine are provided. Finally, the course introduces the main algorithm design strategies and the tools to evaluate their correctness and performance. The goal is to develop the ability to formalize and solve problems algorithmically and the ability to analyze and evaluate solutions.

AIMS AND LEARNING OUTCOMES

Attendance and active participation in the proposed training activities (lectures and exercises) and individual study will allow the student to:

- Understand the theoretical bases of computer science intended as automatic processing of formal languages ​​starting from the simplest computational models such as finite state automata, up to the most complex ones such as the Turing machine.

- Understand the relationship between computational models and formal languages ​​and establish a correspondence between the type of language and the corresponding power required by the computational model.

- Understand the main issues related to the development of algorithms, both related to correctness and performance; how to understand simplified models for resource estimation.

- Know the main algorithms and data structures in common use: their origins, their structure and their performance in terms of consumption of computational resources.

TEACHING METHODS

The course is mainly structured in lectures of a frontal nature whose material will be made available to students in advance on Aulaweb. For each topic, the corresponding references to the textbooks listed in the bibliography will be provided.

SYLLABUS/CONTENT

Prerequisites: deductive logic and proof
​Regular languages ​​and finite state automata
Context-free languages ​​and push-down automata
The Turing machine
Introduction to (Turing) computability
Introduction to (Turing) complexity
From the Turing machine to the RAM machine
Models for the analysis of algorithms: worst case, average case, amortized complexity
Fundamental data structures
"Brute force" strategy and backtracking
"Divide and conquer" strategy
"Diminish and Conquer" strategy
"Transform and Conquer" strategy
Space-time trade-off
"Greedy" algorithms

RECOMMENDED READING/BIBLIOGRAPHY

The theoretical computer science part is taken from the text:

J.E. Hopcroft, R. Motwani, J.D. Ullman Automata Languages ​​and Computability - Pearson

The algorithm design and analysis part is taken from the texts:

R. Sedgewick, K. Wayne - Algorithms (fourth edition) - Addison Wesley
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein - Introduction to Algorithms and Data Structures - 3rd Edition - McGraw-Hill

Other textbooks

The structure of the lectures follows the following text:

A. Levitin - Introduction to The Design and Analysis of Algorithms - 2nd edition - Addison-Wesley

Some of the contents of algorithm design and analysis have been taken from the following texts:

C. Demetrescu, I. Finocchi, G. F. Italiano - Algorithm and Data Structures - 2nd edition McGraw-Hill
S. Skiena - The Algorithm Design Manual - 2nd edition - Springer
D.E. Knuth - The Art of Computer Programming - Vol. 1,2,3 - Addison Wesley
S. Dasgupta, C.H. Papadimitriou, U. Vazirani - Algorithms - McGraw-Hill
G.J.E. Rawlins - Compared to What?: An Introduction to the Analysis of Algorithms - W. H. Freeman.
U. Mamber - Introduction to Algorithms: A Creative Approach - Addison Wesley
J. Bentley - Programming Pearls - 2nd edition - Addison Wesley
J. Kleinberg, E. Tardos - Algorithm Design - Pearson International Edition

Note: It is not necessary to purchase the textbooks to achieve satisfactory preparation for passing the exam. If you wish to consult the texts and they are not available in the library, please contact the instructor.

TEACHERS AND EXAM BOARD

LESSONS

Class schedule

The timetable for this course is available here: Portale EasyAcademy