– BOOLE

Les cadres booléens sont omniprésents en Informatique. L'information stockée dans les ordinateurs est binaire; les circuits qui la traitent ont pour base la logique binaire; les algorithmes et les programmes qui la transmettent, la codent, sont basés sur la logique binaire -ou sur ses extensions à des corps finis. De nmbreux problèmes combinatoires à grande échelle sont traités par des algorithmes et des outils logiciels visant à la résolution de problèmes de satisfaction de contraintes, qui ne sont autres que des extensions de ce paradigme binaire. La plupart de ces problèmes liés aux cadres booléens demandent une grande puissance de calcul; en conséquence il existe souvent, face à un problème de grande taille, plusieurs approches algorithmiques, mais il est difficile de prédire laquelle est la plus appropriée. D'où un fort besoin de méthodologies capables de prédire avec une fiabilité suffisante quelle stratégie a une meilleure chance de succès dans un contexte donné. L'idéal serait, pour chaque problème impliquant un cadre booléen, de pouvoir relier des indicateurs structurels à la complexité moyenne des stratégies de résolution. C'est précisément le but de notre proposition. Notre objectif global est de quantifier le pouvoir d'expression des principaux cadres booléens, i.e. de développer des modèles qui permettront de prédire ce qui est valide, ou non, dans la plupart des cas. En d'autres termes, à l'encontre d'une part substantielle des études sur ce sujet, nous cherchons à élucider les propriétés statistiques des structures booléennes. Le but ultime est de fournir une aide au choix de la meilleure représentation ou du meilleur algorithme, dans un contexte donné, et de développer de nouvelles stratégies algorithmiques dans un certain nombre de cas, basées sur des résultats analytiques rigoureux. Pour résumer, nous proposons de développer une boîte à outils mathématique, cohérente et générale, pour mesurer et comparer les propriétés quantitatives (i.e. probabilistes) des cadres booléens, vus sous l'angle des performances. La cohérence de notre projet vient à la fois des fonctions booléennes, qui sont sous-jacentes à tous les objets de nos recherches, et des méthodes que nous nous proposons d'utiliser et de développer, qui reposent sur la combinatoire analytique et les probabilités. A ce jour, les deux communautés scientifiques qui travaillent, l'une sur les fonctions booléennes, l'autre sur les structures aléatoires discrètes, ont eu relativement peu d'interactions, et les techniques que nous comptons développer ont rarement été appliquées aux objets booléens. En résumé, nous pensons que la nouveauté de notre projet est double: l'introdction de nouvelles méthodes dans l'analyse des cadres booléens; l'extension de la combinatoire analytique et des méthodes probabilistes à un nouveau type de structures discretes.