Spelling suggestions: "subject:"digraphes"" "subject:"bigraphes""
501 |
Etude de la réorganisation de la connectivité cérébrale au repos dans la sclérose en plaques / Assessment of brain functional reorganization of resting-state networks in patients with Multiple SclerosisFaivre, Anthony 11 July 2014 (has links)
L'IRMf de repos qui repose sur l'étude des fluctuations du signal BOLD chez un sujet au repos, pourrait permettre d'explorer les mécanismes du handicap dans la Sclérose En Plaques (SEP). En utilisant l'IRMf de repos, ce travail a eu pour objectif de caractériser la réorganisation fonctionnelle des patients atteints de SEP et ses liens avec leur handicap.Nous avons d'abord réalisé une étude combinant IRMf de repos et d'activation au stade précoce de la SEP et montré l'existence d'une corrélation entre la plasticité fonctionnelle du système moteur des patients au repos et durant la tâche. Nous avons ensuite montré l'existence d'une augmentation diffuse du niveau de connectivité fonctionnelle des patients présentant une SEP débutante, corrélée à leurs performances. Dans la 3ème partie, nous avons objectivé l'existence d'un déclin dynamique de la topologie fonctionnelle corrélée à la progression du handicap grâce à une étude longitudinale utilisant la théorie des graphes. Enfin, nous avons démontré que le gain fonctionnel obtenu par la rééducation chez les patients SEP était corrélé à une augmentation de connectivité fonctionnelle du réseau cérébral par défaut et central exécutif et de densité de substance grise dans le cortex frontal.Nos travaux montrent l'existence d'une réorganisation cérébrale fonctionnelle complexe et dynamique dans la SEP qui pourrait correspondre à des phénomènes compensatoires, dont le déclin avec l'évolution de la maladie participe à la progression du handicap. Ils démontrent l'intérêt de l'IRMf de repos pour la compréhension des substrats anatomo-fonctionnels du handicap dans la SEP et comme potentiel instrument futur d'évaluation thérapeutique. / Resting-state fMRI (rs-fMRI) may provide important clue concerning disability in multiple sclerosis (MS) by exploring the spontaneous BOLD fluctuations at rest in the whole brain. The aim of this work is to depict the functional reorganization of resting-state networks in MS patients and to assess its potential relationships with disability.In the first part, we performed an fMRI protocol combining a rs-fMRI and task-associated fMRI during a motor task, in a group of early MS patients. This study evidenced a direct association between reorganization of connectivity at rest and during activation in the motor system of patients. In the second rs-fMRI study, we evidenced an increased of the global level of connectivity in most of the rs-networks, strongly associated with the level of disability of patients. In the third part, we evidenced in a 2-year longitudinal study using graph theoretical approach that MS patients exhibited a dynamical alteration of functional brain topology that significantly correlated with disability progression. In the last part, we evidenced that the transient clinical improvement following physical rehabilitation in MS patients is associated with reversible plasticity mechanisms located in the default mode network, the central executive network and in the left fronto-orbital cortex. These works evidence that MS patients exhibit a complex and dynamical functional reorganization of rs-networks, significantly associated with disability progression. This PhD thesis confirms that rs-fMRI is a relevant biomarker of pathophysiology leading to disability in MS and represents a promising tool for therapeutic assessment of MS patients in the future.
|
502 |
Approche de gestion orientée service pour l'Internet des objets (IoT) considérant la Qualité de Service (QoS) / Service oriented approach for the Internet of Things (IoT) Quality of Service (QoS) awareGarzone, Guillaume 30 November 2018 (has links)
L’Internet des Objets (IoT) est déjà omniprésent aujourd’hui : domotique, bâtiments connectés ou ville intelligente, beaucoup d’initiatives et d’innovations sont en cours et à venir. Le nombre d’objets connectés ne cesse de croître à tel point que des milliards d’objets sont attendus dans un futur proche.L’approche de cette thèse met en place un système de gestion autonomique pour des systèmes à base d’objets connectés, en les combinant avec d’autres services comme par exemple des services météo accessibles sur internet. Les modèles proposés permettent une prise de décision autonome basée sur l’analyse d’évènements et la planification d’actions exécutées automatiquement. Des paramètres comme le temps d’exécution ou l’énergie consommée sont aussi considérés afin d’optimiser les choix d’actions à effectuer et de services utilisés. Un prototype concret a été réalisé dans un scénario de ville intelligente et de bus connectés dans le projet investissement d'avenir S2C2. / The Internet of Things (IoT) is already everywhere today: home automation, connected buildings or smart city, many initiatives and innovations are ongoing and yet to come. The number of connected objects continues to grow to the point that billions of objects are expected in the near future.The approach of this thesis sets up an autonomic management architecture for systems based on connected objects, combining them with other services such as weather services accessible on the Internet. The proposed models enable an autonomous decision making based on the analysis of events and the planning of actions executed automatically. Parameters such as execution time or consumed energy are also considered in order to optimize the choices of actions to be performed and of services used. A concrete prototype was realized in a smart city scenario with connected buses in the investment for future project: S2C2.
|
503 |
Algorithmes adaptatifs et efficaces de partage de ressources radio pour les communications de type MTC : cas de coexistence H2H/M2M / Adaptive and efficient radio resource sharing schemes for machine type communications underlying cellular networksHamdoun, Safa 27 June 2017 (has links)
L'Internet des objets (IoT) fait référence à la croissance continue des réseaux d'objets du quotidien qui s'interconnectent entre eux ou avec d'autres systèmes Internet via les capteurs sans fil qui y sont attachés. L'IoT promet un futur où des milliards de terminaux intelligents seront connectés et gérés via une gamme de réseaux de communication et de serveurs basés dans le cloud, permettant ainsi l'apparition d'un large spectre d’applications de surveillance et de contrôle. Les communications machine-à-machine (M2M), également connues sous le nom de “Machine-Type-Communication” (MTC) par les réseaux cellulaires, constituent une technologie clé permettant d'activer partiellement l'IoT. Les communications M2M sont un nouveau paradigme qui facilite la connectivité omniprésente entre une myriade de dispositifs sans ou avec intervention humaine limitée. La demande croissante de connectivité a mis au défi les opérateurs de réseau à concevoir de nouveaux algorithmes d'allocation de ressources radio pour gérer l'échelle massive des communications MTC.Contrairement aux technologies d'accès radio traditionnelles, adaptées aux communications usuelles, dites de humain-à-humain (H2H), l'objectif de cette thèse est de développer de nouvelles techniques de partage de ressources radio efficaces et adaptatives pour les MTC dans un scénario de coexistence H2H/M2M. Dans le cadre de cette thèse, notre première contribution consiste en la proposition d'un système d'accès multiple adapté pour résoudre à la fois les problèmes liés à la rareté des ressources radio, à la scalabilité et à la surcharge de la station de base (BS). À cette fin, nous proposons de décomposer les opérations de communication en les groupant. Ainsi, les MTC correspondent à des communications locales en liaison montante entre des dispositifs connus sous le nom de “Machine-Type-Device” (MTD), et un cluster head appelé “Machine-Type- Head” (MTH). Nous examinons ainsi la nécessité d'agréger la technologie M2M et le “dispositif-à-dispositif” (D2D), considéré comme composante majeure des réseaux cellulaires évolutifs du futur. Nous modélisons le problème de partage de ressources radio entre les MTDs et les utilisateurs H2H sous la forme d’un graphe biparti et développons un algorithme de partage de ressources radio pour MTC basé sur les graphes afin d’atténuer les interférences co-canal et donc améliorer l'efficacité du réseau. En outre, une solution semi-distribuée de faible complexité est développée pour atténuer la surcharge de communication d'une solution centralisée que nous proposons également. Ensuite, dans une deuxième contribution de cette thèse, nous nous intéressons à examiner comment les dispositifs M2M peuvent partager les ressources radio disponibles sans pour autant dégrader les performances des applications H2H. Par conséquent, nous proposons un système de partage de ressources efficace en terme de spectre et de puissance. Nous introduisons à l'algorithme de partage de ressources radio basé sur les graphes une fonction adaptative de contrôle de puissance utilisant l'un des deux mécanismes suivants : un contrôleur proportionnel intégral dérivé (PID) et la logique floue. Enfin, comme troisième contribution de cette thèse, nous développons un système de partage de ressources radio efficace en terme de puissance et entièrement distribué pour les MTC. Nous utilisons la théorie des jeux et modélisons le problème de partage de ressources par un jeu hybride où les dispositifs M2M rivalisent pour les ressources radio et basculent de façon opportuniste entre un jeu non-coopératif et un jeu coopératif. Une évaluation des performances des solutions dérivées dans le contexte des réseaux LTE est menée. Les résultats des simulations montrent que les solutions proposées ont un impact significatif sur la maximisation de l'efficacité de l'utilisation du spectre, l'atténuation de l'effet négatif sur les services H2H et la prolongation de la durée de vie des batteries des MTDs / The Internet-of-Things (IoT) refers to the ever-growing network of everyday objects that interconnect to each other or to other Internet-enabled systems via wireless sensors attached to them. IoT envisions a future where billions of smart devices will be connected and managed through a range of communication networks and cloud-based servers, enabling a variety of monitoring and control applications. Machine-to-Machine (M2M) communications supported by cellular networks, also known as Machine-Type-Communications (MTC) acts as a key technology for partially enabling IoT. M2M communications is a new technology paradigm that facilitates the ubiquitous connectivity between a myriad of devices without requiring human intervention. The surge in the demand for connectivity has further challenged network operators to design novel radio resource allocation algorithms at affordable costs to handle the massive scale of MTC.Different from current radio access technologies tailored to traditional Human- to-Human (H2H) communications, the goal of this thesis is to provide novel efficient and adaptive radio resource sharing schemes for MTC under a H2H/M2M coexistence scenario. We first provide a suitable multiple access scheme to address the joint spectrum scarcity, scalability and Base Station (BS) overload issues. Toward this end, we design a group-based operation where MTC corresponds to local uplink communications between Machine-Type-Devices (MTDs), which represent a specific type of devices that do not rely on the presence of a human interface, and a Machine-Type-Head (MTH). This latter plays the role of a cluster head that relays the information to the BS. We thus address the need to aggregate M2M and Device-to-Device (D2D) technology, as one of the major components of the future evolving cellular networks. Having said that, we first propose in this thesis to model the radio resource sharing problem between MTDs and H2H users as a bipartite graph and develop a novel interference-aware graph-based radio resource sharing algorithm for MTC so as to mitigate the co-channel interference and thus enhance network efficiency. Moreover, low-complexity semi-distributed solution is investigated to alleviate the communication overhead of a centralized solution that we propose as well. Then, as a second contribution, we examine how M2M devices can share the available radio resources in cellular networks with no or limited impact on existing H2H services. Consequently, we propose a joint spectrally and power efficient radio resource sharing scheme. Convinced by the strength of the bipartite graph modeling for the resource sharing problem between H2H users and M2M devices, we empower the graph-based radio resource sharing algorithm with a novel adaptive power control feature using one of two following mechanisms: the Proportional Integral Derivative (PID) controller and the fuzzy logic. Finally, in our third contribution of this thesis, we develop a power efficient and fully-distributed radio resource sharing framework for MTC underlying cellular networks. We use game theory and model the resource sharing problem as an efficient hybrid-game where M2M devices compete for radio resources and switch opportunistically, as M2M devices are selfish in nature, between non-cooperative and cooperative games. The different derived solutions are extended to existing cellular networks, and extensive simulation studies in the context of LTE are conducted. The various simulation results show that the proposed solutions can significantly increase the efficiency of the spectrum usage, mitigate the negative effect on H2H services and save the battery life of M2M devices
|
504 |
Contributions to a fast and robust object recognition in images / Contributions à une reconnaissance d'objet rapide et robuste en imagesRevaud, Jérôme 27 May 2011 (has links)
Dans cette thèse, nous présentons tout d'abord une contribution visant à pallier ce problème de robustesse pour la reconnaissance d'instances, puis une extension directe de cette contribution à la reconnaissance et la localisation de classes d'objets. Dans un premier temps, nous avons développé une méthode inspiré de l'appariement de graphe (i.e. graph matching) afin de traiter le problème de la reconnaissance rapide d'instances d'objets spécifiques dans des conditions bruitées. Cette méthode permet de rajouter facilement un nombre quelconque d’autres types de caractéristiques locales (e.g. contours, textures…) moins affectées par le bruit tout en contournant le problème de la normalisation et sans pénaliser la vitesse de détection. Nos expériences sur plusieurs bases de test ont montré la pertinence de notre approche. Notre approche est globalement légèrement moins robuste à l'occultation que les approches existantes, mais elle produit des performances supérieures aux approches standard en conditions bruitées. Dans un second temps, nous avons développé une approche pour la détection de classes d'objets dans le même esprit que celui du sac de mots visuels. Pour cela, nous utilisons nos cascades de micro-classifieurs pour reconnaître des mots visuels plus distinctifs que les mots basés simplement sur des points d'intérêts. L'apprentissage se divise en deux parties: dans un premier temps, nous générons des cascades de micro-classifieurs servant à reconnaître des parties locales des images modèles ; puis dans un second temps, nous utilisons un classifieur afin de modéliser la frontière de décision entre les images de classe et celles de non-classe. Nous montrons que l'association de mots classiques (à partir de points d'intérêts) et de nos mots plus distincts produit une amélioration significative des performances pour un temps de calcul assez faible. / In this thesis, we first present a contribution to overcome this problem of robustness for the recognition of object instances, then we straightly extend this contribution to the detection and localization of classes of objects. In a first step, we have developed a method inspired by graph matching to address the problem of fast recognition of instances of specific objects in noisy conditions. This method allows to easily combine any types of local features (eg contours, textures ...) less affected by noise than keypoints, while bypassing the normalization problem and without penalizing too much the detection speed. Unlike other methods based on a global rigid transformation, our approach is robust to complex deformations such as those due to perspective or those non-rigid inherent to the model itself (e.g. a face, a flexible magazine). Our experiments on several datasets have showed the relevance of our approach. It is overall slightly less robust to occlusion than existing approaches, but it produces better performances in noisy conditions. In a second step, we have developed an approach for detecting classes of objects in the same spirit as the bag-of-visual-words model. For this we use our cascaded micro-classifiers to recognize visual words more distinctive than the classical words simply based on visual dictionaries. Training is divided into two parts: First, we generate cascades of micro-classifiers for recognizing local parts of the model pictures and then in a second step, we use a classifier to model the decision boundary between images of class and those of non-class. We show that the association of classical visual words (from keypoints patches) and our disctinctive words results in a significant improvement. The computation time is generally quite low, given the structure of the cascades that minimizes the detection time and the form of the classifier is extremely fast to evaluate.
|
505 |
Modélisation intégrée produit-process à l'aide d'une approche de métamodélisation reposant sur une représentation sous forme de graphes : Application à la fabrication additive / Product-process integrated meta-modeling using a graph-based approach : Application to additive manufacturingMokhtarian, Hossein 27 March 2019 (has links)
La fabrication additive (FA) a initié un changement de paradigme dans le secteur de la conception et de la fabrication des produits grâce à ses capacités uniques. Cependant, l'intégration des technologies de fabrication additive dans la productique traditionnelle doit permettre d'assurer une production fiable et une qualité reproductible des pièces. Dans cette optique, la modélisation et la simulation jouent un rôle essentiel pour améliorer la compréhension de la nature complexe et multi-physique des procédés de fabrication additive. De plus, l’intégration simultanée de différents modèles multi-physiques et de la prise en compte du procédé utilisé et de la pièce constituent toujours un défi pour la modélisation de ces technologies. L’objectif final de cette recherche est de développer et d’appliquer une approche de modélisation permettant une modélisation intégrée de la fabrication additive. Cette thèse analyse le processus de développement du produit et présente une méthodologie innovante intitulée ‘Dimensional Analysis Conceptual Modeling’ (DACM) pour modéliser les produits et les procédés de fabrication aux différentes étapes de conception. La méthode a été développée pour permettre la simulation de modèles multi-physiques. Elle intègre également une recherche systématique de faiblesses et de contradictions dans une première évaluation des solutions potentielles au problème. La méthodologie développée est appliquée dans plusieurs études de cas afin de présenter des modèles intégrant les processus de fabrication additive et les pièces à fabriquer. Les résultats montrent que la méthodologie DACM permet de modéliser distinctement et simultanément le produit et le processus de fabrication. Cette méthodologie permet aussi d'intégrer les modèles théoriques et expérimentaux déjà existants. Elle contribue à la conception pour la fabrication additive et aide le concepteur à anticiper les limites des procédés et de la conception plus tôt dans les premières étapes de développement du produit. En particulier, cela permet de prendre les bonnes décisions selon les différentes possibilités d'optimiser la conception des pièces et le paramétrage des machines de fabrication additive pour aboutir à la solution la plus adaptée. La méthode permet également de détecter la nécessité de reconcevoir des machines existantes en détectant les faiblesses de celles-ci. Cette thèse montre que la méthode DACM peut être potentiellement utilisée comme une approche de méta-modélisation pour la fabrication additive.Mots-clés: Fabrication Additive, Conception Pour la Fabrication Additive, Modélisation Intégrée, Développement de Produit, Dimensional Analysis Conceptual Modeling Framework / Additive manufacturing (AM) has created a paradigm shift in product design and manufacturing sector due to its unique capabilities. However, the integration of AM technologies in the mainstream production faces the challenge of ensuring reliable production and repeatable quality of parts. Toward this end, Modeling and simulation play a significant role to enhance the understanding of the complex multi-physics nature of AM processes. In addition, a central issue in modeling AM technologies is the integration of different models and concurrent consideration of the AM process and the part to be manufactured. Hence, the ultimate goal of this research is to present and apply a modeling approach to develop integrated modeling in additive manufacturing. Accordingly, the thesis oversees the product development process and presents the Dimensional Analysis Conceptual Modeling (DACM) Framework to model the product and manufacturing processes at the design stages of product development process. The Framework aims at providing simulation capabilities and systematic search for weaknesses and contradictions to the models for the early evaluation of solution variants. The developed methodology is applied in multiple case studies to present models integrating AM processes and the parts to be manufactured. This thesis results show that the proposed modeling framework is not only able to model the product and manufacturing process but also provide the capability to concurrently model product and manufacturing process, and also integrate existing theoretical and experimental models. The DACM framework contributes to the design for additive manufacturing and helps the designer to anticipate limitations of the AM process and part design earlier in the design stage. In particular, it enables the designer to make informed decisions on potential design alterations and AM machine redesign, and optimized part design or process parameter settings. DACM Framework shows potentials to be used as a metamodeling approach for additive manufacturing.
|
506 |
Essays on econometric modelling of temporal networks / Essais sur la modélisation économétrique des réseaux temporelsIacopini, Matteo 05 July 2018 (has links)
La théorie des graphes a longtemps été étudiée en mathématiques et en probabilité en tant qu’outil pour décrire la dépendance entre les nœuds. Cependant, ce n’est que récemment qu’elle a été mise en œuvre sur des données, donnant naissance à l’analyse statistique des réseaux réels.La topologie des réseaux économiques et financiers est remarquablement complexe: elle n’est généralement pas observée, et elle nécessite ainsi des procédures inférentielles adéquates pour son estimation, d’ailleurs non seulement les nœuds, mais la structure de la dépendance elle-même évolue dans le temps. Des outils statistiques et économétriques pour modéliser la dynamique de changement de la structure du réseau font défaut, malgré leurs besoins croissants dans plusieurs domaines de recherche. En même temps, avec le début de l’ère des “Big data”, la taille des ensembles de données disponibles devient de plus en plus élevée et leur structure interne devient de plus en plus complexe, entravant les processus inférentiels traditionnels dans plusieurs cas. Cette thèse a pour but de contribuer à ce nouveau champ littéraire qui associe probabilités, économie, physique et sociologie en proposant de nouvelles méthodologies statistiques et économétriques pour l’étude de l’évolution temporelle des structures en réseau de moyenne et haute dimension. / Graph theory has long been studied in mathematics and probability as a tool for describing dependence between nodes. However, only recently it has been implemented on data, giving birth to the statistical analysis of real networks.The topology of economic and financial networks is remarkably complex: it is generally unobserved, thus requiring adequate inferential procedures for it estimation, moreover not only the nodes, but the structure of dependence itself evolves over time. Statistical and econometric tools for modelling the dynamics of change of the network structure are lacking, despite their increasing requirement in several fields of research. At the same time, with the beginning of the era of “Big data” the size of available datasets is becoming increasingly high and their internal structure is growing in complexity, hampering traditional inferential processes in multiple cases.This thesis aims at contributing to this newborn field of literature which joins probability, economics, physics and sociology by proposing novel statistical and econometric methodologies for the study of the temporal evolution of network structures of medium-high dimension.
|
507 |
Innovation technologique duale : une analyse en termes d'influence et de cohérence / Dual technological innovation : an analysis in terms of influence and coherenceMeunier, Francois-Xavier 15 September 2017 (has links)
L’objet de cette thèse est de traiter l’innovation technologique duale en proposant une approche systémique du concept de dualité et en développant une méthodologie d’évaluation du potentiel dual des technologies. Le travail empirique repose sur l’analyse systématique de la production de connaissances au sein des grandes entreprises ayant une activité de défense. La première partie traite des transferts technologiques entre la sphère civile et la sphère de défense. Le concept de dualité y est abordé au travers du Système Dual d’Innovation (SDI) qui embrasse dans un cadre cohérent l’ensemble des composantes de la dualité (technologique, mais aussi organisationnelle et marchande, etc.). L’étude de la diffusion de la connaissance au sein du SDI permet de mesurer le potentiel dual des technologies. Dans la seconde partie, ce cadre d’analyse est appliqué aux plus grandes entreprises innovantes du domaine de la défense. L’analyse des portefeuilles de brevets de ces firmes révèle des interdépendances qui défissent des ensembles de connaissances synergétiques nommés Systèmes de Connaissances Technologiques (SCT). C’est le potentiel dual des 26 SCT ainsi définis qui est évalué par la suite à l’aide des outils de la cohérence technologique d’une part et ceux de la dominance économique d’autre part. / The purpose of this thesis is the treatment of technological innovation with a systemic approach of the concept of duality and a methodology for evaluating the dual-use potential of technologies. The empirical work is based on the systematic analysis of the knowledge production within large companies with a defense activity. The first part deals with technological transfers between the civil area and the defense area. The concept of duality is looked through the Dual Innovation System (DIS), which embraces in a coherent framework all the components of duality (technological, but also organizational and market, etc.). The study of knowledge diffusion within the SDI allows the assessment of dual-use potential of technologies. In the second part, this framework of analysis is applied to the largest innovative companies in the field of defense. The analysis of the patent portfolios of these firms reveals the interdependencies that define the synergistic knowledge sets known as Technological Knowledge Systems (TKS). It is the dual-use potential of the 26 SCT as defined, which is subsequently evaluated using technological coherence tools and those of economic dominance.
|
508 |
Heuristic Algorithms for Graph Coloring Problems / Algorithmes heuristiques pour des problèmes de coloration de graphesSun, Wen 29 November 2018 (has links)
Cette thèse concerne quatre problèmes de coloration de graphes NPdifficiles, à savoir le problème de coloration (GCP), le problème de coloration équitable (ECP), le problème de coloration des sommets pondérés et le problème de sous-graphe critique (k-VCS). Ces problèmes sont largement étudiés dans la littérature, non seulement pour leur difficulté théorique, mais aussi pour leurs applications réelles dans de nombreux domaines. Étant donné qu'ils appartiennent à la classe de problèmes NP-difficiles, il est difficile de les résoudre dans le cas général de manière exacte. Pour cette raison, cette thèse est consacrée au développement d'approches heuristiques pour aborder ces problèmes complexes. Plus précisément, nous développons un algorithme mémétique de réduction (RMA) pour la coloration des graphes, un algorithme de recherche réalisable et irréalisable (FISA) pour la coloration équitable et un réalisable et irréalisable (AFISA) pour le problème de coloration des sommets pondérés et un algorithme de suppression basé sur le retour en arrière (IBR) pour le problème k-VCS. Tous les algorithmes ont été expérimentalement évalués et comparés aux méthodes de l'état de l'art. / This thesis concerns four NP-hard graph coloring problems, namely, graph coloring (GCP), equitable coloring (ECP), weighted vertex coloring (WVCP) and k-vertex-critical subgraphs (k-VCS). These problems are extensively studied in the literature not only for their theoretical intractability, but also for their real-world applications in many domains. Given that they belong to the class of NP-hard problems, it is computationally difficult to solve them exactly in the general case. For this reason, this thesis is devoted to developing effective heuristic approaches to tackle these challenging problems. We develop a reduction memetic algorithm (RMA) for the graph coloring problem, a feasible and infeasible search algorithm (FISA) for the equitable coloring problem, an adaptive feasible and infeasible search algorithm (AFISA) for the weighted vertex coloring problem and an iterated backtrack-based removal (IBR) algorithm for the k-VCS problem. All these algorithms were experimentally evaluated and compared with state-of-the-art methods.
|
509 |
Grands graphes et grands arbres aléatoires : analyse du comportement asymptotique / Large Random Graphs and Random Trees : asymptotic behaviour analysisMercier, Lucas 11 May 2016 (has links)
Cette thèse est consacrée à l'étude du comportement asymptotique de grands graphes et arbres aléatoires. Le premier modèle étudié est un modèle de graphe aléatoire inhomogène introduit par Bo Söderberg. Un chapitre de ce manuscrit est consacré à l'étude asymptotique de la taille des composantes connexes à proximité de la fenêtre critique, en le reliant à la longueur des excursions d'un mouvement brownien avec dérive parabolique, étendant les résultats obtenus par Aldous. Le chapitre suivant est consacré à un processus de graphes aléatoires proposé par Itai Benjamini, défini ainsi : les arêtes sont ajoutées indépendamment, à taux fixe. Lorsqu'un sommet atteint le degré k, toutes les arêtes adjacentes à ce sommet sont immédiatement supprimées. Ce processus n'est pas croissant, ce qui empêche d'utiliser directement certaines approches usuelles. L'utilisation de limites locales permet de montrer la présence (resp. l'absence) d'une composante géante à certaines étapes dans le cas k>=5 (resp. k<=3). Dans le cas k=4, ces résultats permettent de caractériser la présence d'une composante géante en fonction du caractère surcritique ou non d'un processus de branchement associé. Dans le dernier chapitre est étudiée la hauteur d'un arbre de Lyndon associé à un mot de Lyndon choisi uniformément parmi les mots de Lyndon de longueur n, prouvant que cette hauteur est approximativement c ln n, avec c=5,092... la solution d'un problème d'optimisation. Afin d'obtenir ce résultat, nous couplons d'abord l'arbre de Lyndon à un arbre de Yule, que nous étudions ensuite à l'aide de techniques provenant des théories des marches branchantes et des grandes déviations. / This thesis is dedicated to the study of the asymptotic behavior of some large random graphs and trees. First is studied a random graph model introduced by Bo Söderberg in 2002. One chapter of this manuscript is devoted to the study of the asymptotic behavior of the size of the connected components near the critical window, linking it to the lengths of excursion of a Brownian motion with parabolic drift. The next chapter talks about a random graph process suggested by Itai Benjamini, defined as follows: edges are independently added at a fixe rate. Whenever a vertex reaches degree k, all adjacent edges are removed. This process is non-increasing, preventing the use of some commonly used methods. By using local limits, in the spirit of the PWIT, we were able to prove the presence (resp. absence) of a giant component at some stages of the process when k>=5 (resp. k<=3). In the case k=4, these results allows to link the presence (resp. absence) of a giant component to the supercriticality (resp. criticality or subcriticality) of an associated branching process. In the last chapter, the height of random Lyndon tree is studied, and is proven to be approximately c ln n, in which c=5.092... the solution of an optimization problem. To obtain this result, we couple the Lyndon tree with a Yule tree, then studied with the help of branching walks and large deviations
|
510 |
Quasi transformées de Riesz, espaces de Hardy et estimations sous-gaussiennes du noyau de la chaleur / Quasi Riesz transforms, Hardy spaces and generalized sub-Gaussian heat kernel estimatesChen, Li 24 April 2014 (has links)
Dans cette thèse nous étudions les transformées de Riesz et les espaces de Hardy associés à un opérateur sur un espace métrique mesuré. Ces deux sujets sont en lien avec des estimations du noyau de la chaleur associé à cet opérateur. Dans les Chapitres 1, 2 et 4, on étudie les transformées quasi de Riesz sur les variétés riemannienne et sur les graphes. Dans le Chapitre 1, on prouve que les quasi transformées de Riesz sont bornées dans Lp pour 1<p<2. Dans le Chapitre 2, on montre que les quasi transformées de Riesz est aussi de type faible (1,1) si la variété satisfait la propriété de doublement du volume et l'estimation sous-gaussienne du noyau de la chaleur. On obtient des résultats analogues sur les graphes dans le Chapitre 4. Dans le Chapitre 3, on développe la théorie des espaces de Hardy sur les espaces métriques mesurés avec des estimations différentes localement et globalement du noyau de la chaleur. On définit les espaces de Hardy par les molécules et par les fonctions quadratiques. On montre tout d'abord que ces deux espaces H1 sont les mêmes. Puis, on compare l'espace Hp défini par par les fonctions quadratiques et Lp. On montre qu'ils sont équivalents. Mais on trouve des exemples tels que l'équivalence entre Lp et Hp défini par les fonctions quadratiques avec l'homogénéité t2 n'est pas vraie. Finalement, comme application, on montre que les quasi transformées de Riesz sont bornées de H1 dans L1 sur les variétés fractales. Dans le Chapitre 5, on prouve des inégalités généralisées de Poincaré et de Sobolev sur les graphes de Vicsek. On montre aussi qu'elles sont optimales. / In this thesis, we mainly study Riesz transforms and Hardy spaces associated to operators. The two subjects are closely related to volume growth and heat kernel estimates. In Chapter 1, 2 and 4, we study Riesz transforms on Riemannian manifold and on graphs. In Chapter 1, we prove that on a complete Riemannian manifold, the quasi Riesz transform is always Lp bounded on for p strictly large than 1 and no less than 2. In Chapter 2, we prove that the quasi Riesz transform is also weak L1 bounded if the manifold satisfies the doubling volume property and the sub-Gaussian heat kernel estimate. Similarly, we show in Chapter 4 the same results on graphs. In Chapter 3, we develop a Hardy space theory on metric measure spaces satisfying the doubling volume property and different local and global heat kernel estimates. Firstly we define Hardy spaces via molecules and via square functions which are adapted to the heat kernel estimates. Then we show that the two H1 spaces via molecules and via square functions are the same. Also, we compare the Hp space defined via square functions with Lp. The corresponding Hp space for p large than 1 defined via square functions is equivalent to the Lebesgue space Lp. However, it is shown that in this situation, the Hp space corresponding to Gaussian estimates does not coincide with Lp any more. Finally, as an application of this Hardy space theory, we proved that quasi Riesz transforms are bounded from H1 to L1 on fractal manifolds. In Chapter 5, we consider Vicsek graphs. We prove generalised Poincaré inequalities and Sobolev inequalities on Vicsek graphs and we show that they are optimal.
|
Page generated in 0.3587 seconds