20410556 - CP450 - Probabilistic methods and random algorithms

Get to know the main probabilistic methods and their application to computer science: random algorithms, random graphs and networks, stochastic processes on graphs, branching processes and spread of infection.

Curriculum

teacher profile | teaching materials

Mutuazione: 20410556 CP450 - METODI PROBABILISTICI E ALGORITMI ALEATORI in Matematica LM-40 DE OLIVEIRA STAUFFER ALEXANDRE

Programme

The goal of the course is to discuss modern methods from probability theory and their use to solve fundamental problems from other areas, such as computer science (randomized algorithms and random networks), combinatorics and data science. In particular, in the course we see several applications where the problem to be solved is in fact *not random*, but we choose to resort to a probabilistic solution in an opportunistic way to solve them.

Some of the topics seen in the course are the following:
* Randomized algorithms
* Can we really use perfect randomness in computer science?
* Probabilistic method and its application to computer science, combinatorics and some games
* Concentration of random variables and martingales, and their applications to routing and dimension reduction
* Branching processes and spread of infections
* Percolation, Erdos-Renyi random graphs and random networks
* Random walks on graphs and application to clustering data


Core Documentation

"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis", Mitzenmacher and Upfal, Cambridge University Press
"The probabilistic method", Alon and Spencer, John Wiley & Sons


Type of delivery of the course

Standard lectures In case the emergency situation due to COVID-19 persists, lectures will be delivered through the platform Teams with notes and exercises avaiable in the platform Moodle.

Attendance

Attendance is recommended.

Type of evaluation

Homeworks plus an oral exam. Depending on the number of students, and of their interests, it is possible to replace the oral exam with a seminar or a project (which can either be a simulation project or a problem-solving project).

teacher profile | teaching materials

Mutuazione: 20410556 CP450 - METODI PROBABILISTICI E ALGORITMI ALEATORI in Matematica LM-40 DE OLIVEIRA STAUFFER ALEXANDRE

Programme

The goal of the course is to discuss modern methods from probability theory and their use to solve fundamental problems from other areas, such as computer science (randomized algorithms and random networks), combinatorics and data science. In particular, in the course we see several applications where the problem to be solved is in fact *not random*, but we choose to resort to a probabilistic solution in an opportunistic way to solve them.

Some of the topics seen in the course are the following:
* Randomized algorithms
* Can we really use perfect randomness in computer science?
* Probabilistic method and its application to computer science, combinatorics and some games
* Concentration of random variables and martingales, and their applications to routing and dimension reduction
* Branching processes and spread of infections
* Percolation, Erdos-Renyi random graphs and random networks
* Random walks on graphs and application to clustering data


Core Documentation

"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis", Mitzenmacher and Upfal, Cambridge University Press
"The probabilistic method", Alon and Spencer, John Wiley & Sons


Type of delivery of the course

Standard lectures In case the emergency situation due to COVID-19 persists, lectures will be delivered through the platform Teams with notes and exercises avaiable in the platform Moodle.

Attendance

Attendance is recommended.

Type of evaluation

Homeworks plus an oral exam. Depending on the number of students, and of their interests, it is possible to replace the oral exam with a seminar or a project (which can either be a simulation project or a problem-solving project).

teacher profile | teaching materials

Mutuazione: 20410556 CP450 - METODI PROBABILISTICI E ALGORITMI ALEATORI in Matematica LM-40 DE OLIVEIRA STAUFFER ALEXANDRE

Programme

The goal of the course is to discuss modern methods from probability theory and their use to solve fundamental problems from other areas, such as computer science (randomized algorithms and random networks), combinatorics and data science. In particular, in the course we see several applications where the problem to be solved is in fact *not random*, but we choose to resort to a probabilistic solution in an opportunistic way to solve them.

Some of the topics seen in the course are the following:
* Randomized algorithms
* Can we really use perfect randomness in computer science?
* Probabilistic method and its application to computer science, combinatorics and some games
* Concentration of random variables and martingales, and their applications to routing and dimension reduction
* Branching processes and spread of infections
* Percolation, Erdos-Renyi random graphs and random networks
* Random walks on graphs and application to clustering data


Core Documentation

"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis", Mitzenmacher and Upfal, Cambridge University Press
"The probabilistic method", Alon and Spencer, John Wiley & Sons


Type of delivery of the course

Standard lectures In case the emergency situation due to COVID-19 persists, lectures will be delivered through the platform Teams with notes and exercises avaiable in the platform Moodle.

Attendance

Attendance is recommended.

Type of evaluation

Homeworks plus an oral exam. Depending on the number of students, and of their interests, it is possible to replace the oral exam with a seminar or a project (which can either be a simulation project or a problem-solving project).