Le travail que nous développons dans le cadre de cette thèse s'articule autour des problèmes de recherche de structure de recouvrement de graphes sous contrainte sur le degré des sommets. Comme l'arbre de recouvrement couvre les sommets d'un graphe connexe avec un minimum de liens, il est généralement proposé comme solution à ce type de problèmes. Cependant, pour certaines applications telles que le routage dans les réseaux optiques, les solutions ne sont pas nécessairement des sous-graphes. Nous supposons dans cette thèse que la contrainte sur le degré est due à une capacité limitée instantanée des sommets et que la seule exigence sur le recouvrement est sa connexité. Dans ce cas, la solution peut être différente d'un arbre. Nous reformulons ces problèmes de recouvrement en nous appuyant sur une extension du concept d'arbre appelée hiérarchie de recouvrement. Notre objectif principal est de démontrer son intérêt vis-à-vis de l'arbre en termes de faisabilité et de coût du recouvrement. Nous considérons deux types de contraintes sur le degré : des bornes sur le degré des sommets ou une borne sur le nombre de sommets de branchement et cherchons dans les deux cas un recouvrement de coût minimum. Nous illustrons aussi l'applicabilité des hiérarchies en étudiant un problème prenant davantage en compte la réalité du routage optique. Pour ces différents problèmes NP-difficiles, nous montrons, tant sur le coût des solutions optimales que sur la garantie de performance des solutions approchées, l'intérêt des hiérarchies de recouvrement. Ce constat se voit conforté par des expérimentations sur des graphes aléatoires. / The work conducted in this thesis is focused on the minimum spanning problems in graphs under constraints on the vertex degrees. As the spanning tree covers the vertices of a connected graph with a minimum number of links, it is generally proposed as a solution for this kind of problems. However, for some applications such as the routing in optical networks, the solution is not necessarily a sub-graph. In this thesis, we assume that the degree constraints are due to a limited instantaneous capacity of the vertices and that the only pertinent requirement on the spanning structure is its connectivity. In that case, the solution may be different from a tree. We propose the reformulation of this kind of spanning problems. To find the optimal coverage of the vertices, an extension of the tree concept called hierarchy is proposed. Our main purpose is to show its interest regarding the tree in term of feasibility and costs of the coverage. Thus, we take into account two types of degree constraints: either an upper bound on the degree of vertices and an upper bound on the number of branching vertices. We search a minimum cost spanning hierarchy in both cases. Besides, we also illustrate the applicability of hierarchies by studying a problem that takes more into account the reality of the optical routing. For all those NP-hard problems, we show the interest of the spanning hierarchy for both costs of optimal solutions and performance guarantee of approximate solutions. These results are confirmed by several experimentations on random graphs.

Dans ce mémoire de thèse, on étudie le morphisme de monoïde $mu$du monoïde libre sur l'alphabet des entiers $nb$,`a valeurs dans le groupe modulaire $PSL_2(zb)$,considéré comme monoïde, défini pour tout entier $a$ par $mu(a)=begin{pmatrix} 0 & -1 1 & a+1 end{pmatrix}.$Les nombres de Catalan apparaissent naturellement dans l'étudede sous-ensembles du noyau de $mu$.Dans un premier temps, on met en évidence deux systèmes de réécriture, l'un sur l'alphabet fini ${0,1}$, l'autresur l'alphabet infini des entiers $nb$ et on montreque ces deux systèmes de réécriture définissent des présentations de monoïde de $PSL_2(zb)$ par générateurs et relations.Par ailleurs, on introduit le morphisme d'indice associé `a l'abélianisé du rev^etement universel de $PSL_2(zb)$,le groupe $B_3$ des tresses `a trois brins. Interprété dans deux contextes différents,le morphisme d'indice est associé au nombre de "demi-tours".Ensuite, dans les quatrième et cinquième parties, on dénombre des sous-ensembles du noyau de $mu_{|{0,1}}$ etdu noyau de $mu$, bigradués par la longueur et l'indice. La suite des nombres de Catalan et d'autres diagonales du triangle de Catalan interviennentsimplement dans les résultats.Enfin, on présente l'origine géométrique de cette étude : on explicite le lien entre l'objectif premier de la thèse qui était l'étudedes polygones convexes entiers d'aire minimale et notre intéret pour le monoïde engendré par ces matrices particulières de $PSL_2(zb)$. / In this thesis, we study a morphism of mono"id $mu$ between the free mono"id on the alphabet of integers $nb$and the modular group $PSL_2(zb)$ considered as a mono"id, defined for all integer $a$by $mu(a)=begin{pmatrix} 0 & -1 1 & a+1 end{pmatrix}.$ The Catalan Numbers arised naturally in the study ofsubsets of the kernel of the morphism $mu$.Firstly, we introduce two rewriting systems, one on the finite alphabet ${0,1}$, and the other on the infinite alphabet of integers $nb$. We proove that bothof these rewriting systems defines a mono"id presentation of $PSL_2(zb)$ by generators and relations.On another note, we introduce the morphism of loop associated to the abelianised of the universal covering group of $PSL_2(zb)$, the group $B_3$ ofbraid group on $3$ strands. In two different contexts, the morphism of loop is associated to the number of "half-turns".Then, in the fourth and the fifth parts, we numerate subsets of the kernel of $mu_{|{0,1}}$ and of the kernel of $mu$,bi-graduated by the morphism of lengthand the morphism of loop. The sequences of Catalan numbers and other diagonals of the Catalan triangle come into the results.Lastly, we present the geometrical origin of this research : we detail the connection between our first aim,which was the study of convex integer polygones ofminimal area, and our interest for the mono"id generated by these particular matrices of $PSL_2(zb)$.

No description available.

Les chiroptères sont reconnus comme de potentiels régulateurs des populations d’insectes. Ce sont aussi les mammifères européens pour lesquels les enjeux de conservation sont les plus importants. Ils trouvent dans les forêts des habitats favorables qui sont cependant menacés par les changements climatiques et la fragmentation. Il convient donc de mieux comprendre lesrelations entre les communautés de chiroptères, leurs habitats et leurs proies en forêt. L'objectif de cette thèse est de quantifier les effets, à différentes échelles spatiales, desprincipales composantes de l’habitat forestier sur l’activité, la richesse spécifique, la diversité fonctionnelle et la composition des communautés de chiroptères européens. Les résultats reposent sur des données collectées grâce à des protocoles expérimentaux en Aquitaine et dans les six pays du réseau de placettes forestières organisé par le projet FunDivEurope. De la parcelle au continent, l'accroissement de la diversité des essences forestières, de la proportion de feuillus et du bois mort, en augmentant les ressources en proies et en gîtes, ont des effets positifs sur les communautés de chiroptères. Ces effets, non stationnaires, se renforcent vers le nord avec la rigueur du climat. Nous confirmons également que les chiroptères forestiers, par leur réponse numérique et fonctionnelle aux densités de proie, peuvent limiter la démographie d’un insecte défoliateur. Des mesures de gestion, visant le renforcement des structures-clés des habitats forestiers, sont proposées pour favoriser la conservation des communautés de chiroptères et leur capacité de régulation des insectes ravageurs. / Insectivorous bats are increasingly recognized as potential regulators of pest insect populations.They also represent the group of European mammals with the most unfavorable conservation status. Forests are key habitats for many bat species but are currently under threat from climate change and fragmentation. It is therefore urgent to better understand the relationships between the bats, their prey and their habitats in forests. Our main objective was to quantify the effects, at multiple spatial scales, of the main attributes of forest habitats on the activity, species richness, functional diversity and composition of European bat communities. They were studied using manipulative experiments in Aquitaine plantation forests and automatic recordings in the network of exploratory plots set up in six European countries by the FunDivEurope project. From the plot to the continent scale, increasing tree diversity, amount of broad leaved trees and dead wood, had positive effects on bat communities through an increase in prey and roost resources. However these effects were not stationary, being stronger at higher latitudes, probably due to lower habitat carrying capacity in relation to harsher climatic conditions. In addition we experimentally demonstrated that the numerical and functional responses of bats to prey density could result in effective regulation of pine processionary moth populations. Forest management strategies aim at enhancing key habitat structures, are eventually proposed in order to improve the conservation of bats and to increase the service of pest regulation they can provide.

Le travail effectué durant cette thèse concerne l'étude des méthodes d'Extraction de Connaissances à partir de Données (ECD) dans le cadre des Systèmes d'Information Géographiques (SIG). Nous avons non seulement mis en œuvre et amélioré des méthodes d'ECD classique (Classification de Données, Visualisation de Classifications) mais aussi des méthodes d'ECD spatiales liées à des méthodes d'analyse spatiale (Lissage Spatial, Détermination de Pôles, Sectorisation). Nous avons effectué notre travail de recherche au sein de la société GÉOBS spécialisée dans l'analyse des données géographiques (spatiales), et nous avons donc expérimenté, appliqué et vérifié ces méthodes sur des jeux de données fournis par GÉOBS et liés à des problématiques de Développement Économique, de Géomarketing, d'Analyse de Risque, d'Environnement, de Santé, etc. Ce mémoire offre une vision globale concernant un ensemble de problématiques et de méthodes d'analyse. Il met ainsi en avant la complémentarité des méthodes utilisées qui sont souvent connectées entre elles soit du point de vue technique soit du point de vue de leur utilisation. Finalement, ce fut un travail très enrichissant car il a touché à de nombreuses problématiques et à d'aussi nombreuses méthodes d'extraction de connaissances.

Les programmes mobiles, comme les applettes, sont utiles mais potentiellement hostiles, et il faut donc pouvoir s'assurer que leur exécution n'est pas dangereuse pour le système hôte. Une solution est d'exécuter le programme mobile dans un environnement sécurisé, servant d'interface avec les ressources locales, dans le but de contrôler les flux d'informations entre le code mobile et les ressources, ainsi que les accès du code mobile aux ressources. Nous proposons deux critères de sécurité pour l'exécution de code mobile, obtenus chacun à partir d'une analyse de l'environnement local. Le premier porte sur les flux d'informations, garantit la confidentialité, est fondé sur le code de l'environnement, et est exact et indécidable ; le second porte sur les contrôles d'accès, garantit le confinement, s'obtient à partir du type de l'environnement, et est approché et décidable. Le premier chapitre, méthodologique, présente l'étude d'objets infinis représentés sous la forme d'arbres. Nous avons privilégié pour les définir, une approche équationnelle, et pour raisonner sur eux, une approche déductive, fondée sur l'interprétation co-inductive de systèmes d'inférence. Dans le second chapitre, on montre dans le cas simple du calcul, comment passer d'une sémantique opérationnelle à une sémantique dénotationnelle, en utilisant comme dénotation d'un programme son observation. Le troisième chapitre présente finalement en détail les deux critères de sécurité pour l'exécution de code mobile. Les techniques développées dans les chapitres précédents sont utilisées pour l'étude de la confidentialité, alors que des techniques élémentaires suffisent à l'étude du confinement.

L'extension supersymétrique du Modèle Standard peut contenir des interactions violant la symétrie dite de R-parité. La présence de tels couplages engendrerait une violation des nombres leptonique et/ou baryonique et modifierait en profondeur la phénoménologie de la supersymétrie auprès des futurs collisionneurs de particules. Nous avons développé des tests des interactions violant la R-parité. D'une part, nous avons étudié des signaux clairs de la production d'un seul partenaire supersymétrique de particule du Modèle Standard, qui implique les couplages violant la R-parité, dans le cadre de la physique aux prochains collisionneurs leptoniques et hadroniques. Les résultats montrent que de fortes sensibilités pourront être obtenues sur les paramètres de brisure douce de la supersymétrie et indiquent la possibilité d'une amélioration d'un à deux ordres de grandeur des limites indirectes actuelles sur les valeurs de plusieurs constantes de couplage violant la R-parité. De plus, il a été vérifié que l'analyse de la production d'un seul superpartenaire offre l'opportunité de reconstruire de façon indépendante du modèle théorique diverse masses de superpartenaires avec une grande précision. D'autre part, nous avons étudié des effets de violation de la symétrie CP aux futurs collisionneurs leptoniques dans la production de paire de fermions de saveurs différentes, ou de leur superpartenaire, permettant de mettre en évidence d'éventuelles phases complexes des constantes de couplage violant la R-parité. Nous avons vu notamment que la production d'un quark top accompagné d'un quark charmé permet de tester la violation de CP dans le secteur hadronique. La conclusion de ces travaux est que les phases complexes de certaines constantes de couplage violant la R-parité pourraient être observées, et plus particulièrement dans un scénario où ces couplages exhiberaient une grande hiérarchie dans l'espace des saveurs

La microélectronique est au pied du mur. Pour continuer son développement, l'une des voies à l'étude est l'approche "bottom-up", dont la philosophie peut être résumée comme suit : "faire croître où l'on veut le dispositif tel qu'on le souhaite". C'est dans cette problématique que s'inscrivent les structures unidimensionnnelles, et plus précisément les nanofils semiconducteurs. Dans la présente thèse, nous étudions la croissance des nanofils de silicium par dépôt chimique en phase vapeur, assisté de particules métalliques, appelées catalyseurs. Dans un premier temps, nous étudions la croissance des nanofils de Si, obtenus avec l'or comme catalyseur et le silane comme gaz réactif, via le mécanisme de croissance vapeur-liquide-solide (VLS). Nous nous intéressons plus particuli`erement `a l'impact des paramètres de croissance (pressions partielles des réactifs, température, durée, taille du catalyseur) sur la morphologie des nanofils et la cinétique de croissance de ces derniers. L'ajout de HCl au mélange réactif est étudié. Dans un second temps nous portons notre attention à la croissance de structures branchées. D'abord, une étude expérimentale, couplée à une approche thermodynamique, nous a permis de déterminer une condition nécessaire à la croissance de nanobranches (et de nanofils) de faible diamètre (i.e. < 10 nm), par croissance VLS. Ensuite, nous présentons la croissance de structures branchées obtenues à des températures allant jusqu'à 100 °C sous l'eutectique macroscopique du système Au-Si. L'or étant un matériau indésirable pour de nombreuses applications microélectroniques du fait qu'il provoque au sein du silicium des pièges de niveau profond, nous nous sommes attaché à réaliser la croissance de nanofils de silicium en utilisant des catalyseurs compatibles CMOS. En occurrence, il s'agit de siliciures métalliques (siliciures de platine, de nickel, de palladium). Les nanofils croissent par le mécanisme de croissance vapeur-solide-solide. Enfin, nous illustrons notre travail par des études davantage orientées vers l'intégration technologique, avec des réalisations de champs de fils localisés et de dispositifs, de type MOSFET, à base de nanofils, caractérisés électriquement.

Dans cette thèse, nous nous intéressons à trois problèmes issus de l'informatique théorique, à savoir le placement de formes rectangulaires dans un conteneur (OPP), la coloration dite "forte" d'arêtes des graphes et les codes identifiants dans les graphes. L'OPP consiste à décider si un ensemble d'items rectangulaires peut être placé sans chevauchement dans un conteneur rectangulaire et sans dépassement des bords de celui-ci. Une contrainte supplémentaire est prise en compte, à savoir l'interdiction de rotation des items. Le problème est NP-difficile même dans le cas où le conteneur et les formes sont des carrés. Nous présentons un algorithme de résolution efficace basé sur une caractérisation du problème par des graphes d'intervalles, proposée par Fekete et Schepers. L'algorithme est exact et utilise les MPQ-arbres - structures de données qui encodent ces graphes de manière compacte tout en capturant leurs propriétés remarquables. Nous montrons les résultats expérimentaux de notre approche en les comparant aux performances d'autres algorithmes existants. L'étude de la coloration forte d'arêtes et des codes identifiants porte sur les aspects structurels et de calculabilité de ces deux problèmes. Dans le cas de la coloration forte d'arêtes nous nous intéressons plus particulièrement aux familles des graphes planaires et des graphes subcubiques. Nous montrons des bornes optimales pour l'indice chromatique fort des graphes subcubiques en fonction du degré moyen maximum et montrons que tout graphe planaire subcubique sans cycles induits de longueur 4 et 5 est coloriable avec neuf couleurs. Enfin nous confirmons la difficulté du problème de décision associé, en prouvant qu'il est NP-complet dans des sous-classes restreintes des graphes planaires subcubiques. La troisième partie de la thèse est consacrée aux codes identifiants. Nous proposons une caractérisation des graphes identifiables dont la cardinalité du code identifiant minimum est n − 1, où n est l'ordre du graphe. Nous étudions la classe des graphes adjoints et nous prouvons des bornes inférieures et supérieures serrées pour la cardinalité du code identifiant minimum dans cette classe. Finalement, nous montrons qu'il existe un algorithme linéaire de calcul de ce paramètre dans la classe des graphes adjoints L(G) où G a une largeur arborescente bornée par une constante. En revanche nous nous apercevons que le problème est NP-complet dans des sous-classes très restreintes des graphes parfaits.

Les hélitrons constituent un groupe d'éléments transposables découverts récemment dans les génome eucaryotes. A travers une étude bioinformatique, nous avons étudié leur mode d'invasion, la modularité de leur séquence et leurs impacts sur les gènes à leur proximité dans le génome d'Arabidopsis thaliana. Les hélitrons sont les éléments transposables les plus répandus dans ce génome ; néanmoins ils ne sont que partiellement reconnus par des logiciels d'alignement. Nous avons modélisé ces éléments sous la forme d'une grammaire formelle. Cette grammaire est constituée des deux extrémités terminales séparées par une séquence nucléotidique quelconque de taille fixée. Nous avons créé une matrice d'occurrences des modèles associant toutes les combinaisons possibles d'extrémités. La matrice a fait apparaître des associations préférentielles entre certaines extrémités et a permis la découverte de nouvelles familles d'hélitrons chimériques. La détection des ORFs contenant les protéines de transposition a permis de confirmer la relation hélitron autonome non-autonome et de comprendre le mécanisme de création des chimères d'hélitrons. Nous avons proposé une nouvelle nomenclature des hélitrons basée sur leurs extrémités et non sur leur séquence globale. L'étude de la séquence d'une famille d'hélitrons a montré une réorganisation constante des domaines nucléiques entre les différentes copies de cette famille. Pour comprendre cette organisation, nous avons mis au point le logiciel DomainOrganizer qui permet d'observer la composition en domaines des éléments transposables. DomainOrganizer détecte les frontières entre domaines à partir d'un alignement multiple et crée la liste des domaines. A partir de cette liste, il recherche, par un algorithme d'optimisation combinatoire, le nombre minimal de domaines qui recouvrent au maximum l'ensemble des séquences. Enfin, DomainOrganizer visualise et classe les séquences en fonction de leurs domaines. L'analyse par domaines de la famille AtREP21 a permis de comprendre la nature de cette variabilité et de retracer l'histoire évolutive de cette famille à partir de l'identification des domaines. L'étude de la localisation des hélitrons AtREP3 dans ce génome de plante a montré une insertion préférentielle de ceux-ci dans les promoteurs de gènes. Les profils d'expression de ces gènes, nous a permis d'identifier plusieurs clusters. Par ailleurs, les motifs de régulation ont montré une grande variabilité de motifs dans les promoteurs mais pas dans les hélitrons. Ces résultats ont montré que les hélitrons non-autonomes transportent dans leurs séquences internes des motifs de liaisons aux facteurs de transcription. Des analyses complémentaires devront être réalisées pour comprendre l'action régulatrice des hélitrons sur les gènes situés à leur proximité.