Le but de cette thèse est d’expliquer la délinquance prolifique de certains délinquants. Nous avançons la thèse que la délinquance prolifique s’explique par la formation plus fréquente de situations criminogènes. Ces situations réfèrent au moment où un délinquant entre en interaction avec une opportunité criminelle dans un contexte favorable au crime. Plus exactement, il s’agit du moment où le délinquant fait face à cette opportunité, mais où le crime n’a pas encore été commis. La formation de situations criminogènes est facilitée par l’interaction et l’interdépendance de trois éléments : la propension à la délinquance de la personne, son entourage criminalisé et son style de vie. Ainsi, la délinquance prolifique ne pourrait être expliquée adéquatement sans tenir compte de l’interaction entre le risque individuel et le risque contextuel. L’objectif général de la présente thèse est de faire la démonstration de l’importance d’une modélisation interactionnelle entre le risque individuel et le risque contextuel afin d’expliquer la délinquance plus prolifique de certains contrevenants. Pour ce faire, 155 contrevenants placés sous la responsabilité de deux établissements des Services correctionnels du Québec et de quatre centres jeunesse du Québec ont complété un protocole d’évaluation par questionnaires auto-administrés. Dans un premier temps (chapitre trois), nous avons décrit et comparé la nature de la délinquance autorévélée des contrevenants de notre échantillon. Ce premier chapitre de résultats a permis de mettre en valeur le fait que ce bassin de contrevenants est similaire à d’autres échantillons de délinquants en ce qui a trait à la nature de leur délinquance, plus particulièrement, au volume, à la variété et à la gravité de leurs crimes. En effet, la majorité des participants rapportent un volume faible de crimes contre la personne et contre les biens alors qu’un petit groupe se démarque par un lambda très élevé (13,1 % des délinquants de l’échantillon sont responsables de 60,3% de tous les crimes rapportés). Environ quatre délinquants sur cinq rapportent avoir commis au moins un crime contre la personne et un crime contre les biens. De plus, plus de 50% de ces derniers rapportent dans au moins quatre sous-catégories. Finalement, bien que les délinquants de notre échantillon aient un IGC (indice de gravité de la criminalité) moyen relativement faible (médiane = 77), près de 40% des contrevenants rapportent avoir commis au moins un des deux crimes les plus graves recensés dans cette étude (décharger une arme et vol qualifié). Le second objectif spécifique était d’explorer, au chapitre quatre, l’interaction entre les caractéristiques personnelles, l’entourage et le style de vie des délinquants dans la formation de situations criminogènes. Les personnes ayant une propension à la délinquance plus élevée semblent avoir tendance à être davantage entourées de personnes criminalisées et à avoir un style de vie plus oisif. L’entourage criminalisé semble également influencer le style de vie de ces délinquants. Ainsi, l’interdépendance entre ces trois éléments facilite la formation plus fréquente de situations criminogènes et crée une conjoncture propice à l’émergence de la délinquance prolifique. Le dernier objectif spécifique de la thèse, qui a été couvert dans le chapitre cinq, était d’analyser l’impact de la formation de situations criminogènes sur la nature de la délinquance. Les analyses de régression linéaires multiples et les arbres de régression ont permis de souligner la contribution des caractéristiques personnelles, de l’entourage et du style de vie dans l’explication de la nature de la délinquance. D’un côté, les analyses de régression (modèles additifs) suggèrent que l’ensemble des éléments favorisant la formation de situations criminogènes apporte une contribution unique à l’explication de la délinquance. D’un autre côté, les arbres de régression nous ont permis de mieux comprendre l’interaction entre les éléments dans l’explication de la délinquance prolifique. En effet, un positionnement plus faible sur certains éléments peut être compensé par un positionnement plus élevé sur d’autres. De plus, l’accumulation d’éléments favorisant la formation de situations criminogènes ne se fait pas de façon linéaire. Ces conclusions sont appuyées sur des proportions de variance expliquée plus élevées que celles des régressions linéaires multiples. En conclusion, mettre l’accent que sur un seul élément (la personne et sa propension à la délinquance ou le contexte et ses opportunités) ou leur combinaison de façon simplement additive ne permet pas de rendre justice à la complexité de l’émergence de la délinquance prolifique. En mettant à l’épreuve empiriquement cette idée généralement admise, cette thèse permet donc de souligner l’importance de considérer l’interaction entre le risque individuel et le risque contextuel dans l’explication de la délinquance prolifique. / The purpose of this dissertation is to explain the prolific delinquency of certain offenders. We suggest that prolific delinquency is explained by the formation of a greater number of criminogenic situations. A criminogenic situation makes reference to situations wherein an offender may interact with a criminal opportunity in an environment which is conducive to crime. More precisely, a criminogenic situation is the moment when an offender faces this opportunity, but the crime has not yet been committed. The formation of criminogenic situations facilitated by the interaction and interdependence of three elements: criminal propensity, criminal social environment and deviant lifestyle. Thus, prolific delinquency cannot be adequately explained without accounting for the interaction between individual and contextual risk. The overall objective of this dissertation is to demonstrate the importance of a model based on the interaction between individual and contextual risk to explain the prolific delinquency of some offenders. To accomplish this objective, one hundred and fifty-five offenders, under the responsibility of Services Correctionels du Québec and four Centres Jeunesse, completed an evaluation through self-administered questionnaires. The first objective of this study was to describe and compare, in Chapter Three, the delinquent nature of the offenders in our sample. Our results revealed that our sample of offenders is similar to that of other samples of delinquents; we found this with respect to the nature of their delinquency, and in particular, the volume, diversity and severity of their crimes. Indeed, the majority of the participants reported a small volume of crimes against a person and property. A small group distinguished themselves with a very high lambda (13.1% of offenders in the sample are responsible for 60.3 % of all crimes reported). Additionally, more than four out of five offenders reported having committed at least one crime against a person and one crime against property. Moreover, 50 % reported having committed crimes in at least four subcategories. Finally, although the offenders in our sample have a relatively low IGC (gravity scale) mean (median = 77), nearly 40 % of the offenders reported having committed at least one of the two most serious crimes identified in this study (discharging firearm and robbery). The second specific objective was to explore, in Chapter four, the interaction between personal characteristics, social environment and the lifestyle of offenders which may lead to criminogenic situation. People with a higher propensity to crime tend to be surrounded by other criminalized people and have a more idle lifestyle. The criminalized social environment tends to also influence the lifestyle of these offenders. Thus, the interdependence between these three elements can lead to criminogenic situations and can create a climate conducive to the emergence of prolific delinquency. The last specific objective of this dissertation, covered in Chapter Five, is to analyze the impact of factors leading to situational crime on the nature of the delinquency. Analyses of multiple linear regression and regression trees highlighted the contribution of personal characteristics, social environment and lifestyle in explaining the nature of the crime. On the one hand, regression analyses (additive models) suggest that all the elements leading to situational crime make a unique contribution to the explanation of delinquency. However, on the other hand, regression trees allowed us to better understand the interaction between the elements which underlie prolific delinquency. For example, a lower position on certain items may be offset by a higher position on others. Moreover, the accumulation of risk factors which lead to situational crime does not happen in a linear fashion. These conclusions are supported by the proportions of explained variance which were higher for the regression trees than for the multiple linear regressions. In conclusion, focusing simply on one element (the person and their criminal propensity or the context and its opportunities) or on their combination in a simply additive manner does not represent the reality of criminal phenomenon. This dissertation therefore serves to highlight the importance of considering the interaction between the individual risk and the contextual risk in explaining prolific delinquency.

L’utilisation de réseaux de neurones artificiels pour divers types de traitements d’information bio-inspirés est une technique de plus en plus répandue dans le domaine de l’intelligence artificielle. Leur fonctionnement diffère avantageusement de celui des ordinateurs conventionnels en permettant une plus grande parallélisation des calculs, ce qui explique pourquoi autant d’efforts sont déployés afin de réaliser une plate-forme matérielle dédiée à leur simulation. Pour ce projet, une architecture matérielle flexible simulant efficacement un réseau de neurones à décharges est présentée. Celle-ci se distingue des architectures existantes notamment parce qu’elle utilise une approche de simulation à événements discrets et parce qu’elle permet une détection efficace des événements simultanés. Ces caractéristiques en font une plate-forme de choix pour la simulation de réseaux de neurones à décharges de plus de 100 000 neurones où un niveau important de synchronie des décharges neuronales est atteint. Afin d’en démontrer les performances, une application en traitement d’images utilisant cette architecture a été réalisée sur FPGA. Cette application a permis de démontrer que la structure proposée pouvait simuler jusqu’à 2[indice supérieur 17] neurones et traiter des dizaines de millions d’événements par secondes lorsque cadencé à 100 MHz.

Face à l’évolution technologique rapide des produits, l’innovation incrémentale des nouveaux produits, et la mobilité du personnel le plus expérimenté, les entreprises cherchent à formaliser et à capitaliser leurs expériences et les savoir-faire des acteurs d’entreprise en vue d’une réutilisation ultérieure. Afin de répondre à cette problématique, l’approche du raisonnement à partir de cas conversationnel (RàPCC) est une réponse potentielle à la question de la capitalisation et de la réutilisation des connaissances. Notre recherche s’intéresse aux méthodes permettant de piloter le retour d’expérience (RETEX) appliqué à la résolution de problèmes techniques. Notre méthodologie pour créer un système d’aide au diagnostic des pannes est divisée en quatre phases : la description d’événements, l’élaboration de l’ensemble des solutions apportées aux pannes, la mise en place d’une aide au diagnostic grâce aux arbres de défaillances et la mise en place d’un système informatique. Afin d’extraire les connaissances tacites et les formaliser, nous avons créé des protocoles de décision dans le but d’aider l’expert à résoudre un problème industriel. Nous avons donc proposé une formulation et l’élaboration de cas conversationnels dans le domaine du diagnostic. Ces cas doivent être stockés dans une base de cas. Afin de valider notre proposition méthodologique, nous avons réalisé la phase expérimentale dans une entreprise industrielle de l’Est de la France. Nous proposons finalement une maquette informatique conçue pour l’entreprise. Cette maquette permet de réaliser un diagnostic des pannes en créant des cas dans une base de cas pour une réutilisation ultérieure / Faced with the fast technological development of products, incremental innovation of new products, and the mobility of their most experienced staff, companies are seeking to formalize and capitalize on the experiences and know-how of their personnel in order to reuse them later. To deal with these problems, the conversational case based reasoning (CCBR) approach is a potential answer to the question of capitalization and reuse of knowledge. Our research focuses on methods to manage experience feedback (EF). We are placed in the field of experience feedback applied to technical problem solving. Our methodology for creating aided failure diagnosis systems is divided into four phases: the events description, the development of all solutions to failures, the arrangement of a diagnostic aid through fault trees and setting up a computer system. We based our work on the fault tree approach in order to extract tacit knowledge and its formalization. Our objective was to create decision protocols in order to assist the expert in solving an industrial problem. Therefore, we have proposed a formulation and development of conversational cases in diagnosis. These cases must be memorised in a database of cases. To validate our proposal methodology, we have carried out the experimental phase in an industrial company in eastern France. This experiment allowed us to validate our work and highlight its advantages and limitations. Finally, we propose a computer model designed for the company. This model enables failure diagnosis by creating the case in a case base for later utilization

Cette thèse tire les enseignements de la zone Euro qui représente la phase la plus avancée de l’intégration économique au sein de l’Union Européenne. Cependant, force est de constater que la zone euro affiche des lacunes en termes de mécanismes d’ajustement alternatifs. Ainsi malgré les avancées considérables, cette intégration économique et institutionnelle semble insuffisante pour absorber les chocs asymétriques sur les États. Nous avons utilisé diverses approches (baromètres de convergence, classification par arbre de décision et modèle de Merton) pour évaluer l’efficacité des politiques économiques au sein de l’UEMOA. Nous avons étudié, à partir de données empiriques allant de 1994 à 2015, l’hétérogénéité des principaux agrégats macroéconomiques entre les pays de la zone et leurs évolutions dans le temps. Contrairement aux attentes, des différences existent encore entre les pays. Selon l’objectif de politique macroéconomique mesuré (croissance économique, inflation, chômage), nos résultats révèlent que les changements dans les performances des groupes constitués sont expliqués soit par des migrations entre les groupes, soit par les changements à l’intérieur des groupes. Finalement, nos investigations montrent que l’élargissement à la CEDEAO amplifie ces divergences. Nos résultats montrent enfin une bonne performance de la règle de Taylor comparativement à l’inflation cible depuis 2003. Cette règle serait une "conduite de base" adaptable à la politique de la future banque centrale après avoir levé la difficulté à déterminer les valeurs de référence de l’équation dans ces espaces économiques hétérogènes. / This paper draws lessons from the Eurozone which represents the most advanced stage of economic integration in the European Union. However the alternative adjustment mechanisms in place there prove to be insufficient to absorb asymmetric shocks endured by member states. We used various methods such as convergence barometers, decision tree classification, and Merton model in order to assess the effectiveness of the economic policies in place within the WAEMU . We studied, through empirical data from 1994 to 2015, the heterogeneity of the main macroeconomic aggregates between the countries of the area and it’s evolution over time. Contrary to expectations, discrepancies still exist between countries. In accordance with the goal of macroeconomic policy measured, our results reveal that either the effects of migration between groups, or the changes in performance within groups give an account of the changes in performance inside groups. Our investigations eventually brings to light that the expansion to the ECOWAS amplifies the divergences.Lastly, our results show that the Taylor rule has been well put to use in comparison to targeted inflation since 2003. This rule can be regarded as a "basic rule" adaptable to the policy of the future central bank after having lifted the difficulty in determining the reference values in these heterogeneous economic areas.

Les deux problèmes majeurs considérés dans cette thèse : le b-coloration problème et le graphe emballage problème. 1. Le b-coloration problème : Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. EL Sahili et Kouider demandent s'il est vrai que chaque graphe d-régulier G avec le périmètre au moins 5 satisfait b(G) = d + 1. Blidia, Maffray et Zemir ont montré que la conjecture d'El Sahili et de Kouider est vraie pour d ≤ 6. En outre, la question a été résolue pour les graphes d-réguliers dans des conditions supplémentaires. Nous étudions la conjecture d'El Sahili et de Kouider en déterminant quand elle est possible et dans quelles conditions supplémentaires elle est vrai. Nous montrons que b(G) = d + 1 si G est un graphe d-régulier qui ne contient pas un cycle d'ordre 4 ni d'ordre 6. En outre, nous fournissons des conditions sur les sommets d'un graphe d-régulier G sans le cycle d'ordre 4 de sorte que b(G) = d + 1. Cabello et Jakovac ont prouvé si v(G) ≥ 2d3 - d2 + d, puis b(G) = d + 1, où G est un graphe d-régulier. Nous améliorons ce résultat en montrant que si v(G) ≥ 2d3 - 2d2 + 2d alors b(G) = d + 1 pour un graphe d-régulier G. 2. Emballage de graphe problème : Soit G un graphe d'ordre n. Considérer une permutation σ : V (G) → V (Kn), la fonction σ* : E(G) → E(Kn) telle que σ *(xy) = σ *(x) σ *(y) est la fonction induite par σ. Nous disons qu'il y a un emballage de k copies de G (dans le graphe complet Kn) s'il existe k permutations σi : V (G) → V (Kn), où i = 1, …, k, telles que σi*(E(G)) ∩ σj (E(G)) = ɸ pour i ≠ j. Un emballage de k copies d'un graphe G est appelé un k-placement de G. La puissance k d'un graphe G, noté par Gk, est un graphe avec le même ensemble de sommets que G et une arête entre deux sommets si et seulement si le distance entre ces deux sommets est au plus k. Kheddouci et al. ont prouvé que pour un arbre non-étoile T, il existe un 2-placement σ sur V (T). Nous introduisons pour la première fois le problème emballage marqué de graphe dans son graphe puissance / Two problems are considered in this thesis: the b-coloring problem and the graph packing problem. 1. The b-Coloring Problem : A b-coloring of a graph G is a proper coloring of the vertices of G such that there exists a vertex in each color class joined to at least a vertex in each other color class. The b-chromatic number of a graph G, denoted by b(G), is the maximum number t such that G admits a b-coloring with t colors. El Sahili and Kouider asked whether it is true that every d-regular graph G with girth at least 5 satisfies b(G) = d + 1. Blidia, Maffray and Zemir proved that the conjecture is true for d ≤ 6. Also, the question was solved for d-regular graphs with supplementary conditions. We study El Sahili and Kouider conjecture by determining when it is possible and under what supplementary conditions it is true. We prove that b(G) = d+1 if G is a d-regular graph containing neither a cycle of order 4 nor of order 6. Then, we provide specific conditions on the vertices of a d-regular graph G with no cycle of order 4 so that b(G) = d + 1. Cabello and Jakovac proved that if v(G) ≥ 2d3 - d2 + d, then b(G) = d + 1, where G is a d-regular graph. We improve this bound by proving that if v(G) ≥ 2d3 - 2d2 + 2d, then b(G) = d+1 for a d-regular graph G. 2. Graph Packing Problem : Graph packing problem is a classical problem in graph theory and has been extensively studied since the early 70's. Consider a permutation σ : V (G) → V (Kn), the function σ* : E(G) → E(Kn) such that σ *(xy) = σ *(x) σ *(y) is the function induced by σ. We say that there is a packing of k copies of G into the complete graph Kn if there exist k permutations σ i : V (G) → V (Kn), where i = 1,…, k, such that σ*i (E(G)) ∩ σ*j (E(G)) = ɸ for I ≠ j. A packing of k copies of a graph G will be called a k-placement of G. The kth power Gk of a graph G is the supergraph of G formed by adding an edge between all pairs of vertices of G with distance at most k. Kheddouci et al. proved that for any non-star tree T there exists a 2-placement σ on V (T). We introduce a new variant of graph packing problem, called the labeled packing of a graph into its power graph

Au cours de ce travail, nous nous intéressons aux limites d'échelle de deux classes de cartes. Dans un premier temps, nous regardons les quadrangulations biparties de genre strictement positif g fixé et, dans un second temps, les quadrangulations planaires à bord dont la longueur du bord est de l'ordre de la racine carrée du nombre de faces. Nous voyons ces objets comme des espaces métriques, en munissant leurs ensembles de sommets de la distance de graphe, convenablement renormalisée. Nous montrons qu'une carte prise uniformément parmi les cartes ayant n faces dans l'une de ces deux classes tend en loi, au moins à extraction près, vers un espace métrique limite aléatoire lorsque n tend vers l'infini. Cette convergence s'entend au sens de la topologie de Gromov--Hausdorff. On dispose de plus des informations suivantes sur l'espace limite que l'on obtient. Dans le premier cas, c'est presque sûrement un espace de dimension de Hausdorff 4 homéomorphe à la surface de genre g. Dans le second cas, c'est presque sûrement un espace de dimension 4 avec une frontière de dimension 2, homéomorphe au disque unité de R^2. Nous montrons en outre que, dans le second cas, si la longueur du bord est un petit~o de la racine carrée du nombre de faces, on obtient la même limite que pour les quadrangulations sans bord, c'est-à-dire la carte brownienne, et l'extraction n'est plus requise. / In this work, we discuss the scaling limits of two particular classes of maps. In a first time, we address bipartite quadrangulations of fixed positive genus g and, in a second time, planar quadrangulations with a boundary whose length is of order the square root of the number of faces. We view these objects as metric spaces by endowing their sets of vertices with the graph metric, suitably rescaled.We show that a map uniformly chosen among the maps having n faces in one of these two classes converges in distribution, at least along some subsequence, toward a limiting random metric space as n tends to infinity. This convergence holds in the sense of the Gromov--Hausdorff topology on compact metric spaces. We moreover have the following information on the limiting space. In the first case, it is almost surely a space of Hausdorff dimension 4 that is homeomorphic to the genus g surface. In the second case, it is almost surely a space of Hausdorff dimension 4 with a boundary of Hausdorff dimension 2 that is homeomorphic to the unit disc of R^2. We also show that in the second case, if the length of the boundary is little-o of the square root of the number of faces, the same convergence holds without extraction and the limit is the same as for quadrangulations without boundary, that is the Brownian map.

La plupart des réseaux de capteurs sans fill d’aujourd’hui fonctionne sur le protocole CSMA/CA. Fournir la qualité de service (QdS) dans un tel réseau est un problème difficile compte tenu de la dynamique du réseau et des contraintes en termes de ressources (énergie et mémoire). Dans cette thèse, sans changer le socle commun du CSMA/CA, nous avons proposé des mécanismes auto-adaptatifs qui permettent de gérer la QdS "best-effort" pour des applications nécessitant de la différenciation de services. Trois mécanismes sont proposés : CoSenS pour "Collecting then Sending burst Scheme", P-CoSenS qui a joute la gestion de priorités à CoSenS, et S-CoSenS qui a joute la dimension énergie à CoSenS. La dynamique du réseau est prise en compte grâce à l’auto-adaptation de périodes de collecte et de transmission en rafale. Il est à souligner que le mécanisme CoSenS permet non seulement d’améliorer les performances de CSMA/CA mais aussi de surmonter la difficulté d’ordonnancer les trafics entrant dans un nœud (routeur) car chaque paquet entrant est immédiatement retransmis vers la sortie. En effet, grâce à la pério de de collecte, les paquets entrants sont mis en file d’attente, rendant ainsi possible d’ordonnancer différemment les paquets selon leur priorité (P-CoSenS). Enfin, le compromis énergie/performance est pris en compte dans S-CoSenS. Selon l’état de l’environnement surveillé, le réseau peut se trouver dans une période où circule un trafic non urgent et souvent faible pendant laquelle il est judicieux de minimiser la consommation d’énergie et une pério de de trafic important pendant laquelle le réseau doit transporter des données urgentes pour suivre une situation alarmante de plus près. Comme CoSenS, S-CoSenS permet de s’auto-adapter dynamiquement en fonction de ces situations. L’ensemble de nos propositions est validé par simulations et CoSenS est implémenté sur une plateforme de réseau de capteurs. / Nowadays, most of wireless sensor networks use CSMA/CA protocol. Providing quality of service (QoS) support in such networks is a difficult problem because of the network dynamics and the high constraints in terms of resources like energy and memory. In this thesis and without changing the basic access protocol, CSMA/CA, we developed auto-adaptive mechanisms for best-effort QoS targeted to applications requiring differentiation services. Three mechanisms are proposed; CoSenS for "Collecting then Sending burst Scheme" which enhances the performances of CSMA/CA, P-CoSenS for "Priority CoSenS" which adds priority management to CoSenS and S-CoSenS for "S-CoSenS" which tackles energy efficiency using CoSenS. We emphasize that CoSenS mechanism not only enhances the performance of CSMA/CA in terms of throughput, end-to-end delay and successful transmission rates but enables also the implementation of scheduling policies; since the router collects and queues paquets before retransmitting them, it has a complete knowledge about them and can then schedule them efficiently (P-CoSenS). S-CoSenS tackles the energy/throughput tradeoff. In fact, the state of a network varies according to the monitored environment. The network may be at some times lightly loaded with non urgent traffic and at other times highly loaded with urgent traffic generated by nodes in order to monitor a happening phenomenon more closely and hence take the best decision. In the former case, the network must save energy. In the latter case, it must provide bandwidth. S-CoSenS auto-adapts its sleeping and active periods according the incoming traffic. Our propositions are validated by simulations and CoSenS is implemented on a wireless sensor platform

Soit D un digraphe simple (sans cycle orienté de longueur 2 ). En 1990, P. Seymour a conjecturé que D a un sommet v avec un second voisinage extérieur au moins aussi grand que son (premier) voisinage extérieur [1]. Cette conjecture est connue sous le nom de la conjecture du second voisinage du Seymour (SNC). Cette conjecture, si elle est vraie, impliquerait, un cas spécial plus faible (mais important) de la conjecture de Caccetta et Häggkvist [2] proposé en 1978 : tout digraphe D avec un degré extérieur minimum au moins égale à jV (D)j=k a un cycle orienté de longueur au plus k. Le cas particulier est k = 3, et le cas faible exige les deux : le degré extérieur minimum et le degré intérieur minimum de D sont au moins égaux à jV (D)j=k. La conjecture de Seymour restreinte au tournoi est connue sous le nom de conjecture de Dean [1]. En 1996, Fisher [3] a prouvé la conjecture de Dean en utilisant un argument de probabilité. En 2003, Chen, Shen et Yuster [4] ont démontré que tout digraphe a un sommet v tel que d+(v) _ d++(v) où =0.657298..... est l'unique racine de l'équation 2x3 + x2 - 1 = 0. En 2000, Havet et Thomassé [5] ont donné une preuve combinatoire de la conjecture de Dean, en utilisant un outil appelé l'ordre médian. Ils ont démontré que le dernier sommet d'un tel ordre a toujours un second voisinage extérieur au moins aussi grand que son voisinage extérieur. En 2007, Fidler et Yuster [6] ont utilisé l'ordre médian et un autre outil qui s'appelle le digraphe de dépendance afin de prouver la conjecture de Seymour pour tout digraphe D ayant un degré minimum jV (D)j 2. Ils l'ont montré pour tout tournoi où manque un autre sous-tournoi. El Sahili a conjecturé que pour tout D, il existe un completion T de D et un ordre médian de T tel que le denier sommet a un second voisinage extérieur au moins aussi grand que son voisinage extérieur (EC). Il est clair que, EC implique SNC. Cependant, EC propose une méthode afin de résoudre la SNC. En général, on oriente les non arcs de D de manière appropriée, afin d'obtenir un tournoi T et on essaie de trouver un sommet particulier (le denier sommet d'un ordre médian) avec la propriété désirée. Clairement, grâce aux résultats de [5] et [6], la EC est valable pour tournoi, et tout tournoi où manque un autre sous-tournoi. Nous allons vérifier EC pour tout digraphe D ayant un degré minimum jV (D)j 2. Alors, EC est vraie pour tout digraphe où la SNC est déjà connue d'être vraie non trivialement. Nous sommes aussi intéressés à la version pondérée de SNC et EC. En réalité, Fidler et Yuster [6] ont utilisé les digraphes de dépendance comme un outil supplémentaire et le fait que la SNC pondérée est vraie pour les tournois afin de prouver la SNC pour tout digraphe D ayant un degré minimum1 jV (D)j 2. Nous allons définir le digraphe de dépendance de façon plus générale et qui convient à n'importe quel digraphe. Nous allons utiliser le digraphe de dépendance et l'ordre médian comme des outils dans nos contributions à cette conjecture. Suivant la méthode proposée par la EC, nous démontrons la version pondérée de EC, et par conséquent la SNC, pour les classes des digraphes suivants : Digraphes où manque une étoile généralisée, soleil, étoile, ou un graphe complété. En outre, nous prouvons la EC, et par conséquent la SNC, pour digraphes où manque un peigne et digraphe où manque un graphe complet moins 2 arêtes indépendantes ou moins les arêtes d'une cycle de longueur 5. Par ailleurs, nous prouvons la EC, et par conséquent la SNC, pour les digraphes où manque n étoiles disjointes, sous certaines conditions sur les deux degrés minimum du digraphe de dépendance. Des conditions plus faible sont exigées dans le cas n = 1; 2; 3. Dans certains cas, on trouve au moins deux sommets avec la propriété désirée. / Let D be a digraph without digons (directed cycles of length 2). In 1990, Seymour [1] conjectured that D has a vertex whose first out-neighborhood is at most as large as its second out-neighborhood. Such a vertex is said to have the second neighborhood property (SNP). This conjecture is known as the second neighborhood conjecture (SNC). This conjecture, if true, would imply a weakening of a particular case (but important) of a long standing conjecture proposed by Caccetta and H aggkvist in 1978, which states that every digraph D with minimum out-degree at least jV (D)j=k has a directed cycle of length at most k. The special case is when k = 3 and the weakening requires both minimum out-degree and minimum in-degree at least jV (D)j=k [2]. Seymour's conjecture restricted to tournaments is known as Dean's conjecture [1]. In 1996, Fisher [3] gave a probabilistic proof to Dean's conjecture. In 2003 Chen, Shen and Yuster [4] proved that every digraph contains a vertex v such that d+(v) _ d++(v), where = 0:657298::: is the unique real root of the equation 2x3 + x2 1 = 0. In 2000, another proof of Dean's conjecture was given by Havet and Thomassé using a tool called median order [5]. They proved that the last vertex of this order, called a feed vertex, has second out-neighborhood at least as large as its first out-neighborhood. Median order is found to be a useful tool not only for the class of tournaments but for other classes of digraphs. In 2007, Fidler and Yuster [6] used also median orders to prove Seymour's conjecture for the class of digraphs with minimum degree jV (D)j 2 (i.e. D is a digraph missing a matching) and tournaments minus another subtournament. El Sahili conjectured that for every digraph D there is a completion T of D and a median order of T whose feed vertex has the SNP in D. Clearly, El Sahili's conjecture (EC) implies SNC. However, as one can observe, EC suggests a method (an approach) for solving the SNC, which we will call the completion approach. In general, following this approach, we orient the missing edges of D in some 'proper' way, to obtain a tournament T. Then we consider a particular feed vertex (clearly, it has the SNP in T) and try to prove that it has the SNP in D as well. Clearly, the result of Havet and Thomassé shows that EC is true for tournaments and the result of Fidler and Yuster [6] shows that EC holds for tournaments minus another subtournament. We will verify EC for the class 1 of tournaments missing a matching. So EC is verified for all the classes of digraphs where the SNC is known to hold non trivially. We will be interested also in the weighted version of EC and SNC. In reality, Fidler and Yuster [6] used dependency digraphs as a supplementary tool for proving the SNC for digraphs missing a matching and the fact that the weighted SNC holds for tournaments. We define dependency digraphs in a more general way, which is suitable to any digraph, and use them in our contribution to Seymour's conjecture. We also use the median order as a tool in our contribution. Using these two tools, and following the completion approach, we prove the weighted version of EC, and consequently the SNC, for several classes of digraphs: Digraphs missing a generalized star, sun, star or a complete graph. In addition, we prove EC, and consequently the SNC for digraphs missing a comb, and digraphs whose missing graph is a complete graph minus two independent edges or the edges of a cycle of length five. Moreover, we prove it for digraphs missing n disjoint stars under some conditions. Weaker conditions are required for n = 1; 2; 3. In some cases, we exhibit at least two vertices with the SNP.

Le routage dans Internet est basé sur des tables dites de routage, formées de blocs d’adresses IP. Cependant, la construction et la maintenance de telles tables de routage nécessitent l’utilisation de protocoles complexes qui ne passent pas à l’échelle en termes de mémoire et d’utilisation CPU. De plus, l’expérience montre que le plan d’adressage IP est insuffisant, car la sémantique d’une adresse IP est à la fois un identificateur et un localisateur. Dans nos travaux, nous proposons un système de réseau recouvrant pair-à-pair libre de toute contrainte topologique et utilisant des coordonnées virtuelles prises dans le plan hyperbolique nommé CLOAK (Covering Layer Of Abstract Knowledge en anglais). Les schémas de routages locaux basés sur des coordonnées virtuelles extraites du plan hyperbolique ont suscité un intérêt considérable ces dernières années. Dans cette thèse, nous proposons une nouvelle approche pour saisir le potentiel de la géométrie hyperbolique. L’objectif est de construire un système extensible et fiable pour créer et gérer des réseaux recouvrants dans Internet. Le système est implémenté comme une infrastructure pair-à-pair structuré basé sur les protocoles de la couche transport entre les pairs. Quant à l’organisation des données dans l’espace virtuel, nous employons la réplication pour améliorer la disponibilité et l’accessibilité des objets de l’overlay potentiellement instable. Nous avons implémenté et évalué différentes méthodes de réplication (réplication radiale, réplication circulaire).A l’aide de simulations, nous évaluons notre proposition à travers un certain nombre de métriques et nous montrons que les réseaux recouvrants pair-à-pair basés sur la géométrie hyperbolique ont de bonnes performances par rapport aux autres DHT existantes tout en introduisant flexibilité et robustesse dans les réseaux recouvrants dynamiques. / Internet routing is based on forwarding tables populated by blocks of IP addresses. However, the construction and maintenance of such tables require the use of complex routing protocols that are typically not scalable in terms of memory and CPU usage. Moreover, experience shows that the IP addressing plane is insufficient due to the semantic of an IPaddress being both an identifier and a locator. In this paper, we propose a P2P overlay system of freed topology and using virtual coordinates taken from the hyperbolic plane named CLOAK(Covering Layer Of Abstract Knowledge en anglais). Local knowledge routing schemes based on virtual coordinates taken from the hyperbolic plane have attracted considerable interest in recent years. In this thesis we propose a new approach for seizing the power of the hyperbolic geometry. We aim at building a scalable and reliable system for creating and managing overlay networks over the Internet. The system is implemented as a structured peer-to-peer infrastructure based on the transport layer connections between the peers. Concerning data organisation in the virtual space, we use replication strategy for improve overlay objects disponibilty and accessibility in context potentially unstable. We have implemented and evaluated various replication methods (radial replication, circular replication). Using simulations, we assess our proposal across a certain number of metric and show that overlay Peer-to-Peer network based on the hyperbolic geometry have good performances in comparison with other existent DHT while introducing suppleness and robustness in the dynamic overlay network.

No description available.