Entre mathématiques et informatique : l'analyse des algorithmes (série : Colloquium Jacques Morgenstern)

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.

Disciplines : ,
Mots-clés : fuscia,conférence,recherche,STIC,calcul,complexité,arbre digital,tri,transformation de Mellin,comptage probabiliste,systèmes dynamiques
Type de document : image en mouvement
Type de ressource : lecture
Niveau : higher education,doctorat
Publics visés : learner,teacher
Activité induite : s'informer,apprendre
Proposition d'utilisation : Cycle de conférences mensuelles, les Colloquium Jacques Morgenstern peuvent être choisis par les étudiants de l'Ecole Doctorale STIC dans le cadre des heures de formation complémentaire. Les orateurs interviennent en français ou en anglais.
Auteurs ou éditeurs : Philippe Flajolet,Institut National de Recherche en Informatique et en Automatique,Université de Nice,Ecole Polytechnique Universitaire,Laboratoire I3S