Cette thèse décrit le développement et la mise en œuvre d'un système d'acquisition 3D ayant pour but la localisation temps réel en 3D et l'identification d'électrodes et des antennes utilisées lors d'un examen MEG/EEG. La seconde partie concerne la mise en correspondance de ces données avec les informations de la résonance magnétique. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

The present work proposes visibly pushdown transducers (VPTs) for defining transformations of documents with a nesting structure. We show that this subclass of pushdown transducers enjoy good properties. Notably, we show that functionality is decidable in PTime and k-valuedness in co-NPTime. While this class is not closed under composition and its type checking problem against visibly pushdown automata is undecidable, we identify a subclass, the well-nested VPTs, closed under composition and with a decidable type checking problem. Furthermore, we show that the class of VPTs is closed under look-ahead, and that the deterministic VPTs with look-ahead characterize the functional VPTs transductions. Finally, we investigate the resources necessary to perform transformations defined by VPTs. We devise a memory efficient algorithm. Then we show that it is decidable whether a VPT transduction can be performed with a memory that depends on the level of nesting of the input document but not on its length. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

In this thesis, we introduce the Partitioning-Hub Location-Routing problem (PHLRP), which can be classified as a variant of the hub location problem.<p>PHLRP consists of partitioning a network into sub-networks, locating at least one hub in each subnetwork and routing the traffic within the network such that all inter-subnetwork traffic is routed through the hubs and all intra-subnetwork traffic stays within the sub-networks all the way from the source to the destination. Obviously, besides the hub location component, PHLRP also involves a graph partitioning component and a routing component. PHLRP finds applications in the strategic planning or deployment of the Intermediate System-Intermediate System (ISIS) Internet Protocol networks and the Less-than-truck load freight distribution systems.<p><p>First, we introduce three IP formulations for solving PHLRP. The hub location component and the graph partitioning components of PHLRP are<p>modeled in the same way in all three formulations. More precisely, the hub location component is represented by the p-median variables and constraints; and the graph partitioning component is represented by the size-constrained graph partitioning variables and constraints. The formulations differ from each other in the way the peculiar routing requirements of PHLRP are modeled.<p><p>We then carry out analytical and empirical comparisons of the three IP<p>formulations. Our thorough analysis reveals that one of the formulations is<p>provably the tightest of the three formulations. We also show analytically that the LP relaxations of the other two formulations do not dominate each other. On the other hand, our empirical comparison in a standard branch-and-cut framework that is provided by CPLEX shows that not the tightest but the most compact of the three formulations yield the best performance in terms of solution time. <p><p>From this point on, based on the insight gained from detailed analysis of the formulations, we focus our attention on a common sub-problem of the three formulations: the so-called size-constrained graph partitioning problem. We carry out a detailed polyhedral analysis of this problem. The main benefit from this polyhedral analysis is that the facets we identify for the size-constrained graph partitioning problem constitute strong valid inequalities for PHLRP.<p><p>And finally, we wrap up our efforts for solving PHLRP. Namely, we present<p>the results of our computational experiments, in which we employ some facets<p>of the size-constrained graph partitioning polytope in a branch-and-cut algorithm for solving PHLRP. Our experiments show that our approach brings<p>significant improvements to the solution time of PHLRP when compared with<p>the default branch-and-cut solver of XPress. <p><p>/<p><p>Dans cette thèse, nous introduisons le problème Partitionnement-Location des Hubs et Acheminement (PLHA), une variante du problème de location de hubs. Le problème PLHA partitionne un réseau afin d'obtenir des sous-réseaux, localise au moins un hub dans chaque sous-réseau et achemine le traffic dans le réseau de la maniére suivante :le traffic entre deux<p>sous-réseaux distincts doit être éxpedié au travers des hubs tandis que le traffic entre deux noeuds d'un même sous-réseau ne doit pas sortir de celui-ci. PLHA possède des applications dans le planning stratégique, ou déploiement, d'un certain protocole de communication utilisé<p>dans l'Internet, Intermediate System - Intermediate System, ainsi que dans la distribution des frets.<p><p>Premièrement, nous préesentons trois formulations linéaires en variables entières pour résoudre PLHA. Le partitionnement du graphe et la localisation des hubs sont modélisées de la même maniére dans les trois formulations. Ces formulations diffèrent les unes des autres dans la maniére dont l'acheminement du traffic est traité.<p><p>Deuxièmement, nous présentons des comparaisons analytiques et empiriques des trois formulations. Notre comparaison analytique démontre que l'une des formulations est plus forte que les autres. Néanmoins, la comparaison empirique des formulations, via le solveur CPLEX, montre que la formulation la plus compacte (mais pas la plus forte) obtient les meilleures performances en termes de temps de résolution du problème.<p><p>Ensuite, nous nous concentrons sur un sous-problème, à savoir, le partitionnement des graphes sous contrainte de taille. Nous étudions le polytope des solutions réalisables de ce sous-problème. Les facettes de ce polytope constituent des inégalités valides fortes pour<p>PLHA et peuvent être utilisées dans un algorithme de branch-and-cut pour résoudre PLHA.<p><p>Finalement, nous présentons les résultats d'un algorithme de branch-and-cut que nous avons développé pour résoudre PLHA. Les résultats démontrent que la performance de notre méthode est meilleure que celle de l'algorithme branch-and-cut d'Xpress.<p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Dans cette thèse, nous étudions différents modèles, déterministes et stochastiques, pour les problèmes de dimensionnement de réseaux. Nous examinons également le problème du sac-à-dos stochastique ainsi que, plus généralement, les contraintes de capacité en probabilité.<p>\ / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Résumé<p>Les recherches menées dans cette thèse ont porté sur la réactualisation des données sur la flore et la végétation de deux grandes zones agro-écologiques du Sénégal (les Niayes et le Bassin arachidier) en utilisant l’approche terroir pour mieux envisager la gestion conservatoire des ressources ligneuses. Dans les zones de savanes et de végétations sub-guinéennes respectivement du Bassin arachidier et des Niayes au Sénégal, 288 relevés ont été réalisés par stratification basée sur les villages ou groupes ethniques (Peul, Sérer et Wolof), les systèmes d’utilisation des terres et la topographie dans 6 terroirs villageois et 25 dans les sites de référence. Dans ces terroirs, la connaissance, la priorisation à la conservation des espèces, leur utilisations, comme préalables à la gestion durable de la biodiversité des agrosystèmes, ont aussi été abordées sur 124 espèces ligneuses par enquête ethnobotanique auprès de 216 répondants équitablement répartis entre les ethnies, âges et genres. Ces informants ont aussi évalué la dynamique des formations végétales suivant leur position sur la toposéquence. Les informations sur la dynamique d’occupation des terres ont été obtenues par la cartographie multi-date à partir de photo-aériennes (1954, 1989) et d’image Google earth 2006. Une expérimentation factorielle à trois facteurs (espèces, hauteur et diamètre de coupe) avec 15 répétitions, a été conduite dans le Bassin arachidier sur la régénération des souches des deux principales Combretaceae de la zone (Combretum glutinosum et Guiera senegalensis). Les données obtenues ont été soumises à des analyses multi et uni-variées. <p>Les résultats phytosociologiques ont montré l’individualisation de onze groupements (G) dont d’une part, deux de savane (G4 et G8), un de forêts secondaires (G10) et deux autres issus des végétations semi-aquatiques (G1 et G5) qui sont les plus proches des situations naturelles, et d’autre part deux de milieux perturbés (G6 et G7) et quatre de milieux cultivés et post-culturaux (G2, G3, G9 et G11). Les premiers groupements sont progressivement envahis par les espèces des milieux perturbés, et les seconds par les espèces rudérales et nitrophiles. La position synsystématique de ces groupements a été donnée. 336 espèces ont été recensées :260 dans les Niayes et 176 dans le Bassin arachidier. La richesse des critères de naturalités des terroirs peuls n’est pas toujours supérieure à celle des autres terroirs dans les deux zones. <p>Les résultats d’enquête montrent une subdivision des espèces en quatre classes de priorité à la sauvegarde. Les plus prioritaires sont à usages multiples. En outre, les résultats ethnobotaniques montrent clairement que les villages des Niayes sont globalement séparés de ceux du Bassin arachidier mais aussi que les villages homologues sont différents. L’évaluation ethnobotanique de la diversité végétale est plus importante dans la zone du Bassin arachidier comparée aux Niayes. Elle augmente avec la densité dans les Niayes comme dans le Bassin arachidier excepté dans le terroir wolof de ce dernier. Les villages du Bassin arachidier ne présentent aucune restriction dans le choix des espèces destinées à satisfaire leurs différents besoins. Ce manque de sélectivité y est total et renseigne sur le niveau de rareté des ressources ligneuses. <p>Les résultats cartographiques montrent que les zones des Niayes et du Bassin arachidier connaissent une transformation importante du paysage essentiellement due au processus de création ou d’agrégation des champs en vigueur partout. Cela s’est fait au détriment des formations végétales :suppression des savanes arborées dans les deux zones, suppression et agrégation des savanes arbustives dans les Niayes, fragmentation et dissection dans le Bassin arachidier. <p>Dans le régime de taillis à courte rotation du Bassin arachidier, il serait plus indiqué de pratiquer une coupe sélective suivant les classes de diamètre et les espèces afin de concilier productivité et durabilité en favorisant le développement des rejets proventifs. <p>Une extension de l’approche terroir dans les autres zones éco-géographiques du pays devrait être testée pour vérifier les tendances obtenues dans ce travail et recenser et suivre les groupements végétaux, les intégrer dans la classification moderne afin de faciliter le suivi de leur évolution spatio-temporelle. Elle permettrait sans doute l’évaluation de la variabilité locale de l’importance des espèces.<p><p>Abstract<p>Researches carried out in this thesis about updating flora and vegetation data from two major agroecological regions of Senegal (Niayes and Peanut Basin) used village-scale based methodology in order to better consider ligneous resources conservation. In savannas and sub-guinean vegetations of respectively Peanut Basin and Niayes, 288 records were realized upon stratification method based on ethnic groups (Wolof, Peul and Sérer), land use systems and topography in 6 villages and 25 records in the reference sites. In these villages, knowledge, priorisation and uses, prior to sustainable agrobiodiversity management, were also addressed on 124 ligneous species by ethnobotanic survey with 216 respondants equally distributed to ethnic groups, ages and gender. Respondants also addressed vegetation dynamics a long topographic position. Informations on land occupation trends were gained by air-photography cartography and Google earth 2006 image. Factorial experimentation on 3 factors (species, high and diameter of sprouting) with 15 repetitions was implemented on stump regeneration dynamics of the 2 principal Combretaceae in the Peanut Basin region (Combretum glutinosum and Guiera senegalensis). Multivariate and univariate analysis were performed on the data. <p>Phytosociological results showed discrimination of 11 vegetation groups (G). Two of them (G4 and G8) are savannas samples, one secondary forest (G10), two from semi-aquatic vegetation (G1 and G5); in the other hand, two groups of disturbed situations (G6 and G7) and four cultivated and postcultural groups were found (G2, G3, G9 and G11). The first groups were progressively invaded by cultural and poscultural species and the second groups by ruderary and adventitious species. Systematic position of these groups was indicated. 336 species were recorded: 260 in the Niayes and 176 in the Peanut Basin). Richness in wilderness criterion was not always superior in peul villages.<p>Ethnobotanical results showed subdivision of species diversity in 4 classes of conservation priority. Most conservation priority species were multipurpose trees. A clear separation between Niayes villages and Peanut basin ones, and also between counterparts’ villages was found. Ethnobotanical valuation of species was higher in the Peanut Basin area. It grows with human density a part from wolof village of the Peanut basin. Villages of the Groundnut Basin showed no selectivity in the choice of species to meet their different needs. This lack of selectivity is complete and translates woody resources scarcity. <p>Cartographic results show an important landscape transformation in Niayes and Peanut basin areas due to fields creation or aggregation processes running everywhere. This occurred against vegetation formations :attrition of woody savanna in the two zones, attrition and aggregation of shrubby savanna in Niayes area, fragmentation and dissection in Peanut basin. <p>In short term cutting system of the Peanut Basin, it should be better to practise a selective logging method according to species and diameter classes in order to reconcile productivity and sustainability by ensuring stumps’ low-stem resprouting. <p>An extension of terroir approach methodology in other local eco-geographical zones of Senegal should be tested in order to complete the identification and monitoring of the dynamics of plant communities, their integration into modern classification to facilitate the monitoring of their spatio-temporal evolution. It should allow the assessment of species local importance variability.<p><p><p><p> / Doctorat en Sciences agronomiques et ingénierie biologique / info:eu-repo/semantics/nonPublished

Le comportement électoral dans les communautés mixtes (Résumé)<p><p>Andreea ZAMFIRA<p><p><p>\ / Doctorat en sciences politiques / info:eu-repo/semantics/nonPublished

Stochastic combinatorial optimization problems are combinatorial optimization problems where part of the problem data are probabilistic. The focus of this thesis is on stochastic routing problems, a class of stochastic combinatorial optimization problems that arise in distribution management. Stochastic routing problems involve finding the best solution to distribute goods across a logistic network. In the problems we tackle, we consider a setting in which the cost of a solution is described by a random variable; the goal is to find the solution that minimizes the expected cost. Solving such stochastic routing problems is a challenging task because of two main factors. First, the number of possible solutions grows exponentially with the instance size. Second, computing the expected cost of a solution is computationally very expensive. <p><br><p>To tackle stochastic routing problems, stochastic local search algorithms such as iterative improvement algorithms and metaheuristics are quite promising because they offer effective strategies to tackle the combinatorial nature of these problems. However, a crucial factor that determines the success of these algorithms in stochastic settings is the trade-off between the computation time needed to search for high quality solutions in a large search space and the computation time spent in computing the expected cost of solutions obtained during the search. <p><br><p>To compute the expected cost of solutions in stochastic routing problems, two classes of approaches have been proposed in the literature: analytical computation and empirical estimation. The former exactly computes the expected cost using closed-form expressions; the latter estimates the expected cost through Monte Carlo simulation.<p><br><p>Many previously proposed metaheuristics for stochastic routing problems use the analytical computation approach. However, in a large number of practical stochastic routing problems, due to the presence of complex constraints, the use of the analytical computation approach is difficult, time consuming or even impossible. Even for the prototypical stochastic routing problems that we consider in this thesis, the adoption of the analytical computation approach is computationally expensive. Notwithstanding the fact that the empirical estimation approach can address the issues posed by the analytical computation approach, its adoption in metaheuristics to tackle stochastic routing problems has never been thoroughly investigated. <p><br><p>In this thesis, we study two classical stochastic routing problems: the probabilistic traveling salesman problem (PTSP) and the vehicle routing problem with stochastic demands and customers (VRPSDC). The goal of the thesis is to design, implement, and analyze effective metaheuristics that use the empirical estimation approach to tackle these two problems. The main results of this thesis are: <p>1) The empirical estimation approach is a viable alternative to the widely-adopted analytical computation approach for the PTSP and the VRPSDC; <p>2) A principled adoption of the empirical estimation approach in metaheuristics results in high performing algorithms for tackling the PTSP and the VRPSDC. The estimation-based metaheuristics developed in this thesis for these two problems define the new state-of-the-art. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

The biological membrane surrounding the living cell provides a sealed barrier that tightly regulates the interactions with the outside environment. A large number of integral membrane proteins mediate these interactions and are involved in a wide variety of biological processes. An increasing number of studies have led to the conclusion that lipids provide more than a hydrophobic solvent for membrane proteins, and that interactions between lipids and proteins are required to allow protein function. ABC transporters are one of the most important family of membrane proteins. However, the importance of their lipidic environment is largely unknown. Only a few studies showed that their activity was dependent on the lipidic composition of the surrounding bilayer. The bacterial ABC transporter HorA was used as a model to probe the influence of the lipidic environment on that class of membrane proteins.<p><p> HorA is a multidrug transporter expressed in Lactobacillus brevis, a Gram-positive beer spoilage bacterium. It turned out that phosphatidylethanolamine (PE) was indispensable to maintain both the activity and the structural integrity of HorA.<p> Surprisingly, replacement of PE by the chemically related PC (phosphatidylcholine) did not led to the suppression of HorA activity, but to an unexpected phenotype. Whereas the cytoplasmic domains of HorA were still able to hydrolyze ATP, the membrane parts of the transporter were unable to use that energy to mediate substrate transport. Using several biophysical methods particularly adapted to the study of reconstituted systems, we showed that the structure of HorA is strongly altered by this lipid replacement. In particular, the structural organization of the transmembrane domains of the protein is strongly affected.<p> / Doctorat en Sciences agronomiques et ingénierie biologique / info:eu-repo/semantics/nonPublished

Cette thèse se penche sur les problèmes de décisions devant être prises de manière séquentielle au sein d'un environnement aléatoire. Lors de chaque étape d'un tel problème décisionnel, une alternative doit être sélectionnée parmi un ensemble d'alternatives. Chaque alternative possède un gain moyen qui lui est propre et lorsque l'une d'elles est sélectionnée, celle-ci engendre un gain aléatoire. La sélection opérée peut suivre deux types d'objectifs.<p>Dans un premier cas, les tests viseront à maximiser la somme des gains collectés. Un juste compromis doit alors être trouvé entre l'exploitation et l'exploration. Ce problème est couramment dénommé dans la littérature scientifique "multi-armed bandit problem".<p>Dans un second cas, un nombre de sélections maximal est imposé et l'objectif consistera à répartir ces sélections de façon à augmenter les chances de trouver l'alternative présentant le gain moyen le plus élevé. Ce deuxième problème est couramment repris dans la littérature scientifique sous l'appellation "selecting the best".<p>La sélection de type gloutonne joue un rôle important dans la résolution de ces problèmes de décision et opère en choisissant l'alternative qui s'est jusqu'ici montrée optimale. Or, la nature généralement aléatoire de l'environnement rend incertains les résultats d'une telle sélection. <p>Dans cette thèse, nous introduisons une nouvelle quantité, appelée le "gain espéré d'une action gloutonne". Sur base de quelques propriétés de cette quantité, de nouveaux algorithmes permettant de résoudre les deux problèmes décisionnels précités seront proposés.<p>Une attention particulière sera ici prêtée à l'application des techniques présentées au domaine de la sélection de modèles en l'apprentissage artificiel supervisé. <p>La collaboration avec le service d'anesthésie de l'Hôpital Erasme nous a permis d'appliquer les algorithmes proposés à des données réelles, provenant du milieu médical. Nous avons également développé un système d'aide à la décision dont un prototype a déjà été testé en conditions réelles sur un échantillon restreint de patients. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

The dissertation covers two problems motivated by computational biology: genome rearrangements, and haplotype networks.<p><p>Genome rearrangement problems are a particular case of edit distance problems, where one seeks to transform two given objects into one another using as few operations as possible, with the additional constraint that the set of allowed operations is fixed beforehand; we are also interested in computing the corresponding distances between those objects, i.e. merely computing the minimum number of operations rather than an optimal sequence. Genome rearrangement problems can often be formulated as sorting problems on permutations (viewed as linear orderings of {1,2,n}) using as few (allowed) operations as possible. In this thesis, we focus among other operations on ``transpositions', which displace intervals of a permutation. Many questions related to sorting by transpositions are open, related in particular to its computational complexity. We use the disjoint cycle decomposition of permutations, rather than the ``standard tools' used in genome rearrangements, to prove new upper bounds on the transposition distance, as well as formulae for computing the exact distance in polynomial time in many cases. This decomposition also allows us to solve a counting problem related to the ``cycle graph' of Bafna and Pevzner, and to construct a general framework for obtaining lower bounds on any edit distance between permutations by recasting their computation as factorisation problems on related even permutations.<p><p>Haplotype networks are graphs in which a subset of vertices is labelled, used in comparative genomics as an alternative to trees. We formalise a new method due to Cassens, Mardulyn and Milinkovitch, which consists in building a graph containing a given set of partially labelled trees and with as few edges as possible. We give exact algorithms for solving the problem on two graphs, with an exponential running time in the general case but with a polynomial running time if at least one of the graphs belong to a particular class.<p>/<p>La thèse couvre deux problèmes motivés par la biologie: l'étude des réarrangements génomiques, et celle des réseaux d'haplotypes.<p><p>Les problèmes de réarrangements génomiques sont un cas particulier des problèmes de distances d'édition, où l'on cherche à transformer un objet en un autre en utilisant le plus petit nombre possible d'opérations, les opérations autorisées étant fixées au préalable; on s'intéresse également à la distance entre les deux objets, c'est-à-dire au calcul du nombre d'opérations dans une séquence optimale plutôt qu'à la recherche d'une telle séquence. Les problèmes de réarrangements génomiques peuvent souvent s'exprimer comme des problèmes de tri de permutations (vues comme des arrangements linéaires de {1,2,n}) en utilisant le plus petit nombre d'opérations (autorisées) possible. Nous examinons en particulier les ``transpositions', qui déplacent un intervalle de la permutation. Beaucoup de problèmes liés au tri par transpositions sont ouverts, en particulier sa complexité algorithmique. Nous nous écartons des ``outils standards' utilisés dans le domaine des réarrangements génomiques, et utilisons la décomposition en cycles disjoints des permutations pour prouver de nouvelles majorations sur la distance des transpositions ainsi que des formules permettant de calculer cette distance en temps polynomial dans de nombreux cas. Cette décomposition nous sert également à résoudre un problème d'énumération concernant le ``graphe des cycles' de Bafna et Pevzner, et à construire une technique générale permettant d'obtenir de nouvelles minorations en reformulant tous les problèmes de distances d'édition sur les permutations en termes de factorisations de permutations paires associées.<p><p>Les réseaux d'haplotypes sont des graphes dont une partie des sommets porte des étiquettes, utilisés en génomique comparative quand les arbres sont trop restrictifs, ou quand l'on ne peut choisir une ``meilleure' topologie parmi un ensemble donné d'arbres. Nous formalisons une nouvelle méthode due à Cassens, Mardulyn et Milinkovitch, qui consiste à construire un graphe contenant tous les arbres partiellement étiquetés donnés et possédant le moins d'arêtes possible, et donnons des algorithmes résolvant le problème de manière optimale sur deux graphes, dont le temps d'exécution est exponentiel en général mais polynomial dans quelques cas que nous caractérisons.<p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished