This lecture will be held in English and consists of of two parts.
The first part is a general introduction to the topic of probability theory. We will look at concentration barriers (such as Chernobi barriers) and general techniques for estimating probabilities (for example, Bernoulli's inequality).
The second part examines the use of randomness in Algorithms. Topics include.
- How algorithms can use randomness to make decisions that improve their run-time.
- How well algorithms perform when given a random input.
- Analysis of random structures.