Inizio della pagina -
Logo DISCO
|
Visita la Versione ad elevata leggibilità
|
Vai al Contenuto della pagina
|
Vai alla Fine dei contenuti
|
Vai al Menu Principale
|
Vai alla Barra di navigazione (sei in)
|
Vai al Menu di navigazione (albero)
|
Vai alla Lista dei comandi
|
Vai alla Lista degli approfondimenti
|
Vai al Menu inferiore
|
Logo Ateneo
   
Per gli Studenti
Modelli e computazione

Codice ins.

Insegnamento

CFU ins.

Anno

Sem.

SSD ins.

Responsabile insegnamento

F1801Q132

Modelli e Computazione

12

1

2

 

Bonizzoni Paola

Docente Modulo Modelli della concorrenza: Pomello Lucia
Docente Modulo Teoria della computazione: Bonizzoni Paola

Obiettivi formativi:
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 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 di base 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.

Metodi didattici:
Lezioni frontali e esercitazioni

Programma:
Parte I
Modelli della concorrenza

  • 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, tool di verifica).

Testi:
Verranno distribuite dispense varie. Si segnala inoltre il seguente testo di riferimento:
L. Aceto, A. Ingolfsdottir, K.G. Larsen, J. Srba, Reactive Systems, modelling, Specification and verification, Cambridge Univ. Press, 2007.
http://rsbook.cs.aau.dk/index.php/Main_Page <http://rsbook.cs.aau.dk/index.php/Main_Page>

Parte II 
Teoria della Computazione 

  • Nozioni di base di teoria della computazione (decidibilità, intrattabilità, riduzioni). Classificazione dei problemi in funzione della complessità computazionale. Complessità di  approssimazione.
  • Approcci moderni per la gestione, indicizzazione, compressione  di grandi mole di dati, sia con  strutture dati che con  tecniche algoritmiche avanzate.
  • Strutture dati di indicizzazione (es. suffix-tree, trie, hashing), pattern matching, paradigma shift-And, compressione dati.
  • Applicazioni ed esemplificazioni  all'analisi  del web (reti complesse).

 

Codice ins.

Insegnamento

CFU ins.

Anno

Sem.

SSD ins.

Responsabile insegnamento

F1801Q132

Models and computation

12

1

2

 

Bonizzoni Paola

Course objectives:
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.

Program:
I - Concurrent models
Formal Models for  correctness specification and verification Concurrent models: 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 tools).
II - Theory of Computation
Basic notions of theory of computation (decidability, intractability, reductions). 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, the paradigm shift-and, data compression.
Applications to the WEB (complex networks).
Testi:
Dispense varie
Modalità di verifica dell'apprendimento:
Esame:
Scritto e orale

Tipo valutazione:
Voto finale

Reference textbooks:
Various notes. Suggested book:
L. Aceto, A. Ingolfsdottir, K.G. Larsen, J. Srba,Reactive Systems, modelling, Specification and verification, Cambridge Univ. Press, 2007.

Approfondimenti

Google Translate
Translate to English Translate to French Translate to German Translate to Spanish Translate to Chinese Translate to Portuguese Translate to Arabic
Translate to Albanian Translate to Bulgarian Translate to Croatian Translate to Czech Translate to Danish Translate to Dutch Translate to Finnish Translate to Greek Translate to Hindi
Translate to Hungarian Translate to Irish Translate to Japanese Translate to Korean Translate to Norwegian Translate to Polish Translate to Romanian Translate to Russian Translate to Serbian
Translate to Slovenian Translate to Swedish Translate to Thai Translate to Turkish

(C) Copyright 2016 - Dipartimento Informatica Sistemistica e Comunicazione - Viale Sarca, 336
20126 Milano - Edificio U14
redazioneweb@disco.unimib.it - ultimo aggiornamento di questa pagina 06/12/2012