Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Combinatoire analytique
Résumé
En mathématiques, et plus précisément en combinatoire, la combinatoire analytique (en analytic combinatorics) est un ensemble de techniques décrivant des problèmes combinatoires dans le langage des séries génératrices, et s'appuyant en particulier sur l'analyse complexe pour obtenir des résultats asymptotiques sur les objets combinatoires initiaux.
Les résultats de combinatoire analytique permettent notamment une analyse fine de la complexité de certains algorithmes.
La combinatoire analytique repose fondamentalement sur deux approches :
la première approche, combinatoire, également parfois qualifiée de méthode symbolique, permet de décrire des relations entre des objets mathématiques discrets en les transcrivant directement en termes d'opérations algébriques sur les séries génératrices associées; la deuxième approche, analytique,
utilise ou développe des outils danalyse complexe en vue d'extraire de ces séries génératrices des informations sur le comportement asymptotique du nombre d'objets énumérés. C'est ainsi la nature des singularités de ces séries qui est la clé de l'étude du comportement asymptotique des objets discrets initiaux. Une application importante est l'étude de propriétés probabilistes de grandes structures aléatoires.
Cette théorie a été largement développée notamment par Philippe Flajolet et son école. Elle est détaillée dans son livre avec Robert Sedgewick, Analytic Combinatorics. Elle trouve sa source dans des travaux de précurseurs comme Leonhard Euler, Arthur Cayley, Srinivasa Ramanujan, Gaston Darboux, George Pólya et Donald Knuth.
La méthode symbolique s'appuie sur le concept de classe combinatoire, c'est-à-dire d'ensembles d'objets, où chaque objet a une taille. La méthode permet de traduire des opérations ensemblistes sur les classes en des opérations algébriques sur les séries génératrices associées. On obtient ainsi un processus de traduction purement formel, et automatisable. En pratique, on utilise souvent des séries génératrices dites ordinaires pour les structures non étiquetées, et des séries génératrices exponentielles pour les structures étiquetées.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.