Dissertations / Theses on the topic 'Graphes généralisés'

Ce travail concerne l'etude des systemes lineaires generalises par l'approche bond graph. La modelisation de ces systemes avec choix particulier des vecteurs d'etat ne permet pas de les considerer comme des systemes reguliers surtout lorsqu'ils presentent des impulsions a l'instant initial et a tout instant ulterieur lorsque l'entree n'est pas suffisamment derivable. Une modelisation de ces systemes par bond graph est proposee. Ensuite, une interpretation graphique des elements de chaque matrice composant le modele d'etat generalise est donnee en terme de chemins causaux et de leur gain. Le calcul formel des coefficients du polynome caracteristique generalise a partir du modele bond graph comportant certains elements en causalite derivee, est donne. Ces coefficients peuvent etre ensuite a la base d'une methode de placement de poles formel par retour d'etat statique a partir du modele bond graph. La determination de la matrice de transfert est terminee par le calcul formel des differents numerateurs de cette matrice directement sur le modele bond graph. Le rang bond graph est une propriete interessante dans l'analyse structurelle par l'approche bond graph. Son calcul pour les systemes lineaires generalises est apparu alors comme une extension du resultat enonce pour les systemes reguliers modelises par bond graph. Pour la commandabilite en etat et l'observabilite structurelles, nous avons propose des procedures graphiques permettant de verifier la r- commandabilite et la r- observabilite du systeme generalise associe au modele bond graph
Nous avons egalement interprete graphiquement des criteres algebriques associes au sous systeme rapide dans la forme de rosenbrock du systeme generalise initial. La caracteristique principale d'un systeme generalise est ses modes impulsionnels s'ils existent. La modelisation des systemes generalises par bond graph ne permet pas de les faire apparaitre d'un point de vue structurel mais ceci est possible d'un point de vue formel. Une procedure graphique permettant de determiner formellement le nombre de modes impulsionnels que le systeme generalise peut exhiber a ete proposee. La modelisation par bond graph des systemes a commutation a permis de caracteriser leur modes impulsionnels. Nous avons interprete le nombre de ces modes a l'aide des chemins causaux apparus apres commutation entre element commutant et element i ou c statiquement dependant. Aussi, nous avons propose une interpretation graphique basee sur la notion de chemins causaux et de rang bond graph pour l'etude de la i- commandabilite et de la i- observabilite du systeme a commutation modelise par bond graph

Cette these est constituee par trois parties: (i), (ii) et (iii): i) on generalise le theoreme des bases de burnside a la classe des groupes matroidaux. On precise la structure des groupes matroidaux a sous-groupe de frattini trivial. On montre que les p-groupes dedoubles s'obtiennent canoniquement par extension d'un p-groupe possedant un systeme generateur x et un automorphisme qui inverse tout element de x; ii) on etudie l'influence des ordres des elements d'un groupe fini sur sa structure. On calcule le diametre du graphe de commutativite de plusieurs groupes. On decrit completement les groupes nilpotents et les groupes infinis possedant une fonction de steiner; iii) on classifie les graphes geodetiques de diametre 2. On etudie les graphes f-geodetiques (ou le nombre des geodesiques reliant deux sommets est une fonction donnee, dependant de la distance entre eux). On montre qu'un graphe f-geodetique biparti est regulier si et seulement si il est distance-regulier

De nombreux systèmes réels et applications, tels que les ateliers flexibles et systèmes embarqués, sont formés de tâches communicantes et sont modélisables par des réseaux de Petri pondérés. Le comportement de ces systèmes peut être vérifié sur leur modèle dès la phase de conception afin d'éviter les simulations post-conception coûteuses. Ces systèmes doivent satisfaire trois propriétés : vivacité, capacité bornée et réversibilité. La vivacité préserve la possibilité d'exécuter chaque tâche. La capacité bornée assure une quantité limitée de ressources. La réversibilité évite une initialisation coûteuse et permet de réinitialiser le système. Les méthodes d'analyse de ces propriétés ont généralement une complexité exponentielle. Dans cette thèse, nous étudions plusieurs sous-classes expressives des réseaux de Petri pondérés, soient les classes Fork-Attribution, Choice-Free, Join-Free et Equal-Conflict, pour lesquelles nous développons les premiers algorithmes polynomiaux garantissant vivacité, capacité bornée et réversibilité. Premièrement, nous apportons des transformations polynomiales qui préservent de nombreuses propriétés des réseaux de Petri pondérés et facilitent l'étude de leur comportement. Deuxièmement, nous utilisons ces transformations pour obtenir plusieurs conditions polynomiales suffisantes de vivacité pour les sous-classes considérées. Enfin, ces transformations simplifient l'étude de la réversibilité sous hypothèse de vivacité. Nous donnons plusieurs caractérisations et conditions polynomiales suffisantes de réversibilité pour les sous-classes étudiées. Nos conditions passent à l'échelle et sont aisément implémentables dans les systèmes réels
Many real systems and applications, including flexible manufacturing systems and embedded systems, are composed of communicating tasks and may be modeled by weighted Petri nets. The behavior of these systems can be checked on their model early on at the design phase, thus avoiding costly simulations on the designed systems. Usually, the models should exhibit three basic properties: liveness, boundedness and reversibility.Liveness preserves the possibility of executing every task, while boundedness ensures that the operations can be performed with a bounded amount ofresources. Reversibility avoids a costly initialization phase and allows resets of the system.Most existing methods to analyse these properties have exponential time complexity.By focusing on several expressive subclasses of weighted Petri nets, namely Fork-Attribution, Choice-Free, Join-Free and Equal-Conflict nets,the first polynomial algorithms that ensure liveness, boundednessand reversibility for these classes have been developed in this thesis.First, we provide several polynomial time transformations that preserve structural andbehavioral properties of weighted Petri nets, while simplifying the study of their behavior.Second, we use these transformations to obtain several polynomial sufficient conditions of livenessfor the subclasses considered. Finally, the transformations also prove useful for the study of the reversibility propertyunder the liveness assumption. We provide several characterizations and polynomial sufficient conditionsof reversibility for the same subclasses. All our conditions are scalable and can be easily implemented in real systems

De nombreux systèmes réels et applications, tels que les ateliers flexibles et systèmes embarqués, sont formés de tâches communicantes et sont modélisables par des réseaux de Petri pondérés. Le comportement de ces systèmes peut être vérifié sur leur modèle dès la phase de conception afin d'éviter les simulations post-conception coûteuses. Ces systèmes doivent satisfaire trois propriétés : vivacité, capacité bornée et réversibilité. La vivacité préserve la possibilité d'exécuter chaque tâche. La capacité bornée assure une quantité limitée de ressources. La réversibilité évite une initialisation coûteuse et permet de réinitialiser le système. Les méthodes d'analyse de ces propriétés ont généralement une complexité exponentielle. Dans cette thèse, nous étudions plusieurs sous-classes expressives des réseaux de Petri pondérés, soient les classes Fork-Attribution, Choice-Free, Join-Free et Equal-Conflict, pour lesquelles nous développons les premiers algorithmes polynomiaux garantissant vivacité, capacité bornée et réversibilité. Premièrement, nous apportons des transformations polynomiales qui préservent de nombreuses propriétés des réseaux de Petri pondérés et facilitent l'étude de leur comportement. Deuxièmement, nous utilisons ces transformations pour obtenir plusieurs conditions polynomiales suffisantes de vivacité pour les sous-classes considérées. Enfin, ces transformations simplifient l'étude de la réversibilité sous hypothèse de vivacité. Nous donnons plusieurs caractérisations et conditions polynomiales suffisantes de réversibilité pour les sous-classes étudiées. Nos conditions passent à l'échelle et sont aisément implémentables dans les systèmes réels
Many real systems and applications, including flexible manufacturing systems and embedded systems, are composed of communicating tasks and may be modeled by weighted Petri nets. The behavior of these systems can be checked on their model early on at the design phase, thus avoiding costly simulations on the designed systems. Usually, the models should exhibit three basic properties: liveness, boundedness and reversibility.Liveness preserves the possibility of executing every task, while boundedness ensures that the operations can be performed with a bounded amount ofresources. Reversibility avoids a costly initialization phase and allows resets of the system.Most existing methods to analyse these properties have exponential time complexity.By focusing on several expressive subclasses of weighted Petri nets, namely Fork-Attribution, Choice-Free, Join-Free and Equal-Conflict nets,the first polynomial algorithms that ensure liveness, boundednessand reversibility for these classes have been developed in this thesis.First, we provide several polynomial time transformations that preserve structural andbehavioral properties of weighted Petri nets, while simplifying the study of their behavior.Second, we use these transformations to obtain several polynomial sufficient conditions of livenessfor the subclasses considered. Finally, the transformations also prove useful for the study of the reversibility propertyunder the liveness assumption. We provide several characterizations and polynomial sufficient conditionsof reversibility for the same subclasses. All our conditions are scalable and can be easily implemented in real systems

Cette thèse s'inscrit dans le cadre de l'analyse statistique de données en grande dimension. Nous avons en effet aujourd'hui accès à un nombre toujours plus important d'information. L'enjeu majeur repose alors sur notre capacité à explorer de vastes quantités de données et à en inférer notamment les structures de dépendance. L'objet de cette thèse est d'étudier et d'apporter des garanties théoriques à certaines méthodes d'estimation de structures de dépendance de données en grande dimension.La première partie de la thèse est consacrée à l'étude de modèles parcimonieux et aux méthodes de type Lasso. Après avoir présenté les résultats importants sur ce sujet dans le chapitre 1, nous généralisons le cas gaussien à des modèles exponentiels généraux. La contribution majeure à cette partie est présentée dans le chapitre 2 et consiste en l'établissement d'inégalités oracles pour une procédure Group Lasso appliquée aux modèles linéaires généralisés. Ces résultats montrent les bonnes performances de cet estimateur sous certaines conditions sur le modèle et sont illustrés dans le cas du modèle Poissonien. Dans la deuxième partie de la thèse, nous revenons au modèle de régression linéaire, toujours en grande dimension mais l'hypothèse de parcimonie est cette fois remplacée par l'existence d'une structure de faible dimension sous-jacente aux données. Nous nous penchons dans cette partie plus particulièrement sur la méthode PLS qui cherche à trouver une décomposition optimale des prédicteurs étant donné un vecteur réponse. Nous rappelons les fondements de la méthode dans le chapitre 3. La contribution majeure à cette partie consiste en l'établissement pour la PLS d'une expression analytique explicite de la structure de dépendance liant les prédicteurs à la réponse. Les deux chapitres suivants illustrent la puissance de cette formule aux travers de nouveaux résultats théoriques sur la PLS . Dans une troisième et dernière partie, nous nous intéressons à la modélisation de structures au travers de graphes et plus particulièrement à la détection de communautés. Après avoir dressé un état de l'art du sujet, nous portons notre attention sur une méthode en particulier connue sous le nom de spectral clustering et qui permet de partitionner les noeuds d'un graphe en se basant sur une matrice de similarité. Nous proposons dans cette thèse une adaptation de cette méthode basée sur l'utilisation d'une pénalité de type l1. Nous illustrons notre méthode sur des simulations
This thesis falls within the context of high-dimensional data analysis. Nowadays we have access to an increasing amount of information. The major challenge relies on our ability to explore a huge amount of data and to infer their dependency structures.The purpose of this thesis is to study and provide theoretical guarantees to some specific methods that aim at estimating dependency structures for high-dimensional data. The first part of the thesis is devoted to the study of sparse models through Lasso-type methods. In Chapter 1, we present the main results on this topic and then we generalize the Gaussian case to any distribution from the exponential family. The major contribution to this field is presented in Chapter 2 and consists in oracle inequalities for a Group Lasso procedure applied to generalized linear models. These results show that this estimator achieves good performances under some specific conditions on the model. We illustrate this part by considering the case of the Poisson model. The second part concerns linear regression in high dimension but the sparsity assumptions is replaced by a low dimensional structure underlying the data. We focus in particular on the PLS method that attempts to find an optimal decomposition of the predictors given a response. We recall the main idea in Chapter 3. The major contribution to this part consists in a new explicit analytical expression of the dependency structure that links the predictors to the response. The next two chapters illustrate the power of this formula by emphasising new theoretical results for PLS. The third and last part is dedicated to graphs modelling and especially to community detection. After presenting the main trends on this topic, we draw our attention to Spectral Clustering that allows to cluster nodes of a graph with respect to a similarity matrix. In this thesis, we suggest an alternative to this method by considering a $l_1$ penalty. We illustrate this method through simulations

La coloration des graphes est un sujet central en théorie des graphes, et divers concepts de coloration ont été étudiés dans la littérature. Cette thèse étudie certains de ces concepts de coloration et les problèmes associés. Il s'agit notamment de la coloration des graphes signés généralisés, du nombre de choix fractionnels forts des graphes, du nombre de coloration généralisé des graphes, de la largeur gémellaire des graphes, de la discordance (combinatoire) des systèmes d'ensembles définissables et des classes de graphes chi_p-bornées. Un graphe signé est une paire (G, sigma), où G est un graphe et sigma: E(G) to {+,-} est une signature. Un graphe signé généralisé est également une paire (G, sigma), où la signature sigma attribue à chaque arête e une permutation sigma(e) dans un ensemble S comme son signe. Dans une coloration d'un graphe signé ou d'un graphe signé généralisé (G, sigma), le signe sigma(e) détermine les paires de couleurs qui doivent être évitées en tant que couleurs des sommets terminaux de e. Une question naturelle motivée par le théorème des quatre couleurs est de savoir pour quels sous-ensembles S de S_4, tout graphe planaire est S-4-colorable. Cette question a maintenant une réponse complète: seul S={id} posséde cette propriété, ce qui signifie que le théorème des quatre couleurs est strict au sens de la coloration généralisée des graphes signés. Ce résulat a été établi par une séquence de six articles, par différents groupes d'auteurs. L'une des contributions de cette thése est le résultat établi dans l'un de ces articles, à savoir que que de nombreux ensembles S n'ont pas la propriété désirée. La thèse considère également des questions similaires pour les graphes planaires sans triangle, ce qui peut être considéré comme une exploration de l'étanchéité du théorème de Grötzsch. Notre résultat montre que pour tout sous-ensemble S de S_3, si S n'est pas conjugué à un sous-ensemble de {id, (12)}, alors il existe un graphe planaire sans triangle qui n'est pas S-3-colorable. Une autre tentative pour renforcer le théorème de Grötzsch est de considérer le nombre de choix fractionnaire fort des graphes planaires sans triangle. Il a été prouvé par Voigt qu'il existe des graphes planaires sans triangle qui ne sont pas 3-choissables. Cette thèse prouve que le supremum du nombre de choix fractionnel fort des graphes planaires sans triangle est au moins 3+1/17. Un sujet important de la théorie structurelle des graphes est l'étude de la complexité structurelle des graphes. Quelques concepts et invariants de graphes sont largement étudiés dans la littérature. Récemment, le concept de largeur gémellaire a été introduit. Dans cette thèse, nous prouvons qu'un graphe G sans sous graphe K_{s,s} et de largeur gémellaire d a ses nombres de coloration forts (faibles) r bornés supérieurement par une fonction exponentielle en r et que nous pouvons construire des graphes réalisant une telle dépendance en r. L'une des deux notions centrales de la théorie structurelle des classes de graphes éparses est celle de classes d'expansion bornée. La discordance combinatoire est un sujet important. Elle mesure les irrégularités inévitables des systèmes d'ensembles et la difficulté intrinsèque de leur approximation. Dans cette thèse, nous donnons une nouvelle caractérisation des classes d'expansion bornée en termes de discordance de système définissables. La notion de chi-boundedness est un sujet central en théorie des graphes chromatiques. Dans cette thèse, les classes chi-bornées sont étudiées ici dans le contexte des colorations stellaires et, plus généralement, des chi_p-colorations. Considéré dans le cadre général de l'édute des classes éparses, il conduit à des extensions naturelles de la notion de classe d'expansion bornée. Nous résolvons ici deux conjectures liées à la limitation du nombre chromatique stellaire (i.e. chi_2). Nous donnons des caractérisations structurelles des classes (fortement et faiblement) chi_p-bornée
Graph coloring is a central topic in graph theory, and various coloring concepts have been studied in the literature. This thesis studies some of the coloring concepts and related problems. These include coloring of generalized signed graphs, strong fractional choice number of graphs, generalized coloring number of graphs, twin-width of graphs, (combinatorial) discrepancy of definable set systems and chi_p-bounded classes of graphs. A signed graph is a pair (G, sigma), where G is a graph and sigma: E(G) to {+,-} is a signature. A generalized signed graph is also a pair (G, sigma), where the signature sigma assigns to each edge e a permutation sigma(e) in a set S as its sign. In a coloring of a signed graph or a generalized signed graph (G, sigma), the sign sigma(e) determines the pairs of colors that need to be avoided as the colors of the end vertices of e. Let S_k be the set of all permutations of [k]. A natural question motivated by the four color theorem is for which subsets S of S_4, every planar graph is S-4-colorable. This question is now completely answered: only S={id} has this property, which means that the four color theorem is tight in the sense of generalized signed graph coloring. This answer is obtained in a sequence of six papers, by different groups of authors. The contribution of this thesis is the results in one of the papers, which shows that many sets S do not have the desired property. The thesis also considers similar questions for triangle-free planar graphs, which can be viewed as exploring the tightness of Grötzsch Theorem. Our result shows that for any subset S of S_3, if S is not conjugate to a subset of {id, (12)}, then there exists a triangle-free planar graph which is not S-3-colorable. Another attempt to strengthen Grötzsch Theorem is to consider multiple list coloring of triangle-free planar graphs. It was proved by Voigt that there are triangle-free planar graphs that are not 3-choosable. This thesis strengthens Voigt's result by considering the strong fractional choice number of graphs and proves that the supremum of the strong fractional choice number of triangle-free planar graphs is at least 3+1/17. One important subject in structural graph theory is to study the structural complexity of graphs or classes of graphs and a few concepts and graph invariants are studied extensively in the literature. These include treewidth of graphs, generalized coloring number, etc. Recently, the concept of twin-width was introduced by Bonnet, Kim, Thomassé and Watrigant. In this thesis, we study the relation between twin-width and generalized coloring number. We prove that a graph $G$ with no K_{s,s}-subgraph and twin-width d has strong(weak) r-coloring numbers bounded by an exponential function of r and that we can construct graphs achieving such a dependency in r. One of the two central notions in structural theory of classes of sparse graphs is the classes with bounded expansion. These classes have strong algorithmic and structural properties and enjoy numerous characterizations and applications. Combinatorial discrepancy is a significant subject in its own right. It measures the inevitable irregularities of set systems and the inherent difficulty to approximate them. In this thesis, we give a new characterization of bounded expansion classes in terms of discrepancy of definable set systems. The notion of chi-boundedness is a central topic in chromatic graph theory. This thesis studies chi-bounded classes in the context of star colorings and, more generally, chi_p-colorings, say chi_s-bounded and (strongly and weakly) chi_p-bounded classes. This fits to a general scheme of sparsity and leads to natural extensions of the notion of bounded expansion class. Here we solve two conjectures related to star coloring ({i.e.} chi_2) boundedness and give structural characterizations of strongly chi_p-bounded classes and weakly chi_p-bounded classes

Étude sur les graphes bipartis orientes de Moore montrant que de tels graphes existent, pour certaines valeurs du diamètre, et servent a la construction d'une classe de graphes bipartis orientes, asymptotiquement optimaux. Dans la deuxième partie du travail, quelques notions de coloration des graphes sont présentées. Celles-ci permettent de généraliser certains résultats déjà connus dans le cadre de la coloration habituelle et d'en obtenir d'autres plutôt spécifiques a ces notions. La généralisation de la notion de perfection en b-perfection est proposée ce qui permet l'obtention des graphes triangules représentant la seule classe de graphes b-parfaits

Les modèles d'appariements aléatoires représentent de nombreux systèmes stochastiques concrets dans lesquels des éléments de différentes classes sont appariés selon des règles de compatibilités spécifiées. Par exemple, on peut citer les systèmes dédiés à l'allocation d'organes, les sites de recherche d'emplois, de logements, etc. De tels modèles sont toujours associés à un triptyque d'éléments : un graphe connexe, dit de compatibilités, dont les sommets représentent les classes des éléments pouvant entrer dans le systèmeet dont chaque arête relie deux classes compatibles, une politique d'appariements permettant de décider, en cas d'incertitude, quels appariements vont s'effectuer à l'intérieur du système, et un taux d'arrivées selon lequel les éléments entrent en son sein. Dans cette thèse, nous considérons des graphes généralisés, c'est-à-dire que l'on autorise l'appariement de deux éléments de la même classe, et nous étendons donc à ce cadre certains résultats déjà connus dans le cas de graphes simples. La stabilité d'un système régi par un modèle d'appariements est une propriété très importante. En effet, elle assure que les admissions au sein du système étudié sont contrôlées de sorte que les éléments ne restent pas bloqués à l'intérieur et que leur nombre n'augmente pas indéfiniment. Il est donc essentiel que le taux d'arrivées des éléments permette au système d'être stable. Dans ce manuscrit, nous caractérisons de manière algébrique cette zone de stabilité pour certains modèles d'appariements (généraux, généraux avec abandons, bipartis, bipartis étendus) ou de files d'attente, dites skill-based. Par ailleurs, nous démontrons que la politique d'appariements dite First Come, First Matched (FCFM) possède la propriété d'être maximale (généralisée), c'est-à-dire que la zone de stabilité du modèle d'appariements général associé à un graphe de compatibilités et à une politique quelconque est toujours incluse dans celle associée à ce même graphe et à FCFM. Notons que cette dernière coïncide alors avec un ensemble de mesures défini par des conditions purement algébriques. Dans ce cas, la question de l'étude des mesures permettant la stabilité des systèmes régis par un modèle d'appariements revient donc à celle, plus élémentaire, de la caractérisation d'un ensemble déterministe. Nous donnons alors un moyen de construction (simple) des mesures appartenant à celui-ci, ce qui peut s'avérer très utile pour calibrer le contrôle d'accès au système. En effet, la vérification algorithmique qu'une mesure quelconque vérifie ces conditions algébriques nécessite un nombre d'opérations polynomial en le nombre de sommets du graphe, et devient donc très coûteuse à mesure que ce cardinal augmente. Nous explicitons également, sous une forme produit, l'expression de la loi stationnaire de l'évolution temporelle du contenu d'un système stable régi par un modèle d'appariements général et sous la politique FCFM, permettant, notamment, de calculer explicitement des caractéristiques à l'équilibre de systèmes concrets et d'estimer leurs performances en temps long. On peut ainsi, par exemple, calculer la taille moyenne à l'équilibre d'une liste d'attente dans le cadre de dons croisés de reins, ou encore, estimer le temps moyen d'attente sur une interface pair-à-pair ou un site de rencontres.Enfin, les taux d'appariements associés à un modèle d'appariements (général ou biparti étendu) stable sont étudiés. Ils sont définis comme étant les fréquences asymptotiques des appariements réalisés et fournissent un critère de performance des systèmes régis par de tels modèles d'appariements, de même que les propriétés de politique-insensibilité et d'équité de ces taux, qui sont également discutées
Stochastic matching models represent many concrete stochastic systems in which elements of different classes are matched according to specified compatibility rules. For example, we can cite systems dedicated to organs allocation, job search sites, housing allocation programs, etc. Such models are typically associated to a triplet of elements: a connected graph, called compatibility graph, whose vertices represent the classes of elements that can enter the system and whose edges connect two compatible classes, amatching policy which decides the matches to be concretely executed, in case of multiple choices, and an arrival rate according to which the elements enter within it. In this thesis, we consider generalized graphs, meaning that we allow the matching of two elements of the same class, and we therefore extend to this framework some results already known in the case of simple graphs.The stability of a system governed by a matching model is a very important property. It ensures that the admissions within the system under study, are regulated, so that the elements do not accumulate in the system in the long run. It is therefore essential that the arrival rate of the elements allows the system to be stable. In this manuscript, we characterize, algebraically, this stability region for some matching models (general, general with reneging, bipartite, extended bipartite) or skill-based queueing systems.Moreover, we demonstrate that the matching policy called First Come, First Matched (FCFM) has the property of being (generalized) maximal, meaning that the stability region of the general matching model associated with a compatibility graph and with any policy is always included in the one associated with this same graph and ruled by FCFM. Note that this latter then coincides with a set of measures defined by purely algebraic conditions. In this case, the study of stability of the matching model at hand boils down to the more elementary question of characterizing of a deterministic set of measures. We then givea (simple) way to construct the measures belonging to the latter set. This turns out to be very useful for admission control, as checking the algebraic conditions requires a number of operations which is polynomial in the number of vertices of the considered compatibility graph, and therefore becomes very expensive as the number of vertices grows large.We also give, in a product form, the expression of the stationary distribution of the number-in-system process of a stable system governed by a general matching model and under the FCFM policy, allowing, in particular, to explicitly calculate characteristics at equilibrium of concrete systems and to estimate their long-time performance. We can thus, for example, calculate the size average at equilibrium of a waiting list in the case of cross-donation of kidneys, or even, estimate the average waiting time on a peer-to-peerinterface or on a dating website.Finally, the matching rates associated with a stable matching model (general or extended bipartite) are studied. They are defined as the asymptotic frequencies of the executed respective matchings, and provide an insightful performance criterion for the corresponding matching systems, as well as the policy-insensitivity and fairness properties of the matching rates, which are also discussed

Les définitions actuelles des infrastructures de sécurité (française, européenne, G-20) sont inadaptées à la réalité des attaques observées ou potentielles. Il en est de même des attaques elles-mêmes et en conséquence le terme « cyberattaque » réduit considérablement le champ conceptuel et opérationnel de celui qui est en charge de la protection et de la défense. La quasi-totalité des approches se réduit à identifier le champ strictement technique informatique (systèmes, réseaux) et à oublier d’autres dimensions propres au renseignement. Ainsi les principales méthodologies d’identification et de gestion du risque (EBIOS ou méthodologies similaires) considèrent une définition particulièrement restrictive, statique et locale de la notion d’infrastructure critique. La modélisation elle-même des attaquants et des attaques est extrêmement réduite. La principale erreur est de restreindre les approches techniques et les angles d’attaque d’un attaquant au seul champ informatique. Les angles « cyber » peuvent ne pas exister ou représenter un volet limitée dans un scenario global d’attaque. En outre, l’approche classique néglige le volet opérationnel gouvernant la préparation et la conduite de la manœuvre dans une attaque. Les modélisations par arbres d’attaques sont également très limitées du fait d’une restriction au seul champ cyber (systèmes et réseaux).Il est alors nécessaire de concevoir une définition très élargie, laquelle doit être dictée par la vision de l'attaquant et non celle du défenseur. Cette thèse vise à développer de nouveaux modèles d'infrastructure de sécurité basés sur la théorie des graphes et a modéliser de manière très élargie le concept d’attaque, incluant ou non un champ cyber. Cette représentation déjà utilisée pour décrire la topologie des infrastructures critiques sera enrichie pour appréhender de manière exhaustive l'environnement avec lesquelles elles interagissent. Les interdépendances avec d’autres entités (personnes, autres infrastructures critiques…) sont un élément clef dans la construction de scenarii d’attaques sophistiquées. Cette représentation enrichie doit aboutir à des nouveaux modèles d'attaquants, plus réalistes et mettant en œuvre des composants externes de l'infrastructure mais appartenant à son environnement proche. L'objectif majeur est la recherche de chemins optimaux dans un scénario d'attaque défini par l'objectif de l'adversaire. Cette approche globale, apporte une définition plus fine (et donc plus réaliste) de la sécurité comme étant le coût le plus faible du chemin d'attaque pris sur l'ensemble des adversaires réalistes (polynomiaux, i.e. agissant en temps fini).Le programme de recherche est structuré en cinq étapes. Les deux premières étapes visent à définir les modèles et les objets représentant les infrastructures de sécurité ainsi que les attaquants auxquelles elles sont confrontées. La troisième étape consiste en la définition d'une méthodologie générique pour évaluer la sécurité d'une infrastructure de sécurité. Cette étape doit aboutir à la conception d'heuristiques de recherche de vulnérabilités. Afin de valider les modèles et la méthodologie proposés, le programme de thèse prévoit le développement d'un démonstrateur recherche sous la forme d'une plate-forme d'évaluation. Enfin, la dernière étape consistera à l'évaluation d'un système existant à partir de la plate-forme en mettant en œuvre la méthodologie proposée. L'objectif de cette dernière étape est de valider les modèles et la méthodologie et d'en proposer une amélioration si nécessaire
The current definitions of a critical infrastructure are not adapted to the actual attacks which are observed these days. The problem is the same for the definition of an attack and therefore, the term « cyber attack » tends to reduce the conceptual and operational field of the person in charge of the security. Most of the approaches are reduced to identify the technical and IT domain only, and they forget the others domains specific to the intelligence. Then, the main methodologies to identify and to manage risk (EBIOS or some similar methodologies) take into account a definition of a critical infrastructure which is restrictive, static and local. The model of attacker and attack is also extremely narrowed as the technical approaches and the angles of attack of an attacker tend to be restricted to the IT domain only, even if the « cyber » angles may not exist or may only be a small part of an attack scenario.Therefore, it is necessary to have a new definition of a critical infrastructure, more complete and made according to the attacker point of view. Indeed, critical infrastructures can be protected by assessing the threats and vulnerability. This thesis aims to develop new models of infrastructure and attack accurately, models which will based on graph theory, with or without the cyber part. This graph-based representation is already used a lot to describe infrastructure, it will be enriched in order to have a more exhaustive view of an infrastructure environment. The dependencies with other entities (people, others critical infrastructures, etc.) have to be taken into account in order to obtain pertinent attack scenarios. This enriched representation must lead to new models of attackers, more realistic and implementing external components of the infrastructure which belong to its immediate environment. The main objective is the research of optimal paths or other mathematical structures which can be translated into attack scenarios. This global approach provides a finer (and therefore more realistic) definition of security as the lowest cost of the attack path.The research program is structured in five stages. The first two steps are aimed at defining the models and objects representing the security infrastructures as well as the attackers they are confronted with. The major difficulty encountered in developing a relevant infrastructure model is its ability to describe. Indeed, the more the model is rich, the more it can describe the infrastructure and the adversaries that attack it. The counterpart of developing a relevant model is its exponential characteristic. In these security models, we therefore expect that the problem of finding the vulnerabilities of a security infrastructure is equivalent to difficult problems, i.e. NP-hard or even NP-complete. The locks to be lifted will therefore consist in the design of heuristics to answer these problems in finite time with an ``acceptable" response. The third step is to define a generic methodology for assessing the safety of a security infrastructure. In order to validate the proposed models and methodology, the thesis program provides for the development of a research demonstrator in the form of an evaluation platform. Finally, the last step will be to evaluate an existing system from the platform by implementing the proposed methodology. The objective of this last step is to validate the models and the methodology and to propose an improvement if necessary

Cette dissertation se divise en deux parties, distinctes mais connexes, qui sont le reflet de la cotutelle. Nous étudions et résolvons des problèmes concernant d'une part la combinatoire des mots dans un contexte abélien et d'autre part des problèmes de couverture dans des graphes. Chaque question fait l'objet d'un chapitre. En combinatoire des mots, le premier problème considéré s'intéresse à la régularité des suites au sens défini par Allouche et Shallit. Nous montrons qu'une suite qui satisfait une certaine propriété de symétrie est 2-régulière. Ensuite, nous appliquons ce théorème pour montrer que les fonctions de complexité 2-abélienne du mot de Thue--Morse ainsi que du mot appelé ''period-doubling'' sont 2-régulières. Les calculs et arguments développés dans ces démonstrations s'inscrivent dans un schéma plus général que nous espérons pouvoir utiliser à nouveau pour prouver d'autres résultats de régularité. Le deuxième problème poursuit le développement de la notion de mot de retour abélien introduite par Puzynina et Zamboni. Nous obtenons une caractérisation des mots sturmiens avec un intercepte non nul en termes du cardinal (fini ou non) de l'ensemble des mots de retour abélien par rapport à tous les préfixes. Nous décrivons cet ensemble pour Fibonacci ainsi que pour Thue--Morse (bien que cela ne soit pas un mot sturmien). Nous étudions la relation existante entre la complexité abélienne et le cardinal de cet ensemble. En théorie des graphes, le premier problème considéré traite des codes identifiants dans les graphes. Ces codes ont été introduits par Karpovsky, Chakrabarty et Levitin pour modéliser un problème de détection de défaillance dans des réseaux multiprocesseurs. Le rapport entre la taille optimale d'un code identifiant et la taille optimale du relâchement fractionnaire d'un code identifiant est comprise entre 1 et 2 ln(|V|)+1 où V est l'ensemble des sommets du graphe. Nous nous concentrons sur les graphes sommet-transitifs, car nous pouvons y calculer précisément la solution fractionnaire. Nous exhibons des familles infinies, appelées quadrangles généralisés, de graphes sommet-transitifs pour lesquelles les solutions entière et fractionnaire sont de l'ordre |V|^k avec k dans {1/4, 1/3, 2/5}. Le second problème concerne les (r,a,b)-codes couvrants de la grille infinie déjà étudiés par Axenovich et Puzynina. Nous introduisons la notion de 2-coloriages constants de graphes pondérés et nous les étudions dans le cas de quatre cycles pondérés particuliers. Nous présentons une méthode permettant de lier ces 2-coloriages aux codes couvrants. Enfin, nous déterminons les valeurs exactes des constantes a et b de tout (r,a,b)-code couvrant de la grille infinie avec |a-b|>4. Il s'agit d'une extension d'un théorème d'Axenovich
This dissertation is divided into two (distinct but connected) parts that reflect the joint PhD. We study and we solve several questions regarding on the one hand combinatorics on words in an abelian context and on the other hand covering problems in graphs. Each particular problem is the topic of a chapter. In combinatorics on words, the first problem considered focuses on the 2-regularity of sequences in the sense of Allouche and Shallit. We prove that a sequence satisfying a certain symmetry property is 2-regular. Then we apply this theorem to show that the 2-abelian complexity functions of the Thue--Morse word and the period-doubling word are 2-regular. The computation and arguments leading to these results fit into a quite general scheme that we hope can be used again to prove additional regularity results. The second question concerns the notion of return words up to abelian equivalence, introduced by Puzynina and Zamboni. We obtain a characterization of Sturmian words with non-zero intercept in terms of the finiteness of the set of abelian return words to all prefixes. We describe this set of abelian returns for the Fibonacci word but also for the Thue-Morse word (which is not Sturmian). We investigate the relationship existing between the abelian complexity and the finiteness of this set. In graph theory, the first problem considered deals with identifying codes in graphs. These codes were introduced by Karpovsky, Chakrabarty and Levitin to model fault-diagnosis in multiprocessor systems. The ratio between the optimal size of an identifying code and the optimal size of a fractional relaxation of an identifying code is between 1 and 2 ln(|V|)+1 where V is the vertex set of the graph. We focus on vertex-transitive graphs, since we can compute the exact fractional solution for them. We exhibit infinite families, called generalized quadrangles, of vertex-transitive graphs with integer and fractional identifying codes of order |V|^k with k in {1/4,1/3,2/5}. The second problem concerns (r,a,b)-covering codes of the infinite grid already studied by Axenovich and Puzynina. We introduce the notion of constant 2-labellings of weighted graphs and study them in four particular weighted cycles. We present a method to link these labellings with covering codes. Finally, we determine the precise values of the constants a and b of any (r,a,b)-covering code of the infinite grid with |a-b|>4. This is an extension of a theorem of Axenovich

Cette thèse s’inscrit dans le domaine de la combinatoire algébrique et énumérative. Elle est consacrée à l’étude des problèmes d’énumération en utilisant des algèbres de Hopf combinatoires, en particulier l’algèbre des fonctions symétriques sur les mots WSym. Nous donnons des versions non commutatives du théorème de Redfield-Pólya dans l’algèbre WSym, ainsi que dans d’autres algèbres de Hopf combinatoires comme l’algèbre des fonctions symétriques sur les bi-mots BWSym, où nous donnons un relèvement (décomposition maximale) de ce théorème. Nous construisons d’autres algèbres de Hopf sur les partitions d’ensembles et sur des objets qui les généralisent et nous les utilisons pour l’étude des versions non commutatives des polynômes de Bell qui ont été définis par E. T. Bell et interviennent fortement en combinatoire énumérative. Ces polynômes font intervenir des objets combinatoires comme les partitions d’ensembles. Alors, c’est tout à fait naturel de chercher des analogues de ces identités dans des algèbres dont les bases sont indexées par des objets en lien avec les partitions (partitions en listes, partitions colorées, etc). Puis, nous donnons des analogues de quelques identités concernant les polynômes partiels, des fonctions binomiales et d’autres identités comme la formule d’inversion de Lagrange et la formule de Faà di Bruno. Enfin, nous nous intéressons à l’étude combinatoire des structures algébriques apparaissant dans les problèmes de l’ordre normal des bosons. Nous définissons des nouveaux objets combinatoires (nommés B-diagrammes) et construisons deux algèbres : une algèbre de Hopf construit sur les B-diagrammes et l’algèbre de Fusion qui réalise l’algèbre des B-diagrammes B sur des variables. Nous constatons que pour des cas particuliers des B-diagrammes, nous retrouvons deux sous-algèbres WSym et BWSym isomorphes à B
This thesis fits into the field of algebraic and enumerative combinatorics. It is devoted to the study of problems of enumeration using combinatorial Hopf algebras, particularly, the algebra of word symmetric functions WSym. We give noncommutative versions of the Redfield-Pólya theorem in WSym and other combinatorial Hopf algebras as the algebra of biword symmetric functions BWSym. In the second algebra, we give a relevement (version without multiplicities) of this theorem. We construct other Hopf algebras on set partitions and other objects which generealize them. We use these algebras to study noncommutative version of Bell polynomials. These polynomials involve combinatorial objects like set partitions. So it seems natural for us to investigate analogous formulæ in some combinatorial Hopf algebras with bases indexed by objects related to set partitions (set partitions into lists, colored set partitions, etc). Then, we give analogous identities of partial Bell polynomials, binomial functions, Lagrange inversion and Faà di Bruno formula. Finally, we are interested in the combinatorial structures arising in the boson normal ordering problem. We define new combinatorial objects (called B-diagrams). After studying the combinatorics and the enumeration of B-diagrams, we propose two constructions of algebras called : the Fusion algebra defined using formal variables and another algebra constructed directly from B-diagrams. We show the connection between these two algebras and that the algebra of B-diagrams B can be endowed with Hopf structure. We recognise two known combinatorial Hopf subalgebras of B : WSym the algebra of word symmetric functions indexed by set partitions and BWSym the algebra of biword symmetric functions indexed by set partitions into lists

Cette thèse se compose de quatre articles autonomes s'articulant en trois thèmes: la conjecture de Kashiwara-Vergne, le graphe-complexe de Kontsevich et les bigèbres magmatiques. Ces articles sont liés par la notion de bigèbre et les idempotents qui leurs sont attachés: dans le premier cas on utilise les propriétés des bigèbres classiques et dans le second des bigèbres Zinbiel-associatives. Le résultat principal du premier article consiste à donner une solution complète et explicite de la première équation de la conjecture de Kashiwara-Vergne en utilisant les propriétés intrinsèques de l'idempotent Eulérien et de l'idempotent de Dynkin. Dans le second article on généralise un théorème de Kontsevich à l'homologie de Leibniz. On démontre que l'homologie de Leibniz des champs de vecteurs symplectiques sur une variété formelle se reconstruit à partir de l'homologie d'un nouveau type de complexe de graphes : le graphe complexe symétrique. La troisième partie est composée de deux articles traitant des bigèbres magmatiques. Dans le premier on démontre que toute bigèbre magmatique infinie se reconstruit à partir de ses primitifs. En collaboration avec Ralf Holtkamp, on généralise ce résultat à des bigèbres magmatiques partielles en construisant une nouvelle structure d'algèbres vérifiée par les primitifs
This thesis contains four articles developed around three themes : the Kashiwara-Vergne conjecture, Kontsevich's graph complex and magmatic bialgebras. The results obtained are linked by the notion of generalised bialgebras and their idempotents: in the first case we use the properties of classical bialgebras and in the second, a structure theorem for Zinbiel-associatives bialgebras. The main result of the first article is to construct explicitly all the solutions of the first equation of Kashiwara-Vergne conjecture, using the interplay between the Eulerian idempotent and the Dynkin idempotent. In second chapter we generalise the Kontsevich's theorem that computes the Lie homology of vector fields on a formal manifold. Indeed, we prove that the Leibniz homology of these symplectic vector fields on a formal manifold can be reconstructed thanks to the homology associated to a new type of graphs: the symmetric graphs. The third part contains two articles on magmatic bialgebras. In the first one, we prove a structure theorem which permits to reconstruct any infinite magmatic bialgebra through its primitives. In collaboration with Ralf Holtkamp, we extend this result to partial magmatic bialgebras and we construct a new type of operad that encodes the algebraic structure satisfied by the primitives

La géostatistique est la branche des statistiques s’intéressant à la modélisation des phénomènes ancrés dans l’espace au travers de modèles probabilistes. En particulier, le phénomène en question est décrit par un champ aléatoire (généralement gaussien) et les données observées sont considérées comme résultant d’une réalisation particulière de ce champ aléatoire. Afin de faciliter la modélisation et les traitements géostatistiques qui en découlent, il est d’usage de supposer ce champ comme stationnaire et donc de supposer que la structuration spatiale des données se répète dans le domaine d’étude.Cependant, lorsqu’on travaille avec des jeux de données spatialisées complexes, cette hypothèse devient inadaptée. En effet, comment définir cette notion de stationnarité lorsque les données sont indexées sur des domaines non euclidiens(comme des sphères ou autres surfaces lisses)? Quid également du cas où les données présentent structuration spatiale qui change manifestement d’un endroit à l’autre du domaine d’étude? En outre, opter pour des modèles plus complexes,lorsque cela est possible, s’accompagne en général d’une augmentation drastique des coûts opérationnels (calcul et mémoire), fermant alors la porte à leur application à de grands jeux de données. Dans ce travail, nous proposons une solution à ces problèmes s’appuyant sur la définition de champs aléatoires généralisés sur des variétés riemanniennes. D’une part, travailler avec des champs aléatoires généralisés permet d’étendre naturellement des travaux récents s’attachant à tirer parti d’une caractérisation des champs aléatoires utilisés en géostatistique comme des solutions d’équations aux dérivées partielles stochastiques. D’autre part, travailler sur des variétés riemanniennes permet à la fois de définir des champs sur des domaines qui ne sont que localement euclidiens, et sur des domaines vus comme déformés localement (ouvrant donc la porte à la prise en compte du cas non stationnaire). Ces champs généralisés sont ensuite discrétisés en utilisant une approche par éléments finis, et nous en donnons une formule analytique pour une large classe de champs généralisés englobant les champs généralement utilisés dans les applications. Enfin, afin de résoudre le problème du passage à l’échelle pour les grands jeux de données, nous proposons des algorithmes inspirés du traitement du signal sur graphe permettant la simulation, la prédiction et l’inférence de ces champs par des approches "matrix-free"
Geostatistics is the branch of statistics attached to model spatial phenomena through probabilistic models. In particular, the spatial phenomenon is described by a (generally Gaussian) random field, and the observed data are considered as resulting from a particular realization of this random field. To facilitate the modeling and the subsequent geostatistical operations applied to the data, the random field is usually assumed to be stationary, thus meaning that the spatial structure of the data replicates across the domain of study. However, when dealing with complex spatial datasets, this assumption becomes ill-adapted. Indeed, how can the notion of stationarity be defined (and applied) when the data lie on non-Euclidean domains (such as spheres or other smooth surfaces)? Also, what about the case where the data clearly display a spatial structure that varies across the domain? Besides, using more complex models (when it is possible) generally comes at the price of a drastic increase in operational costs (computational and storage-wise), rendering them impossible to apply to large datasets. In this work, we propose a solution to both problems, which relies on the definition of generalized random fields on Riemannian manifolds. On one hand, working with generalized random fields allows to naturally extend ongoing work that is done to leverage a characterization of random fields used in Geostatistics as solutions of stochastic partial differential equations. On the other hand, working on Riemannian manifolds allows to define such fields on both (only) locally Euclidean domains and on locally deformed spaces (thus yielding a framework to account for non-stationary cases). The discretization of these generalized random fields is undertaken using a finite element approach, and we provide an explicit formula for a large class of fields comprising those generally used in applications. Finally, to solve the scalability problem,we propose algorithms inspired from graph signal processing to tackle the simulation, the estimation and the inference of these fields using matrix-free approaches

Une carte généralisée est un modèle topologique permettant de représenter implicitementun ensemble de cellules (sommets, arêtes, faces , volumes, . . .) ainsi que l'ensemblede leurs relations d'incidence et d'adjacence au moyen de brins et d'involutions. Les cartes généralisées sont notamment utilisées pour modéliser des images et objets3D. A ce jour il existe peu d'outils permettant l'analyse et la comparaison de cartes généralisées.Notre objectif est de définir un ensemble d'outils permettant la comparaisonde cartes généralisées.Nous définissons tout d'abord une mesure de similarité basée sur la taille de la partiecommune entre deux cartes généralisées, appelée plus grande sous-carte commune.Nous définissons deux types de sous-cartes, partielles et induites, la sous-carte induitedoit conserver toutes les involutions tandis que la sous-carte partielle autorise certaines involutions à ne pas être conservées. La sous-carte partielle autorise que les involutionsne soient pas toutes conservées en analogie au sous-graphe partiel pour lequelles arêtes peuvent ne pas être toutes présentes. Ensuite nous définissons un ensembled'opérations de modification de brins et de coutures pour les cartes généralisées ainsiqu'une distance d'édition. La distance d'édition est égale au coût minimal engendrépar toutes les successions d'opérations transformant une carte généralisée en une autrecarte généralisée. Cette distance permet la prise en compte d'étiquettes, grâce à l'opérationde substitution. Les étiquettes sont posées sur les brins et permettent d'ajouter del'information aux cartes généralisées. Nous montrons ensuite, que pour certains coûtsnotre distance d'édition peut être calculée directement à partir de la plus grande souscartecommune.Le calcul de la distance d'édition est un problème NP-difficile. Nous proposons unalgorithme glouton permettant de calculer en temps polynomial une approximation denotre distance d'édition de cartes. Nous proposons un ensemble d'heuristiques baséessur des descripteurs du voisinage des brins de la carte généralisée permettant de guiderl'algorithme glouton, et nous évaluons ces heuristiques sur des jeux de test générésaléatoirement, pour lesquels nous connaissons une borne de la distance.Nous proposons des pistes d'utilisation de nos mesures de similarités dans le domainede l'analyse d'image et de maillages. Nous comparons notre distance d'éditionde cartes généralisées avec la distance d'édition de graphes, souvent utilisée en reconnaissancede formes structurelles. Nous définissons également un ensemble d'heuristiquesprenant en compte les étiquettes de cartes généralisées modélisant des images etdes maillages. Nous mettons en évidence l'aspect qualitatif de notre appariement, permettantde mettre en correspondance des zones de l'image et des points du maillages.

Les systèmes embarqués en temps réel, malgré leurs ressources limitées, évoluent très rapidement. Pour ces systèmes, il est impératif de garantir que les tâches ne manquent pas leurs échéances, mais aussi la bonne qualité des données transmises de tâche en tâche. Il est obligatoire de trouver des compromis entre les contraintes d'ordonnancement du système et celles appliquées aux données. Pour garantir ces propriétés, nous considérons le mécanisme sans attente. L'accès aux ressources partagées suit le principe d'un seul producteur, plusieurs lecteurs. Pour contenir toutes les particularités de communication apportées par le mécanisme de communication uORB, nous avons modélisé les interactions entre les tâches par un graphe biparti que nous avons appelé graphe de communication et qui est composé d'ensembles de messages dits de domaine. Pour améliorer la prévisibilité de la communication inter-tâches, nous étendons le modèle de Liu & Layland avec le paramètre état de communication utilisé pour contrôler les points d'écriture/lecture.Nous avons considéré deux types de contraintes de données : les contraintes locales de données et les contraintes globales de données. Pour vérifier les contraintes locales des données, nous nous appuyons sur le mécanisme de sous-échantillonnage destiné à vérifier les contraintes locales des données. En ce qui concerne les contraintes globales des données, nous avons introduit deux nouveaux mécanismes : le " dernier lecteur de marque" et le " mécanisme de défilement ou d'écrasement ". Ces 2 mécanismes sont en quelque sorte complémentaires. Le premier fonctionne au début du fuseau tandis que le second fonctionne à la fin du fuseau
Real-time embedded systems, despite their limited resources, are evolving very quickly. For such systems, it is not enough to ensure that all jobs do not miss their deadlines, it is also mandatory to ensure the good quality of the data being transmitted from tasks to tasks. Speaking of the data quality constraints, they are expressed by the maintenance of a set of properties that a data sample must exhibit to be considered as relevant. It is mandatory to find trade-offs between the system scheduling constraints and those applied to the data. To ensure such properties, we consider the wait-free mechanism. The size of each communication buffer is based on the lifetime bound method. Access to the shared resources follows the single writer, many readers. To contain all the communication particularities brought by the uORB communication mechanism we modeled the interactions between the tasks by a bipartite graph that we called communication graph which is comprised of sets of so-called domain messages. To enhance the predictability of inter-task communication, we extend Liu and Layland model with the parameter communication state used to control writing/reading points.We considered two types of data constraints: data local constraints and data global constraints. To verify the data local constraints, we rely on the sub-sampling mechanism meant to verify data local constraints. Regarding the data global constraints, we introduced two new mechanism: the last reader tags mechanism and the scroll or overwrite mechanism. These 2 mechanisms are to some extent complementary. The first one works at the beginning of the spindle while the second one works at the end of the spindle

Dans cette thèse, qui s'inscrit dans l'étude de la modélisation géométrique via les méthodes formelles, nous proposons un langage graphique à base de règles dédié à la description des opérations topologiques des cartes généralisées. Notre langage est fondé sur la théorie des transformations de graphes. Dans nos règles, les variables permettent d'abstraire les cellules topologiques (sommets, arêtes, faces, volumes, etc.) manipulées dans les opérations topologiques. Nous avons défini des critères syntaxiques sur les règles assurant que les objets obtenus par application des règles satisfont les contraintes de cohé- rence des cartes généralisées. La conception de ce langage a été motivée par l'étude de la dynamique de l'appareil de Golgi. Il est connu que dans cette organelle, la topologie des compartiments joue un rôle essentiel. Néanmoins, la structure globale de l'appareil de Golgi reste encore méconnue. Plusieurs hypothèses de fonctionnement sont ainsi avancées par les biologistes. Notre langage à base de règles fournit un cadre pour la simulation puis la comparaison de ces différentes hypothèses d'appareil de Golgi.

Réaliser des variations d'un même modèle est un besoin en expansion dans de nombreux domaines de modélisation (architecture, archéologie, CAO, etc.). Mais la production manuelle de ces variations est fastidieuse, il faut donc faire appel à des techniques permettant de rejouer automatiquement tout ou partie du processus de construction du modèle, après spécification des modifications. La majorité des approches dédiées à la réalisation du rejeu sont basées sur un système de modélisation paramétrique, composée d’un modèle géométrique et d’une spécification paramétrique permettant d’enregistrer la succession d’opérations l’ayant créé ainsi que leurs paramètres. On peut ensuite faire varier ces paramètres ou éditer cette liste d’opérations afin de modifier le modèle. On utilise pour cela un système de nommage persistant, introduit dans les années 90, et permettant d’identifier et d’apparier les entités d’une spécification initiale et celles d'une spécification rejouée. L’objectif de cette thèse est de proposer un système de nommage persistant général, homogène et permettant de gérer l’édition de spécification paramétriques (déplacer, ajouter et supprimer des opérations). Nous nous basons sur la bibliothèque Jerboa, qui repose sur des règles de transformation de graphes, tant pour utiliser ces règles dans la réalisation de la méthode de nommage que pour lier les notions de spécification paramétrique à ces règles de transformations de graphes. Nous décrivons ensuite comment exploiter notre méthode de nommage pour rejouer et éditer des spécifications paramétriques d’opérations, puis nous la comparons avec les approches de la littérature
In many modelling fields, such as architecture, archaeology or CAD, performing many variations of the same model is an expanding need. But building all those variations manually takes time. It is therefore needed to use automatic technics to revaluate some parts of a model, or even an entire model, after the user specifies the modifications. Most of the existing approaches dedicated to revaluating models are based on a system called parametric modelling. It is made of two parts, a geometric model and a parametric specification, which allows to record the series of operation that created the model, and the different parameters of those operations. This way, the user can change some parameters, or edit the list of operations to modify the model. To do so, we use a system called persistent naming, introduced during the 90ies, that allows us to identify and match the entities of an initial specification and the ones of a revaluated specification. In this thesis, our goal is to propose a persistent naming system that would be general, homogeneous and that would allow the user to edit a parametric specification (which means move, add, or delete some operations). We base our system on the Jerboa library, which uses graph transformation rules. This way, we will be able to use those rules to create our naming system, while also linking the notions of graph transformation rules and parametric specification. We will then describe how to use our naming method to revaluate or edit parametric specifications. Finally, we will compare our method with the other ones from the literature

Les cônes généralisés (CG), introduits pour la première fois au début des années 1970, sont largement utilisés en C.A.O, en C.F.A.O et dans les domaines de l'imagerie médicale, de la robotique et de la reconnaissance de formes. Un CG est représenté, grosso-modo, par l'espace balayé par le déplacement d'une section le long d'une trajectoire. Dans ce mémoire, des méthodes de construction permettant d'obtenir des objets 3D à l'aide de ces CG sont décrites. Plus particulièrement, l'introduction de paramètres défmis par l'utilisateur (profils, orientations et déformations de la section) et représentés sous forme de fonctions, permet d'élargir la famille des objets créés par extrusion. Un cadre formel a été défini pour les fonctions défmissant les CG, afin d'assurer le plus possible la validité des résultats. Toujours dans le souci d'assurer la validité des objets créés, il a été développé des algorithmes simples et pratiques contrôlant, pendant la construction, les problèmes de recouvrement. A 1' écart des formulations mathématiques traditionnelles des CG, il est présenté une technique permettant de défmir les CG à l'aide des quaternions. Cela donne la possibilité d'inclure les paramètres de déformation de la section dans un même cadre mathématique. Dans la deuxième partie de ce mémoire, sont présentées des méthodes permettant de construire des cônes généralisés ramifiés. La notion de trajectoire arborescente est introduite, ainsi que des méthodes systématiques défmissant les parties tubulaires sur lesquelles s'appuiera l'embranchement G1 continu. La réalisation de cet embranchement nécessite l'utilisation de la théorie des raccords de surfaces dès lors que l'on représente les CG avec des surfaces de formes libres. Ainsi, les principales techniques de raccords G1 continus entre facettes rectangulaires et triangulaires de Béziers sont rappelées et étendues aux facettes B-splines. Une étude complète sur les contraintes portant sur les fonctions de raccordement est aussi présentée. Afin de valider les techniques précédentes dans un cadre précis, une discussion sur les problèmes de C et G continuité est proposée. Son but est de définir un mode de dérivation qui permet d'inclure l'ensemble des fonctions G-continues dans l'ensemble des fonctions C-continues.

Dans un espace discret, comme l'ensemble des points à coordonnées entières, la modélisation de l'isotropie pose des difficultés théoriques notables. À ce jour, aucune théorie géométrique sur $\ZZ^n$ n'est apte à rendre compte de l'isotropie telle qu'elle est décrite par la géométrie euclidienne. Dans l'optique de contribuer à cette problématique, nous nous intéressons à la conception d'algorithmes capables de donner aux rotations discrètes des propriétés proches de celles de la rotation euclidienne. Ces algorithmes doivent de plus fonctionner à base d'arithmétique entière. Après avoir montré la non-existence de rotation discrète transitive sur $\ZZ^n$, nous introduisons un codage de rotations discrètes que nous relions à la fois à la dynamique symbolique et aux automates cellulaires. Il s'agit alors de mener une étude locale des rotations discrètes. Cette étude se situe au carrefour entre géométrie discrète et systèmes dynamiques symboliques. La pertinence des configurations obtenues est justifiée par l'existence de transducteurs planaires capables d'effectuer des rotations à partir des configurations. Ensuite, afin de réinterpréter ces configurations dans le cadre de la théorie des systèmes dynamiques, nous étendons des notions classiques de cette théorie à la dimension 2. Pour la rotation discrétisée, la dynamique symbolique associée est conjuguée avec un jeu de deux translations orthogonales sur un tore bidimensionnel. Après analyse, nous constatons que les configurations obtenues sont des superpositions de configurations de faible complexité. Cela évoque alors les généralisations planaires des mots sturmiens étudiées entre autres par Valérie Berthé et Laurent Vuillon. Des résultats analogues sont aussi obtenus pour les rotations $3$-transvections. L'analyse les rotations discrètes par le biais de systèmes dynamiques a permis de nombreux résultats : mise en évidence de la quasipériodicité des configurations, calcul de la fréquence des symboles, caractérisation des rotations discrétisées bijectives, ce qui est aussi la réciproque du théorème d'Éric Andrès et Marie-Andrée Jacob. Nous avons aussi étudié les discontinuités du processus de rotation. Ces discontinuités ont lieu pour des angles issus d'un sous-ensemble des angles quadratiques (i.e. les angles charnières). En combinant ces remarques, nous aboutissons à deux algorithmes. Le premier algorithme réalise des rotations sans faire aucun calcul à virgule flottante et sans calculer aucun sinus ni aucun cosinus. Il fonctionne de manière incrémentale et en ordre de complexité optimal. Le second algorithme est une implémentation de la rotation $3$-transvections sur automates cellulaires. D'autres pistes pour la conception d'algorithmes sont mentionnées dans la thèse. En outre, nous nous intéressons aussi aux méthodes substitutives qui engendrent les configurations de rotations. Pour les angles quadratiques, nous montrons que les configurations de rotations sont des entrelacements de configurations autosimilaires; et nous présentons le schéma d'une approche basée sur les graphes de Rauzy pour l'inférence de substitutions planaires. En combinant ces deux approches, nous mettons en avant les éléments essentiels de la démonstration de l'autosimilarité de $C_{\pi/4}$. Les applications potentielles de cette thèse concernent à terme l'implémentation d'algorithmes de rotations pour processeurs graphiques. Elle contribue aussi à l'étude des méthodes algorithmiques pour la modélisation physique en milieu discret de phénomènes isotropes.

Le problème du dimensionnement des mémoires pour systèmes embarqués consiste à définir la taille à allouer pour chaque mémoire tel que la surface globale occupée par ces mémoires soit minimale et que le système embarqué puissent fonctionner sans bloquage lié à un sous dimensionnement de ces mémoires. Nous modélisons ce problème d'optimisation en utilisant le modèle des graphes d'événements généralisés (GEG en abrégé). Nous montrons que ce problème d'optimisation est étroitement lié au problème de vivacité d'un GEG. Nous proposons une transformation des GEG, appelée normalisation, permettant de définir une condition suffisante de vivacité ainsi qu'un algorithme polynomial pour tester cette condition sur des GEG quelconques. Nous proposons des résultats nouveaux de complexité pour des problèmes d'optimisation bi-critères (ie. Surface globale / débit du système). Nous développons un algorithme polynomial 2-approché pour la résolution du problème bi-critère du débit maximum intrinsèque.

Cette thèse porte sur le développement facilité d'applications de cartographie et de transport, plus particulièrement sur la génération de réseaux piétonniers pour des applications telles que la navigation, le calcul d'itinéraires, l'analyse d'accessibilité et l'urbanisme. Afin d'atteindre ce but, nous proposons un modèle de données à deux couches qui cartographie l'espace public dans une hiérarchie d'objets géospatiaux sémantisés. A bas niveau, la géométrie 2D des objets géospatiaux est représentée par une partition planaire, modélisée par une structure topologique d'arrangement 2D. Cette représentation permet des traitements géométriques efficaces et efficients, ainsi qu'une maintenance et une validation aisée au fur et à mesure des éditions lorsque la géométrie ou la topologie d'un objet sont modifiées. A haut niveau, les aspects sémantiques et thématiques des objets géospatiaux sont modélisés et gérés. La hiérarchie entre ces objets est maintenue à travers un graphe dirigé acyclique dans lequel les feuilles correspondent à des primitives géométriques de l'arrangement 2D et les noeuds de plus haut niveau représentent les objets géospatiaux sémantiques plus ou moins aggrégés. Nous avons intégré le modèle de données proposé dans un framework SIG nommé StreetMaker en complément d'un ensemble d'algorithmes génériques et de capacités SIG basiques. Ce framework est alors assez riche pour générer automatiquement des graphes de réseau piétonnier. En effet, dans le cadre d'un projet d'analyse d'accessibilité, le flux de traitement proposé a permis de produire avec succès sur deux sites un graphe de réseau piétonnier à partir de données en entrées variées : des cartes vectorielles existantes, des données vectorielles créées semi-automatiquement et des objets vectoriels extraits d'un nuage de points lidar issu d'une acquisition de cartographie mobile.Alors que la modélisation 2D de la surface du sol est suffisante pour les applications SIG 2D, les applications SIG 3D nécessitent des modèles 3D de l'environnement. La modélisation 3D est un sujet très large mais, dans un premier pas vers cette modélisation 3D, nous nous sommes concentrés sur la modélisation semi-automatique d'objets de type cylindre généralisé (tels que les poteaux, les lampadaires, les troncs d'arbre, etc) à partir d'une seule image. Les méthodes et techniques développées sont présentées et discutées
This thesis addresses easy and effective development of mapping and transportation applications which especially focuses on the generation of pedestrian networks for applications like navigation, itinerary calculation, accessibility analysis and urban planning. In order to achieve this goal, we proposed a two layered data model which encodes the public space into a hierarchy of semantic geospatial objects. At the lower level, the 2D geometry of the geospatial objects are captured using a planar partition which is represented as a topological 2D arrangement. This representation of a planar partition allows efficient and effective geometry processing and easy maintenance and validation throughout the editions when the geometry or topology of an object is modified. At the upper layer, the semantic and thematic aspects of geospatial objects are modelled and managed. The hierarchy between these objects is maintained using a directed acyclic graph (DAG) in which the leaf nodes correspond to the geometric primitives of the 2D arrangement and the higher level nodes represent the aggregated semantic geospatial objects at different levels. We integrated the proposed data model into our GIS framework called StreetMaker together with a set of generic algorithms and basic GIS capabilities. This framework is then rich enough to generate pedestrian network graphs automatically. In fact, within an accessibility analysis project, the full proposed pipeline was successfully used on two sites to produce pedestrian network graphs from various types of input data: existing GIS vector maps, semi-automatically created vector data and vector objects extracted from Mobile Mapping lidar point clouds.While modelling 2D ground surfaces may be sufficient for 2D GIS applications, 3D GIS applications require 3D models of the environment. 3D modelling is a very broad topic but as a first step to such 3D models, we focused on the semi-automatic modelling of objects which can be modelled or approximated by generalized cylinders (such as poles, lampposts, tree trunks, etc.) from single images. The developed methods and techniques are presented and discussed

L’échange d’informations entre périphériques variés et sur internet soulève de nombreux problèmes par le volume et l’hétéroclisme des données échangées. La plupart de ces échanges utilisent le format XML. Afin de les faciliter, des traitements intelligents, comme la classification et la transformation automatiques, ont été développés. Le but de cette thèse est double : proposer un framework d'apprentissage pour la classification de documents XML et étudier l'apprentissage de transformations de documents XML. Le choix d’utiliser la Programmation Logique Inductive a été fait. Même si les méthodes d'apprentissage ont alors un surcoût algorithmique non négligeable (certaines opérations deviennent NP-dures), la représentation relationnelle semble adaptée aux documents XML de par son expressivité. Notre framework pour la classification fait suite à l'étude de familles de clauses pour la représentation de structures arborescentes. Il repose sur une réécriture des opérations de base de la PLI que sont la theta-subsomption et le moindre généralisé [Plotkin1971]. Nos algorithmes sont polynomiaux en temps dans la taille de leur entrée là où ceux standards sont exponentiels. Ils permettent une identification à la limite [Gold1967] de nos familles de clauses. Notre seconde contribution débute par la modélisation d’une famille de clauses dans la lignée des programmes fonctionnels [Paulson91]. Ces clauses sont une adaptation à la PLI des scripts d'édition et prennent en compte un contexte. Elles permettent la représentation de transformations de documents XML. Leurs apprentissages sont possibles grâce à deux algorithmes de type A*, approche courante en PLI (HOC-Learner [Santos2009])
The recent proliferation of XML documents in databases and web applications rises some issues due to the numerous data exchanged and their diversity. To ease their uses, some smart means have been developed such as automatic classification and transformation. This thesis has two goals:• To propose a framework for the XML documents classification task.• To study the XML documents transformation learning.We have chosen to use Inductive Logic Programming. The expressiveness of logic programs grants flexibility in specifying the learning task and understandability to the induced theories. This flexibility implies a high computational cost, constraining the applicability of ILP systems. However, XML documents being trees, a good concession can be found.For our first contribution, we define clauses languages that allow encoding xml trees. The definition of our classification framework follows their studies. It stands on a rewriting of the standard ILP operations such as theta-subsumption and least general generalization [Plotkin1971]. Our algorithms are polynomials in time in the input size whereas the standard ones are exponentials. They grant an identification in the limit [Gold1967] of our languages.Our second contribution is the building of methods to learn XML documents transformations. It begins by the definition of a clauses class in the way of functional programs [Paulson91]. They are an ILP adaptation of edit scripts and allow a context. Their learning is possible thanks to two A*-like algorithms, a common ILP approach (HOC-Learner [Santos2009])

Le contrôle des processus de désassemblage fait référence aux méthodes et aux techniques utilisées pour démonter de manière sûre et efficace des composants mécaniques ou des ensembles complexes. Pour ce faire, des approches de commandes des contrôles sont développés pour satisfaire les contraintes imposées à ces systèmes. Plus précisément, dans cette thèse nous nous s'intéressons à trois types de spécifications : les contraintes marquages, les Contraintes de Marquage Généralisées (CMGs), et les Contraintes d'Exclusions Mutuelles (CEMs).Pour cela, nous avons proposé trois méthodes analytiques. La première contribution concerne une nouvelle technique de conception de lois de commande pour les systèmes de désassemblages afin d'assurer la satisfaction des contraintes de marquage dans des Graphes d'Evénements Temporisés (GETs) avec certaines transitions d'entrée incontrôlables. La deuxième technique met l'accent sur la synthèse des contrôleurs tout en assurant des CMGs spécifiées par des inégalités pondérées dans l'algèbre Min-Plus soumis à des GETs. La dernière approche vise à piloter les processus de désassemblages modélisés par des Réseaux de Graphes d'Evénements Temporisés (RGETs) imposés à des CEMs.En alternative, il convient de noter que ces approches se basent sur les structures conceptuelles des Systèmes à Evénements Discrets (SEDs) ainsi que sur l'algèbre Min-Plus. Ces outils offrent la capacité de représenter de façon exacte et méthodique les systèmes de manufacturier. Par conséquent, la problématique se trouve formulée en utilisant des modèles linéaires de contrôle basés sur l'algèbre Min-Plus. En fait, le comportement de ces graphes est décrite en utilisant des équations Min-Plus linéaires, et les contraintes sont exprimées par des inégalités ou des inégalités pondérées dans l'algèbre Min-Plus.Des conditions suffisantes pour l'existence des lois de commande causales sont établies. Ces contrôleurs développés sont des retours d'états qui peuvent être symbolisés par des places de surveillance empêchant le système de toute violation de contrainte. Le graphe est vivant et sans blocage
Disassembly process control involves the methods and techniques used to safely and efficiently disassemble mechanical components or complex assemblies. To do this, control approaches are developed to satisfy the constraints imposed on these systems. More specifically, in this thesis we are interested in three types of specifications: marking constraints, Generalized Marking Constraints (GMCs), and Mutual Exclusion Constraints (MECs).To this aim, we have proposed three analytical methods. The first contribution concerns a new technique for designing control laws for disassembly systems to ensure the satisfaction of marking constraints in Timed Event Graphs (TEGs) with some uncontrollable input transitions. The second technique focuses on controller synthesis while ensuring GMCs specified by weighted inequalities in the Min-Plus algebra subject to GETs. The final method aims to control disassembly processes modelled by Timed Event Graph Networks (NGETs) imposed on MECs.Alternatively, it is worth noting that these approaches are based on the conceptual structures of Discrete Event Systems (DES) and the Min-Plus algebra. These tools offer the ability to represent manufacturing systems accurately and methodically. Consequently, the problem is formulated using linear control models based on Min-Plus algebra. In fact, the behaviour of these graphs is described using linear Min-Plus equations, and constraints are expressed by inequalities or weighted inequalities in the Min-Plus algebra.Sufficient conditions for the existence of causal control laws are established. These developed controllers are state feedbacks that can be represented by monitoring places preventing the system from any constraint violation. The graph is alive and unblocked

Nous étudions des problèmes statistiques classiques, tels que la détection de communautés dans un graphe, l’analyse en composantes principales, les modèles de mélanges Gaussiens, les modèles linéaires (généralisés ou non), dans un cadre Bayésien. Nous calculons pour ces problèmes le “risque de Bayes” qui est la plus petite erreur atteignable par une méthode statistique, dans la limite de grande dimension. Nous observons alors un phénomène surprenant : dans de nombreux cas il existe une valeur critique de l’intensité du bruit au-delà de laquelle il n’est plus possible d’extraire de l’information des données. En dessous de ce seuil, nous comparons la performance d’algorithmes polynomiaux à celle optimale. Dans de nombreuses situations nous observons un écart : bien qu’il soit possible – en théorie – d’estimer le signal, aucune méthode algorithmiquement efficace ne parvient à être optimale. Dans ce manuscrit, nous adoptons une approche issue de la physique statistique qui explique ces phénomènes en termes de transitions de phase. Les méthodes et outils que nous utilisons proviennent donc de la physique, plus précisément de l’étude mathématique des verres de spins
We study classical statistical problems such as community detection on graphs, Principal Component Analysis (PCA), sparse PCA, Gaussian mixture clustering, linear and generalized linear models, in a Bayesian framework. We compute the best estimation performance (often denoted as “Bayes Risk”) achievable by any statistical method in the high dimensional regime. This allows to observe surprising phenomena: for many problems, there exists a critical noise level above which it is impossible to estimate better than random guessing. Below this threshold, we compare the performance of existing polynomial-time algorithms to the optimal one and observe a gap in many situations: even if non-trivial estimation is theoretically possible, computationally efficient methods do not manage to achieve optimality. From a statistical physics point of view that we adopt throughout this manuscript, these phenomena can be explained by phase transitions. The tools and methods of this thesis are therefore mainly issued from statistical physics, more precisely from the mathematical study of spin glasses

Ce travail présente un système de localisation d'objets solides 3D dans une image optique par prédiction/vérification. Les traitements préalables sont la description des objets, ici représentés par une structure C. S. G. Par listes et la calibration de la caméra. La prédiction utilise ces informations, ainsi que les matrices de position pour construire une image des régions. Ces matrices proviennent soit d'informations issues d'un contrôleur de robot, soit d'une génération d'hypothèses. La prédiction utilise des modules de projection de formes primitives telles que les polyhèdres, les ellipsoïdes et les cônes généralisés. La prise en compte de formes plus complexes se fait à l'aide de graphes d'occlusion. La vérification effectue un test de superposition entre les régions prédites d'une part et les régions obtenues après des traitements effectués sur des images acquises d'autre part.

Cette thèse a pour première vocation d'être un état de l'art sur le calcul quantique, sinon exhaustif, simple d'accès (chapitres 1, 2 et 3). La partie originale de cet essai consiste en deux approches mathématiques du calcul quantique concernant quelques systèmes quantiques : la première est de nature algébrique et fait intervenir des structures particulières : les corps et les anneaux de Galois (chapitre 4), la deuxième fait appel à la géométrie dite projective (chapitre 5). Cette étude a été motivée par le théorème de Kochen et Specker et par les travaux de Peres et Mermin qui en ont découlé

Nous nous intéressons au problème de la reconstruction tridimensionnelle d'objets complexes à partir de coupes sériées. Le premier chapitre du mémoire s'attache à montrer l'intérêt de mettre à la disposition de la modélisation géologique 3D un ensemble d'outils variés et notamment des méthodes d'interpolation et de reconstruction adaptées. Le second chapitre pose la problématique générale de la reconstruction 3D et propose un état de l'art sur les méthodes existantes. Ces deux chapitres composent la première partie du manuscrit. Dans la deuxième partie du mémoire nous proposons une nouvelle méthode de reconstruction 3D qui permet de traiter de manière simple et automatique l'ensemble des problèmes de topologie (trous, branchements multiples, contours isolés). Elle s'appuie sur la construction adaptative de coupes intermédiaires par interpolation entre les sections initiales (chapitre 3). Ce processus utilise un diagramme de Voronoï généralisé simplifié, le réseau bissecteur, comme outil d'interpolation 2D. Nous fournissons une description géométrique complète du réseau bissecteur 2D et nous montrons que sa complexité algébrique est la même que celle des éléments qui permettent de le calculer (segments en 2D, portions de plans en 3D). Nous proposons ensuite deux algorithmes de construction des réseaux bissecteurs interne et externe de formes polygonales éventuellement trouées, dont la complexité en temps est respectivement en O(n2 log n) et O(n2), et la mémoire en O(n2) et O(n) respectivement (chapitre 4). La mise en correspondance des contours est abordée dans le chapitre 5 et nous suggérons quelques solutions pour traiter certains problèmes délicats. La construction du réseau bissecteur permet ensuite d'obte~ir une surface valide de l'objet en guidant de manière directe la triangulation entre les points des différentes sections. Il n'y a donc pas besoin de post-traitements. De plus, l'ajout automatique de portions de coupes intermédiaires dans les zones de changements de topologie ou de variations de morphologie permet une meilleure définition des surfaces générées (chapitre 6). Dans la dernière partie du mémoire nous discutons les résultats obtenus et nous les comparons avec ceux de deux méthodes existantes (chapitre 7).

Cette thèse se concentre sur certains sujets en génétique des populations. Dans la première partie, nous donnons des formules y compris l'espérance et la variance de la hauteur et celles de la longueur du graphe de recombinaison ancestral (ARG) et l'espérance et la variance du nombre de recombinaison et nous montrons que l'espérance de la longueur de l'ARG est une combinaison linéaire de l'espérance de la longueur de la coalescence de Kingman et l'espérance de la hauteur de l'ARG. En outre, nous avons obtenu une relation entre l'espérance la longueur de l'ARG et l'espérance du nombre de recombinaisons. À la fin de cette partie, nous montrons que l'ARG descend de l'infini de telle sorte que X_0 =∞, alors que X_t < ∞ ; pour tout t et on trouve la vitesse à laquelle l'ARG descend de l'infini. Dans la deuxième partie on généralise la formule d'échantillonnage d'Ewens (GESF) en présence de la recombinaison pour les échantillons de taille n = 2 et n = 3. Dans la troisième partie de la thèse, nous étudions l'ARG le long du génome et nous avons trouvé la distribution du nombre de mutations dans le cas avec une seule recombinaison dans la généalogie de l'échantillon
This thesis is concentrated on some sub jects on population genetics. In the first part we give formulae including the expectation and variance of the height and the length of the ancestral recombination graph (ARG) and the expectation and variance of the number of recombination events and we show that the expectation of the length of the ARG is a linear combination of the expectation of the length of Kingman's coalescent and the expectation of the height of the ARG. Also we show give a relation between the expectation of the ARG and the expectation of the number of recombination events. At the end of this part we show that the ARG comes down from infinity in the sense that we can dfine it with X_0 = ∞, while X_t <∞ ; for all t and we find the speed that the ARG comes down from infinity. In the second part wfind a generalization of the the Ewens sampling formula (GESF) in the presence of recombination for sample of sizes n = 2 and n = 3. In the third part of the thesis we study the ARG along the genome and we we find the distribution of the number of mutations when we have one recombination event in the genealogy of the sample

Cette thèse a pour première vocation d’être un état de l’art sur le calcul quantique, sinon exhaustif, simple d’accès (chapitres 1, 2 et 3). La partie originale de cet essai consiste en deux approches mathématiques du calcul quantique concernant quelques systèmes quantiques : la première est de nature algébrique et fait intervenir des structures particulières : les corps et les anneaux de Galois (chapitre 4), la deuxième fait appel à la géométrie dite projective (chapitre 5). Cette étude a été motivée par le théorème de Kochen et Specker et par les travaux de Peres et Mermin qui en ont découlé
The first vocation of this thesis would be a state of the art on the field of quantum computation, if not exhaustive, simple access (chapters 1, 2 and 3). The original (interesting) part of this treatise consists of two mathematical approaches of quantum computation concerning some quantum systems : the first one is an algebraic nature and utilizes some particular structures : Galois fields and rings (chapter 4), the second one calls to a peculiar geometry, known as projective one (chapter 5). These two approaches were motivated by the theorem of Kochen and Specker and by work of Peres and Mermin which rose from it

La neuroimagerie est confrontée à des difficultés pour analyser et réutiliser la masse croissante de données hétérogènes qu’elle produit. La provenance des données est complexe – multi-sujets, multi-analyses, multi-temporalités – et ces données ne sont stockées que partiellement, limitant les possibilités d’études multimodales et longitudinales. En particulier, la connectivité fonctionnelle cérébrale est analysée pour comprendre comment les différentes zones du cerveau travaillent ensemble. Il est nécessaire de gérer les données acquises et traitées suivant plusieurs dimensions, telles que le temps d’acquisition, le temps entre les acquisitions ou encore les sujets et leurs caractéristiques. Cette thèse a pour objectif de permettre l’exploration de relations complexes entre données hétérogènes, ce qui se décline selon deux axes : (1) comment gérer les données et leur provenance, (2) comment visualiser les structures de données multidimensionnelles. L’apport de nos travaux s’articule autour de trois propositions qui sont présentées à l’issue d’un état de l’art sur les domaines de la gestion de données hétérogènes et de la visualisation de graphes. Le modèle de données BMI-LM (Bio-Medical Imaging – Lifecycle Management) structure la gestion des données de neuroimagerie en fonction des étapes d’une étude et prend en compte le caractère évolutif de la recherche grâce à l’association de classes spécifiques à des objets génériques. L’implémentation de ce modèle au sein d’un système PLM (Product Lifecycle Management) montre que les concepts développés depuis vingt ans par l’industrie manufacturière peuvent être réutilisés pour la gestion des données en neuroimagerie. Les GMD (Graphes Multidimensionnels Dynamiques) sont introduits pour représenter des relations complexes entre données qui évoluent suivant plusieurs dimensions, et le format JGEX (Json Graph EXchange) a été créé pour permettre le stockage et l’échange de GMD entre applications. La méthode OCL (Overview Constraint Layout) permet l’exploration visuelle et interactive de GMD. Elle repose sur la préservation partielle de la carte mentale de l’utilisateur et l’alternance de vues complètes et réduites des données. La méthode OCL est appliquée à l’étude de la connectivité fonctionnelle cérébrale au repos de 231 sujets représentées sous forme de GMD – les zones du cerveau sont représentées par les nœuds et les mesures de connectivité par les arêtes – en fonction de l’âge, du genre et de la latéralité : les GMD sont obtenus par l’application de chaînes de traitement sur des acquisitions IRM dans le système PLM. Les résultats montrent deux intérêts principaux à l’utilisation de la méthode OCL : (1) l’identification des tendances globales sur une ou plusieurs dimensions et (2) la mise en exergue des changements locaux entre états du GMD
Neuroimaging domain is confronted with issues in analyzing and reusing the growing amount of heterogeneous data produced. Data provenance is complex – multi-subjects, multi-methods, multi-temporalities – and the data are only partially stored, restricting multimodal and longitudinal studies. Especially, functional brain connectivity is studied to understand how areas of the brain work together. Raw and derived imaging data must be properly managed according to several dimensions, such as acquisition time, time between two acquisitions or subjects and their characteristics. The objective of the thesis is to allow exploration of complex relationships between heterogeneous data, which is resolved in two parts : (1) how to manage data and provenance, (2) how to visualize structures of multidimensional data. The contribution follow a logical sequence of three propositions which are presented after a research survey in heterogeneous data management and graph visualization. The BMI-LM (Bio-Medical Imaging – Lifecycle Management) data model organizes the management of neuroimaging data according to the phases of a study and takes into account the scalability of research thanks to specific classes associated to generic objects. The application of this model into a PLM (Product Lifecycle Management) system shows that concepts developed twenty years ago for manufacturing industry can be reused to manage neuroimaging data. GMDs (Dynamic Multidimensional Graphs) are introduced to represent complex dynamic relationships of data, as well as JGEX (Json Graph EXchange) format that was created to store and exchange GMDs between software applications. OCL (Overview Constraint Layout) method allows interactive and visual exploration of GMDs. It is based on user’s mental map preservation and alternating of complete and reduced views of data. OCL method is applied to the study of functional brain connectivity at rest of 231 subjects that are represented by a GMD – the areas of the brain are the nodes and connectivity measures the edges – according to age, gender and laterality : GMDs are computed through processing workflow on MRI acquisitions into the PLM system. Results show two main benefits of using OCL method : (1) identification of global trends on one or many dimensions, and (2) highlights of local changes between GMD states

La problématique de cette thèse se place à l’interface entre le domaine scientifique du contrôle non destructif par ultrasons (CND US) et l’adéquation algorithme architecture. Le CND US comprend un ensemble de techniques utilisées pour examiner un matériau, qu’il soit en production ou maintenance. Afin de détecter d’éventuels défauts, de les positionner et les dimensionner, des méthodes d’imagerie et de reconstruction ont été développées au CEA-LIST, dans la plateforme logicielle CIVA.L’évolution du matériel d’acquisition entraine une augmentation des volumes de données et par conséquent nécessite toujours plus de puissance de calcul pour parvenir à des reconstructions en temps interactif. L’évolution multicoeurs des processeurs généralistes (GPP), ainsi que l’arrivée de nouvelles architectures comme les GPU rendent maintenant possible l’accélération de ces algorithmes.Le but de cette thèse est d’évaluer les possibilités d’accélération de deux algorithmes de reconstruction sur ces architectures. Ces deux algorithmes diffèrent dans leurs possibilités de parallélisation. Pour un premier, la parallélisation sur GPP est relativement immédiate, contrairement à celle sur GPU qui nécessite une utilisation intensive des instructions atomiques. Quant au second, le parallélisme est plus simple à exprimer, mais l’ordonnancement des nids de boucles sur GPP, ainsi que l’ordonnancement des threads et une bonne utilisation de la mémoire partagée des GPU sont nécessaires pour obtenir un fonctionnement efficace. Pour ce faire, OpenMP, CUDA et OpenCL ont été utilisés et comparés. L’intégration de ces prototypes dans la plateforme CIVA a mis en évidence un ensemble de problématiques liées à la maintenance et à la pérennisation de codes sur le long terme
This thesis work is placed between the scientific domain of ultrasound non-destructive testing and algorithm-architecture adequation. Ultrasound non-destructive testing includes a group of analysis techniques used in science and industry to evaluate the properties of a material, component, or system without causing damage. In order to characterize possible defects, determining their position, size and shape, imaging and reconstruction tools have been developed at CEA-LIST, within the CIVA software platform.Evolution of acquisition sensors implies a continuous growth of datasets and consequently more and more computing power is needed to maintain interactive reconstructions. General purprose processors (GPP) evolving towards parallelism and emerging architectures such as GPU allow large acceleration possibilities than can be applied to these algorithms.The main goal of the thesis is to evaluate the acceleration than can be obtained for two reconstruction algorithms on these architectures. These two algorithms differ in their parallelization scheme. The first one can be properly parallelized on GPP whereas on GPU, an intensive use of atomic instructions is required. Within the second algorithm, parallelism is easier to express, but loop ordering on GPP, as well as thread scheduling and a good use of shared memory on GPU are necessary in order to obtain efficient results. Different API or libraries, such as OpenMP, CUDA and OpenCL are evaluated through chosen benchmarks. An integration of both algorithms in the CIVA software platform is proposed and different issues related to code maintenance and durability are discussed

La simulation est de plus en plus utilisée dans le domaine industriel du Contrôle Non Destructif. Elle est employée tout au long du processus de contrôle, que ce soit pour en accélérer la mise au point ou en comprendre les résultats. Les travaux menés au cours de cette thèse présentent une méthode de calcul rapide de champ ultrasonore rayonné par un capteur multi-éléments dans une pièce isotrope, permettant un usage interactif des simulations. Afin de tirer parti des architectures parallèles communément disponibles, un modèle régulier (qui limite au maximum les branchements divergents) dérivé du modèle générique présent dans la plateforme logicielle CIVA a été mis au point. Une première implémentation de référence a permis de le valider par rapport aux résultats CIVA et d'analyser son comportement en termes de performances. Le code a ensuite été porté et optimisé sur trois classes d'architectures parallèles aujourd'hui disponibles dans les stations de calcul : le processeur généraliste central (GPP), le coprocesseur manycore (Intel MIC) et la carte graphique (nVidia GPU). Concernant le processeur généraliste et le coprocesseur manycore, l'algorithme a été réorganisé et le code implémenté afin de tirer parti des deux niveaux de parallélisme disponibles, le multithreading et les instructions vectorielles. Sur la carte graphique, les différentes étapes de simulation de champ ont été découpées en une série de noyaux CUDA. Enfin, des bibliothèques de calculs spécifiques à ces architectures, Intel MKL et nVidia cuFFT, ont été utilisées pour effectuer les opérations de Transformées de Fourier Rapides. Les performances et la bonne adéquation des codes produits ont été analysées en détail pour chaque architecture. Dans plusieurs cas, sur des configurations de contrôle réalistes, des performances autorisant l'interactivité ont été atteintes. Des perspectives pour traiter des configurations plus complexes sont dressées. Enfin la problématique de l'industrialisation de ce type de code dans la plateforme logicielle CIVA est étudiée
The Non Destructive Testing field increasingly uses simulation.It is used at every step of the whole control process of an industrial part, from speeding up control development to helping experts understand results. During this thesis, a simulation tool dedicated to the fast computation of an ultrasonic field radiated by a phase array probe in an isotropic specimen has been developped. Its performance enables an interactive usage. To benefit from the commonly available parallel architectures, a regular model (aimed at removing divergent branching) derived from the generic CIVA model has been developped. First, a reference implementation was developped to validate this model against CIVA results, and to analyze its performance behaviour before optimization. The resulting code has been optimized for three kinds of parallel architectures commonly available in workstations: general purpose processors (GPP), manycore coprocessors (Intel MIC) and graphics processing units (nVidia GPU). On the GPP and the MIC, the algorithm was reorganized and implemented to benefit from both parallelism levels, multhreading and vector instructions. On the GPU, the multiple steps of field computing have been divided in multiple successive CUDA kernels.Moreover, libraries dedicated to each architecture were used to speedup Fast Fourier Transforms, Intel MKL on GPP and MIC and nVidia cuFFT on GPU. Performance and hardware adequation of the produced algorithms were thoroughly studied for each architecture. On multiple realistic control configurations, interactive performance was reached. Perspectives to adress more complex configurations were drawn. Finally, the integration and the industrialization of this code in the commercial NDT plateform CIVA is discussed

Réaliser des variations d'un même modèle est un besoin en expansion dans de nombreux domaines de modélisation (architecture, archéologie, CAO, etc.). Mais la production manuelle de ces variations est fastidieuse, il faut donc faire appel à des techniques permettant de rejouer automatiquement tout ou partie du processus de construction du modèle, après spécification des modifications. La majorité des approches dédiées à la réalisation du rejeu sont basées sur un système de modélisation paramétrique, composée d’un modèle géométrique et d’une spécification paramétrique permettant d’enregistrer la succession d’opérations l’ayant créé ainsi que leurs paramètres. On peut ensuite faire varier ces paramètres ou éditer cette liste d’opérations afin de modifier le modèle. On utilise pour cela un système de nommage persistant, introduit dans les années 90, et permettant d’identifier et d’apparier les entités d’une spécification initiale et celles d'une spécification rejouée. L’objectif de cette thèse est de proposer un système de nommage persistant général, homogène et permettant de gérer l’édition de spécification paramétriques (déplacer, ajouter et supprimer des opérations). Nous nous basons sur la bibliothèque Jerboa, qui repose sur des règles de transformation de graphes, tant pour utiliser ces règles dans la réalisation de la méthode de nommage que pour lier les notions de spécification paramétrique à ces règles de transformations de graphes. Nous décrivons ensuite comment exploiter notre méthode de nommage pour rejouer et éditer des spécifications paramétriques d’opérations, puis nous la comparons avec les approches de la littérature
In many modelling fields, such as architecture, archaeology or CAD, performing many variations of the same model is an expanding need. But building all those variations manually takes time. It is therefore needed to use automatic technics to revaluate some parts of a model, or even an entire model, after the user specifies the modifications. Most of the existing approaches dedicated to revaluating models are based on a system called parametric modelling. It is made of two parts, a geometric model and a parametric specification, which allows to record the series of operation that created the model, and the different parameters of those operations. This way, the user can change some parameters, or edit the list of operations to modify the model. To do so, we use a system called persistent naming, introduced during the 90ies, that allows us to identify and match the entities of an initial specification and the ones of a revaluated specification. In this thesis, our goal is to propose a persistent naming system that would be general, homogeneous and that would allow the user to edit a parametric specification (which means move, add, or delete some operations). We base our system on the Jerboa library, which uses graph transformation rules. This way, we will be able to use those rules to create our naming system, while also linking the notions of graph transformation rules and parametric specification. We will then describe how to use our naming method to revaluate or edit parametric specifications. Finally, we will compare our method with the other ones from the literature

La majorité des courbes et surfaces rencontrées dans la modélisation géométrique sont définies comme l'ensemble des solutions d'un système d'équations et d'inéquations algébriques (ensemble semi-algébrique). De nombreux problèmes dans différentes disciplines scientifiques font appel à des requètes de proximité telles que la recherche du ou des voisins les plus proches ou la quantification du voisinage de deux objets.

Le diagramme de Voronoï d'un ensemble d'objets est une décomposition de l'espace en zones de proximité. La zone de proximité d'un objet est l'ensemble des points plus proches de cet objet que de tout autre objet. Les diagrammes de Voronoï permettent de répondre aux requètes de proximité après avoir identifié la zone de proximité à laquelle le point objet de la requète appartient. Le graphe dual du diagramme de Voronoï est appelé le graphe de Delaunay. Seules les approximations par des coniques peuvent garantir un ordre de continuité approprié au niveau des points de contact, ce qui est nécessaire pour garantir l'exactitude du graphe de Delaunay.

L'objectif théorique de cette thèse est la mise en évidence des propriétés algébriques et géométriques élémentaires de la courbe déplacée d'une courbe algébrique et de réduire le calcul semi-algébrique du graphe de Delaunay à des calculs de valeurs propres. L'objectif pratique de cette thèse est le calcul certifié du graphe de Delaunay pour des ensembles semi-algébriques de faible degré dans le plan euclidien.

La méthodologie associe l'analyse par intervalles et la géométrie algébrique algorithmique. L'idée centrale de cette thèse est qu'un pré-traitement symbolique unique peut accélérer l'évaluation numérique certifiée du détecteur de conflits dans le graphe de Delaunay. Le pré-traitement symbolique est le calcul de l'équation implicite de la courbe déplacée généralisée d'une conique. La réduction du problème semi-algébrique de la détection de conflits dans le graphe de Delaunay à un problème d'algèbre linéaire a été possible grâce à la considération du sommet de Voronoï généralisé (un concept introduit dans cette thèse).

Le calcul numérique certifié du graphe de Delaunay a été éffectué avec une librairie de résolution de systèmes zéro-dimensionnels d'équations et d'inéquations algébriques basée sur l'analyse d'intervalles (ALIAS). Le calcul certifié du graphe de Delaunay repose sur des théorèmes sur l'unicité de racines dans des intervalles donnés (Kantorovitch et Moore-Krawczyk). Pour les coniques, les calculs sont accélérés lorsque l'on ne considère que les équations implicites des courbes déplacées.

L’objet de cette thèse est de définir un type de poésie visuelle moderne (XXe-XXIe), que nous avons nommé la poésie graphique et qui attache une importance considérable à l’expérimentation plastique du signe graphique, qui manifeste une conscience aiguë des ressources visuelles de la graphie et entend réaliser la poésie dans la matérialité des formes de l’écriture. Cette pratique graphique et plastique du poème s’inscrit dans la continuité, mais également dans un certain renouveau des avant-gardes poétiques et artistiques du XXe siècle, notamment du surréalisme. La poésie graphique désigne une pratique de la poésie à caractère spécifiquement graphique, qui recouvre tant une peinture du signe qu’un travail typographique de la lettre pour élaborer le poème. La particularité des poètes graphiques est leur double vocation, celle d’écrivain et celle de plasticien. Ils expérimentent l’écriture dans sa dimension linguistique et dans sa dimension graphique, en considérant que l’activité de scription ou de linotypie — c’est-à-dire la peinture ou le dessin du mot, du signe graphique, la typographie et l’édition — est déjà littérature. Autrement dit, ils envisagent que la création et la matérialisation du poème procèdent du même geste. Les logogrammes de Christian Dotremont, les poèmes-estampes et les livres d’artistes (Éditions Erta) de Roland Giguère, les recueils de signes inventés et d’encres d’Henri Michaux et la typoésie de Jérôme Peignot constituent des formes de poésie graphique. Notre étude porte donc sur des œuvres francophones, issues des domaines belge, français et québécois, produites entre 1950 et 2004. Trois caractéristiques définissent principalement la poésie graphique : l’ambiguïté et le nomadisme du signe du poème par rapport aux ordres sémiotiques — scriptural, iconique et plastique —, la présence d’un rythme et d’un lyrisme graphiques, comme modalités de l’expression du sujet dans la matière graphique, et une remise en cause de la ligne de partage entre les arts autographiques et allographiques, nécessitant de nouveaux modes de perception et de lecture du poème et du livre, soit une « iconolecture » et une « tactilecture ».
The purpose of this thesis is to define a type of modern visual poetry (20th – 21st), that we called graphic poetry. The graphic poetry focuses on a plastic and visual experimentation of the graphic sign, demonstrates an important conscience of the visual potential of the written form and tries to produce poetry in the materiality of the writing shapes. This artistic practice of poetry follows and also renews the poetic and plastic avant-gardes of the 20th century, more particularly surrealism. The graphic poetry refers to a practice of poem which is specifically graphic and includes a painting of the sign as a typographic work of the letter in order to produce the poem. The main characteristic of graphic poets is their double vocation : they are writers and visual artists. They experiment writing in its linguistic dimension and its graphic dimension, because they believe that the action of drawing a line or making of a linotype setting — namely the painting or the drawing of the word, of the graphic sign, the typography and the publishing — is already literature. In other words, graphic poets think that the creation and the materialization of the poem proceed of the same gesture. Christian Dotremont’s logograms, Roland Giguère’s artists’ books (Editions Erta) and prints-poems, Henri Michaux’s anthologies of invented painted signs and Jérôme Peignot’s typoems are some forms of graphic poetry. Our study focuses on francophone works, which come from Belgian, French and Quebec fields, published between 1950 and 2004. Three characteristics mainly define the graphic poetry : the ambiguity and the nomadism of the sign in relation to the semiotic systems (graphic, iconic and plastic), graphics rhythm and lyricism, as modalities of the expression of the subject in the graphic material, and a questioning of the distinction between autographic arts and allographic arts, requiring new ways of perception and reading of the poem and the book, that we called visual-reading and touch-reading.
Réalisé en cotutelle avec l'Université de la Sorbonne - Paris IV