This teaching unit introduces the main strategies for designing algorithms and the tools for evaluating their correctness and performance. The objective is to develop the ability to formalize and solve problems algorithmically, as well as the capacity for analysis and evaluation of solutions. Additionally, concepts related to propositional logic and induction, and the main models of computation for computer science, such as automata, grammars, and Turing machines, are developed.
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.
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.
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
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.
Ricevimento: Please see the page of the course on Aulaweb for office hours or get in touch with the teacher at armando.tacchella@unige.it
ARMANDO TACCHELLA (President)
The timetable for this course is available here: EasyAcademy
