Dans cette thèse, nous nous intéressons à la résolution exacte de problèmes NP-difficiles sur les graphes et les hypergraphes. Les problèmes que nous étudions regroupent dans un premier temps des variantes du problème classique du nombre chromatique. Les variantes de ce problème se distinguent par la difficulté introduite par les relations entre les classes de couleurs, ou la difficulté de reconnaissance des classes de couleurs elles-mêmes. Puis nous ferons le lien avec les problèmes de transversaux sur les hypergraphes. Plus particulièrement, il s’agira de s’intéresser à l’énumération de transversaux minimaux dans un hypergraphe de rang borné. Outre la résolution exacte, nous nous intéressons à la résolution à paramètre fixe. Le problème de racine carrée de graphe est un problème important en théorie des graphes. Nous proposons et montrons la solubilité à paramètre fixe de deux problèmes d’optimisation reliés. Finalement, nous nous intéresserons à la résolution de problèmes de graphe, soit en lien avec les problèmes de colorations, soit pour montrer les performances possibles de différents algorithmes en fonction de l’espace mémoire disponible. Dans cette thèse, nous aurons à cœur d’appliquer judicieusement la grande majorité des techniques essentielles en algorithmique exacte exponentielle. Principalement, nous appliquerons la programmation dynamique ou le principe d’inclusion-exclusion pour les problèmes de coloration. La technique de programmation dynamique se retrouvera pour d’autres problèmes de cette thèse, aux côtés d’autres méthodes comme la technique de branchement ou de mesurer et conquérir / In this thesis, we are interested in the exact computation of np-hard problems on graphs and hypergraphs. Firstly, we study several variants of colorings. Those variants appear harder than the famous chromatic number problem, by adding difficulty in recognizing the color classes, or more often by introducing various relationships between them. Then we link to problems of transversals in hypergraphs. More precisely, we are interested in enumerating minimal transversals in bounded ranked hypergraphs. Besides the exact computation, we are also interested in fixed parameter tractability. For this area, we study two optimization versions of the famous square root of graphs problem. Finally, we will be interested in solving other problems of graphs related to colorings, or in order to compare efficiencies of algorithms depending on the memory space available. In this thesis, we will apply most of major techniques in designing exact exponential algorithms. The main techniques we use are dynamic programming, inclusion-exclusion, branching, or measure and conquer

The research presented in this thesis investigated the functional morphology in root<br />systems in relation to their role in providing anchorage and stability for the plant. The<br />anchorage of different types of root systems was investigated as well as the influence of<br />several environmental factors on their development. The research presented in this study<br />was completed by carrying out a series of modelling, glasshouse and field experiments<br />using physical models and real plants.<br />Model experiments showed that solid shapes like bulbs are very well suited to resist<br />vertical upward forces, i.e. uprooting, and shed some light on the mechanism of<br />anchorage in bulbs. The results of this laboratory study showed that the concept of<br />optimal bulb shape for resisting uprooting is viable. Uprooting tests on real bulb plants<br />confirmed the theoretical predictions about it, and showed the importance of bulbs in<br />anchorage. This study also proved that the soil type is very important when considering<br />the anchorage of solid forms such as the bulbs.<br />A second model study showed that the simplest models of tap root-dominated root<br />systems increase their resistance to overturning with the third and second power of the<br />embedment depth in cohesionless and in cohesive soil respectively. Anchorage strength<br />of a root system dominated by a tap root will be maximised with minimum investment<br />in structural material if the rigid tap root is extended to the largest possible depth.<br />Glasshouse experiments investigated the effects of soil compaction and temperature,<br />two of the most important environmental factors, on the axial and lateral development<br />and growth of the root systems of two species of young pines. It was shown that the rate<br />of root axial development in both investigated species decreased with an increase in soil<br />compaction whereas the lateral proliferation of their roots systems was not significantly<br />affected by soil consistency. A temperature of around 15°C seemed to be optimal for the<br />root elongation rate since the increase in axial length of the roots of both species was<br />largest at this temperature.<br />The effect of mechanical stimulation as a factor in shaping the root systems of plants<br />was also investigated. Apart from the changes caused to the parts of the tree above<br />ground, unidirectional periodical flexing induced an increase in total root CSA and<br />larger biomass allocation to the roots parallel to the plane of flexing which, in turn,<br />resulted in a larger number of major lateral roots with larger CSA in the plane of<br />flexing.<br />Mechanical and morphological field studies on two Pinus species investigated the<br />anchorage of plate root systems and showed that lateral roots in older trees are not the<br />major source of root anchorage in either of the species; although in both species a<br />certain asymmetry in the distribution of major lateral root CSA was recorded, it was not<br />significantly correlated to the asymmetry in anchorage.

L'implantation en Virgule Flottante (VF) d'une fonction à valeurs réelles est réalisée avec arrondi correct si le résultat calculé est toujours égal à l'arrondi de la valeur exacte, ce qui présente de nombreux avantages. Mais pour implanter une fonction avec arrondi correct de manière fiable et efficace, il faut résoudre le "dilemme du fabricant de tables" (TMD en anglais). Deux algorithmes sophistiqués (L et SLZ) ont été conçus pour résoudre ce problème, via des calculs longs et complexes effectués par des implantations largement optimisées. D'où la motivation d'apporter des garanties fortes sur le résultat de ces pré-calculs coûteux. Dans ce but, nous utilisons l'assistant de preuves Coq. Tout d'abord nous développons une bibliothèque d'"approximation polynomiale rigoureuse", permettant de calculer un polynôme d'approximation et un intervalle bornant l'erreur d'approximation à l'intérieur de Coq. Cette formalisation est un élément clé pour valider la première étape de SLZ, ainsi que l'implantation d'une fonction mathématique en général (avec ou sans arrondi correct). Puis nous avons implanté en Coq, formellement prouvé et rendu effectif 3 vérifieurs de certificats, dont la preuve de correction dérive du lemme de Hensel que nous avons formalisé dans les cas univarié et bivarié. En particulier, notre "vérifieur ISValP" est un composant clé pour la certification formelle des résultats générés par SLZ. Ensuite, nous nous sommes intéressés à la preuve mathématique d'algorithmes VF en "précision augmentée" pour la racine carré et la norme euclidienne en 2D. Nous donnons des bornes inférieures fines sur la plus petite distance non nulle entre sqrt(x²+y²) et un midpoint, permettant de résoudre le TMD pour cette fonction bivariée. Enfin, lorsque différentes précisions VF sont disponibles, peut survenir le phénomène de "double-arrondi", qui peut changer le comportement de petits algorithmes usuels en arithmétique. Nous avons prouvé en Coq un ensemble de théorèmes décrivant le comportement de Fast2Sum avec double-arrondis.

Le calcul scientifique est souvent associé au calcul numérique. Pourtant dans de nombreuses disciplines scientifiques il est nécessaire d'aller au-delà du calcul approché : nécessité de certification des résultats, calculs dans des structures mathématiques discrètes, instabilité des algorithmique numériques. Le calcul exact s'attache donc à donner des résultats exacts ou certifiés. Cependant, la principale obstruction à l'utilisation du Calcul Formel est bien souvent les faibles performances des systèmes commerciaux y compris pour les opérations fondamentales comme l'algèbre linéaire. L'objectif de ces travaux est donc de réduire l'écart entre le calcul exact et le calcul numérique, tant sur le plan algorithmique, que sur le plan logiciel. Les défis sont multiples : développer une arithmétique efficace dans les structures discrètes ; concevoir des algorithmes ayant un terme dominant de complexité optimal même en tenant compte de la croissance des données intermédiaires ; transcrire ces algorithmes dans des logiciels combinant efficacité pérenne, interfaçage et généricité.

La fixation symbiotique d’N par les légumineuses est très sensible aux ravageurs, provoquant des dommages sur les racines nodulées, avec un impact sur la fixation d’N et la croissance qui demeure mal connu. Nous avons alors analysé la réponse adaptative de la fixation symbiotique et de la croissance du pois Frisson sauvage et 3 de ses mutants hypernodulants P64, P118 et P121, respectivement mutés sur les gènes SYM28, SYM29 et NOD3, à une ablation de la moitié du système racinaire, en fin de phase végétative. La réponse adaptative a été mesurée 8 jours après ablation, dans des conditions d'alimentation en carbone par la photosynthèse variées. A 380 ppm, le mutant P118 a montré la plus faible diminution de l’activité spécifique de fixation (-17%) suite à l’ablation comparé au sauvage et aux 2 autres mutants (-36% à -62%) associé à une accélération chez les mutants P118 et P121 et un maintien (sauvage et P64) de la croissance des nodosités. A 150 ppm, suite à l’ablation, l’activité spécifique de fixation symbiotique par les nodosités a été diminuée (sauvage), maintenue (P64 et P118) ou augmentée (P121), associée à une accélération (sauvage et P121) ou un maintien (P64 et P118) de la croissance des nodosités. A 750 ppm, l’activité spécifique de fixation a diminué suite à l’ablation pour tous les génotypes, associée à un ralentissement (P64), un maintien (P118, sauvage) ou une faible accélération (P121) de la croissance des nodosités. Les résultats montrent une plus grande capacité de la fixation symbiotique des mutants hypernodulants (P118 et P121 essentiellement) à résister au stress provoqué par l’ablation. / Symbiotic N fixation of legumes is very sensitive to environmental stresses, like pea pests damaging nodulated roots. However, the impact on their N uptake capacity and plant growth has not been studied so far.We analyzed the adaptive response symbiotic N2 fixation and plant growth of pea wild type Frisson and hypernodulating mutants P64, P118 and P121 mutated respectively on genes SYM28, SYM29 and NOD3 to root pruning of half the root system at the end of the vegetative stage. The adaptive responses of pea: cv. Frisson and 3 of its hypernodulating mutants were compared under varying carbon supplies from photosynthesis.At 380 ppm, mutant P118 showed the lowest decrease of the specific activity of N fixation (-17%) following root pruning compared to the wild type and the 2 others mutants (-36% to -62%), associated to an acceleration (P118 and P121) and a maintained (wild type and P64) nodule growth. At 150 ppm, following root pruning, specific activity of N fixation of nodules decreased in wild type, was maintained in P64 and P118 and increased in P121. At 750 ppm, specific activity of N fixation of nodules decreased for all genotypes following root pruning, associated to a maintained nodule growth in wild type and P118, a slower growth in P64 and acceleration in P121.Our results showed a greater capacity of hypernodulating mutants P118 and P121 to withstand the stress induced by root pruning of half the root system.

Le syndrome de l’intestin irritable (SII) et le syndrome de la vessiedouloureuse (SVD) sont tous deux caractérisés par une hypersensibilité viscérale àla distension. Sur le plan épidémiologique, ces deux syndromes sont étroitementassociés puisque les patients SII ont une prévalence du syndrome de la vessiedouloureuse 7 fois plus élevée que la population générale. Cependant, le mécanismeresponsable de la sensibilisation du tube digestif et de l’appareil urinaire n’a jamaisété étudié. Compte tenu de l’innervation commune de ces deux organes, il estprobable que ce mécanisme mette en jeu sur le long terme des phénomènes de laplasticité neuro-gliale aux niveaux communs d’intégration de la sensibilité pelvienne.L’objectif général de ce travail était d’établir et de caractériser un modèleanimal de sensibilisation croisée vessie/colon, aigu et chronique, afin de mieuxcomprendre les mécanismes impliqués dans l’hypersensibilité viscérale croisée. / Irritable bowel syndrome (IBS) and Bladder pain syndrome (BPS) are bothcharacterized by visceral hypersensitivity to distension. Epidemiology showed thatthese two syndromes are closely associated since IBS patients have a prevalence ofbladder pain syndrome that is 7 times higher than the general population. However,the mechanism responsible for sensitization of the gastrointestinal tract and theurinary tract has never been studied. Given the common innervation of these twoorgans, it is likely that this mechanism involves long-term phenomena of neuro-glialplasticity at the common levels of integration of pelvic sensitivity.The overall objective of this work was to establish and characterize an animalmodel of bladder / colon cross-sensitization, acute and chronic, to better understandthe mechanisms involved in cross-visceral hypersensitivity.

L’origine des suites de mégacristaux des kimberlites est sujette à d’intenses débats depuis de nombreuses années. La suite complexe de mégacristaux (grenat, clinopyroxène, zircon, baddeleyite, ilménite, rutile et nodules d’intercroissances rutile-silicates) des kimberlites diamantifères de Mbuji-Mayi (Kasaï Oriental), mises en place au Crétacé dans le craton archéen du Congo-Kasaï, a été étudiée en détails dans le but d’établir les relations entre les différents minéraux de la suite, leur relation au magma kimberlitique-hôte et au manteau lithosphérique cratonique archéen. L’étude des mégacristaux de grenat des kimberlites pauvres en diamants du Kundelungu (Katanga) a permis en outre d’établir la comparaison entre les mégacristaux de deux provinces kimberlitiques en République Démocratique du Congo, qui diffèrent notamment par leur âge de mise en place et par la composition et l’âge du socle traversé. <p>L’ensemble des données minéralogiques et géochimiques acquises (éléments majeurs et en traces, géochimie isotopique de l’oxygène, du Nd et de l’Hf) est intégré dans le but de déterminer la nature du (ou des) processus qui a (ont) donné naissance à ces suites de mégacristaux. <p>En parallèle, l’origine d’un xénolite rare de clinopyroxénite à kyanite exceptionnellement riche en Cr des kimberlites de Mbuji-Mayi a été explorée.<p>Bien qu’ils partagent de nombreuses caractéristiques avec d’autres suites de mégacristaux kimberlitiques, les mégacristaux de RDC sont généralement enrichis en Cr et appauvris en Fe et Ti, et ne présentent pas de preuve d’une origine par cristallisation fractionnée à partir d’un magma, ce qui permet de suggérer une origine différente, en l’occurrence une liaison plus directe avec le manteau lithosphérique réfractaire local lors de leur formation. Une origine métasomatique par interaction entre un liquide/fluide précurseur de la kimberlite et les péridotites du manteau lithosphérique est donc favorisée. L’ensemble des espèces minérales qui forme la suite de mégacristaux peut en effet trouver un équivalent compositionnel dans les lithologies métasomatisées de la lithosphère mantélique. <p>Les mégacristaux de grenat des deux provinces partagent des similarités frappantes qui sont interprétées en termes de processus de formation similaires. En revanche, ils ont systématiquement montré un comportement géochimique singulier, suggérant un processus de formation différent des autres mégacristaux. Ils semblent en effet avoir retenu l’héritage des compositions variables d’anciens protolites de grenat affectés récemment par un métasomatisme de type kimberlitique. Ces grenats résultent de la recristallisation de grenats initialement présents dans les péridotites cratoniques de la lithosphère archéenne. Par contre, les mégacristaux de clinopyroxène, zircon, baddeleyite, ilménite, rutile et les nodules d’intercroissances rutile-silicates se sont effectivement formés récemment par l’interaction métasomatique entre le liquide/fluide proto-kimberlitique et les péridotites cratoniques. Des variations locales du rapport (fluide et/ou liquide)/roche et de l’activité en SiO2 lors de la percolation du magma proto-kimberlitique asthénosphérique dans le manteau lithosphérique cratonique, couplées à la nature propre à la kimberlite de la région, permettent d’intégrer l’ensemble des mégacristaux dans un modèle pétrogénétique commun, avec des processus de formation parfois contrastés. <p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

L'implantation en Virgule Flottante (VF) d'une fonction à valeurs réelles est réalisée avec arrondi correct si le résultat calculé est toujours égal à l'arrondi de la valeur exacte, ce qui présente de nombreux avantages. Mais pour implanter une fonction avec arrondi correct de manière fiable et efficace, il faut résoudre le «dilemme du fabricant de tables» (TMD en anglais). Deux algorithmes sophistiqués (L et SLZ) ont été conçus pour résoudre ce problème, via des calculs longs et complexes effectués par des implantations largement optimisées. D'où la motivation d'apporter des garanties fortes sur le résultat de ces pré-calculs coûteux. Dans ce but, nous utilisons l'assistant de preuves Coq. Tout d'abord nous développons une bibliothèque d'«approximation polynomiale rigoureuse», permettant de calculer un polynôme d'approximation et un intervalle bornant l'erreur d'approximation à l'intérieur de Coq. Cette formalisation est un élément clé pour valider la première étape de SLZ, ainsi que l'implantation d'une fonction mathématique en général (avec ou sans arrondi correct). Puis nous avons implanté en Coq, formellement prouvé et rendu effectif 3 vérifieurs de certificats, dont la preuve de correction dérive du lemme de Hensel que nous avons formalisé dans les cas univarié et bivarié. En particulier, notre «vérifieur ISValP» est un composant clé pour la certification formelle des résultats générés par SLZ. Ensuite, nous nous sommes intéressés à la preuve mathématique d'algorithmes VF en «précision augmentée» pour la racine carré et la norme euclidienne en 2D. Nous donnons des bornes inférieures fines sur la plus petite distance non nulle entre sqrt(x²+y²) et un midpoint, permettant de résoudre le TMD pour cette fonction bivariée. Enfin, lorsque différentes précisions VF sont disponibles, peut survenir le phénomène de «double-arrondi», qui peut changer le comportement de petits algorithmes usuels en arithmétique. Nous avons prouvé en Coq un ensemble de théorèmes décrivant le comportement de Fast2Sum avec double-arrondis. / The Floating-Point (FP) implementation of a real-valued function is performed with correct rounding if the output is always equal to the rounding of the exact value, which has many advantages. But for implementing a function with correct rounding in a reliable and efficient manner, one has to solve the ``Table Maker's Dilemma'' (TMD). Two sophisticated algorithms (L and SLZ) have been designed to solve this problem, relying on some long and complex calculations that are performed by some heavily-optimized implementations. Hence the motivation to provide strong guarantees on these costly pre-computations. To this end, we use the Coq proof assistant. First, we develop a library of ``Rigorous Polynomial Approximation'', allowing one to compute an approximation polynomial and an interval that bounds the approximation error in Coq. This formalization is a key building block for verifying the first step of SLZ, as well as the implementation of a mathematical function in general (with or without correct rounding). Then we have implemented, formally verified and made effective 3 interrelated certificates checkers in Coq, whose correctness proof derives from Hensel's lemma that we have formalized for both univariate and bivariate cases. In particular, our ``ISValP verifier'' is a key component for formally verifying the results generated by SLZ. Then, we have focused on the mathematical proof of ``augmented-precision'' FP algorithms for the square root and the Euclidean 2D norm. We give some tight lower bounds on the minimum non-zero distance between sqrt(x²+y²) and a midpoint, allowing one to solve the TMD for this bivariate function. Finally, the ``double-rounding'' phenomenon can typically occur when several FP precision are available, and may change the behavior of some usual small FP algorithms. We have formally verified in Coq a set of results describing the behavior of the Fast2Sum algorithm with double-roundings.