Une méthode "constructive" de résolution de problèmes de dénombrement et sa mise en oeuvre

G. TISSEAU, H. GIROIRE, F. LE CALVEZ, M. URTASUN, J. DUMA

IBP-Laforia 1996/11: Rapport de Recherche Laforia / Laforia research reports
14 pages - Octobre/October 1996 - French document.

PostScript : 50 Ko /Kb

Titre / Title: Une méthode "constructive" de résolution de problèmes de dénombrement et sa mise en oeuvre

Résumé : Nous présentons une méthode de résolution de problèmes de dénombrement appelée "méthode constructive de dénombrement". Elle consiste à élaborer une définition de l'ensemble à dénombrer qui puisse être interprétée comme un algorithme (éventuellement non déterministe) de génération des éléments de cet ensemble. La définition est dite "constructive" si l'algorithme n'effectue aucune élimination, c'est-à-dire si tout essai conduit à coup sûr à un élément solution. Sous certaines conditions, l'étude de la structure de l'algorithme permet de déterminer le cardinal de l'ensemble à dénombrer. Dans le cadre du projet Combien?, nous avons réalisé un système de résolution de problèmes de dénombrement qui utilise cette méthode. Par ailleurs, celle-ci fournit un cadre conceptuel qui permet actuellement à un utilisateur de communiquer au système un énoncé d'exercice et une proposition de solution, et au système d'étudier la validité de cette proposition.

Abstract : A method for solving problems in combinatorial mathematics called "constructive method of counting" is presented in this paper. It consists in elaborating a definition of the set to be enumerated that can be interpreted as a non deterministic algorithm capable to generate the elements of the set. The definition is said to be "constructive" if the algorithm never eliminates a proposed element by backtracking. Under certain conditions the study of the structure of the algorithm allows to calculate the number of elements in the set. Within the framework of the Combien? project, we have implemented a system that solves combinatorial problems using this method. Besides, the method yields a conceptual framework that allows the user to input the text of a problem and a proposal for its solution. Next, this conceptual framework allows the system to study the validity of this proposal.

Publications internes Laforia 1996 / Laforia research reports 1996