Anno Accademico 16/17

Logica per Informatica

Si vogliono fornire agli studenti strumenti formali per il ragionamento rigoroso sia in linguaggio naturale che in linguaggi formali. Si vuole utilizzare la logica come strumento per una descrizione rigorosa della specifica di un programma e per porre le basi della verifica automatica di proprietà di programmi.

Simulation and Modelling

The purpose of this course is the introduction to the Performance Evaluation of computing systems and telecommunication networks. The course consists of two parts: the first introduces the most important techniques used to study models of the behavior of traffic systems; the second deals with the presentation of a few fundamental models followed by the accurate discussion of a few case studies published in the literature.


The introductory level of this course does not allow to model and to analyze real systems, but provides enough information to enable the student to perform the analysis of existing systems knowing the methods that are best suited for this goal and the capabilities of existing solution techniques. The course is taught using a language and examples coming from the performance evaluation of computing systems, but the techniques discussed during the lectures are suited for the analysis of models pertaining to a much larger spectrum of application fields.

 

The models discussed in this course correspond to probabilistic representations in which different aspects of reality are expressed in form of networks of servers in front of which queues may develop because of the existence of congestion and/or synchronization phenomena. The analysis of the behaviour of these queuing networks is approached during this course using analytic and numerical techniques (in the simple cases) and simulation methods in the complex ones.

The methodological part of the course is further divided in three other sections referring to Operational Analysis, Markov Chains and Queuing theory, and Simulation.

 

Operational Analysis is discussed in the first part of the course to introduce the basic concepts of this subject and to tackle the modelling and analysis of relatively simple case studies. When the probabilistic characteristics of the models become more complex, the course introduces  Markov chains and discusses how this mathematical framework can be used to study in a nice and elegant manner intrinsically complex models, but with computational costs that may be extremely large.

When Markov chains turn out to be inadequate for tackling the complexity of real cases, Discrete Event Simulation becomes the most suitable analysis technique.

 

The simulation of a probabilistic model consists of writing a program capable of reproducing (with a certain level of abstraction) the behaviour of the model. The execution of the simulation program corresponds to the evolution of the model, starting from an initial state and ending in a predefined final state. The execution of the program is driven by random number generators and thus corresponds to one of the possible evolutions of the model. Measures performed during the simulation are instances of random variables; the statistical analysis of the simulation output is thus performed to obtain interval estimates (confidence intervals) of the performance indices of the models.

 

Once the basic elements of modelling and analysis of these models have been discussed, the course focuses on a few reference applications coming from telecommunication and distributed computing contexts and shows how components of systems of this type can be modelled and evaluated for the assessment of their performance. These case studies, taken from the literature, are presented with the aim of providing the student with an idea of how these methods are used in reality and of the complexity of their application to concrete cases.

 

Integral part of the course is the periodic assignment of  exercises  and the proposal of a final project that will be discussed during the oral exam.

Scopo di questo corso è l'introduzione alla Valutazione delle Prestazioni dei sistemi di calcolo e delle reti di telecomunicazione. Il corso si compone di due parti: la prima tratta le più importanti metodologie di analisi utilizzate per lo studio dei modelli utili per l'analisi del comportamento dei sistemi di traffico; la seconda prevede la discussione di alcuni modelli fondamentali, seguita dall'approfondimento di alcuni casi di studio presentati in letteratura.

 

Il livello introduttivo del corso non permette di affrontare lo studio e la modellizzazione di sistemi reali, tuttavia la preparazione fornita è sufficiente per rendere ogni studente capace di affrontare lo studio di casi reali avendo conoscenza del metodo di analisi da seguire e delle potenzialità delle tecniche disponibili. Il linguaggio e gli esempi utilizzati durante il corso si ispirano alla problematica della valutazione delle prestazioni dei sistemi di calcolo, ma le metodologie discusse hanno un ambito di applicazione ben più vasto.

 

I modelli discussi in questo corso sono delle rappresentazioni probabilistiche in cui  vari aspetti della realtà vengono espressi sotto forma di  reti di stazioni di servizio in fronte alle quali è possibile che si formino delle code a causa di fenomeni di congestione o di sincronizzazione. Lo studio del comportamento di queste reti di code viene affrontato in questo corso facendo uso di tecniche analitiche e numeriche (nei casi più semplici) e di tecniche simulative in quelli più complessi.

 

La parte metodologica del corso è suddivisa a sua volta in tre sezioni riguardanti

l'Analisi Operazionale, la teoria delle Catene di Markov e delle code, e la Simulazione.

 

L'Analisi Operazionale viene discussa nella prima parte del corso per introdurre i concetti fondamentali di questa materia e per affrontare la modellazione e la soluzione di casi relativamente semplici.

Quando le caratteristiche probabilistiche dei modelli da analizzare si complicano, il corso introduce le Catene di Markov ed illustra come questo modello matematico possa permettere di affrontare con eleganza problemi intrinsecamente molto complessi, ma a spesa di un costo computazionale generalmente molto elevato. Quando anche le Catene di Markov risultano inadeguate per affrontare le problematiche dei sistemi reali si fa ricorso alla Simulazione ad Eventi Discreti.

 

La simulazione del comportamento di un modello probabilistico consiste nella scrittura di un programma capace di riprodurre (con un certo livello di astrazione) le modalità di funzionamento del modello stesso. L'esecuzione di questo programma corrisponde ad una evoluzione del modello a partire da un certo stato iniziale per giungere ad un determinato stato finale. Questa esecuzione è guidata da generatori di numeri casuali e corrisponde quindi ad una delle possibili evoluzioni del modello. Le misure eseguite durante la simulazione diventano pertanto delle istanze di variabili casuali e sono oggetto di analisi statistica per fornire stime intervallari (intervalli di confidenza) degli indici di prestazione del modello stesso.

Sviluppate le conoscenze delle tecniche di base utilizzate per l’analisi di questi modelli, il corso sposta l’attenzione su alcune applicazioni di riferimento prese dal contesto delle reti di telecomunicazione e dei sistemi di calcolo distribuiti per affrontare la modellazione di alcune loro componenti e per valutarne le prestazioni. Questi casi di studio, presi dalla letteratura, sono discussi con lo scopo di fornire allo studente un'idea dell'uso reale di queste metodologie e della complessità della loro applicazione in casi concreti.

 

Parte integrante del corso sono una serie di esercizi che vengono periodicamente assegnati ed un progetto finale che viene discusso in sede di esame.