Introduction à la combinatorique en vue des applications. (French) Zbl 0169.01801

Kaufmann, A.

Paris: Dunod. xviii, 608 p. (1968).

Après le grand traité de E. Netto, révisé par Viggo Brun et Th. Skolem, il pouvait sembler bien téméraire d’écrire un ouvrage d’ensemble sur l’analyse combinatoire. D’autre part, en dehors des premiers éléments, enseignés dans les classes de mathématiques spéciales des lycées, cette discipline, depuis de longues années, avait fini par tomber en désuétude. Mais, avec l’emploi de plus en plus général des machines électroniques, certaines branches de l’analyse combinatoire connaissent aujourdhui un renouveau d’actualité. Enfin, beaucoup de problèmes anciens ont été “réexposés” par les auteurs de notes en les recouvrant d’un vocabulaire entièrement renouvelé. C’est de toutes ces parties de la théorie que l’A. s’occupe, le mode d’exposition étant choisi, avant tout, en fonction des applications pratiques. Ainsi, selon les termes même de l’A., cette introduction n’est-elle pas un précis d’analyse combinatoire, c’est, parmi “une trentaine d’autres, traduits dans les principales langues” qui traduisent un “effort promotionnel à l’aide du livre scientifique pour inciter à l’acquisition des méthodes, à l’application et à la recherche”, un ouvrage essentiellement didactique et d’initiation “dont le seule mérite est une sincère volonté d’être utile”.
L’ouvrage comporte cinq chapitres et deux annexes.
I. Notions de base. Arrangements. Combinaisons. Emploi des fonctions génératrices pour les dénombrements.
II. Arrangements soumis à restriction. Règle d’inclusion et d’exclusion. Criblages. Permutations discordantes. Rencontres. Ménages. ...
III. Introduction très développée à la théorie des graphes. Arbres. Treillis.
IV. Enumération de chemins et de circuits. Enumérations de séquences avec répétition, de facteurs d’un graphe, des dissections.
V. Etant donné un critère permettant de définir quelles solutions sont préférées aux autres, on se propose de trouver le sous ensemble de solutions qu’elles forment (solutions “optimales”). L’ “optimisation” s’obtient en général par criblages successifs, au moyen de fonctions numériques sur le graphe, et dont on cherche les extrémums. Méthode de Monte-Carlo. Optimisation d’un chemin dans un graphe, Arbre optimal. Couverture. Couplage...
L’annexe A (Notions d’algèbre), expose en une trentaine de pages l’essentiel des questions suivantes: Algèbre booléienne. Anneau des classes résiduelles mod \(n\). Champs de Galois. Algèbre binaire.
L’annexe B, un peu plus longue, est consacrée à un exposé des méthodes de codage, à la détection des erreurs de transmission et à leur correction.
Les exercices sont proposés à la suite des paragraphes qu’ils illustrent. Une liste des symboles et notations adoptés par l’A. précède le chapitre I. Un index sommaire des termes employés renvoie aux pages. La bibliographie se limite à la liste de quelques ouvrages, que l’A. a consultés, à l’exclusion de tout article.

Reviewer: Albert Sade (Pertuis / France)

MSC:

05-01

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics

Keywords:

combinatorics