Cette thèse se positionne dans le contexte des réseaux sans fil multi-sauts (réseaux de capteurs/actionneurs/robots mobiles). Ces réseaux sont composés d’entités indépendantes à la puissance limitée et fonctionnant sur batteries qui communiquent exclusivement par voie radio. Pour pouvoir relayer les messages d’un robot à une station de base, on utilise des protocoles dits « de routage» qui ont en charge de déterminer quel robot doit relayer le message. Nous nous sommes basés sur le protocole CoMNet, qui adapte la topologie du réseau à son trafic lors du routage afin d’économiser de l’énergie en déplaçant les robots. Mais modifier la topologie c'est aussi modifier les possibilités de routage. Nous proposons donc MobileR (Mobile Recursivity) qui choisit le prochain noeud en ayant anticipé par le calcul les conséquences de tous les changements de topologie possibles. Un autre problème vient du fait qu’il y a souvent plusieurs nœuds qui détectent un même événement et vont émettre des messages à router vers la station de base. Ces messages vont finir par se croiser, et le nœud de croisement va sans cesse être relocalisé sur chacun des chemins. Le protocole PAMAL (PAth Merging ALgorithm) détecte ces intersections : il va provoquer une fusion des chemins de routage en amont du nœud de croisement et une agrégation de paquets en aval. Enfin, le protocole GRR (Greedy Routing Recovery) propose un mécanisme de récupération pour augmenter le taux de délivrance des messages dans les réseaux de capteurs/actionneurs avec obstacle(s). En effet, les protocoles de routage actuels échouent face à un obstacle. GRR va permettre de contourner l’obstacle en relocalisant des nœuds tout autour. / This thesis is about wireless multi-hop networks such as sensor/actuator networks and actuator networks. Those networks are composed of independent entities which have limited computing and memory capabilities and are battery powered. They communicate through the radio medium and do not require any static infrastructure. In order to relay messages between actuators up to the base station, we use what is called "routing protocols". My works rely on CoMNet, the first geographic routing protocol which aims to adapt the network topology to the routed traffic in order to save energy. Nevertheless, CoMNet does not consider the consequences of those relocations more than in a one-hop way. We proposed MobileR (Mobile Recursivity), which anticipates the routing in a multi-hop manner through computations over its one-hop neighbors. Hence it can select the “best” next forwarding node according to its knowledge. Another important topic is that events are likely to be detected by multiple sensors and all of them transmit message toward the destination. But those messages are likely to cross over an intersection node. This crossing provokes useless oscillation for it and premature node death. The PAMAL (PAth Merging ALgorithm) routing algorithm detects those routing path crossing and provokes a path merging upstream and uses a packet aggregation downstream. Finally, the Greedy Routing Recovery (GRR) protocol takes controlled mobility into account in order to increase delivery rate on topology with holes or obstacles. GRR includes a dedicated relocation pattern which will make it circumvent routing holes and create a routing path.

On s'intéresse dans cette thèse, à la mise en évidence des propriétés de connexité dans les données à analyser. Dans le cas de l'analyse des données ”classique” (i.e. linéaire), comme les surfaces de séparation des classes sont des hyperplans (des droites en dimension 2), la notion topologique sous-jacente est presque toujours la convexité. Au contraire dans tout ce qui suit, on cherche en priorité à segmenter les données en sous-ensembles (classes) connexes.

Malgré le grand succès de l'Internet des Objets, la plupart de ses applications sont basées uniquement sur l'actionnement statique. Cependant, l'ajout d'un rôle actif pour les actionneurs sera nécessaire afin d'optimiser les systèmes où ils sont présents. Pour ce faire, dans cette thèse, nous introduisons un nouveau concept appelé Internet des Objets Hétérogènes qui prend en compte les actionnements statique et dynamique. L'actionnement dynamique est fourni par un robot mobile ou un capteur mobile. Dans ce cas, nous exploitons le potentiel de la mobilité contrôlée en proposant des algorithmes efficaces pour maintenir la connectivité entre les dispositifs. Nous montrons par simulation l'efficacité des algorithmes proposés et leur performance en termes de temps de convergence, de connectivité et de distance parcourue. Une fois que la connectivité entre les dispositifs est garantie, un autre défi majeur qui devrait être résolu est l'énorme quantité de données qu'ils génèrent. Pour faire face à ce problème, nous proposons une approche d'inférence bayésienne qui permet d'éviter la transmission des données fortement corrélées. L'algorithme de propagation de croyance, couplé au modèle de champ aléatoire de Markov, est utilisé dans ce cas pour inférer les données manquantes. Selon différents scénarios, notre approche est évaluée sur la base des données réelles recueillies à partir des capteurs déployés sur des environnements intérieurs et extérieurs. Les résultats montrent que notre approche réduit considérablement la quantité de données transmises et la consommation d'énergie, tout en maintenant un niveau acceptable d'erreur d'inférence et de qualité de l'information. / Despite of the large success of IOT, most of its applications are based only on static actuation. However, adding an active role for actuators will be needed, in order to optimize the systems where they are present. To achieve this goal, in this thesis, we introduce a new concept called Internet of Heterogeneous Things which takes into account both static and dynamic actuation. The dynamic actuation is provided by a mobile robot or a mobile sensor. In this case, we exploit the potential of controlled mobility by proposing efficient algorithms to maintain the global connectivity among devices. We show by simulation the efficiency of the proposed algorithms and their performance in terms of convergence time, connectivity, and traveled distance. Once the connectivity among devices is guaranteed, another major challenge that should be solved is the huge amount of data they generate and transmit. To tackle this problem, we propose a Bayesian Inference Approach which allows avoiding the transmission of high correlated data. Belief Propagation algorithm, coupled with the Markov Random Field model, is used in this case to reconstruct the missing sensing data. According to different scenarios, our approach is evaluated based on the real data collected from sensors deployed on indoor and outdoor environments. The results show that our proposed approach reduces drastically the number of transmitted data and the energy consumption, while maintaining an acceptable level of inference error and information quality.

La notion de connexité est fondamentale en théorie des graphes. Nous proposons une étude approfondie d'un récent développement dans ce domaine, en ajoutant des contraintes de matroïdes.Dans un premier temps, nous exhibons deux opérations de réduction sur les graphes connectés avec contraintes de matroïdes. Ces opérations permettent de généraliser le théorème de caractérisation de la connectivité de Menger et le théorème de packing d'arborescences d'Edmonds.Cependant, cette extension du théorème d'Edmonds ne garantie plus que les arborescences soient couvrantes. Il a été conjecturé que l'on peut toujours trouver de telles arborescences couvrantes. Nous prouvons cette conjecture dans certains cas particuliers, notamment pour les matroïdes de rang deux et pour les matroïdes transversaux. Nous réfutons cette conjecture dans le cas général en construisant un contre-exemple à plus de 300 sommets, sur une extension parallèle du matroïde de Fano.Enfin, nous explorons d'autres notions de connexité avec contraintes de matroïdes: pour des graphes mixtes, des hypergraphes, et avec condition d'atteignabilité. / The notion of connectivity is fundamental in graph theory. We study thoroughly a recent development in this field, with the addition of matroid constraints.Firstly, we exhibit two reduction operations on connected graphs with matroid constraints. Using these operations, we generalize the Menger's theorem on connectivity and Edmond's theorem on packing of arborescences.However, this extension of Edmond's theorem does not ensure that the arborescences are spanning. It has been conjectured that one can always find such spanning arborescences. We prove this conjecture in some cases, including matroids of rank two and transversal matroids. We disprove this conjecture in the general case by providing a counter-example with more than 300 vertices, on a parallel extension of the Fano matroid.Finally, we explore other generalizations of connectivity with matroid constraints: in mixed graphs, hypergraphs and with reachability conditions.

Orienter un graphe c'est remplacer chaque arête par un arc de mêmes extrémités. On s'intéresse à la connexité du graphe orienté ainsi obtenu. L'orientation avec des contraintes d'arc-connexité est maintenant comprise en profondeur mais très peu de résultats sont connus en terme de sommet-connexité. La conjecture de Thomassen avance que les graphes suffisament sommet-connexes ont une orientation k-sommet-connexe. De plus, la conjecture de Frank propose une caractérisation des graphes qui admettent une telle orientation. Les résultats de cette thèse s'articulent autour des notions d'orientation, de packing, de connexité et de matroïde. D'abord, nous infirmons une conjecture de Recski sur la décomposition d'un graphe en arbres ayant des orientations avec degrés entrants prescrits. Nous prouvons également un nouveau résultat sur le packing d'arborescences enracinées avec contraintes de matroïdes. Ceci généralise un résultat fondamental d'Edmonds. Enfin, nous démontrons un nouveau théorème de packing sur les bases des matroïdes de dénombrement qui nous permet d'améliorez le seul résultat connu sur la conjecture de Thomassen. D'autre part, nous donnons une construction et un théorème d'augmentation pour une famille de graphes liée à la conjecture de Frank. En conclusion, nous réfutons la conjecture de Frank et prouvons que, pour tout entier k >= 3, décider si un graphe a une orientation k-sommet-connexe est un problème NP-complet. / Orienting an undirected graph means replacing each edge by an arc with the same ends. We investigate the connectivity of the resulting directed graph. Orientations with arc-connectivity constraints are now deeply understood but very few results are known in terms of vertex-connectivity. Thomassen conjectured that sufficiently highly vertex-connected graphs have a k-vertex- connected orientation while Frank conjectured a characterization of the graphs admitting such an orientation. The results of this thesis are structures around the concepts of orientation, packing, connectivity and matroid. First, we disprove a conjecture of Recski on decomposing a graph into trees having orientations with specified indegrees. We also prove a new result on packing rooted arborescences with matroid constraints. This generalizes a fundamental result of Edmonds. Moreover, we show a new packing theorem for the bases of count matroids that induces an improvement of the only known result on Thomassen's conjecture. Secondly, we give a construction and an augmentation theorem for a family of graphs related to Frank's conjecture. To conclude, we disprove the conjecture of Frank and prove that, for every integer k >= 3, the problem of deciding whether a graph admits a k-vertex-orientation is NP-complete.

Cette thèse a pour but d’étudier la qualité de texte chez les jeunes adultes universitaires. La première partie de ce travail est théorique et définit ce qu’est un texte et comment s’élabore sa qualité. Cette dernière est envisagée à travers les concepts linguistiques de cohérence et de cohésion. Ces deux notions sont dès lors développées, décrites et opérationnalisées à des fins d’expérimentation. La deuxième partie de la thèse est empirique et expose trois études expérimentales. La première a pour but de déterminer si les performances orthographiques varient en fonction du genre textuel produit et de quelle manière. La deuxième étude se penche sur des marques linguistiques de la cohésion servant à l’élaboration de la cohérence. Plus précisément, il s’agit de déterminer si les procédés anaphoriques et les marqueurs de connectivité varient selon le genre textuel produit. La dernière étude a pour but d’évaluer les relations existant entre l’usage de ces mêmes indices et une charge cognitive-attentionnelle accrue ou allégée portée spécifiquement sur la correction orthographique. Au terme de ces recherches, il apparaît que plusieurs facteurs semblent liés aux variations dans l’usage et la maîtrise des marques étudiées et seraient donc liés aux variations de qualité textuelle. / Doctorat en Sciences psychologiques et de l'éducation / info:eu-repo/semantics/nonPublished

In this thesis, we consider the k-edge connected L-hop-constrained network design problem. Given a weighted graph G=(N,E), a set D of pairs of terminal nodes, and two integers k,L > 1, it consists in finding in G the minimum cost subgraph containing at least k edge-disjoint paths of at most L edges between each pair in D. This problem is of great interest in today's telecommunication industry, where highly survivable networks need to be constructed. We first study the particular case where the set of demands D is reduced to a single pair {s,t}. We propose an integer programming formulation for the problem, which consists in the st-cut and trivial inequalities, along with the so-called L-st-path-cut inequalities. We show that these three classes of inequalities completely describe the associated polytope when k=2 and L=2 or 3, and give necessary and sufficient conditions for them to be facet-defining. We also consider the dominant of the associated polytope, and discuss how the previous inequalities can be separated in polynomial time. We then extend the complete and minimal description obtained above to any number k of required edge-disjoint L-st-paths, but when L=2 only. We devise a cutting plane algorithm to solve the problem, using the previous polynomial separations, and present some computational results. After that, we consider the case where there is more than one demand in D. We first show that the problem is strongly NP-hard, for all L fixed, even when all the demands in D have one root node in common. For k=2 and L=2,3, we give an integer programming formulation, based on the previous constraints written for all pairs {s,t} in D. We then proceed by giving several new classes of facet-defining inequalities, valid for the problem in general, but more adapted to the rooted case. We propose separation procedures for these inequalities, which are embedded within a Branch-and-Cut algorithm to solve the problem when L=2,3. Extensive computational results from it are given and analyzed for both random and real instances. Since those results appear less satisfactory in the case of arbitrary demands (non necessarily rooted), we present additional families of valid inequalites in that situation. Again, separation procedures are devised for them, and added to our previous Branch-and-Cut algorithm, in order to see the practical improvement granted by them. Finally, we study the problem for greater values of L. In particular, when L=4, we propose new families of constraints for the problem of finding a subgraph that contains at least two L-st-paths either node-disjoint, or edge-disjoint. Using these, we obtain an integer programming formulation in the space of the design variables for each case. ------------------------------------------------ Dans cette thèse, nous considérons le problème de conception de réseau k-arete connexe à chemins L-bornés. Etant donné un graphe pondéré G=(N,E), un ensemble D de paires de noeuds terminaux, et deux entiers k,L > 1, ce problème consiste à trouver, dans G, un sous-graphe de cout minimum tel que, entre chaque paire dans D, il existe au moins k chemins arete-disjoints de longueur au plus L. Ce problème est d'un grand intéret dans l'industrie des télécommunications, où des réseaux hautement fiables doivent etre construits. Nous étudions tout d'abord le cas particulier où l'ensemble des demandes D est réduit à une seule paire de noeuds. Nous proposons une formulation du problème sous forme de programme linéaire en nombres entiers, laquelle consiste en les inégalités triviales et de coupe, ainsi que les inégalités dites de L-chemin-coupe. Nous montrons que ces trois types d'inégalités décrivent complètement le polytope associé lorsque k=2 et L=2,3, et donnons des conditions nécessaires et suffisantes pour que celles-ci en définissent des facettes. Nous considérons également le dominant du polytope associé et discutons de la séparation polynomiale des trois classes précédentes. Nous étendons alors cette description complète et minimale à tout nombre k de chemins arete-disjoints de longueur au plus 2. De plus, nous proposons un algorithme de plans coupants utilisant les précédentes séparations polynomiales, et en présentons quelques résultats calculatoires, pour tout k>1 et L=2,3. Nous considérons ensuite le cas où plusieurs demandes se trouvent dans D. Nous montrons d'abord que le problème est fortement NP-dur, pour tout L fixé et ce, meme si les demandes sont toutes enracinées en un noeud. Pour k=2 et L=2,3, nous donnons une formulation du problème sous forme de programme linéaire en nombres entiers. Nous proposons également de nouvelles classes d'inégalités valides, pour lesquelles nous réalisons une étude faciale. Celles-ci sont alors séparées dans le cadre d'un algorithme de coupes et branchements pour résoudre des instances aléatoires et réelles du problème. Enfin, nous étudions le problème pour de plus grandes valeurs de L. En particulier, lorsque L=4, nous donnons de nouvelles familles de contraintes pour le problème consistant à déterminer un sous-graphe contenant entre deux noeuds fixés au moins deux chemins de longueur au plus 4, que ceux-ci doivent etre arete-disjoints ou noeud-disjoints. Grace à ces dernières, nous parvenons à donner une formulation naturelle du problème dans chacun de ces deux cas.

Les deux questions de connexité auxquelles on s'intéresse concernent : – l'espace des feuilletages de codimension 1 sur une variété de dimension 3 ; – l'espace des représentations du groupe Z^2 dans le groupe des difféomorphismes lisses de l'intervalle. Le résultat principal, qu'on démontre dans la seconde partie de la thèse, est le suivant : si deux feuilletages de codimension 1 sur une variété close de dimension 3 ont des sous-fibrés tangents homotopes, on peut les relier par un chemin de feuilletages. Cet énoncé cache une subtilité : si les feuilletages donnés sont lisses, le chemin obtenu peut contenir, près de ses extrémités, des feuilletages qui ne sont que C^1. Cela vient de ce qu'on ne sait pas si l'espace des représentations de Z^2 dans les difféomorphismes de l'intervalle est connexe ou non. En tentant de répondre à cette question, on a montré le phénomène suivant qui fait l'objet de la première partie de la thèse : de nombreux difféomorphismes lisses de R+, sans autre point fixe que l'origine, ont un centralisateur C^infini non dénombrable et dense dans leur centralisateur C^1, lequel est un groupe à un paramètre. On discute également les propriétés arithmétiques de ce sous-groupe.

É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

Cette thèse porte sur deux thèmes : 1)Percolation et connexité sur les graphes géométriques aléatoires dits "type AB". 2)Comparaison stochastique directionnellement convexe de processus ponctuels et leurs propriétés de percolation et connexité. Dans le premier sujet, nous définissons un graphe biparti, dit "de type AB", sur deux processus ponctuels de Poisson indépendants. Cet graphe est une extension continue de graphe dit "type AB" sur une grille régulière. Nous montrons l'existence de percolation pour toute dimension supérieure à deux et nous établissons des bornes pour l'intensité critique. Dans le cas de dimensions deux, nous caractérisons exactement l'intensité critique. Pour le problème de connexité, nous étudions le modelé sur les processus ponctuels de Poisson indépendant dans le cube de volume un avec des intensités n et c_n pour une constante c > 0. Nous établissons des bornes asymptotiques presque sûres pour le seuil de connexité. 2) Le but du deuxième sujet de travail est de définir l'ordre directionnellement convexe de processus ponctuels est de lier cet ordre aux propriétés de regroupement des points de processus ponctuels et, dans un contexte applicatif, aux caractéristiques de la performance des réseaux de communication sans fil. La dernière partie de cette thèse porte sur la comparaison des intensités critiques de percolation pour les processus ponctuels ordonnés selon cet ordre et les applications de ces résultats de comparaison pour les réseaux sans fils. Nous concluons en montrant que les processus ponctuels inférieurs, selon cet ordre, à un processus ponctuel de Poisson ont une transition de phase non-triviale dans plusieurs modelés des percolation.