La loi de Moore prédit que le nombre de composants dans un circuit double tous les 18 mois. Cette augmentation permet de diminuer les délais dans ces composants, mais amènent une augmentation des délais liés aux interconnexions par rapport aux délais dans les composants et de la consommation de puissance. Récemment, les délais dans les interconnexions sont devenus trop importants par rapport aux délais dans les portes logiques au point où la méthode de synthèse automatisée de circuits intégrés actuelle est devenue inadéquate. Puisque le traitement des interconnexions s'effectue lors de la synthèse physique, une nouvelle approche, inversant les étapes de la synthèse physique et de la synthèse logique, a été envisagée. La conception d'un système, utilisant un langage orienté-objet et offrant de la portabilité et une intégration de modules futurs, a été l'objet de cette recherche puisqu'un système utilisant un tel procédé n'a pas encore vu le jour. Une plate-forme de synthèse a été développée et celle-ci a été testée à l'aide d'un module de gestion de budgets de délai. Premièrement, une lecture de la description logique du circuit provenant de la synthèse comportementale a été effectuée en utilisant un décomposeur analytique et un analyseur syntaxique. Ensuite, pendant cette lecture, un réseau booléen hiérarchique représentant le circuit a été bâti selon une infrastructure prédéfinie. Afin de pouvoir tester la plate-forme, des budgets de délais ont été assignés à chaque noeud du réseau en propageant le temps d'arrivée et le temps requis dans un circuit provenant d'une description logique hiérarchique complexe. Finalement, la gestion de budgets de délai a été faite par un algorithme conçu à cet effet et les résultats de celle-ci ont été analysés. Le résultat obtenu est une plate-forme de synthèse capable de faire de la gestion de budget de délais sur les chemins critiques dans un circuit donné. De plus, celle-ci pourra être utilisée de nouveau pour d'autres projets liés à la synthèse de circuits. La pertinence de cette recherche repose sur la résolution d'un problème grandissant dans le monde de la synthèse automatisée des circuits intégrés.

Cette thèse aborde le problème de la décomposition booléenne des tableaux multidimensionnels de données binaires par modèle de mélange post non-linéaire. Dans la première partie, nous introduisons une nouvelle approche pour la factorisation booléenne en matrices binaires (FBMB) fondée sur un modèle de mélange post non-linéaire. Contrairement aux autres méthodes de factorisation de matrices binaires existantes, fondées sur le produit matriciel classique, le modèle proposé est équivalent au modèle booléen de factorisation matricielle lorsque les entrées des facteurs sont exactement binaires et donne des résultats plus interprétables dans le cas de sources binaires corrélées, et des rangs d'approximation matricielle plus faibles. Une condition nécessaire et suffisante d'unicité pour la FBMB est également fournie. Deux algorithmes s'appuyant sur une mise à jour multiplicative sont proposés et illustrés dans des simulations numériques ainsi que sur un jeu de données réelles. La généralisation de cette approche au cas de tableaux multidimensionnels (tenseurs) binaires conduit à la factorisation booléenne de tenseurs binaires (FBTB). La démonstration de la condition nécessaire et suffisante d’unicité de la décomposition booléenne de tenseurs binaires repose sur la notion d'indépendance booléenne d'une famille de vecteurs. L'algorithme multiplicatif fondé sur le modèle de mélange post non-linéaire est étendu au cas multidimensionnel. Nous proposons également un nouvel algorithme, plus efficace, s'appuyant sur une stratégie de type AO-ADMM (Alternating Optimization -ADMM). Ces algorithmes sont comparés à ceux de l'état de l'art sur des données simulées et sur un jeu de données réelles / This work is dedicated to the study of boolean decompositions of binary multidimensional arrays using a post nonlinear mixture model. In the first part, we introduce a new approach for the boolean factorization of binary matrices (BFBM) based on a post nonlinear mixture model. Unlike the existing binary matrix factorization methods, the proposed method is equivalent to the boolean factorization model when the matrices are strictly binary and give thus more interpretable results in the case of correlated sources and lower rank matrix approximations compared to other state-of-the-art algorithms. A necessary and suffi-cient condition for the uniqueness of the BFBM is also provided. Two algorithms based on multiplicative update rules are proposed and tested in numerical simulations, as well as on a real dataset. The gener-alization of this approach to the case of binary multidimensional arrays (tensors) leads to the boolean factorisation of binary tensors (BFBT). The proof of the necessary and sufficient condition for the boolean decomposition of binary tensors is based on a notion of boolean independence of binary vectors. The multiplicative algorithm based on the post nonlinear mixture model is extended to the multidimensional case. We also propose a new algorithm based on an AO-ADMM (Alternating Optimization-ADMM) strategy. These algorithms are compared to state-of-the-art algorithms on simulated and on real data

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Proposition d'une méthode dite de positionnement pour la conception d'algorithmes parallèles pour réseaux symboliques composés de cellules programmables. Simulation d'algorithmes symboliques dans le langage Occam, caractérisé par un mécanisme de synchronisation locale. Quelques résultats partiels sur une conjecture a propos du plus long cycle que peut générer séquentiellement un réseau booléen monotone sont présentés

Cette thèse porte sur deux thèmes : 1)Percolation et connexité sur les graphes géométriques aléatoires dits "type AB". 2)Comparaison stochastique directionnellement convexe de processus ponctuels et leurs propriétés de percolation et connexité. Dans le premier sujet, nous définissons un graphe biparti, dit "de type AB", sur deux processus ponctuels de Poisson indépendants. Cet graphe est une extension continue de graphe dit "type AB" sur une grille régulière. Nous montrons l'existence de percolation pour toute dimension supérieure à deux et nous établissons des bornes pour l'intensité critique. Dans le cas de dimensions deux, nous caractérisons exactement l'intensité critique. Pour le problème de connexité, nous étudions le modelé sur les processus ponctuels de Poisson indépendant dans le cube de volume un avec des intensités n et c_n pour une constante c > 0. Nous établissons des bornes asymptotiques presque sûres pour le seuil de connexité. 2) Le but du deuxième sujet de travail est de définir l'ordre directionnellement convexe de processus ponctuels est de lier cet ordre aux propriétés de regroupement des points de processus ponctuels et, dans un contexte applicatif, aux caractéristiques de la performance des réseaux de communication sans fil. La dernière partie de cette thèse porte sur la comparaison des intensités critiques de percolation pour les processus ponctuels ordonnés selon cet ordre et les applications de ces résultats de comparaison pour les réseaux sans fils. Nous concluons en montrant que les processus ponctuels inférieurs, selon cet ordre, à un processus ponctuel de Poisson ont une transition de phase non-triviale dans plusieurs modelés des percolation.

La synthèse logique joue un rôle fondamental dans les compilateurs de silicium. Alors que l'état de l'art de la synthèse deux couches est très avance, celui de la synthèse multi-couches reste encore un sujet très ouvert. L'objet de cette thèse est de présenter des méthodes originales de synthèse de contrôleurs et de systèmes combinatoires pour une implémentation multi-couches a base de cellules de bibliothèque. Le premier chapitre définit le concept de compilation de silicium et introduit l'une de ses composantes, la synthèse logique. L'importance du marche de la synthèse logique y est clairement définie ainsi que ses implications dans la conception actuelle de circuits intégrés. Le deuxième chapitre concerne la synthèse de contrôleurs. Le probleme du codage des machines d'états fini est traite en détail et une methode basée sur la théorie d'immersion de cubes intersectant dans un hypercube booléen est proposée. Le troisième chapitre est consacre a la synthèse de circuits combinatoires et une methode d'optimisation temporelle de tels dispositifs est développée. Ces travaux ont été implémentés dans un environnement industriel

Le calcul de motifs dans de grandes relations binaires a été très étudié. Un succès emblématique concerne la découverte d'ensembles fréquents et leurs post-traitements pour en dériver des règles d'association. Il s'agit de calculer des motifs dans des relations binaires qui enregistrent quelles sont les propriétés satisfaites par des objets. En fait, de nombreux jeux de données se présentent naturellement comme des relations n-aires (avec n > 2). Par exemple, avec l'ajout de dimensions spatiales et/ou temporelles (lieux et/ou temps où les propriétés sont enregistrées), la relation binaire Objets x Propriétés est étendue à une relation 4-aire Objets x Propriétés x Lieux x Temps. Nous avons généralisé le concept de règle d'association dans un tel contexte multi-dimensionnel. Contrairement aux règles usuelles qui n'impliquent que des sous-ensembles d'un seul domaine de la relation, les prémisses et les conclusions de nos règles peuvent impliquer des sous-ensembles arbitraires de certains domaines. Nous avons conçu des mesures de fréquence et de confiance pour définir la sémantique de telles règles et c'est une contribution significative de cette thèse. Le calcul exhaustif de toutes les règles qui ont des fréquences et confiances suffisantes et l'élimination des règles redondantes ont été étudiés. Nous proposons ensuite d'introduire des disjonctions dans les conclusions des règles, ce qui nécessite de retravailler les définitions des mesures d'intérêt et les questions de redondance. Pour ouvrir un champ d'application original, nous considérons la découverte de règles dans des graphes relationnels dynamiques qui peuvent être codés dans des relations n-aires (n ≥ 3). Une application à l'analyse des usages de bicyclettes dans le système Vélo'v (système de Vélos en libre-service du Grand Lyon) montre quelques usages possibles des règles que nous savons calculer avec nos prototypes logiciels. / Pattern discovery in large binary relations has been extensively studied. An emblematic success in this area concerns frequent itemset mining and its post-processing that derives association rules. In this case, we mine binary relations that encode whether some properties are satisfied or not by some objects. It is however clear that many datasets correspond to n-ary relations where n > 2. For example, adding spatial and/or temporal dimensions (location and/or time when the properties are satisfied by the objects) leads to the 4-ary relation Objects x Properties x Places x Times. Therefore, we study the generalization of association rule mining within arbitrary n-ary relations: the datasets are now Boolean tensors and not only Boolean matrices. Unlike standard rules that involve subsets of only one domain of the relation, in our setting, the head and the body of a rule can include arbitrary subsets of some selected domains. A significant contribution of this thesis concerns the design of interestingness measures for such generalized rules: besides a frequency measures, two different views on rule confidence are considered. The concept of non-redundant rules and the efficient extraction of the non-redundant rules satisfying the minimal frequency and minimal confidence constraints are also studied. To increase the subjective interestingness of rules, we then introduce disjunctions in their heads. It requires to redefine the interestingness measures again and to revisit the redundancy issues. Finally, we apply our new rule discovery techniques to dynamic relational graph analysis. Such graphs can be encoded into n-ary relations (n ≥ 3). Our use case concerns bicycle renting in the Vélo'v system (self-service bicycle renting in Lyon). It illustrates the added-value of some rules that can be computed thanks to our software prototypes.

Les aquifères fissurés de type karst contiennent d'importantes ressources en eau. Ces aquifères sont complexes et hétérogènes sur une gamme d'échelles importantes. Leur gestion nécessite l'utilisation d'outils et de méthodologies adaptés. Dans le cadre de cette étude, différents outils et méthodologies numériques d'étude ont été développés pour la modélisation des aquifères karstiques, et plus généralement, des milieux poreux très fissurés 2D et 3D - en mettant l'accent sur la morphologie et sur le comportement hydrodynamique du milieu à travers la notion de changement d'échelle ("second changement d'échelle", reposant sur un modèle d'écoulement local de type Darcy et/ou Poiseuille avec quelques généralisations). Plusieurs axes sont explorés concernant la morphologie du milieu poreux fissuré (milieux aléatoires, milieux booléens avec réseaux statistiques de fissures, mais aussi, modèles morphogénétiques). L'étude du changement d'échelle hydrodynamique tourne autour du concept de macro perméabilité. Dans un premier temps, l'étude porte sur un modèle de perte de charge linéaire darcien. Les perméabilités effectives sont calculées numériquement en termes des fractions volumiques de fissures et du contraste de perméabilité matrice/fissures. Elles sont analysées et comparées à des modèles théoriques (analytiques). Une étude particulière des effets de quasi-percolation pour les grands contrastes aboutit à la définition de trois fractions critiques liées à des seuils de percolation. Pour tenir compte des effets inertiels dans les fissures, l'étude est étendue au cas d'une loi locale comprenant un terme quadratique en vitesse (Darcy/Ward-Forchheimer). Une perméabilité macroscopique équivalente non linéaire est définie et analysée à l'aide d'un modèle inertiel généralisé (linéaire/puissance). Enfin, l'anisotropie hydraulique à grande échelle du milieu fissuré est étudiée, en termes de perméabilités directionnelles, à l'aide d'une méthode numérique d'immersion. / Karstic aquifers contain large subsurface water resources. These aquifers are complex and heterogeneous on a large range of scales. Their management requires appropriate numerical tools and approaches. Various tools and numerical methodologies have been developed to characterize andmodel the geometry and hydraulic properties of karstic aquifers, more generally, of highly fissured 2D and 3D porous media. In this study, we emphasize morphological characterization, and we analyze hydrodynamic behavior through the concept of upscaling ("second upscaling"). Concerning the morphology of fissured porous media, several axes are explored : random media, composite random Boolean media with statistical properties, and morphogenetic models. Hydrodynamic upscaling is developed using the macro-permeability concept. This upscaling method is based on either Darcy's linear law, or on a linear/quadratic combination of Darcy's and Ward-Forchheimer's quadratic law (inertial effects). First, the study focuses on Darcy's linear head loss law, and Darcian effective permeabilities are calculated numerically in terms of volume fractions of fissures and "fissure/matrix" permeability contrasts. The results are analysed and compared with analytical results and bounds. A special study of percolation and quasi-percolation effects, for high contrasts, leads to defined three critical fractions. These critical fractions are "connected" to percolation thresholds. Secondly, in order to consider inertial effect in fissures, the study is extended to a local law with a quadratic velocity term (Darcy/Ward-Forchheimer). Then, an equivalent nonlinear macroscopic permeability is defined and analysed using a generalized inertial model (linear/power). Finally, the large scale hydraulic anisotropy of fissured medium is studied, in terms of directional permeabilities, using an "immersion" numerical method.

Ce mémoire est consacré à trois modèles classiques de géométrie aléatoire : les mosaïques, les enveloppes convexes et le modèle booléen. Dans la première partie, on étudie les mosaïques poissonniennes d'hyperplans isotropes et plus particulièrement leur zéro-cellule qui est un polyèdre convexe aléatoire de l'espace euclidien. Deux cas particuliers de zéro-cellules sont la cellule typique de Poisson-Voronoi et la cellule de Crofton. On donne une formule explicite pour la loi du nombre de côtés d'une zéro-cellule en dimension deux. On s'intéresse au comportement asymptotique de cette loi et on fait le lien avec le problème de Sylvester des points en position convexe. On décrit ensuite la loi du rayon circonscrit ainsi que le comportement asymptotique du polyèdre à grand rayon inscrit au moyen de théorèmes limites. De cette manière et aussi par l'utilisation de la fréquence fondamentale, on apporte des précisions à l'énoncé de la conjecture de D. G. Kendall. La seconde partie a pour objet les enveloppes convexes de processus ponctuels de Poisson isotropes dans la boule-unité. On établit un résultat de type grandes déviations pour le nombre de sommets. On montre ensuite la convergence de la frontière de l'enveloppe après changement d'échelle et on en déduit des résultats de valeurs extrêmes, estimations de variance, théorèmes centraux limites et principes d'invariance pour certaines caractéristiques. Dans la troisième partie, on s'intéresse enfin aux modèles de recouvrement de type booléen de l'espace euclidien. Dans un premier travail, on applique une variante du modèle sans interpénétration des objets à la modélisation d'un phénomène de fissuration. On étudie ensuite la convergence de la composante connexe de l'origine d'un modèle booléen vers la cellule de Crofton en dimension deux. On s'intéresse enfin à la fonction de visibilité de cette composante connexe pour laquelle on obtient une estimée de la queue de distribution et des résultats de valeurs extrêmes.

Les enjeux économiques de l'industrie pétrolière imposent un important besoin de décrire la structure géologique des réservoirs d'hydrocarbures et des caractéristiques pétrophysiques des roches qui les constituent. La modélisation des réservoirs consiste à construire des modèles numériques qui représentent les hétérogénéités dans le réservoir à différentes échelles. Le schéma booléen est un modèle très utilisé pour établir un modèle lithologique de l'architecture interne du réservoir, que ce soit à l'échelle d'une unité génétique ou à l'échelle granulométrique à l'intérieur de ce dernier. Ce modèle présente néanmoins un problème important lors de son application à la modélisation de réservoirs présentant une distribution non stationnaire des lithofaciès qui les composent. Les proportions de ces lithofaciès fournissent une information sur leur distribution spatiale et constituent un outil très efficace pour déterminer la présence d'une non stationnarité. Elles permettent de quantifier l'information géologique des dépôts et constituent ainsi une importante contrainte à respecter pour obtenir des simulations géologiquement réalistes. Dans cette thèse, nous avons intégré dans le modèle booléen cette information contenue dans les proportions. Le problème abordé est l'inférence des paramètres du modèle à partir des proportions. Deux aspects ont été traités. D'une part, la définition du problème d'inférence du point de vue théorique, en établissant le rapport entre les variables expérimentales et les paramètres constitutifs du modèle. D'autre part, le développement d'un outil informatique opérationnel permettant d'automatiser le passage entre les données de proportion et les paramètres du modèle. Nous proposons une méthode d'inférence, basée sur un processus de déconvolution, qui permet d'introduire l'information des proportions dans le modèle et ainsi de reproduire dans les simulations une distribution non stationnaire des hétérogénéités de l'unité sédimentaire. Ces simulations respectent ainsi par construction la distribution latérale et verticale des proportions dans l'unité de même que la valeur moyenne globale de la proportion sur tout le volume étudié. Celle-ci est associée à des paramètres pétrophysiques telle que la porosité, et il est important de la retrouver dans les simulations.