Curriculum M1 MPRI at ENS Paris-Saclay

PACS: Probabilistic Aspects of Computer Science

Description: The aim of this course is to introduce the main models for discrete-event systems (Markov chains, Markov decision processes, probabilistic automata), along with their underlying theory and associated algorithms. It also covers random graph theory—a framework particularly well-suited to modeling large-scale distributed systems such as telecommunication networks or social networks. This course prepares students for the courses within the "Automata/Games" track of the MPRI Master's program (second year).

Outline:

  1. Discrete-time Markov chains: renewal processes, asymptotic analysis, algorithms for finite chains
  2. Continuous-time Markov chains
  3. Markov decision processes: finite-horizon rewards, discounted rewards, long-term average rewards
  4. Probabilistic automata: stochastic languages, expressiveness, decidable and undecidable problems
  5. Random graphs: combinatorics, distribution thresholds, and asymptotic properties (cycles, connectivity, etc.)


References:

  • Probability and Computing : Randomized Algorithms and Probabilistic Analysis by Mitzenmacher M, Upfal E, Cambridge University Press 2005
  • Mathematical Techniques for Analyzing Concurrent and Probabilistic Systems (Crm Monograph Series, 23) by Parker, Rutten, Kwiatkowska and Norman
  • Random Graphs (Cambridge Studies in Advanced Mathematics) by Béla Bollobás
  • Web site of instructors ...