Skip to main content
If you continue browsing this website, you agree to our policies:
  • Condizioni di utilizzo e trattamento dei dati
Continue
x
If you continue browsing this website, you agree to our policies:
  • Condizioni di utilizzo e trattamento dei dati
Continue
x
e-Learning - UNIMIB
  • Home
  • My Media
  • More
Listen to this page using ReadSpeaker
English ‎(en)‎
English ‎(en)‎ Italiano ‎(it)‎
 Log in
e-Learning - UNIMIB
Home My Media
Percorso della pagina
  1. Science
  2. Master Degree
  3. Informatica [F1802Q - F1801Q]
  4. Courses
  5. A.A. 2021-2022
  6. 1st year
  1. Models and Computation
  2. Summary
Insegnamento con unità didattiche Course full name
Models and Computation
Course ID number
2122-1-F1801Q132
Course summary SYLLABUS

Blocks

Skip Teaching units

Teaching units

Course full name Concurrent Models Course ID number 2122-1-F1801Q132-F1801Q132M
Course summary SYLLABUS
Course full name Thory of Computation Course ID number 2122-1-F1801Q132-F1801Q133M
Course summary SYLLABUS

Course Syllabus

  • Italiano ‎(it)‎
  • English ‎(en)‎
Export

Obiettivi

Il corso ha come obiettivo l'acquisizione di capacità di analisi e di sintesi in riferimento ai modelli e metodi
computazionali utilizzati dall'informatica. In particolare lo studente dovrà acquisire capacità di formalizzare e
modellare problemi utilizzando anche approcci teorici moderni sviluppati per poter trattare problematiche
computazionali nel mondo web e di gestione di grandi molidi dati e nell'ambito della analisi e verifica di sistemi
software. Il corso si compone di due moduli, il primo denominato Modelli della concorrenza fornisce gli strumenti
teorici per comprendere e manipolare concetti di base dell'informatica relativi al comportamento e descrizione di
processi, quali ad esempio la concorrenza. Il secondo modulo, denominato Teoria della Computazione ha come
obiettivo l'acquisizione di strumentalità di base dell'informatica volte alla comprensione della complessità
computazionale dei problemi, alla loro classificazione e alle metodologie algoritmiche per la loro soluzione. Inoltre,
si intendono fornire capacità in merito alla soluzione di problematiche teoriche poste dalle nuove tecnologie (web,
flusso di dati, reti complesse, etc.) mediante strutture dati recentemente proposte.

Contenuti sintetici

Teoria della Computazione: Nozioni di base di teoria della computazione (decidibilità, intrattabilità, riduzioni).
Classificazione dei problemi in funzione della complessità computazionale. Complessità di approssimazione e
parametrica. Approcci moderni per la gestione, indicizzazione, compressione di dati massivi sia con strutture dati
che con tecniche algoritmiche innovative. Strutture dati succinte (FM-index), indicizzazione e ricerca per i big-data
con tecniche di hashing probabilistico, algoritmi di compressione dati. Applicazioni ed esemplificazioni all'analisi di
dati del web. Modelli formali per la specifica e la verifica di correttezza.

Modelli della concorrenza: modelli interattivi e reattivi, calcoli di processi e reti di Petri. Sintassi e semantica a interleaving (sistemi di transizioni) e a
ordini parziali (reti di Petri), semantica osservazionale e bisimulazione. La specifica di proprietà e la loro verifica
(logiche modali e temporali, algoritmi di verifica).

Programma esteso

1 Nozioni di base di teoria della computazione (decidibilità, intrattabilità, riduzioni). Classificazione dei problemi in
funzione della complessità computazionale. Complessità di approssimazione.
2 Approcci moderni per la gestione, indicizzazione, compressione di grandi mole di dati, sia con strutture dati che
con tecniche algoritmiche avanzate.
3 Strutture dati di indicizzazione (es. FM-index, bloom filters, hashing), pattern matching, paradigma shift-And,
compressione dati LZ, strutture dati succinte.
4 Applicazioni ed esemplificazioni all'analisi di big-data.
5 Modelli formali per la specifica e la verifica di correttezza. La semantica assiomatica dei programmi sequenziali
6 Modelli della concorrenza: modelli di sistemi reattivi, calcoli di processi e reti di Petri.
7 Sintassi e semantica a interleaving (sistemi di transizioni) e a ordini parziali (reti di Petri), semantica
osservazionale e bisimulazione
8 La specifica di proprietà e la loro verifica (logiche modali e temporali, algoritmi di verifica).

Prerequisiti

Nessuno.

Modalità didattica

Lezioni frontali ed esercitazioni- Il corso è in lingua italiana.

Materiale didattico

Dispense e articoli pubblicati sul sito dell'insegnamento. Testi di consultazione indicati sul sito dell'insegnamento.

Periodo di erogazione dell'insegnamento

Primo semestre.

Modalità di verifica del profitto e valutazione

Esami scritto e orale. Vengono erogate due prove scritte, una per la parte di Teoria e una per la parte di Modelli. Le
prove scritte consistono nello svolgimento di esercizi relativi all'acquisizione di competenze specifiche nelle
tematiche principali del programma del corso. Le prove orali invece comprendono una discussione della parte
scritta e domande sui contenuti dell'insegnamento (si vedano i dettagli nei syllabi dei due moduli).

Il voto finale e' la media dei voti ottenuti nei due moduli.

Orario di ricevimento

Su appuntamento o come orario da ricevimento indicato su sito web.

Export

Aims

The main objective of the course is the acquisition of skills related to the analysis and development of
computational models and methods in computer science. The student should gain the ability of formalizing and
modelling problems using theoretical models and modern computational approaches to solve problems arising from
the WEB and the analysis and verification of software systems. The course consists of two sessions, the first one
devoted to Concurrent models deals with the theoretical tools used to face basic concepts in computer science
concerning the behaviour and description of processes, such as concurrency. The second session introduces to
the Theory of Computation and deals with the acquisition of basic theoretical tools that allow to understand the
computational complexity of problems, how they are classified according to their complexity and then how they can
be solved by algorithmic methodologies.

Contents

Theory of Computation: Basic notions of theory of computation (decidability, intractability,
Classification of problems with respect their computational complexity. Approximation complexity. Modern
approaches to indexing, compression of large data sets by using novel data structures and algorithmic techniques.
Indexed data structures (ex. Suffix-tree, trie, hashing), pattern matching.

Concurrent models: Formal Models for correctness specification and verification. Interactive and reactive models,
process calculi, Petri nets. Syntax and semantics of interleaving (transition systems) and of partial orders (petri
nets), observational semantics and bisimulation. Specifying and verifying properties (modal and temporal logics,
verification algorithms).

Detailed program

1 Basic notions of theory of computation (decidability, intractability, reductions). Classification of problems with
respect their computational complexity. Approximation complexity.
2 Modern approaches to indexing, compression of massive data sets by using novel data structures and
algorithmic techniques.
3 Indexed data structures (ex bloom filters, hashing), pattern matching, the paradigm shift-and, data compression,
succinct data structures.
4 "Applications to the analysis of massive data.
5 Formal Models for correctness specification and verification, assiomatic semantics
6 Concurrent models: models of reactive systems, process calculi, Petri nets
7 Syntax and semantics of interleaving (transition systems) and of partial orders (Petri nets), observational
semantics and bisimulation.
8 Specifying and verifying properties (modal and temporal logics, verification algorithms).

Prerequisites

None.

Teaching form

Lectures and practice exercises- the course is in Italian

Textbook and teaching resource

Notes and papers available on the course site. Reference texts suggested on the course site.

Semester

First semester.

Assessment method

Oral and written exams. The written exam consists of two assignments one for each module of the course, Theory
and Models. Each assignment consists of a list of exercises whose solution requires the acquisition of skills related
to the main topics of the course syllabus. The oral exam consists in a discussion of the written assignments with
the main aim (see the details of the two modules).

The final grade is the average of the two grades obtained for each single module.

Office hours

By appointment or as indicated by the web-site.

Enter

Key information

ECTS
12
Term
First semester
Activity type
Mandatory
Course Length (Hours)
106
Language
Italian

Students' opinion

View previous A.Y. opinion

Bibliography

Find the books for this course in the Library

Enrolment methods

Manual enrolments
Guest access
Self enrolment (Student)

You are not logged in. (Log in)
Policies
Get the mobile app
Powered by Moodle
© 2025 Università degli Studi di Milano-Bicocca
  • Privacy policy
  • Accessibility
  • Statistics