Coordination: Serge Haddad (LMF, ENS Paris-Saclay)

• Serge Haddad (lectures part 1)
• Stéphane Le Roux (exercices part 1)
• Thomas Nowak (lectures part 2)
• Gabriel Le Bouder (exercises part 2)

Probability occurs more and more often in computer science both to address the modelling and simulation of systems where the specification is incomplete, to design efficient (yet simple) algorithms, to study the robustness of security protocols agains attack, etc. The goal of this course is to cover several of these aspects in order to show the versatility of the probability applied to computer science. Every part of this course is intended to be a introduction revealing ideas, principles and techniques while more elaborated techniques will be described in M2 courses.

• Basic Algorithms
• Finite Automata
• Basics of probability

• Discrete Time Markov Chains
  • Discrete event systems
  • Renewal processes with arithmetic distribution
  • Discrete time Markov chains
  • Finite discrete time Markov chains

• Continuous Time Markov Chains
  • Renewal processes with non arithmetic distribution
  • Continuous time Markov chains
  • Finite continuous time Markov chains

• Markov Decision Processes
  • Presentation
  • Finite horizon analysis
  • Discounted reward analysis
  • Average reward analysis

• Probabilistic Automata
  • Presentation
  • Properties of stochastic languages
  • Decidability results

Handout

Page of the practical sessions

• Part 1
  • FELLER W. An Introduction to Probability Theory and Its Applications, Vol. 1 and 2 Wiley
  • FOATA D., FUCHS A. Calcul des probabilités, cours et exercices corrigés Dunod
  • FOATA D., FUCHS A. Processus stochastiques Dunod
  • PUTERMAN M.L. Markov Decision Processes Wiley
  • PAZ A. Introduction to probabilistic automata New York, Academic Press

• Part 2
  • Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. 2nd edition. Cambridge University Press, Cambridge, 2017. ENS Paris-Saclay Library Amazon
  • Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, Cambridge, 1995. ENS Paris-Saclay Library Amazon
  • Noga Alon and Joel H. Spencer. The Probabilistic Method. 4th edition. John Wiley & Sons, Hoboken, 2016. ENS Paris-Saclay Library Amazon

• 2.8 Advanced Techniques of Verification
• 2.11.1 Parameterized Algorithms
• 2.11.2 Randomness in Complexity
• 2.15 Analysis of algorithms
• 2.17.1 Foundations of Network Models
• 2.18.1 Distributed Algorithms for Networks
• 2.29.2 Theory of Practical Graph Algorithms
• 2.34.1 Quantum Information and Applications
• 2.40 Langages de Programmation Probabilistes