Les méthodes aléatoires sont un des outils clés en informatique, pas limité à leur utilisation la plus connue dans les algorithmes aléatoires. Nos objectifs pour ce cours sont doubles :
(i) Nous donnerons une introduciton aux diverses application de méthodes aléatoire en informatique.
- Algorithmes aléatoires,
- jeu du menteur et je de devinette (Mastermind) et leurs applications à la communication bruyante et aux problèmes de protection de la vie privée,
- graphes aléatoires et réseaux sociaux,
- algorithmes épidémiques construits sur des paradigmes de ragots aléatoires (les noeuds contactent des voisins aléatoires pour échanger des informations),
- algorithmes évolutionnistes.
(ii) En parallèle, nous développerons un petit mais puissant ensemble d'outils mathématiques qui permettront de comprendre la plupart des utilisations de l'aléatoire en informatique :
- le méthode du premier moment,
- le théorème du collectionneur de coupons,
- inégalités simples de Chernoff,
- plusieurs astuces pour gérer les dépendances.
Requis : La beauté de ce domaine est que des utilisations relativements simples d'aléatoire donne des résultats étonnament puissants. Des connaissances préalables approfondies en théorie des probabilités ne sont donc sont pas nécessaires. Cependant, ce thème nécessite l'usage de probabilitésélémentaires discrètes. Si vous avez peur des affirmations comme "si vous lancez un dé à 6 faces standard, alors attendez vous à un résultat de 3,5" ou "le nombre attendu de lancés de dé jusqu'à ce que vous tombiez sur un "un" est 6", alors ne prenez pas ce cours. Des connaissances de base des algorithme et leurs analyses (par ex. vus en INF421) est aussi utile. Enfin, ce n'est pas un cours de mathématiques, mais nous utilisons des arguments mathématiques pour comprendre les choses. Le cours est accompagné de PC et non de TD, il est donc dans le même esprit que INF421, si l'on enlève les devoirs et le projet de programmation optionnel.
Modalités d'évaluation : examen écrit (3h) et deux tests courts (20 min), chacun peut augmenter légèrement la note finale.
Langue : Tout est en anglais. Il est autorisé de répondre en fançais lors de l'examen.
Randomized methods are one of the key tools in computer science, clearly not limited to their best-known use in randomized algorithms. Our aims for this course are twofold:
(i) We shall give an introduction to the diverse applications of randomized methods in computer science.
- Randomized algorithms,
- liar games and guessing games (Mastermind) and their applications to noisy communication and privacy problems,
- random graphs and social networks,
- epidemic algorithms building on the random gossip paradigm (nodes contact random neighbors to exchange information),
- evolutionary algorithms.
(ii) Parallel to this, we shall develop a small, but powerful set of mathematical tools that suffice to understand most uses of randomness in computer science:
- the first moment method,
- the coupon collector theorem,
- simple Chernoff bounds,
- a number of tricks to deal with dependencies.
Requirements: The beauty of this field is that relatively simple uses of randomness yield surprisingly powerful results. In such, no deep probability theory prerequisites are needed. However, naturally, this topic does require the use of elementary discrete probabilities. So if you are afraid of statements like "if you roll a standard 6-sided die, then the expect result is 3.5" or "the expected number of die rolls until you see a "one" is 6", then you should not take this course.
A basic knowledge of algorithms and their analysis, e.g., as taught in INF421, is also helpful. Finally, this is not a mathematics course (by far not), but we use mathematical arguments to understand things. The course comes with PC, not with TD. It is thus in style similar to INF421 if you remove the homeworks and the optional programming project.
Evaluation mechanism: Written exam (3h) and two short tests (20min), each of which can mildly increase the final grade.
Languange: Everything is in English. For the exam, answers in French are equally accepted.
- Teaching coordinator: Doerr Benjamin