Pour traiter les énormes masses de données issues des applications, l’amélioration des performances des ordinateurs ne suffit pas et il est nécessaire de concevoir des algorithmes efficaces en théorie et en pratique. Dans cette course à la performance, l’introduction d’une part de hasard a constitué l’une des avancées les plus fécondes. On parle alors d’algorithmes randomisés. Les algorithmes randomisés comptent sur le hasard pour éviter, au moins en moyenne, les configurations complexes (en général rares) qui pénalisent les performances ; ils sont souvent à la fois simples et efficaces et constituent les algorithmes de choix en pratique. Si les algorithmes randomisés ont été inventés pour résoudre des problèmes géométriques, ils occupent maintenant une place importante dans tous les domaines de l’algorithmique.
Le cours expose la théorie des algorithmes incrémentaux randomisés sur l’exemple du calcul de l’enveloppe convexe d’un ensemble fini de points. Contrairement à l’algorithme incrémental exposé au premier cours, cet algorithme est optimal en toutes dimensions et son analyse est élémentaire. Le cours présente d’autres exemples d’algorithmes incrémentaux randomisés et montre également comment le résultat central de la théorie, de nature probabiliste, conduit à des résultats combinatoires déterministes qu’on ne sait pas démontrer autrement.
