Course detail

Model-Based Analysis

FIT-MBAAcad. year: 2022/2023

Introduction of model-base design, testing, analysis and model checking. Petri nets as a model of parallel systems. Techniques for analysis of Petri nets. Markov chains as a model of probabilistic systems. Techniques for analysis of Markov chains. Timed automata as a model of systems working with real-time. Techniques for analysis of timed automata. UML and SysML diagrams within model-based design and techniques for their analysis. Introduction to the tools for analysis of the presented models.

Language of instruction

Czech

Number of ECTS credits

5

Mode of study

Not applicable.

Guarantor

doc. Mgr. Adam Rogalewicz, Ph.D.

Department

Department of Intelligent Systems (UITS)

Learning outcomes of the course unit

Not applicable.

Prerequisites

Basic knowledge of graph theory, formal languages concepts and automata theory. Basic knowledge of statistics and probability. Basic knowledge of software engineering.

Co-requisites

Not applicable.

Planned learning activities and teaching methods

Not applicable.

Assesment methods and criteria linked to learning outcomes

Three projects (10 points each), final exam (70 points).

Course curriculum

Not applicable.

Work placements

Not applicable.

Aims

Introduce students to the possibility of software (resp. hardware) quality assurance by creating its model, check correctness on the level of the model, and subsequently translate (sometimes automatelly) the model into the target programming language. These principles are introduced on four models, in particular: Petri nets, Markov chains, timed automata and UML/SysML diagrams.

Specification of controlled education, way of implementation and compensation for absences

3 projects, 10 points each.

Students have to achieve at least 30 points, otherwise the exam is assessed by 0 points.

Recommended optional programme components

Not applicable.

Prerequisites and corequisites

Basic literature

Boucherie, R. J.(editor), van Dijk, N. M. (editor): Markov Decision Processes in Practice, Springer, 2017. ISBN-13: 978-3319477640 Dostupné online ze sítě VUT.
Christel Baier and Joost-Pieter Katoen: Principles of Model Checking, MIT Press, 2008. ISBN: 978-0-262-02649-9
Reisig, W.: Petri Nets, An Introduction, Springer Verlag, 1985. ISBN: 0-387-13723-8

Recommended reading

Češka, M.: Petriho sítě, Akad.nakl. CERM, Brno, 1994. ISBN: 8-085-86735-4
Jensen, K.: Coloured Petri Nets, Basic Concepts, Analysis Methods and Practical Use, Springer Verlag, 1993. ISBN: 3-540-60943-1
Kaynar, D.,  Lynch, N., Segala, R., Vaandrager, F. :The Theory of Timed I/O Automata, Morgan & Claypool, 2010.  ISBN-13: 978-1608450022 Dostupné online.

Elearning

eLearning: currently opened course

Classification of course in study plans

  • Programme IT-MSC-2 Master's

    branch MBI , 0 year of study, summer semester, elective
    branch MBS , 0 year of study, summer semester, elective
    branch MGM , 2 year of study, summer semester, elective
    branch MIN , 2 year of study, summer semester, compulsory
    branch MMM , 0 year of study, summer semester, compulsory
    branch MPV , 0 year of study, summer semester, elective
    branch MSK , 0 year of study, summer semester, elective

  • Programme MITAI Master's

    specialization NADE , 0 year of study, summer semester, elective
    specialization NBIO , 0 year of study, summer semester, elective
    specialization NCPS , 0 year of study, summer semester, elective
    specialization NEMB , 0 year of study, summer semester, elective
    specialization NGRI , 0 year of study, summer semester, elective
    specialization NHPC , 0 year of study, summer semester, elective
    specialization NIDE , 0 year of study, summer semester, elective
    specialization NISD , 0 year of study, summer semester, elective
    specialization NISY up to 2020/21 , 0 year of study, summer semester, elective
    specialization NMAL , 0 year of study, summer semester, elective
    specialization NMAT , 0 year of study, summer semester, elective
    specialization NNET , 0 year of study, summer semester, elective
    specialization NSEC , 0 year of study, summer semester, elective
    specialization NSEN , 0 year of study, summer semester, compulsory
    specialization NSPE , 0 year of study, summer semester, elective
    specialization NVER , 0 year of study, summer semester, compulsory
    specialization NVIZ , 0 year of study, summer semester, elective
    specialization NISY , 0 year of study, summer semester, elective

  • Programme IT-MSC-2 Master's

    branch MIS , 2 year of study, summer semester, compulsory-optional

  • Programme MITAI Master's

    specialization NEMB up to 2021/22 , 0 year of study, summer semester, elective

Type of course unit

 

Lecture

39 hod., optionally

Teacher / Lecturer

doc. Mgr. Adam Rogalewicz, Ph.D.
doc. Mgr. Lukáš Holík, Ph.D.
doc. RNDr. Milan Češka, Ph.D.
Ing. Jan Fiedor, Ph.D.

Syllabus

  1. Introduction to the topic of model-based design, testing and analysis. The term model-checking.
  2. Petri nets. Basic terms, history and applications.
  3. P/T Petri nets, definition, evolution rules, state space, bacis problems of analysis.
  4. Analysis of P/T Petri nets, coveribility tree, P- and T- invariants.
  5. Extensions of P/T Petri nets and Coloured Petri nets. Decidability and relation to Turing machines.
  6. Markov chains as a model of probabilistic systems, Markov chains in discrete and continuous time. Temporal logic for specification of behaviour of Markov chains.
  7. Analysis of Markov chains (model checking).
  8. Extension of Markov chains by nondeterminism - Markov decision processes. Use of Markov chains in theory of operation. Synthesis of operation for Markov decision processes.
  9. Timed automata and their use in modelling of systems with real-time.
  10. Timed automata analysis, region abstraction, decidable problems.
  11. Timed temporal logic TCTL and its relation to timed automata.
  12. UML/SysML diagrams and their use in model-based design and analysis.
  13. Model checking of systems described by UML (state) diagrams.

Exercise in computer lab

6 hod., compulsory

Teacher / Lecturer

doc. Mgr. Adam Rogalewicz, Ph.D.
Ing. Roman Andriushchenko
doc. Mgr. Lukáš Holík, Ph.D.
doc. RNDr. Milan Češka, Ph.D.

Syllabus

  1. Analysis of P/T Petri nets, tools NetLab a PIPE.
  2. Analysis of Markov chains, tool PRISM
  3. Analysis of timed automata, tool UPPAAL.

Project

7 hod., compulsory

Teacher / Lecturer

doc. Mgr. Lukáš Holík, Ph.D.
Ing. Roman Andriushchenko
doc. Mgr. Adam Rogalewicz, Ph.D.

Syllabus

  1. Application of Petri nets.
  2. Application of Markov chains.
  3. Application of timed automata.

Elearning

eLearning: currently opened course