Simulation is one of the most common techniques used for the evaluation of the performance and if the reliability of Discrete Event Dynamic Systems (DEDS) often modelled with Stochastic Processes. Discrete Event Simulation consists on the execution of a program which results in the production of a realization of a stochastic process driven by Monte-Carlo methods. Learning how to construct a simulator is the main objective of this course, together with the development of the techniques needed for the statistical analysis of the simulation output. To deeply understand the difficulty of writing an efficient simulator equipped with the output analysis components, students will be required to write a few simple simulators “from scratch” without using available tools and libraries.

Part I  (6 CFUs) Simulation and Operational Analysis – The first part of the course is devoted to the presentation and discussion of Discrete Event Simulation. Special attention is devoted to the measures that must be implemented to quantify the simulation results and to operational relations that may be derived among these measures useful to gain confidence on the correctness of the reliability of simulation outputs.

Part II (3 CFUs) Stochastic Processes and Markov Chains – The second part of the course introduces probability based analysis techniques that may be used to further improve the confidence on simulation results

At the end of the course the students will be able to perform the simulation of non-trivial Discrete Event Systems. The exercises and the final project will provide the students with the capability of writing the simulators using a general purpose programming language. Having developed the simulators “from scratch” will allow the students to understand the potentials and the limits of the Discrete Event Simulation technique, thus providing them with the capability of using professional simulators with competence

The course will be based on theoretical lessons as well as on the solution of class exercises. Computer implementations will be required as homework assignments. Personal training on assigned exercises is important for the success in this class.

The final examination will consist in the discussion of a project developed individually by te students used as the basis for asking questions on the theoretical aspects of the exercise. Students will not be required to be able to reproduce the derivations used  to obtain the results discussed during the course, but will have to know the definitions and the applications of the theory.


Prerequisiti

Il corso richiede conoscenze di logica, programmazione e di algoritmi; inoltre si assume che lo studente possegga le nozioni di linguaggio formale, grammatica e di automa, gli argomenti svolti negli esami: Matematica Discreta e Logica, Programmazione 1 e 2, Algoritmi e Strutture Dati, Linguaggi Formali e Traduttori.


Argomenti del corso

Il Corso affronta i seguenti problemi: che cos'e' un algoritmo? Quali problemi si possono risolvere con un algoritmo? E in quali casi un algoritmo richiede risorse inaccessibili nella pratica? Affrontare questi problemi richiede definire la nozione di macchine di Turing, di funzioni calcolabile, i vari possibili criteri di misura delle risorse disponibili (tempo, memoria, processori), le classi di complessita' e il problema P = NP. L'obbiettivo e' imparare la definizione del concetto di calcolo, una maggiore consapevolezza delle limitazioni intrinseche all'uso delle macchine, ed un'idea delle strategie per aggirare a tali limitazioni.


Modalità del corso

Le lezioni si svolgono in aula, ed utilizzano Moodle sia per inviare  messaggi agli studenti che per descrivere sezioni ed esercizi svolti.


Libro di testo e Dispense

Il libro di testo del corso e' il seguente: M. Sipser:"Introduction to the theory of Computation", Course Technology Ptr., 3^edition, 2012. Svolgeremo parte delle sezioni 3,4,5 della parte 2 (Calcolabilità), tranne i risultati sulle grammatiche, e una parte da definire della parte 3 (Complessità). Per maggiori dettagli si veda il programma di esame.



Piano del corso.

48 ore e 24 lezioni di 2 ore ciascuna.

 

Programma tradizionale.

Chiediamo le dimostrazioni di 3 enunciati: Indecidibilità della Accettazione (4.11: linee generali), Teorema 4.22 (detto anche T. di Post), CLIQUE è NP-completo (7.32). In tutti gli altri casi viene richiesto il solo enunciato.

 

Teoria della Computabilità

    • Le Macchine di Turing deterministiche, a più registri, non deterministiche (§ 3).
    • Problemi con soluzione non calcolabile: prova (linee generali) che il problema della accettazione non è decidibile (§ 4 da 4.2). Prova del T. 4.22 (detto anche T. di Post).

 

Teoria della Complessità

    • Classi di Complessita' Temporale (§ 7): definizioni P, NP, EXPTIME, inclusioni note e congetturate, NP-completezza (7.34), Enunciato del Teorema di Cook (7.27).
    • Problemi NP-completi: enunciato problema del cammino di Hamilton e problema SUBSETSUM (sez. 7.3), prova che CLIQUE è NP-completo (7.32).

In corso è suddiviso in due parti:

- Analisi di Fourier (prof. P. Boggiatto)

- Probabilità (prof.ssa L. Sacerdote)