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

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.

Cette thèse est consacrée à la modélisation qualitative des réseaux biologiques pour l'innovation thérapeutique. Elle étudie comment utiliser les réseaux Booléens, et comment les améliorer, afin d'identifier des cibles thérapeutiques au moyen d'approches in silico. Elle se compose de deux travaux : i) un algorithme exploitant les attracteurs des réseaux Booléens pour l'identification in silico de cibles dans des modèles Booléens de réseaux biologiques pathologiquement perturbés, et ii) une amélioration des réseaux Booléens dans leur capacité à modéliser la dynamique des réseaux biologiques grâce à l'utilisation des opérateurs de la logique floue et grâce au réglage des arrêtes. L'identification de cibles constitue l'une des étapes de la découverte de nouveaux médicaments et a pour but d'identifier des biomolécules dont la fonction devrait être thérapeutiquement modifiée afin de lutter contre la pathologie considérée. Le premier travail de cette thèse propose un algorithme pour l'identification in silico de cibles par l'exploitation des attracteurs des réseaux Booléens. Il suppose que les attracteurs des systèmes dynamiques, tel que les réseaux Booléens, correspondent aux phénotypes produits par le système biologique modélisé. Sous cette hypothèse, et étant donné un réseau Booléen modélisant une physiopathologie, l'algorithme identifie des combinaisons de cibles capables de supprimer les attracteurs associés aux phénotypes pathologiques. L'algorithme est testé sur un modèle Booléen du cycle cellulaire arborant une inactivation constitutive de la protéine du rétinoblastome, tel que constaté dans de nombreux cancers, tandis que ses applications sont illustrées sur un modèle Booléen de l'anémie de Fanconi. Les résultats montrent que l'algorithme est à même de retourner des combinaisons de cibles capables de supprimer les attracteurs associés aux phénotypes pathologiques, et donc qu'il réussit l'identification in silico de cibles proposée. En revanche, comme tout résultat in silico, il y a un pont à franchir entre théorie et pratique, requérant ainsi une utilisation conjointe d'approches expérimentales. Toutefois, il est escompté que l'algorithme présente un intérêt pour l'identification de cibles, notamment par l'exploitation du faible coût des approches computationnelles, ainsi que de leur pouvoir prédictif, afin d'optimiser l'efficience d'expérimentations coûteuses. La modélisation quantitative en biologie systémique peut s'avérer difficile en raison de la rareté des détails quantitatifs concernant les phénomènes biologiques, particulièrement à l'échelle subcellulaire, l'échelle où les médicaments interagissent avec leurs cibles. Une alternative permettant de contourner cette difficulté est la modélisation qualitative étant donné que celle-ci ne requiert que peu ou pas d'informations quantitatives. Parmi les méthodes de modélisation qualitative, les réseaux Booléens en sont l'une des plus populaires. Cependant, les modèles Booléens autorisent leurs variables à n'être évaluées qu'à vrai ou faux, ce qui peut apparaître trop simpliste lorsque des processus biologiques sont modélisés. En conséquence, le second travail de cette thèse propose une méthode de modélisation dérivée des réseaux Booléens où les opérateurs de la logique floue sont utilisés et où les arrêtes peuvent être réglées. Les opérateurs de la logique floue permettent aux variables d'être continues, et ainsi d'être plus finement évaluées qu'avec des méthodes de modélisation discrètes tel que les réseaux Booléens, tout en demeurant qualitatives. De plus, dans le but de considérer le fait que certaines interactions peuvent être plus lentes et/ou plus faibles que d'autres, l'état des arrêtes est calculé afin de moduler en vitesse et en force le signal qu'elles véhiculent. La méthode proposée est illustrée par son implémentation sur un petit échantillon de la signalisation du récepteur au facteur de croissance épidermique... [etc] / This thesis is devoted to the qualitative modeling of biological networks for therapeutic innovation. It investigates how to use the Boolean network formalism, and how to enhance it, for identifying therapeutic targets through in silico approaches. It is composed of two works: i) an algorithm using Boolean network attractors for in silico target identification in Boolean models of pathologically disturbed biological networks, and ii) an enhancement of the Boolean network formalism in modeling the dynamics of biological networks through the incorporation of fuzzy operators and edge tuning. Target identification, one of the steps of drug discovery, aims at identifying biomolecules whose function should be therapeutically altered in order to cure the considered pathology. The first work of this thesis proposes an algorithm for in silico target identification using Boolean network attractors. It assumes that attractors of dynamical systems, such as Boolean networks, correspond to phenotypes produced by the modeled biological system. Under this assumption, and given a Boolean network modeling a pathophysiology, the algorithm identifies target combinations able to remove attractors associated with pathological phenotypes. It is tested on a Boolean model of the mammalian cell cycle bearing a constitutive inactivation of the retinoblastoma protein, as seen in cancers, and its applications are illustrated on a Boolean model of Fanconi anemia. The results show that the algorithm returns target combinations able to remove attractors associated with pathological phenotypes and then succeeds in performing the proposed in silico target identification. However, as with any in silico evidence, there is a bridge to cross between theory and practice, thus requiring it to be used in combination with wet lab experiments. Nevertheless, it is expected that the algorithm is of interest for target identification, notably by exploiting the inexpensiveness and predictive power of computational approaches to optimize the efficiency of costly wet lab experiments. Quantitative modeling in systems biology can be difficult due to the scarcity of quantitative details about biological phenomenons, especially at the subcellular scale, the scale where drugs interact with there targets. An alternative to escape this difficulty is qualitative modeling since it requires few to no quantitative information. Among the qualitative modeling approaches, the Boolean network formalism is one of the most popular. However, Boolean models allow variables to be valued at only true or false, which can appear too simplistic when modeling biological processes. Consequently, the second work of this thesis proposes a modeling approach derived from Boolean networks where fuzzy operators are used and where edges are tuned. Fuzzy operators allow variables to be continuous and then to be more finely valued than with discrete modeling approaches, such as Boolean networks, while remaining qualitative. Moreover, to consider that some interactions are slower and/or weaker relative to other ones, edge states are computed in order to modulate in speed and strength the signal they convey. The proposed formalism is illustrated through its implementation on a tiny sample of the epidermal growth factor receptor signaling pathway. The obtained simulations show that continuous results are produced, thus allowing finer analysis, and that modulating the signal conveyed by the edges allows their tuning according to knowledge about the modeled interactions, thus incorporating more knowledge. The proposed modeling approach is expected to bring enhancements in the ability of qualitative models to simulate the dynamics of biological networks while not requiring quantitative information. The main prospect of this thesis is to use the proposed enhancement of Boolean networks to build a version of the algorithm based on continuous dynamical systems...[etc]