MODELS OF COMPUTATION
Docenti
 Scheda dell'insegnamento
 Obiettivi formativi
 Prerequisiti
 Contenuti
 Metodi didattici
 Verifica dell'apprendimento
 Testi
 Altre informazioni
 Mutuazioni
The course has a definite theoretical character. The main objective is the acquisition of the most fundamental notions regarding models of computation, both sequential and distributed/parallel. The focus of the course is on the development of student’s capability of modelling and analyzing complex systems within a formal mathematical approach. Classical sequential and parallel computation models will be presented, starting from Deterministic, Nondeterministic, Oracle and Alternating Turing Machines. In this context, classical Finite state automata will be considered as the natural description of a finite control of any computation device or program. More recent models for distributed systems/networks based on automata (weighted, timed, probabilistic) will also be considered, both synchronous and asynchronous. These topics are fundamental and indispensable to understand notions, concepts and result that every computer science student should master, as:
• Church Turing’s Thesis and the existence of undecidable problems
• The notion of simulations among syntactic models and semantic issues
• Complexity analysis of algorithms and problems, in terms of time, space and number of processors. Intractable problems and their classifications (nondeterminism, parallelism, games)
• Communicating strategies in a distributed environment (I/O, synchronous, asynchronous, broadcasting);
• Modelling, analysis and verification of distributed complex systems; safety proprieties and the Combinatorial explosion problem
• The role of a Compositional approach in complex systems specification and verification. Automata with interfaces for modelling open systems.
Notions, concepts and techniques presented are of fundamental importance in dealing with applied problems, even if the course character is essentially theoretical. In particular, a mathematical and rigorous approach is needed when considering problems as: protocols and circuits verification, security issues in networks, planning, , computational learning, , time and probability in critical systems; .complex systems, both hardware and software.
The student is supposed to learn how to use suitable formal tools in different applied contexts, and to motivate adequately their use in specific applications, by confronting them on a solid mathematical ground.
The course will be selfcontained as much as possible. Basic notions and results on algebra and logic, algorithms, grammars and formal languages, finite state automata, Turing Machines, as provided in first courses on Algebra, Algorithms, Formal Languages and Automata, are needed and will be briefly recalled if necessary.
Any algorithm is given through the description of its control structure and the data structure on which instruction operates. Hence, corner stones of classical computer science are the notion of Finite state automaton (FSA), describing precisely the control structure of any sequential program or, more generally, of any state/ transition discrete dynamical system, and of Turing Machine ( Finite state automaton enriched by the capability of modifying data), considered the general model of computation (according to the CurchTuring Thesis). Both these models are very natural with respect to sequential computations, but they represent non sequential systems and parallel or distributed computations, where more machines interact during their computation, only by considering a (weaker) notion of nondeterminism.
Surprisingly, since the beginning FSA have been associated with networks, where a single node is a classical automaton: the seminal paper of McCulloch and Pitts introduced FSA as a formal model of neurons, aiming at modeling neuron networks. Von Neumann extended these approach by introducing Cellular automata in order to model synchronous networks with fixed topology. A widely accepted formal model for networks of interacting machines and their behavior, that could be used for verification, is still missing.
Topics indicated with (*) will be discussed during the lectures and are integral part of the exam, topics indicated with (**) may be discussed during the lectures and could be material for individual study.
In details (the hours are indicative):
 Preliminaries: strings, languages, operations, free monoid, languages/characteristic functions/sets (3h) (*)
 Finite representation of languages, Cantor's results, Hilbert and undecidability (3h) (*)
 Deterministic and Oracle Turing Machines as general computing devices. (3h) (*)
 Universal T.M., interpreter, compiler, Halting Problem (4h) (*)
 Recursive and recursively enumerable sets , examples, software correctness, discussion (4h) (*)
 Non deterministic and Alternating T. M. as general models for parallel computation, simulations, examples and classical problems (3h) (*)
 Time and space complexity for algorithms, problems, T.M (3h) (*)
 Complexity theory, classes P, NP, P Space, NC; Complete problems, Cook's theorem, examples of complete problems , applications (8h) (*)
 Games and their complexity. (2h)(**)
 Other classical formalisms: Ram language, While language, compilers, Partially Recursive Functions, Turing equivalence, Church Turing Thesis (8h) (*)
 Smn, Recursion , Rice Theorems (4h) (*)
 Beyond the ChurchTuring thesis: discussion (2h) (**)
 Grammars and the Chomsky Hierarchy, regular and context free languages, applications (4h) (*)
 Membership problem for classes of problems with application to parsing (4h) (*)
 Finite state automata and their role in modeling discrete sequential systems, basic properties and examples (3h) (*)
 Compositionality and Kleene's theorem. (4h) (*)
 Nerode's Theorem (2h) (*)
 Automata based models for distributed systems and their behavior, both synchronous and asynchronous: Cellular Automata, Zielonka’s Asynchronous Automata and Trace languages, Petri nets (12h) (*)
 Weighted automata for describing timed,and probabilistic dynamical systems: Rabin automata, Markov chains (2h) (**).
 “Concurrent”and biological system models based on term rewriting and regular expressions: Lindenmayer systems, Milner ‘s CCS and various process algebras. Statecharts as hierarchical systems. (6h) (**)
 SpanCospan: a compositional approach to the specification and verification of distributed systems/networks (2h)(**)
The teaching activities include lectures (60h) and class exercises (12h). The formalisms and arguments presented during lectures are motivated with examples of application and through class exercises, that have an essential role in preparing the final exam. Students are expected to actively participate in discussion over general topics as: the role of compositionality, the role of formal approaches, possible applications. The students are encouraged to present an argument of their interest (previous discussion with the professor) during the lessons, if possible, or during the exam.
The evaluation procedure consists of an oral discussion which aims to test the correct comprehension and the acquisition of the scientific material contained in the textbook; at least two questions will be formulated on this material. The student can propose a starting argument for the examination. Historical and interdisciplinary motivations and in particular practical applications for the theoretical material of the course will be questioned (at least two questions). At least one question will be on topics of recent interest presented during the lessons and not contained in the proposed textbooks, but only on the lecture slides. Final mark (out of 30) depends on the completeness and correctness of answers to specific questions (70%), the clarity of the exposition.(10%) and adequateness of answers
The site http://bertoni.di.unimi.it/ contains most of the material presented during the course lectures, in italian:
Computability theory (Calcolabilità),
Complexity and Games theory (Complessità e Teoria dei Giochi ), only partially covered
Texts:
J.Hopcroft, J.Ullmann, Formal languages and their relations to automata, on line
U. Montanari, R. Bruni, Models of Computation, Springer
R.F.C. Walters, Categories and Computer Science, Cambridge University Press, 1992 (in English)
Note that the course is original and the material innovative, hence, a textbook containing all the topics presented during the lessons does not exists at the present.
In preparation:
A. Gianola, S. Kasangian, N.Sabadini, Da Turing alle reti.
Slides from the lectures will be collected and posted on the University site of the course; scientific papers will be suggested as possible individual learning percorse.
Office hours will be defined at the beginning of the course. It will always be possible to contact directly the professor via email in order to obtain an appointment at different hours: nicoletta.sabadini@uninsubria.it

corso di studio in: MATEMATICA

corso di studio in: MATEMATICA

corso di studio in: MATEMATICA
Cerchi il programma? Potrebbe non essere ancora stato caricato o riferirsi ad insegnamenti che verranno erogati in futuro.
Seleziona l‘anno in cui ti sei immatricolato e troverai le informazioni relative all'insegnamento del tuo piano di studio.