Discrete Event Systems, 2014-2015

Master of Science in Computer and Automation Engineering

University of Siena

Discrete Event Systems

October 2014 - January 2015

1 News
2 About the instructor
    2.1 Instructor
    2.2 Office hours
3 About the course
    3.1 Training objectives
    3.2 Required background
    3.3 Syllabus
    3.4 Didactic methods
    3.5 Reference book
4 Exams
    4.1 Learning assessment procedures
    4.2 Texts
    4.3 Results
5 Teaching material
    5.1 Exercises with solutions
6 About the lectures
    6.1 Timetable
    6.2 Lecture schedule

1 News

Results of the written exam of February 18, 2015 are available in Section 4.3.
- See Section 4.1 for the admission rules to the oral exam.
- Students admitted to the oral exam are requested to send an email to the Instructor to fix a date for the oral exam.
Past exams are available in Section 4.2 (in English only Academic Years 2012/13 and 2013/14, some exams are with solutions).

2 About the instructor

2.1 Instructor

	Simone Paoletti, PhD
	Assistant Professor
	Building: San Niccolò
	Floor: 2
	Room: 229 (red circle on the map)
	Email:
	Phone: 0577 23 4850 ext. 1020
	Web: http://www3.diism.unisi.it/~paoletti/

2.2 Office hours

Contact the Instructor via email.

3 About the course

3.1 Training objectives

Discrete event systems are systems whose dynamic behaviour is driven by asynchronous occurrences of discrete events.
Examples can be found in a variety of fields, such as control, computer science, automated manufacturing, and communication and transportation networks.
The aim of this course is to equip the students with several modelling and analysis tools for discrete event systems.
Lab tutorials with Matlab will be an important part of this course.

3.2 Required background

Dynamical systems
Probability

3.3 Syllabus

Prerequisites (dynamic systems and probability)
Logical models of discrete event systems
Timed models of discrete event systems
Stochastic timed models of discrete event systems
Markov chains
Queueing theory
Markovian queueing networks

3.4 Didactic methods

The course will be organized in lectures (50%) and tutorials, held both in class (25%) and in computer lab (25%).

3.5 Reference book

[CL08] C.G. Cassandras, S. Lafortune, "Introduction to discrete event systems". 2nd ed., Springer, 2008.

4 Exams

4.1 Learning assessment procedures

The exam consists of a written part (with the help of Matlab) and an oral part.
- Admission to the oral exam is subject to a grade ≥ 18 (out of 30) obtained at the written exam.
- The oral exam should be given within the same session as the written exam.
- In case of failure of the oral exam, the student must repeat also the written exam.
One midterm and one endterm written exam will be scheduled during the course.
- Admission to the oral exam is subject to an average grade ≥ 18 and both grades ≥ 15.
- During the winter session of exams, students may repeat either the midterm or the endterm written exam to enhance the grade.

4.2 Texts

Exams of Academic Year 2013/14 (some with solutions)
Exams of Academic Year 2012/13 (some with solutions)
Exams of Academic Year 2011/12 (in Italian)
Exams of Academic Year 2010/11 (in Italian)
Exams of Academic Year 2009/10 (in Italian)
Exams of Academic Year 2008/09 (in Italian, some with solutions)
Exams of Academic Year 2007/08 (in Italian, some with solutions)
Exam of November 12, 2014 (in Italian)
Midterm exam of November 19, 2014 (with solutions)
Exam of February 3, 2015 (with solutions of Exercises 1 and 2)
Exam of February 18, 2015 (with solutions of Exercises 1 and 2)

4.3 Results

5 Teaching material

5.1 Exercises with solutions

Exercises on timed automata
Exercises on stochastic timed automata
Exercises on stochastic timed automata with Poisson clock structure
NEW! Exercises on discrete-time homogeneous Markov chains

6 About the lectures

6.1 Timetable

Monday - from 9AM to 1PM (room F)
Wednesday - from 2PM to 4PM (room F)

6.2 Lecture schedule

Date	Topics	Book sections	Notes
October 1, 2014 (2h)	Presentation of the course Introduction to Discrete Event Systems (DES)		Slides
October 6, 2014 (4h)	Basics of system theory Concept of system Static vs dynamical systems Concept of state Concept of event Time-driven vs event-driven systems Systems vs (mathematical) models Definition of Discrete Event System (DES) Examples: queueing system tank system	Chapter 1 (except §1.2.7, §1.2.8 and §1.3.5)
October 8, 2014 (2h)	Logical models of DES: state automata (with outputs) Graphical representation of state automata Exercises	Section 2.2.2 Examples 2.10 and 2.11	Exercises (with solutions)
October 13, 2014 (4h)	Lecture canceled
October 15, 2014 (2h)	Lecture canceled
October 20, 2014 (4h)	Time and event timing Introduction to event timing dynamics Definition of clock structure Timed models of DES: timed automata Algorithm for event timing dynamics	Sections 5.1 and 5.2
October 22, 2014 (2h)	Exercises		Exercises (with solutions)
October 27, 2014 (4h)	Review of probability theory Uncertainty sources in models of DES Models of DES with uncertainty: stochastic timed automata	Sections 6.1, 6.3 and 6.4 Appendix I (except §I.7 and §I.8)
October 29, 2014 (2h)	Example of analysis of a stochastic timed automaton		Example
November 3, 2014 (4h)	The exponential distribution: definition and properties Stochastic timed automata with Poisson clock structure The Poisson counting process	Sections 6.6, 6.7 and 6.8
November 5, 2014 (2h)	Exercises		Exercises (with solutions)
November 10, 2014 (4h)	Exercises		Exercises (with solutions)
November 12, 2014 (2h)	Exercises		Exercises (with solutions)
November 17, 2014 (4h)	Exercises (summary) Use of simulation for analysis of stochastic timed automata Law of large numbers Estimation of state and event probabilities Estimation of empirical probability density functions
November 19, 2014 (2h)	Midterm written exam
November 24, 2014 (4h)	Basics of stochastic processes Markov property and Markov processes Discrete-time homogeneous Markov chains Graphical representation Transition probability matrix and its properties Chapman-Kolmogorov equations State holding times Example	Sections 7.1 and 7.2 (from §7.2.1 to §7.2.7)
November 26, 2014 (2h)	Discrete-time homogeneous Markov chains State probabilities Classification of states	Section 7.2 (only §7.2.8)
December 1, 2014 (4h)	Discrete-time homogeneous Markov chains Steady state analysis Exercises	Section 7.2 (only §7.2.9)	Exercises (with solutions)
December 3, 2014 (2h)	Exercises		Exercises (with solutions)
December 10, 2014 (2h)	Continuous-time homogeneous Markov chains Graphical representation Transition rate matrix and its properties Chapman-Kolmogorov equations	Section 7.3 (except §7.3.7)
December 15, 2014 (4h)	Continuous-time homogeneous Markov chains State holding times Transition probabilities State probabilities Classification of states Steady state analysis Equivalences between classes of models Stochastic timed automata with Poisson clock structure Continuous-time homogeneous Markov chains	Section 7.3 (only §7.3.7)
December 17, 2014 (2h)	Endterm written exam
January 7, 2015 (2h)	Simulation of stochastic timed automata (lab tutorial)		Matlab files
January 12, 2015 (4h)	Queueing theory Specification of queueing models A/B/m/K notation Transient and steady state analysis Characterization of steady state Performance of queueing systems Little's law PASTA property Examples of Markovian queueing systems	Sections from 8.1 to 8.6 (except §8.2.5)
January 14, 2015 (2h)	Exercises		Exercises (with solutions)

File translated from T_EX by T_TH, version 4.03.
On 18 Nov 2016, 17:58.