Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

# Motivation and Main Objectives

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.

# Prerequisites

• Basic Algorithms
• Finite Automata
• Basics of probability

# Part 1: Markovian Models

• 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

# Part 2: Randomized Algorithms & Random Structures

Date Topic Reading Handout In-Class Problems Homework
Nov. 6, 2023 Markov, Chebyshev Chapters 1-3 Lecture 1 1.6, 1.12, 3.12, 3.18, 3.19, 3.26 1.5, 2.13, 2.16, 2.32
Nov. 13, 2023 Chernoff, Balls into Bins Chapters 4-5 & 17.1 Lecture 2 4.7, 4.9, 4.12, 5.3, 17.2 Exploratory Assignment 5.8
Nov. 20, 2023 Probabilistic Method Chapter 6 Lecture 3 6.3, 6.8, 6.11, 6.14, 6.15 6.4, 6.10, 6.19, 6.20
Nov. 27, 2023 Birth of the Giant Component The giant component: the golden anniversary
Erdős-Rényi Random Graphs: The Giant Component
Lecture 4
Dec. 4, 2023 Normal Distribution Chapter 9 Lecture 5 9.2, 9.9, 9.13, 9.14 9.6, 9.12, 9.15
Dec. 11, 2023 Entropy Chapter 10 Lecture 6 10.1, 10.4, 10.10, 10.15, 10.16 10.3, 10.12, 10.17
Dec. 18, 2023 Sample Complexity Chapter 14 Lecture 7 14.1, 14.6, 14.8, 14.9-14.10 14.2, 14.3-14.5, 14.7, 14.13
Jan. 8, 2024 Exam Preparation - - - -
Jan. 15, 2024 Final Exam - - - -

# Bibliography

• 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

# Related Courses

Universités partenaires
Établissements associés