13 janvier 2003
Jusqu’au dix-neuvième siècle, les mathématiques sont de nature largement algorithmique, mais les problèmes de complexité, s’ils sont présents, restent souvent subliminaux. L’avènement de l’informatique pose, dès les années 1950, de nombreuses questions dès lors que l’on cherche à comprendre, prédire, et quantifier les performances des algorithmes. Donald Knuth fonde au début des années 1960 le nouveau domaine de l’analyse d’algorithmes.
Au fil de quelques exemples, on retracera l’évolution des idées depuis la période des pionniers jusqu’à maintenant. On verra par exemple qu’un même ”processus informatique”, l’arbre digital, apparaît dans le traitement et la compression de données textuelles, en algorithmique distribuée et dans certains protocoles de communication, en calcul numérique garanti et géométrie algorithmique, dans l’optimisation de requêtes en bases de données, etc.
La compréhension des phénomènes de complexité relatifs à ces algorithmes croise alors, de façon transverse, de nombreux chapitres des mathématiques, classiques ou non, pures ou appliquées. On verra ainsi surgir des domaines tels l’analyse combinatoire, les singularités de fonctions de variable complexe, la théorie des probabilités, les transformations intégrales et fonctions spéciales, l’analyse fonctionnelle, voire la théorie analytique des nombres.
Tous ces domaines illustrent, selon le mot du physicien Eugene Wigner, la ”déraisonnable efficacité des mathématiques” dans les sciences, ici, l’informatique.
Fichier pdf de la présentation
[Vidéo indisponible]
