# Fiches de cours 2017-2018

## Probabilistic methods

English

#### Remarque

pas donné en 2017-18

#### Summary

We systematically explore the exciting fact that randomness (i.e., coin flipping) can be used profitably to construct various mathematical structures with unexpected and often paradoxical properties, and to efficiently solve otherwise hopelessly difficult computational tasks.

#### Content

• Linearity of expectation
• Applications in combinatorics and number theory
• Randomized algorithms (sorting, convex hull, linear programming)
• The second moment method
• Random graphs

#### Keywords

random variable, expected value, probabilistic method, random graph, coloring

#### Learning Prerequisites

##### Required courses

Probability theory

##### Recommended courses

Discrete Mathematics or Graph Theory

##### Important concepts to start the course

Graph, random variable, expectation, variance, binomial coefficients, asymptotics

#### Learning Outcomes

By the end of the course, the student must be able to:
• Define and explain basic concepts in probability and discrete mathematics
• Define threshold functions, and analyze their asymptotic behavior
• Prove explain, and apply the first and second moment methods
• Prove explain, and apply the Local Lemma
• Solve exercises, design randomized algorithms
• Describe and explain the evolution of random graphs

#### Transversal skills

• Summarize an article or a technical report.
• Demonstrate the capacity for critical thinking
• Assess progress against the plan, and adapt the plan as appropriate.

#### Teaching methods

Lectures and exercises

#### Expected student activities

Attending the lectures, solving the exercises, reading sections from the textbook

Exam written

#### Resources

##### Bibliography

Noga Alon-Joel Spencer: The Probabilistic Method (Wiley)

Stasys Jukna: Extremal Combinatorics (Springer)

### Dans les plans d'études

• Informatique, 2017-2018, Master semestre 2
• Semestre
Printemps
• Forme de l'examen
Ecrit
• Crédits
5
• Matière examinée
Probabilistic methods
• Cours
2 Heure(s) hebdo x 14 semaines
• Exercices
2 Heure(s) hebdo x 14 semaines
• Ingénierie mathématique, 2017-2018, Master semestre 2
• Semestre
Printemps
• Forme de l'examen
Ecrit
• Crédits
5
• Matière examinée
Probabilistic methods
• Cours
2 Heure(s) hebdo x 14 semaines
• Exercices
2 Heure(s) hebdo x 14 semaines
• Ingénierie mathématique, 2017-2018, Master semestre 4
• Semestre
Printemps
• Forme de l'examen
Ecrit
• Crédits
5
• Matière examinée
Probabilistic methods
• Cours
2 Heure(s) hebdo x 14 semaines
• Exercices
2 Heure(s) hebdo x 14 semaines
• Mathématiques - master, 2017-2018, Master semestre 2
• Semestre
Printemps
• Forme de l'examen
Ecrit
• Crédits
5
• Matière examinée
Probabilistic methods
• Cours
2 Heure(s) hebdo x 14 semaines
• Exercices
2 Heure(s) hebdo x 14 semaines
• Mathématiques - master, 2017-2018, Master semestre 4
• Semestre
Printemps
• Forme de l'examen
Ecrit
• Crédits
5
• Matière examinée
Probabilistic methods
• Cours
2 Heure(s) hebdo x 14 semaines
• Exercices
2 Heure(s) hebdo x 14 semaines
• Mathématiques pour l'enseignement, 2017-2018, Master semestre 2
• Semestre
Printemps
• Forme de l'examen
Ecrit
• Crédits
5
• Matière examinée
Probabilistic methods
• Cours
2 Heure(s) hebdo x 14 semaines
• Exercices
2 Heure(s) hebdo x 14 semaines
• Mathématiques pour l'enseignement, 2017-2018, Master semestre 4
• Semestre
Printemps
• Forme de l'examen
Ecrit
• Crédits
5
• Matière examinée
Probabilistic methods
• Cours
2 Heure(s) hebdo x 14 semaines
• Exercices
2 Heure(s) hebdo x 14 semaines
• Systèmes de communication - master, 2017-2018, Master semestre 2
• Semestre
Printemps
• Forme de l'examen
Ecrit
• Crédits
5
• Matière examinée
Probabilistic methods
• Cours
2 Heure(s) hebdo x 14 semaines
• Exercices
2 Heure(s) hebdo x 14 semaines
• Systèmes de communication - master, 2017-2018, Master semestre 4
• Semestre
Printemps
• Forme de l'examen
Ecrit
• Crédits
5
• Matière examinée
Probabilistic methods
• Cours
2 Heure(s) hebdo x 14 semaines
• Exercices
2 Heure(s) hebdo x 14 semaines

LuMaMeJeVe
8-9
9-10
10-11
11-12
12-13
13-14
14-15
15-16
16-17
17-18
18-19
19-20
20-21
21-22
Cours
Exercice, TP
Projet, autre

### légende

• Semestre d'automne
• Session d'hiver
• Semestre de printemps
• Session d'été
• Cours en français
• Cours en anglais
• Cours en allemand