Combien de façons de mélanger divers ingrédients, de chances de gagner à un jeu de hasard, de chemins possibles pour se rendre d'un point à un autre sur un réseau routier ? Autant de questions auxquelles Mathématiques appliquées à l'informatique répond. Cet ouvrage en 3 volumes s'adresse à tous ceux qui veulent s'initier aux théories combinatoires, sans oublier les étudiants de classes préparatoires et d'université. Des applications concrètes telles que le Sudoku et les moteurs de recherche sont présentées et accompagnées de traitements informatiques expérimentaux. À l'aide d'éléments théoriques de base et d'une multitude d'exemples, une montée progressive en puissance propose un aperçu de l'état de l'art en la matière. La mise en oeuvre de nombreux algorithmes et de programmes informatiques permet de confronter la théorie à l'expérience. Cette approche non conventionnelle de la combinatoire renforce l'originalité de cet ouvrage.
Sommaire
Volume 1. Algorithmes et théorie en combinatoire. Introduction générale. Quelques éléments d'histoire. Arrangements et combinaisons. Énumérations dans l'ordre alphabétique. Énumération par arborescences. Langages, fonctions génératrices et récurrences. Cheminements dans un quadrillage. Arrangements et combinaisons avec répétitions. Formule du crible. Chaînes de montagnes ou mots de parenthèses. Nombres de Catalan. D'autres chaînes de montagnes. Quelques applications des nombres de Catalan et des mots de parenthèses. La formule de Burnside. Matrices et circulation sur un graphe. Parties et partitions d'un ensemble. Partitions d'un nombre. Les drapeaux. Murs et empilages. Pavages de surfaces rectangulaires par des formes simples. Permutations. Bibliographie. Index. Volume 2. Algorithmes et théorie des probabilités. Rappels sur les probabilités discrètes. Le hasard et l'ordinateur. Discret et continu. Fonction génératrice associée à une variable aléatoire discrète dans un jeu. Graphes et matrices pour le traitement de problèmes de probabilité. Jeux de pile ou face répétés. Cheminements au hasard sur des graphes. Tirages répétitifs, jusqu'à la sortie d'un certain motif. Exercices de probabilités. Bibliographie. Index. Volume 3. Algorithmes et théorie des graphes. Graphes et cheminements. Explorations dans les graphes. Arbres à noeuds numérotés, théorème de Cayley et codage de Prüfer. Arbres binaires. Graphes pondérés : plus courts chemins et arbre couvrant minimal. Cycles et chemins eulériens, arbres couvrants d'un graphe. Énumération des arbres couvrants d'un graphe non orienté. Énumération des chemins eulériens dans les graphes non orientés. Chemins et circuits hamiltoniens. Annexe 1. Matrices. Annexe 2. Déterminants et combinatoire des cheminements.