Information Engineering

The general training objectives: The course, of a theoretical nature, has as main objective the acquisition of the basic notions on automata and languages, and the development of the skills of formalization, abstraction, modeling of systems and analysis of complex problems. Knowledge and ability to understand The course aims to provide the basic knowledge of the theory of automata and languages, with particular attention to finite state automata seen as a mathematical description of the finished control of a program or, more generally, of a system discrete sequential, and to the Turing Machines, seen as a general model of computation. The study of these formalisms, cornerstones of all modern informatics, is essential for the understanding of concepts, results and fundamental concepts for an informatics, among which: the notions of algorithm or sequential procedure and the possibility of their abstract description through sequences, choices and cycles, the result of sequential programming; the existence of problems that can not be solved or problems that are "difficult" to solve, in terms of calculation resources, and therefore the need for their classification in complexity classes; the clear distinction between syntactic and semantic aspects and the notion of simulation and reduction, as an instrument of semantic comparison between formalisms or syntactically different problems. Knowledge and comprehension skills applied The course, even if fundamentally theoretical, has a significant applicative value. In particular, the theoretical bases learned make it possible to deal with numerous applicative problems in a mathematically clear and rigorous way: the applications of the theory of automata and of languages, in fact, range from the recognition of artificial and natural languages, through compile theory, to the pattern string matching, al description and verification of complex software and hardware systems (Model Checking), to game theory. Autonomy of judgment and communication skills The expected learning outcomes are linked to the ability to use the most appropriate formal tools in different application contexts, adequately motivating their choice. Ability to learn The formal concepts and tools presented in the course favor the individual deepening of one's own knowledge and the understanding of topics covered in other courses, such as the problems related to the specification, implementation and verification of systems. SPECIFIC OBJECTIVES: 1) knowledge and understanding of the logical and formal bases of calculability theory 2) ability to apply basic knowledge on calculation models: automata, languages. 3) skills related to the comparison between the different models and their applicability to programming 4) ability to communicate and transmit the contents of theoretical computer science by inserting them into the foundation of an information technology theory. 5) critical skills that allow to compare in a laboratory form the various applications of the classification of problems with respect to their complexity (classes P / np / np-HARD)