Archives de catégorie : Analyse

Michèle SORIA (04/03/2020), « Combinatoire Analytique : énumération, statistiques et génération aléatoire »

Oratrice

Michèle SORIA (Sorbonne Université, LIP6)

Titre

« Combinatoire Analytique : énumération, statistiques et génération aléatoire »

Résumé

La Combinatoire Analytique, développée par Philippe Flajolet et son école à partir des années 1980, est une théorie dont l’objectif est de quantifier les propriétés de structures discrètes variées, telles que mots, permutations, arbres, graphes… L’approche est celle d’un calcul sur les structures, fondé sur les propriétés algébriques et analytiques des séries génératrices de dénombrement.

On étudie des structures qui peuvent être spécifiées récursivement en fonction d’opérations combinatoires telles que Union, Produit, Séquence, Ensemble, Cycle. La phrase-clé de la Combinatoire  Analytique est « If you can specify, you can analyse » : à partir des spécifications, on développe une chaîne de traitement systématique, voire automatique, qui donne les lois asymptotiques générales gouvernant les séquences de dénombrement et le comportement des paramètres.

La première étape consiste à transcrire les spécifications en termes d’opérations algébriques sur les séries génératrices de  dénombrement des structures. Dans l’étape suivante, les séries génératrices sont interprétées comme des fonctions analytiques, dont les singularités sont déterminantes pour les estimations asymptotiques. Cette vision par l’analyse complexe permet d’étudier les propriétés statistiques des structures de grande taille, et de montrer des phénomène d’universalité : de nombreuses propriétés des structures combinatoires dépendent de traits globaux de leur définition, et non de détails.

Cet exposé présente un panorama de résultats de Combinatoire Analytique, ainsi que quelques algorithmes efficaces pour l’énumération et la génération aléatoire. Il est illustré de nombreux exemples et accompagné de traitements automatiques avec les  modules COMBSTRUCT et GFUN de MAPLE.

Informations

Mercredi 4 mars 2020, 14h-16h

Salle 24-25/405 du LIP6 (rotonde 25, 4e étage)
4 place Jussieu, 75005 Paris
métro Jussieu (lignes 7 et 10)

 

Marie-José Durand-Richard : « Les diagrammes de fonctionnement de The Analytical Engine, de Charles Babbage 1791-1877) à Ada Lovelace (1815-1852) » (11/04/2019)

Marie-José Durand-Richard (Paris 8, SPHERE, CNRS)

« Les diagrammes de fonctionnement de The Analytical Engine, de Charles Babbage 1791-1877) à Ada Lovelace (1815-1852) »

Résumé

Charles Babbage (1791-1877) a élaboré les plans de The Analytical Engine afin de matérialiser la conception symbolique de l’algèbre élaborée au sein d’un réseau d’algébristes nommé The Analytics. Cette conception était fondée sur les propriétés strictement opératoires des développements en série. Suite à la présentation de ses plans en Italie en 1841, l’ingénieur militaire Luigi Menabrea (1809-1896) a publié en français quelques exemples de  diagrammes de fonctionnement de cette machine, diagrammes que je qualifie de statiques. Dans les précieuses notes qu’elle ajoute dans sa traduction de cet article en anglais, Ada Lovelace (1815-1852) les complète par de nouveaux diagrammes, que je qualifie de dynamiques. On étudiera ces diagrammes afin d’examiner quelles sont les caractéristiques qui peuvent permettre, ou non, de les qualifier de programmes.

Informations

Jeudi 11 avril 2019

Salle 24-25/405 du LIP6 (rotonde 25, 4e étage)
4 place Jussieu, 75005 Paris
métro Jussieu (lignes 7 et 10)

Assia Mahboubi, « Démonstrations assistées par ordinateur » (07/02/2019)

Assia MAHBOUBI (Inria, LS2N, Université de Nantes)

« Démonstrations assistées par ordinateur »

Informations pratiques

Jeudi 7 février 2019

Salle 24-25/405 du LIP6 (rotonde 25, 4e étage)

4 place Jussieu, 75005 Paris
métro Jussieu (lignes 7 et 10)

Affiche (PDF)

Résumé

Les ordinateurs ont profondément transformé la pratique des mathématiques contemporaines, mettant en particulier leur puissance de calcul au service de l’observation, de la conjecture et même de la validation “par calcul”. La généralisation rapide de l’accès à une puissance de calcul surhumaine a même suscité de nouvelles formes de mathématiques, à l’interface avec l’informatique, comme le calcul formel ou l’analyse numérique. Moins connus que certains systèmes de calcul symbolique, numérique ou statistique, les “assistants de preuve” font néanmoins partie des logiciels qui permettent de faire des mathématiques sur ordinateur. Ils sont conçus pour aider leurs utilisateurs à représenter définitions, énoncés et démonstrations dans un formalisme logique précis et non ambigu, sous la forme de bibliothèques digitales de mathématiques formalisées. Il existe plusieurs sous-familles d’assistants de preuves, qui diffèrent en particulier sur le choix de fondations logiques, qui détermine le langage formel utilisé. En particulier, une majorité d’entre eux sont basés sur une forme de théorie des types, une approche des fondations logiques qui donne une place privilégiée aux fonctions, et au concept de calcul. Mais dans tous les case, une telle (ré)écriture des théories mathématiques serait bien trop piétonne pour être envisageable, sinon intéressante, sans l’aide de la machine. Cette dernière permet en retour de réduire la vérification des preuves à une tâche routinière et mécanisée. Mais ce n’est pas le seul bénéfice d’une telle formalisation et nous discuterons dans cet exposé la pratique et les enjeux de cette forme de mathématiques assistées par ordinateur.

Cet exposé ne présuppose pas de connaissance particulière en logique ou en programmation.