Informations pratiques

Description de la ressource

Résumé

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.

• Granularité : leçon
• Structure : atomique

"Domaine(s)" et indice(s) Dewey

• (511.8)
• (004.0151)

Domaine(s)

Informations pédagogiques

• 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.
• Activité induite : s'informer, apprendre

Informations techniques

• Configuration conseillée : Nécessite le client Real Player et une connexion Internet haut débit.

Intervenants

Édition

• Institut National de Recherche en Informatique et en Automatique
• Université de Nice
• Ecole Polytechnique Universitaire
• Laboratoire I3S

Diffusion

Cette ressource vous est proposée par :

• Cette ressource fait partie de
  • Colloquium Jacques Morgenstern