To see the other types of publications on this topic, follow the link: Théorie topologique des graphes.
Dissertations / Theses on the topic 'Théorie topologique des graphes'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Théorie topologique des graphes.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Delanoue, Nicolas. "Algorithmes numériques pour l'analyse topologique : Analyse par intervalles et théorie des graphes." Phd thesis, Université d'Angers, 2006. http://tel.archives-ouvertes.fr/tel-00340999.
Full textAbstract:
Le travail présenté dans cette thèse concerne d'une part, l'étude qualitative d'ensembles et d'autre part, celui de l'étude de la stabilité d'un système dynamique. Les méthodes numériques proposées combinent le calcul par intervalles et la théorie des graphes.De nombreux problèmes, comme l'étude de l'espace des configurations d'un robot, se ramènent à une étude qualitative d'ensembles. Ici, la ``taille'' de l'ensemble importe peu, ce qui compte, c'est sa ``topologie''. Les méthodes proposées calculent des invariants topologiques d'ensembles. Les ensembles considérés sont décrits à l'aide d'inégalités $\mathcal{C}^{\infty}$. L'idée maîtresse est de décomposer un ensemble donné en parties contractiles et d'utiliser l'homologie de \v Cech.
La seconde partie de la thèse concerne l'étude de point
asymptotiquement stables des systèmes dynamiques (linéaires ou non). Plus largement, on propose une méthode pour approcher le bassin d'attraction d'un point asymptotiquement stable. Dans un premier temps, on utilise la théorie de Lyapunov et le calcul par intervalle
pour trouver effectivement un voisinage inclus dans le bassin d'attraction d'un point prouvé asymptotiquement stable. Puis, on combine, une fois de plus, la théorie des graphes et les méthodes d'intégration d'équations différentielles ordinaires pour améliorer ce voisinage et ainsi construire un ensemble inclus dans le bassin
d'attraction de ce point.
2
Bellet, Thomas. "Transformations de graphes pour la modélisation géométrique à base topologique." Thesis, Poitiers, 2012. http://www.theses.fr/2012POIT2261/document.
Full textAbstract:
De nombreux domaines comme le jeu vidéo, l’architecture, l’ingénierie ou l’archéologie font désormais appel à la modélisation géométrique. Les objets à représenter sont de natures diverses, et leurs opérations de manipulation sont spécifiques. Ainsi, les modeleurs sont nombreux car tous spécialisés à leur domaine d’application. Or ils sont à la fois chers à développer, souvent peu robustes, et difficilement extensibles. Nous avons proposé dans la thèse l’approche alternative suivante :– fournir un langage dédié à la modélisation qui permet de définir les opérations quelque soit le domaine d’application ; dans ce langage, les objets sont représentés avec le modèle topologique des cartes généralisées, dont nous avons étendu la définition aux plongements ; les opérations sont elles définies par des règles de transformation de graphes, issues de la théorie des catégorie ;– garantir les opérations définies dans le langage à l’aide de conditions de cohérence ; une opération dont la définition vérifie ces conditions ne produit pas d’anomalie ;– développer un noyau de modeleur générique qui interprète ce langage ; les opérations définies sont directement appliquées dans le modeleur, sans implantation dans un langage de programmation ; l’outil assure également la vérification automatique des conditions du langage pour prévenir un utilisateur lorsqu’il propose une opération incohérente.Le langage et le modeleur développés se sont révélés performants à la fois en termes de temps de développement et en termes de temps machine. L’implantation d’une nouvelle opération par une règle ne prend que quelques minutes à l’aide des conditions du langage, au contraire de l’approche classiGeometric modeling is now involved in many fields such as: video games, architecture, engineering and archaeology. The represented objects are very different from one field to another, and so are their modeling operations. Furthermore, many specific types of modeling software are designed for high programing costs, but with a relatively low rate of effectiveness.The following is an alternative approach:– we have conceived a dedicated language for geometric modeling that will allow us to define any operation of any field; objects in this language are defined with the topological model of generalized maps, this definition has been extended to the embedding informations; here the operations are defined as graph transformation rules which originate from the category theory;– we have ensured operation definitions with consistency conditions; these operations that satisfy those conditions do not generate anomalies; – we have designed generic modeling software to serve as an interpreter of this language; the operation definitions are directly applied without the need for more programing; the software also automatically checks the language conditions and warns the user if he designs a non-consistent operation.The provided language and software prove to be efficient, and all for a low programing cost. Designing a new operation takes only minutes thanks to the language conditions, as opposed to hours of programming and debugging with the past approach
3
Colin, Fabrice. "Applications de la topologie algébrique en théorie des graphes." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1996. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/mq21733.pdf.
Full text
4
Dussaux, Valere. "Spécifications partielles de dessin de graphe : Étude logique et combinatoire." Bordeaux 1, 2002. http://www.theses.fr/2002BOR12527.
Full textAbstract:
Les travaux présentés dans cette thèse concernent les spécifications de dessins de graphe. On introduit la notion de carte partielle dont deux cas extrêmes sont le graphe (sans indication de dessin) et la carte (combinatoire) qui spécifie complètement le dessin (à déformation près) d'un graphe connexe. Des problèmes de réalisabilité de dessin sans croisement d'arêtes, sur le plan, sur des surfaces plus complexes, sont étudiés des points de vue logique et combinatoire au moyen de la structure de carte partielle. Dans la formulation de ceux-ci intervient le problème de l'ordonnancement cyclique. On obtient des caractérisations par configurations exclues de relations cycliquement consistantes, de certaines classes de cartes partielles et des cartes dessinables sur une surface donnée. Ces caractérisations sont exprimables dans la logique du second ordre monadique.
5
Soto, Gomez Mauricio Abel. "Quelques propriétés topologiques des graphes et applications à internet et aux réseaux." Paris 7, 2011. http://www.theses.fr/2011PA077228.
Full textAbstract:
Ce travail étudie des propriétés topologiques des graphes et leurs applications aux réseaux de communications, notamment aux graphes représentant structure d'Internet. Dans un premier temps, on s'intéresse à l'arborescence des graphes par l'étude de deux paramètres : l'hyperbolicité et la largeur arborescente (treewidth). Pour l' hyperbolicité, on analyse sa relation avec d'autres paramètres de graphes et on montre que certaines décompositions de graphes en permettent un calcul efficace. On calcule ces deux paramètres dans des instantanés d'Internet pour différents niveaux hiérarchiques et différentes périodes de temps. On y apporte des interprétations structurelles et algorithmiques pour les valeurs obtenues. On aborde ensuite le problème de partitionnement de graphes (clustering) sous l'angle de la modularité, paramètre qui mesure la qualité d'un partitionnement, largement utilisé dans la littérature. On analyse la modularité du point de vue théorique et son comportement asymptotique pour certaines familles de graphes. Enfin, on s'intéresse à une approche comminatoire de la théorie des files d'attente où les injections de paquets sont effectuées par un adversaire. On propose une généralisation de ce modèle par l'introduction de différentes classes de requêtesThis thesis focuses on topological properties of graphs and their application on communication networks, specifically on graphs reflecting Internet structure. We first look how far from a tree a graph may be by the study of two parameters: hyperbolicity and treewidth. For hyperbolicity, we analyse the relation with others graph parameters, we also show that some graph decompositions allow its efficient computation. We compute both parameters o Internet snapshots at different levels of granularity and time periods. We propose some structural and algorithmic consequences of obtained values. Then, we study the graph clustering problem from the perspective of modularity, which measures a clustering quality and is largely studied in the literature. We analyse modularity from a theoretical point of view and [describe] its asymptotic behaviour for some graph families. Finally, we deal with adversarial queueing theory, a combinatorial framework derived from classic queueing theory where injection process is und the control of an adversary. We propose a new model generalisation by considering request of distinct types
6
Beaudou, Laurent. "Autour de problèmes de plongements de graphes." Phd thesis, Université Joseph Fourier (Grenoble), 2009. http://tel.archives-ouvertes.fr/tel-00401226.
Full textAbstract:
Cette thèse s'articule autour de la notion de plongement de graphe. Un plongement de graphe consiste à envoyer les sommets d'un graphe dans une autre structure par une application qui conserve certaines propriétés à déterminer. Nous pouvons distinguer deux grandes familles de plongements. D'une part les plongements purement combinatoires qui envoient les éléments d'un graphe G dans un autre graphe H. La propriété la plus naturelle à conserver est la notion d'adjacence entre les sommets. Nous nous intéressons à la conservation d'une propriété supplémentaire : la distance entre les sommets. Nous caractérisons plusieurs familles de graphes se plongeant de cette façon dans les hypercubes ou les graphes de Hamming. Les plongements topologiques visent à représenter un graphe G sur une surface quelconque. Les sommets sont envoyés vers des points d'une surface et les arêtes vers des courbes continues entre ces points. Comment représenter un graphe afin de minimiser le nombre de croisements d'arêtes ? Nous nous posons ces questions à travers l'étude de la planarité et des nombres de croisements de certains graphes.
7
Benchettara, Nasserine. "Prévision de nouveaux liens dans les réseaux d'interactions bipartis : Application au calcul de recommandation." Paris 13, 2011. http://scbd-sto.univ-paris13.fr/secure/edgalilee_th_2011_benchettara.pdf.
Full textAbstract:
Dans cette thèse, nous étudions le problème de la prévision d'apparition de nouveaux liens dans les réseaux d'interactions. Nous nous intéressons en particulier aux réseaux dynamiques ayant une structure bipartite. Nous proposons un modèle de prévision de liens utilisant les techniques d'apprentissage automatique supervisé. Le problème de prévision de liens est considéré dans ce cas comme un problème de classification binaire. Notre approche applique un schéma de propositionnalisation où chaque paire de noeuds est décrite par un ensemble d'attributs représentant des mesures topologiques. Ces mesures sont calculées dans le graphe biparti et dans les graphes projetés qui en découlent. Nous montrons que ces nouvelles similarités dites " indirectes " apportent un gain d'information bénéfique par rapport aux seules similarités directes. Cette thèse apporte aussi de nouvelles solutions au problème de déséquilibre des données dû à la disproportion inhérente entre le nombre de liens qui peuvent se former et le nombre de liens qui se forment réellement. Nous proposons tout d'abord d'utiliser des méthodes de sous-échantillonnage informé pour réduire le déséquilibre. Une deuxième solution au niveau algorithmique consiste en une approche d'apprentissage semi-supervisé. Dans ce cas, le problème de prévision de liens est vu comme un problème d'apprentissage à partir d'un ensemble d'instances étiquetées (classe minoritaire) et un ensemble d'instances non-étiquetées (classe majoritaire). Nous montrons que cette nouvelle approche permet d'améliorer les performances du classifieur sur la classe minoritaire. Les différentes approches proposées sont appliquées sur les données réelles dans le cadre de deux applications : recommandation de collaborations académiques et recommandation de produits dans un site de vente de musique en ligneIn this work, we handle the problem of new link prediction in dynamic complex networks. We mainly focus on studying networks having a bipartite underlaying structure. We propose to apply a propositionnalization approach where each couple of nodes in the network is described by a set of topological measures. One first contribution in this thesis is to consider measures computed in the bipartite graph and also in the associated projected graphs. A supervised machine learning approach is applied. This approach though it gives some good results, suffers from the obvious problem of class skewness. We hence focus on handling this problem. Informed sub-sampling approaches are first proposed. A semi-supervised machine learning approach is also applied. All proposed approaches are applied and evaluated on real datasets used in real application of academic collaboration recommendation and product recommendation in an e-commerce site
8
Vlitas, Dimitrios. "Contribution à la théorie de Ramsey en dimension infinie." Paris 7, 2012. http://www.theses.fr/2012PA077240.
Full textAbstract:
Dans un article récent, S. Solecki a prouvé un théorème de Ramsey fini auto-dual qui donne d'une façon naturelle simultanément le théorème de Ramsey fini classique et le théorème de Graham-Rothschild. Dans le premier chapitre de cette thèse nous prouvons le théorème de Ramsey infini auto-dual correspondant, qui a similairement pour conséquence le théorème de de Ramsey infini classique et le théorème de Carlson-Simpson. Cela est réalise par une approche différente de celle de Solecki. Dans le second chapitre de cette thèse, nous étendons un résultat de K. Miliken. Étant donné un arbre U qui a un branchement fini uniforme mais une longueur infinie, une notion de famille uniforme de sous-arbre finis forts est introduite. Ensuite nous prouvons un résultat de classification de Ramsey pour les relations d'équivalence définies sur ces familles uniformes. Dans le troisème et dernier chapitre de cette thèse, nous complétons une tentative de H. Lefmann de montrer que les relations d'équivalence de Borel sur les sous-ensembles à n éléments de 2A{\omega}, qui respectent un type d'ordre, ont une base de Ramsey finieIn a recent paper S. Solecki proves a finite self dual Ramsey theorem that in a natural way gives simultaneously the classical finite Ramsey theorem and the Graham-Rothschild theorem. In the first chapter of this thesis we prove the corresponding infinite dimensional self dual theorem, giving similarly as a consequence the infinite classical Ramsey theorem and the Carlson-Simpson theorem. This is done by a different approach than that of Solecki. In the second chapter of the present thesis we extend a result of K. Milliken. Given a fixed tree U that has some finite uniform branching but is of infinite length, a notion of uniform family of finite strong subtrees is introduced. Then we prove a Ramsey classification result for equivalence relations defined on these uniform families. In the third and final chapter of the thesis, we complete the attempt of H. Lefmann to show that Borel equivalence relations on the n-element subsets of 2A{\omega}, that respect an order type, have a finite Ramsey basis
9
Bonis, Thomas. "Algorithmes d'apprentissage statistique pour l'analyse géométrique et topologique de données." Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLS459/document.
Full textAbstract:
Dans cette thèse, on s'intéresse à des algorithmes d'analyse de données utilisant des marches aléatoires sur des graphes de voisinage, ou graphes géométriques aléatoires, construits à partir des données. On sait que les marches aléatoires sur ces graphes sont des approximations d'objets continus appelés processus de diffusion. Dans un premier temps, nous utilisons ce résultat pour proposer un nouvel algorithme de partitionnement de données flou de type recherche de modes. Dans cet algorithme, on définit les paquets en utilisant les propriétés d'un certain processus de diffusion que l'on approche par une marche aléatoire sur un graphe de voisinage. Après avoir prouvé la convergence de notre algorithme, nous étudions ses performances empiriques sur plusieurs jeux de données. Nous nous intéressons ensuite à la convergence des mesures stationnaires des marches aléatoires sur des graphes géométriques aléatoires vers la mesure stationnaire du processus de diffusion limite. En utilisant une approche basée sur la méthode de Stein, nous arrivons à quantifier cette convergence. Notre résultat s'applique en fait dans un cadre plus général que les marches aléatoires sur les graphes de voisinage et nous l'utilisons pour prouver d'autres résultats : par exemple, nous arrivons à obtenir des vitesses de convergence pour le théorème central limite. Dans la dernière partie de cette thèse, nous utilisons un concept de topologie algébrique appelé homologie persistante afin d'améliorer l'étape de "pooling" dans l'approche "sac-de-mots" pour la reconnaissance de formes 3DIn this thesis, we study data analysis algorithms using random walks on neighborhood graphs, or random geometric graphs. It is known random walks on such graphs approximate continuous objects called diffusion processes. In the first part of this thesis, we use this approximation result to propose a new soft clustering algorithm based on the mode seeking framework. For our algorithm, we want to define clusters using the properties of a diffusion process. Since we do not have access to this continuous process, our algorithm uses a random walk on a random geometric graph instead. After proving the consistency of our algorithm, we evaluate its efficiency on both real and synthetic data. We then deal tackle the issue of the convergence of invariant measures of random walks on random geometric graphs. As these random walks converge to a diffusion process, we can expect their invariant measures to converge to the invariant measure of this diffusion process. Using an approach based on Stein's method, we manage to obtain quantitfy this convergence. Moreover, the method we use is more general and can be used to obtain other results such as convergence rates for the Central Limit Theorem. In the last part of this thesis, we use the concept of persistent homology, a concept of algebraic topology, to improve the pooling step of the bag-of-words approach for 3D shapes
10
Abouelaoualim, Abdelfattah. "EXPLORATION DES GRAPHES ARETES-COLOREES : TOPOLOGIE, ALGORITHMES, COMPLEXITE ET (NON)-APPROXIMABILITE." Phd thesis, Université Paris Sud - Paris XI, 2007. http://tel.archives-ouvertes.fr/tel-00281533.
Full textAbstract:
Dans la pratique, énormément de problèmes concrets peuvent être modélisés par un graphe. Par exemple, une carte géographique est typiquement un graphe dans lequel on serait amener à chercher des chemins courts entre les villes, ou à passer par toutes les routes ou toutes les villes.... Cela explique pourquoi la théorie des graphes est certainement le domaine le plus populaire des mathématiques discrètes malgré son jeune âge....
11
Angelier, Pierre. "Algorithmique des graphes de visibilité." Paris 7, 2002. http://www.theses.fr/2002PA077007.
Full text
12
Sandouk, Mohamed Zouheir. "Méthodes et algorithmes pour l'infographie : exploitation des propriétés topologiques et géométriques de la scène." Toulouse 3, 1990. http://www.theses.fr/1990TOU30156.
Full textAbstract:
L'objectif de ces travaux est d'ameliorer des outils de l'infographie et d'accelerer des algorithmes de visualisation et en particulier le lancer de rayons. Par une exploitation de la coherence topologique et spatiale, nous proposons des techniques appliquees a des differentes modelisations: 1) modelisation csg: il s'agit d'utiliser le maximum d'informations que peut contenir l'arbre csg. Ces informations, obtenues dans une etape de pre-traitement, servent a reduire le nombre total d'intersection rayon-primitives. Cette reduction s'effectue grace a deux phases d'optimisation: la premiere phase est l'optimisation par les englobants relatifs. La seconde est l'utilisation du graphe de connexion et la normalisation de l'arbre csg; 2) modelisation quelconque: il s'agit d'utiliser au maximum les proprietes contenues dans la geometrie de la scene en proposant une generalisation du lemme euclidien: par deux points passe une droite et une seule. Ces informations, obtenues dans une etape de pre-traitement, servent a reduire le nombre total d'intersection rayon-primitives. Cette idee de generalisation du lemme euclidien peut etre utilisee pour traiter d'autres problemes dans l'infographie. Nous avons envisage son utilisation, pour le choix d'une bonne vue. Nous presentons a la fin une approche analytique pour l'evaluation de l'efficacite des optimisations proposees
13
Poudret, Mathieu. "Transformations de graphes pour les opérations topologiques en modélisation géométrique - Application à l'étude de la dynamique de l'appareil de Golgi." Phd thesis, Université d'Evry-Val d'Essonne, 2009. http://tel.archives-ouvertes.fr/tel-00503818.
Full textAbstract:
Dans cette thèse, qui s'inscrit dans l'étude de la modélisation géométrique via les méthodes formelles, nous proposons un langage graphique à base de règles dédié à la description des opérations topologiques des cartes généralisées. Notre langage est fondé sur la théorie des transformations de graphes. Dans nos règles, les variables permettent d'abstraire les cellules topologiques (sommets, arêtes, faces, volumes, etc.) manipulées dans les opérations topologiques. Nous avons défini des critères syntaxiques sur les règles assurant que les objets obtenus par application des règles satisfont les contraintes de cohé- rence des cartes généralisées. La conception de ce langage a été motivée par l'étude de la dynamique de l'appareil de Golgi. Il est connu que dans cette organelle, la topologie des compartiments joue un rôle essentiel. Néanmoins, la structure globale de l'appareil de Golgi reste encore méconnue. Plusieurs hypothèses de fonctionnement sont ainsi avancées par les biologistes. Notre langage à base de règles fournit un cadre pour la simulation puis la comparaison de ces différentes hypothèses d'appareil de Golgi.
14
Abouelaoualim, Abdelfattah. "Exploration des graphes arêtes-colorées : topologie, algorithmes, complexité et (non)-approximabilité." Paris 11, 2007. https://tel.archives-ouvertes.fr/tel-00281533.
Full textAbstract:
Les graphes dont les arêtes sont coloriées par c>1 couleurs, avec c un entier donné, autrement dit les graphes c-arêtes-colorées, connaissent un nombre grandissant de champs d’applications notamment en biologie moléculaire et en technologie intégrée à très grande échelle sans oublier leur intérêt théorique puisqu’ils sont une généralisation des graphes orientés. Dans cette thèse nous explorons ces graphes pour extraire et étudier les structures (i. E. , les sous-graphes) dites proprement-arêtes-coloriées c'est-à-dire dans lesquelles chaque paire d’arêtes adjacentes sont de couleurs distinctes. Tout d’abord, nous avons jugé nécessaire de réserver la première partie de la thèse à un état de l’art qui présente les travaux les plus importants et couvre la majorité des questions traitées dans ce domaine depuis les années soixante. En suite, dans une deuxième partie, nous avons commencé par donner des caractérisations de certaines structures proprement-arêtes-coloriées telles que les chaînes et les cycles, et puis nous nous sommes orientés vers la construction des algorithmes, l’étude de l’aspect de la complexité et l’approximabilité d’une variété de structuresThe graphs which edges are colored with c>1 colors, with c is a given integer, in other words c-edge-colored graphs, have a growing number of fields of applications particularly in molecular biology and VLSI. Their theoretical motivation is obvious sine they are a generalization of digraphs. In the present work, we explore these graphs to extract and study structures (i. E. Subgraphs) called properly-edge-colored which every pair of adjacent edges differ in color. We start this work by a part introducing the most notable results in the literature and cover the majority of questions treated in this topic since the sixties. In the second part, first we give characterizations of certain properly-edge-colored structures such as paths and cycles. After that, we were interested by the construction of polynomial algorithms, the study of complexity and approximability aspect of a variety of structures
15
Wagner, Emmanuel. "On Khovanov-Rozansky homology of graphs and links." Université Louis Pasteur (Strasbourg) (1971-2008), 2007. https://publication-theses.unistra.fr/restreint/theses_doctorat/2007/WAGNER_Emmanuel_2007.pdf.
Full textAbstract:
Cette thèse est consacrée à la catégorification d'invariants polynomiaux d'entrelacs et de graphes. Pour tout entier strictement positif n, Khovanov et Rozansky ont introduit en 2004 une homologie bigraduée d'entrelacs, ainsi qu'une homologie de graphes planaires. Etant donné n, leur homologie d'entrelacs catégorifie la n-ième spécialisation du polynôme d'entrelacs HOMFLYPT et leur homologie de graphes planaires catégorifie un polynôme de graphes associé. Dans cette thèse, on étudie ces homologies et on généralise leur construction en introduisant une graduation supplémentaire. Tout d'abord, on généralise une formule de Jaeger pour les polynômes d'entrelacs aux polynômes de graphes planaires, ainsi qu'à l'homologie de graphes planaires; on étend ensuite l'homologie d'entrelacs de Khovanov-Rozansky aux graphes plongés. Puis on construit une homologie trigraduée d'entrelacs. Cette homologie recouvre l'homologie bigraduée d'entrelacs de Khovanov et Rozansky. Enfin, on donne des exemples, des applications et des généralisations de l'homologie trigraduée d'entrelacs. On développe des outils d'algèbre homologique qui permettent de calculer explicitement l'homologie trigraduée d'entrelacs pour des exemples et on considère des déformations de l'homologie trigraduée d'entrelacsThis thesis is devoted to the categorification of polynomial invariants of graphs and links. For any positive integer n, Khovanov and Rozansky introduced in 2004 a bigraded link homology, and an homology of planar graphs. Given n, their link homology categorifies the n-th specialization of the HOMFLY-PT polynomial and their homology of planar graphs categorifies an associated graph polynomial. In this thesis, we study these homology and generalize their constructions by introducing an additional grading. First, we generalize a formula of Jaeger for link polynomials to polynomials of planar graphs and associated homology of planar graphs; we extend also the link homology of Khovanov and Rozansky to embedded graphs. Then we construct a triply graded link homology. This homology recovers the bigraded link homology of Khovanov and Rozansky. Finally, we give examples, applications and generalizations of the triply graded link homology. We develop homological tools that permit to compute explicitly the triply graded link homology for some knots and we consider deformations of the triply graded link homology
16
Oujamaa, Lydia. "Evolution topologique des hubs dans l'état de conscience altérée post-traumatique : un marqueur de récupération fonctionnelle." Thesis, Université Grenoble Alpes, 2020. http://www.theses.fr/2020GRALS013.
Full textAbstract:
Ce travail doctoral s’inscrit dans le champ de la recherche translationnelle. Nous avonsvoulu explorer la plasticité cérébrale post-lésionnelle qui sous-tend la restauration de la conscience après un coma traumatique. L’étude de la connectivité fonctionnelle de repos, c’est à dire de la corrélation temporelle du signal BOLD (blood oxygenationlevel dependent) entre régions cérébrales, a été appliquée à une cohorte de 36 patients traumatisés crâniens graves sortant de réanimation. A cette date, les patients pouvaient se trouver en état de conscience altérée ou être conscients. Nous avons réalisé une étude transversale et longitudinale : une 1ère IRM fonctionnelle en condition de veille de repos était réalisée à la sortie des soins intensifs et une seconde après un séjour de un moisen rééducation post-réanimation. Ainsi, à l’aide de la méthode des graphes, nous avons exploré l’intérêt diagnostique et pronostique de la connectivité fonctionnelle lors de la réémergence de la conscience après coma traumatique.Nous avons centré notre analyse sur un index de perturbation des hubs qui traduitla redistribution des connexions fonctionnelles dans le graphe. Les hubs du réseau cérébral,qui physiologiquement concentrent le plus de connexions, ont été caractérisésavec plusieurs métriques d’intégration, de ségrégation et de centralité dans le transfertd’information.Nos résultats suggèrent qu’une perturbation de la topologie des hubs fonctionnels estobjectivement "cartographiable" et qu’elle est corrélée à l’évolution neurologique cliniqueaprès agression cérébrale. En effet, notre étude a montré que, chez le traumatisé crâniengrave adulte, ce marqueur de perturbation fonctionnelle du réseau cérébral est sensible,dans une analyse de groupe, à l’état de conscience (patients conscients vs en état deconscience altérée) et à sa restauration au cours du temps. L’index de perturbation deshubs est également sensible à une autre dimension clinique : la prédiction du handicap neurologique à 6 mois post-coma.La computation des données de connectivité en une méta-donnée, l’index de perturbationdes hubs de l’ensemble du réseau cérébral, permet d’aller plus loin qu’un modèle descriptif de la plasticité cérébrale après coma (d’altération ou de restitution de connectivité dans un ou plusieurs réseaux). Ainsi, la restitution de la capacité du cerveau à traiterde l’information locale dans les hubs fonctionnels serait nécessaire à la ré-émergence de la conscience après coma traumatique. Ce résultat est original car dans la littérature actuelle, basée sur les théories de l’espace de travail global et de l’intégration de l’information,l’atteinte traumatique cérébrale est modélisée comme une altération de laconnectivité à longue distance et donc de l’intégration fonctionnelle.Cette étude pilote était un pré-requis pour évaluer à l’avenir cet index de perturbation fonctionnelle cérébrale à l’échelle individuelle et objectiver la réponse thérapeutique(psychostimulants, électrostimulation cérébrale....) de patients en état de conscience altéréeThis work takes part in the field of translational research. Our aim was to explore thepost-lesional brain plasticity necessary to recover consciousness after a traumatic coma.The study of resting state functional connectivity, meaning the temporal correlation ofBOLD signal (blood oxygenation level dependent) between remote cerebral areas, wasapplied to severe traumatic brain injured (sTBI) patients.Using graph method, we explored the diagnosis and prognosis value of resting statefunctional connectivity during recovery of consciousness after a traumatic coma.Thirty six sTBI patients were studied in a cross sectional and a longitudinal design.We recorded a resting state functional MRI sequence while sTBI patients were eitherconscious or in altered state of consciousness when discharged from intensive care unit(ICU). A second fMRI was recorded after one month spent in a post-ICU rehabilitationunit.Our analysis focused on a hub disruption index (HDI) which expresses the reallocationof functional connections inside the graph. In the brain network, the hubs, which are definedas highly connected to the brain network in healthy subjects, have been characterizedwith integration, segregation and centrality metrics for information transfer.Our results suggest that the topological disruption of functional hubs is an objectivemapping of the brain network changes that correlates with post-TBI neurological recovery.Indeed, in our group analysis, the hub disruption index of the post TBI brainnetwork was sensitive to the state of consciousness and to its recovery during a onemonth follow-up. This index was also relevant to predict the level of disability 6 monthsafter injury.The computation of connectivity data in a metadata, the hub disruption index ofthe brain network, enhances the classical approach describing the post-traumatic brainplasticity as a loss and recovery of connectivity in one or several cortical networks. Therecovery of the brain network ability to compute local information in the functionalhubs could be necessary to recover consciousness after a traumatic coma. This resultis original as the recent litterature, based on the information integration theory andthe global workspace theory of consciousness, is considering severe TBI as a long rangeconnectivity disruption inducing a functional integration impairment.This pilot study was necessary prior to the assessment of the HDI on a single-subjectlevel and to quantifie the response of brain injured patients with disorder of consciousnessto several therapeutic options (psychostimulant drugs, electrical stimulation..)
17
Giorgetti, Alain. "Combinatoire bijective et énumérative des cartes pointées sur une surface." Phd thesis, Université de Marne la Vallée, 1998. http://tel.archives-ouvertes.fr/tel-00724977.
Full textAbstract:
Une carte est le plongement d'un graphe dans une surface, à un homéomorphisme près. Ainsi, une carte est un objet topologique énumérable, en fonction du nombre de ses sommets, de ses arêtes et de ses faces. Les cartes admettent des symétries internes qui rendent leur énumération difficile. On n'envisage dans ce travail que l'énumération des cartes pointées, le pointage supprimant toutes les symétries. Le nombre exact de cartes pointées sur une surface donnée n'est connu que pour les surfaces de petit genre, comme la sphère (genre 0), le tore ou le plan projectif (genre 1). En effet, la complexité des méthodes de calcul de ces nombres augmente rapidement avec le genre des surfaces. Un travail important de cette thèse a été de convertir l'une de ces méthodes de calcul en une preuve de l'existence d'une structure commune à toutes les séries génératrices de cartes pointées de genre non nul. Pour chaque surface orientable, on réduit le problème à la détermination d'un polynôme, dont le degré est majoré par une fonction simple du genre de la surface. Un résultat analogue est obtenu pour les cartes pointées sur les surfaces non orientables. Des conséquences pratiques et une implantation logicielle de tous ces résultats sont décrites. De nouvelles formules explicites d'énumération sont données. Indépendamment, une bijection géométrique nouvelle est exposée, entre certaines cartes 2-coloriables et les partitions de polygones, énumérées par les nombres de Schröder.
18
Ehounou, Joseph. "Algorithmes de graphes pour la découverte de la topologie d'un réseau énergétique par la connaissance de ses flots." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLV056/document.
Full textAbstract:
Dans les réseaux énergétiques, la connaissance des équipements, leurs emplacements et leursfonctions sont les prérequis à l’exploitation de l’infrastucture. En effet, tout opérateur disposed’une carte appelée schéma synoptique indiquant les connexions entre les équipements. À partirde cette carte, sont prises des décisions pour un fonctionnement optimal du réseau.Ce schéma synoptique peut être érronné parce que des opérations de maintenance sur le réseaun’auraient pas été retranscrites ou mal saisies. Et cela peut entrainer des coûts supplémentairesd’exploitation du réseau énergetique.Nous considérons le réseau électrique d’un Datacenter. Ce réseau est composé d’une topologiephysique modélisée par un DAG sans circuit et de mesures électriques sur ces arcs. La particularitéde ce réseau est que les mesures contiennent des erreurs et cette topologie est inconnue c’est-à-direles arcs sont connus mais les extrémités des arcs sont inconnues. Dans le cas où ces mesuressont correctes alors la corrélation des arcs induit la matrice d’adjacence du line-graphe du graphenon-orienté sous-jacent de notre DAG. Un line-graphe est un graphe dans lequel chaque sommet etson voisinage peuvent être partitionnés par une ou deux cliques et que chaque arête est couvertepar une clique. Cependant, avec la présence des erreurs de mesures, nous avons un graphe avecdes arêtes en plus ou en moins qui n’est pas nécessairement un line-graphe. Si ce graphe est unline-graphe alors il n’est pas le line-graphe de notre DAG. Notre problème est de découvrir cettetopologie en se basant sur ces mesures électriques.Nous débutons par une étude bibliographique des corrélations de mesures possibles afin dedéterminer celle qui est pertinente pour notre problème. Ensuite nous proposons deux algorithmespour résoudre ce problème. Le premier algorithme est l’algorithme de couverture et il déterminel’ensemble des cliques qui couvre chaque sommet de notre graphe. Le second algorithme estl’algorithme de correction. Il ajoute ou supprime des arêtes au voisinage d’un sommet non couvertde telle sorte que son voisinage soit partitionné en une ou deux cliques. Enfin, nous évaluons lesperformances de nos algorithmes en vérifiant le nombre d’arêtes corrigées et la capacité à retournerle graphe le plus proche du line-graphe de notre DAGIn energy network, the knowledge of equipments, their locations and their functions are theimportant information for the distributor service operator. In fact, each operator has a networkplan often named synoptic schema. That schema shows the interconnexion between equipments inthe network. From this schema, some management decisions have taken for ensuring an optimalperformance of a network.Sometimes, a synoptic schema has some mistakes because the maintenance operations, such aschanged the connexion between equipments or replaced equipments, have not been updated orhave been written with errors. And these mistakes increase exploitation cost in the energy network.We consider an electric network of a datacenter. This network consists of physical topologymodelised by a DAG without circuit and measurements are on the edges of a DAG. The mainpoint of the network is that measurements are some mistakes and the topology is unknown i.ewe know edges but the nodes of edges are unknown. When measurements are correct then thecorrelations between pairwise edges provide the adjacency matrix of the linegraph of undirectedgraph of the DAG. A linegraph is a graph in which each node and the neighbor are partitionnedby one or deux cliques. However, with the mistakes in measurements, the obtained graph is nota linegraph because it contains more or less edges. If the obtained graph is a linegraph then it isa linegraph of the other DAG. Our problem is to discovery the topology of the DAG with somemistakes in measurements.We start by the state of art in the measurement correlations in order to choose the good methodfor our problem. Then, we propose two algorithms to resolve our problem. The first algorithmis the cover algorithm and it returns the set of cliques in the graph. The second algorithm is acorrection algorithm which adds or deletes edges in the graph for getting a nearest linegraph ofthe DAG. In the last, we evaluate the performances of the algorithms by checking the number ofedges corrected and the ability to return a nearest linegraph of the DAG
19
Tabourier, Lionel. "Méthode de comparaison des topologies de graphes complexes : applications aux réseaux sociaux." Paris 6, 2010. http://www.theses.fr/2010PA066335.
Full textAbstract:
Les graphes des réseaux d'interactions sociales révèlent des propriétés topologiques dont nous cherchons à comprendre l'origine. Dans ce but nous manquons de références qui permettraient de construire une échelle de comparaison de leurs caractéristiques géométriques. Cette thèse propose une méthode générique pour produire des graphes synthétiques dont les propriétés sont ajustables, dans l'ambition de réaliser un balisage de l'espace des graphes. La méthode proposée dérive de procédures markoviennes dont l'étape élémentaire consiste à échanger les extrêmités de liens du graphe. Selon les contraintes imposées, une telle procédure doit être adaptée; nous discutons alors des difficultés inhérentes à sa réalisation pratique et les moyens à notre disposition pour estimer sa validité. Puis nous rendons compte d'applications pratiques sur des réseaux technologiques, de collaborations, ou d'échanges commerciaux. Le principe mis en oeuvre dans ces illustrations consiste à construire une suite d'ensembles de graphes obéissant à des contraintes de plus en plus exigeantes; puis à comparer les propriétés de chacun aux données réelles afin de déterminer quels éléments topologiques ont un rôle essentiel. Au fil des exemples, nous proposons des améliorations techniques de nos algorithmes qui permettraient d'en élargir les utilisations possibles. Cette méthode serait suffisamment générale pour pouvoir décrire des réseaux d'interactions d'une autre nature, mais aussi pour intégrer des informations supplémentaires à la description graphique telles que l'activité temporelle des agents; nous proposons pour conclure quelques éléments de réflexion pour réaliser ces objectifs.
20
Goddet, Étienne. "Analyse spectrale et surveillance des réseaux maillés de retour de courant pour l'aéronautique." Thesis, Université Grenoble Alpes (ComUE), 2017. http://www.theses.fr/2017GREAT099/document.
Full textAbstract:
Depuis plusieurs années, l’aéronautique est confrontée à une mutation majeure due à l’émergence des matériaux composites. Ce changement, justifié par les excellentes propriétés mécaniques des matériaux composites et un gain de masse important, implique une révision complète des réseaux de retour de courant. Pour faciliter cette révision, la thèse propose de lier au travers de l’analyse spectrale des graphes les performances des réseaux électriques avec leur topologie. Deux objectifs couplés sont étudiés : un dimensionnement topologique visant un bon compromis masse/robustesse et une stratégie de surveillance de ces réseauxThe principles of the electrical system design in future aircrafts have to be reconsidered due to the emergence of new composite materials. The use of these materials for the aircraft structure has indeed implied a complete revision of on-board current return path networks. To facilitate this revision, it is proposed to link through the spectral graph analysis the performances of electrical networks with their topology. The aim of this thesis is to give topological drivers that could help the aeronautical engineers during the design process and then to propose a monitoring methodology
21
Gauthier, Valentin. "Développement d'un langage de programmation dédié à la modélisation géométrique à base topologique, application à la reconstruction de modèles géologiques 3D." Thesis, Poitiers, 2019. http://www.theses.fr/2019POIT2252/document.
Full textAbstract:
La modélisation géométrique est utilisée dans de nombreux domaines pour la construction d’objets 3D, l’animation ou les simulations. Chaque domaine est soumis à ses propres contraintes et nécessiterait un outil dédié. En pratique, un même outil est utilisé pour plusieurs domaines, en factorisant les caractéristiques communes. Ces modeleurs fournissent un ensemble d'opérations types, que l'utilisateur compose pour construire ses objets. Pour des opérations plus spécifiques, les outils actuels offrent des API.La plate-forme Jerboa propose un outil de génération d'opérations géométriques personnalisées. Elles sont définies graphiquement par des règles de transformations de graphes. Des vérifications automatiques de préservation de la cohérence des objets sont faites lors de l’édition qui peuvent être enrichies par des propriétés métiers. Notre contribution a consisté à étendre le langage par des scripts, pour composer les règles et réaliser des opérations complexes. Nous avons étendu les vérifications automatiques, en particulier pour assurer la cohérence géométrique. Enfin, nous avons modifié le processus d'application des opérations pour augmenter les possibilités de contrôle.Pour valider cette approche, nous avons développé un modeleur dédié à la géologie, pour la représentation du sous-sol, en collaboration avec l'entreprise Géosiris. Nous avons défini un flux d'activité avec Géosiris en suivant des contraintes spécifiques à la géologie. Grâce à la rapidité de développement des opérations dans Jerboa, nous avons pu prototyper et tester rapidement plusieurs algorithmes de reconstruction du sous-sol, pour les appliquer sur des données réelles fournies par l'entrepriseGeometric modeling is used in various scopes for 3D object construction, animation or simulations. Each domain must cope with its constraints and should have its dedicated tool. In fact, several common characteristics of different domains are factored in a single tool. These modelers contain sets of basic operations that the user composes to build his objects. For more specific operations, current common tools offer API.Jerboa’s platform allows to generate personalized geometrical operations. These are defined by graph transformation rules. During their design, many automated verifications are done for the preserving of object consistency. They also be enriched with additional properties. Our contribution consists in extending the Jerboa language with scripts to compose rules and define complex operations. We also extended automated verifications, in particular to ensure geometric consistaency. Finally, we modified operations application process, in order to increase user control possibilities.To validate this approach, we have implemented a geological dedicated modeler for subsoil modeling, in collaboration with Geosiris Company. We defined a workflow with Geosiris that follows specific geological reconstruction constraints. Thanks to the Jerboa rapid prototyping mecanism, we developped and quickly tested several subsoil reconstruction algorithms, and apply them to real data provided by the company
22
Wagner, Emmanuel. "Sur l'homologie de Khovanov-Rozansky des graphes et des entrelacs." Phd thesis, Université Louis Pasteur - Strasbourg I, 2007. http://tel.archives-ouvertes.fr/tel-00192447.
Full textAbstract:
Cette thèse est consacrée à la catégorification d'invariants polynomiaux d'entrelacs et de graphes. Pour tout entier strictement positif n, Khovanov et Rozansky ont introduit en 2004 une homologie bigraduée d'entrelacs, ainsi qu'une homologie de graphes planaires. Etant donné n, leur homologie d'entrelacs catégorifie la n-ième spécialisation du polynôme d'entrelacs HOMFLYPT et leur homologie de graphes planaires catégorifie un polynôme de graphes associé. Dans cette thèse, on étudie ces homologies et on généralise leur construction en introduisant une graduation supplémentaire. Tout d'abord, on généralise une formule de Jaeger pour les polynômes d'entrelacs aux polynômes de graphes planaires, ainsi qu'à l'homologie de graphes planaires; on étend ensuite l'homologie d'entrelacs de Khovanov-Rozansky aux graphes plongés. Puis on construit une homologie trigraduée d'entrelacs. Cette homologie recouvre l'homologie bigraduée d'entrelacs de Khovanov et Rozansky. Enfin, on donne des exemples, des applications et des généralisations de l'homologie trigraduée d'entrelacs. On développe des outils d'algèbre homologique qui permettent de calculer explicitement l'homologie trigraduée d'entrelacs pour des exemples et on considère des déformations de l'homologie trigraduée d'entrelacs.
23
de, Felipe Paramio Ana Belén. "Topologie des espaces de valuations et géométrie des singularités." Sorbonne Paris Cité, 2015. http://www.theses.fr/2015USPCC136.
Full textAbstract:
On étudie la fibre de l'espace de Riemann-Zariski au-dessus d'un point fermé x d'une variété algébrique X définie sur un corps algébriquement clos. On caractérise son type d'homéomorphisme pour des points réguliers et des singularités normales de surface. Cela est fait en étudiant le lien avec l'entrelac non Archimédien normalisé de x dans X. On démontre qu'ils ont le même comportementWe study the fiber of the Riemann-Zariski space above a closed point x of an algebraic variety X defined over an algebraically closed field. We characterize its homeomorphism type for regular points and normal surface singularities. This is done by studying the relation between this space and the normalized non-Archimedean link of x in X. We prove that their behavior is the same
24
Memari, Pooran. "Geometric tomography with topological guarantees." Nice, 2010. http://www.theses.fr/2010NICE4053.
Full textAbstract:
Le sujet de cette thèse porte sur la reconstruction de formes `a partir de coupes planaires. Dans de nombreux domaines d’application, il est nécessaire de reconstruire des formes à partir de sections. L’importance du sujet en imagerie médicale a conduit, depuis les années 1990, à des résultats importants qui sont cependant pour la plupart limités au cas de sections parallèles. Pourtant en échographie, les données obtenues au moyen d’une sonde guidée manuellement, forment une série d’images représentant des coupes de l’organe par des plans non parallèles. Cette application directe motivait le sujet de ma thèse. Dans cette thèse nous considérons le problème de la reconstruction d’une 3-variété `a bord plongée dans R3, à partir de ses intersections avec un ensemble de plans en positions arbitraires, appelées coupes. C’est pour la première fois que ce problème est étudié en toute généralité, dans le but de fournir des garanties théoriques satisfaisantes sur le résultat de la reconstruction. Aucune garantie théorique n’a été obtenue même pour le cas de coupes parallèles avant cette thèse. Dans le premier chapitre de ce manuscrit, nous étudions la méthode de reconstruction proposée par Liu et al. En 2008. Nous prouvons que si certaines conditions d’échantillonnage sont vérifiées, cette méthode permet de reconstruire la topologie de l’objet `a partir des coupes données. Nous prouvons également que l’objet reconstruit est homéomorphe (et isotope) à l’objet. Le deuxième chapitre présente une nouvelle méthode de reconstruction en utilisant le diagramme de Voronoi des sections. Cette méthode permet d’établir plus de connections entre les sections par rapport `a la première méthode. Favoriser les connections entre les sections est motivé par la reconstruction d’objets fins `a partir de sections peu denses. Nous présentons des conditions d’échantillonnage qui sont adaptées aux objets fins et qui permettent de prouver l’équivalence homotopique entre l’objet reconstruit et l’objet de départ. En effet, nous prouvons que si les plans de coupe sont suffisamment transversales `a l’objet, notre méthode de reconstruction est topologiquement valide et peut traiter des topologies complexes des sections avec plusieurs branchements. Dans le dernier chapitre de ce manuscrit, nous présentons une autre méthode de reconstruction qui permet d’établir encore plus de connections entre les sections en comparant avec les deux premières méthodes. Notre méthode est basée sur la triangulation de Delaunay et suit une approche duale en considérant le diagramme de Voronoi des sections. L’algorithme correspondant a été implémenté en C++, en utilisant la bibliothèque CGAL. Les résultats de la reconstruction obtenus par cet algorithme sont très satisfaisants pour les topologies complexes des sections. En se basant sur les études que nous avons développées durant cette thèse, nous espérons pouvoir fournir un fondement solide pour le processus d’acquisition et de reconstruction des données échographiques afin d’avoir un logiciel fiable pour les diagnosticsThe purpose of this doctoral thesis is to provide a method to reconstruct three dimensional shapes from cross-sections. The principal motivation is 3D reconstruction of organs that is widely considered to be an important diagnostic aid in the medical world. However, the actual simulation results, namely in 3D ultrasonic simulation, are not reliable to be used in diagnosis. This thesis is the first geometric analysis of the reliability and the validity of reconstruction methods from cross-sectional data. Even in the case of parallel sections, no formal analysis and guarantees had been obtained before this thesis. More formally, we consider the problem of reconstructing a compact 3-manifold (with boundary) embedded in R3 from its cross-sections with a given set of cutting planes having arbitrary orientations. The first Chapter of this manuscript is devoted to analyzing a method presented by Liu et al. In 2008. We prove that under appropriate sampling conditions, the resulting reconstructed object is homeomorphic (and isotopic) to the original object. In the second chapter, we present a second reconstruction method that makes use of the Voronoi diagram of the sections. This method performs more connections between the sections comparing to the first method. Increasing the connectivity between the sections is motivated by reconstructing tree-like structures from sparse sectional data. The provided sampling conditions, leading to topological guarantees, are adapted to tree-like structures: Indeed, we show that if the cutting planes are sufficiently transversal to the surface we want to reconstruct, then the method can handle complex branching structures. Finally, in the third chapter, we show how the Voronoi-Delaunay duality allows us to perform still more connections between the sections comparing to the two first methods. The preliminary experimental results are quite promising, e. G. , regarding the practicality of the approach to reconstruct complex cross-sectional branching situations such as the coronary arterial tree. The hope is that the theoretical studies provided in this thesis will be a first step to provide solid foundations and theoretical guarantees for medical diagnostic software
25
Sadi, Ahcène. "Processus de certification de documents utilisant un authentifiant chaotique mesurable comme le Code à BullesTM par analyse d’images." Caen, 2013. http://www.theses.fr/2013CAEN2090.
Full textAbstract:
Cette thèse s’intéresse au processus de certification de documents utilisant le Code à BullesTM. Les modalités que présente le code à BullesTM ressemblent à ceux d’une biométrie, en s’inspirant de cette dernière nous avons présenté une architecture adaptée pour un système d’authentification utilisant le Code à BullesTM. Dans la première partie, nous somme intéressé aux prétraitements d’images numériques. La morphologie mathématique offre un large panel d’opérateurs pour appréhender divers problèmes de traitement d’images. Les traitements morphologiques peuvent être définis en termes d’opérations algébriques sur des ensembles ou en termes d’équations aux dérivées partielles (EDP). Dans ce contexte, nous avons choisi de travailler sur une nouvelle approche de la morphologie mathématique basée sur des équations aux différences partielles (EdP) définies sur des graphes de topologie arbitraire. Cette méthodologie permet de généraliser ces deux approches pour le traitement non local des images. Nous avons proposé une nouvelle classe de filtre de chocs à base des équations aux différences partielles (EdP) et nous avons monté leurs efficacités sur les images industrielles, nous avons proposé une nouvelle approche permettant de segmenter ce genre d’image en utilisant ces filtres de chocs. Dans la seconde partie, nous nous somme intéressé aux algorithmes d’authentification et d’identification du Code à BullesTM. Nous avons présenté un panorama de techniques employées en base de données pour indexer des données multimédias. Nous avons présenté une approche qui exploite les arbres M-TREE pour générer un système d’indexation pour Code à BullesTMThis thesis focuses on the documents certification using the Bubble TagTM. The modalities presented by the Bubble TagTM are similar to those of biometrics. Based on that similarity, we present a new architecture of documents system authentication. In the first part, we were interested in the digital images preprocessing, which is a very delicate phase in the authentication systems. Mathematical morphology provides a wide range of operators to understand various problems of image processing. Morphological processes operators can be defined in terms of algebraic (discrete) sets or as partial differential equations (PDEs). In this context, we decided to work on a new approach using mathematical morphology based on partial differences equations (PdEs) on weighted graphs. This methodology allows us to generalize these two approaches to a non-local image processing. We have proposed a new class of shock filter based on PdEs. We demonstrated their effectiveness in industrial images, and we proposed a new approach to segment this kind of image using the shocks filters. In the second part, we were interested in authentication and identification algorithms for Bubble TagTM. We presented an overview of techniques for indexing data used in the multimedia database. We have presented an approach that exploits the M-TREE trees to generate an indexing for a Bubble TagTM identification system
26
Barbot, Thierry. "Géométrie transverse des flots d'Anosov." Lyon 1, 1992. http://www.theses.fr/1992LYO10274.
Full textAbstract:
Nous nous interessons dans cette these a la classification des flots d'anosov a equivalence topologique pres. Nous etablissons: si le groupe fondamental d'une variete admet un sous-groupe abelien distingue non cyclique, alors tout flot d'anosov de codimension un sur cette variete est topologiquement equivalent a la suspension d'un diffeomorphisme; si un des feuilletages faibles d'un flot d'anosov de dimension trois est transversalement projectif, alors ce flot est topologiquement equivalent a une suspension ou a un flot geodesique; tout flot d'anosov produit sur une variete graphee est obtenu par recollement de morceaux de flots geodesiques
27
Fiorio, Christophe. "Approche interpixel en analyse d'images, une topologie et des algorithmes de segmentation." Montpellier 2, 1995. http://www.theses.fr/1995MON20179.
Full textAbstract:
Le but de tout processus de segmentation d'images est la caracterisation des entites representees dans l'image. La plupart des methodes existantes s'appuient sur les seuls elements materialises formant l'ensemble image: les pixels ou les voxels. Nous proposons de prendre en compte les elements de bord des pixels ou des voxels afin d'etudier les liaisons et connexions entre ces derniers. Ceci nous permet de definir une topologie adaptee a l'analyse d'images: la topologie-etoile. Un resultat important de cette topologie est qu'elle permet de recuperer sans peine les theoremes de la geometrie classique sur ir#n. Nous associons a cette etude topologique un detecteur de contours en interpixel et des algorithmes de segmentation exhibant une cooperation parfaite region-contour. En outre le graphe des frontieres, extension proposee du graphe d'adjacence, s'inscrit lui-aussi dans le cadre d'une approche globale combinatoire en analyse d'images
28
Ben, Salah Fatma. "Modélisation et simulation à base de règles pour la simulation physique." Thesis, Poitiers, 2018. http://www.theses.fr/2018POIT2293.
Full textAbstract:
La simulation physique des objets déformables est au cœur de plusieurs applications dans l’informatique graphique. Dans ce contexte, nous nous intéressons à l’élaboration d’une plate-forme, qui combine le modèle topologique des Cartes Généralisées avec un ou plusieurs modèles mécaniques, pour l’animation physique d’objets maillés déformables, pouvant endurer des transformations topologiques comme des déchirures ou des fractures.Pour offrir un cadre aussi général que possible, nous avons adopté une approche à base de règles de manipulation et de transformation de graphes, telle que proposée par le logiciel JERBOA. Cet environnement offre des possibilités de prototypage rapide de différents modèles mécaniques. Il nous a permis de définir précisément le stockage des informations mécaniques dans la description topologique du maillage et de simuler les déformations en utilisant une base topologique pour le calcul des interactions et l’affectation des forces. Toutes les informations mécaniques sont ainsi stockées dans le modèle topologique, sans recours à une structure auxiliaire.La plate-forme réalisée est générale. Elle permet de simuler des objets 2D ou 3D, avec différents types de maillages, non nécessairement homogènes. Elle permet de simuler différents modèles mécaniques, continus ou discrets, avec des propriétés diverses d’homogénéité et d’isotropie. De plus, différentes solutions d’évolution topologique ont été proposées. Elles impliquent la sélection d’un critère déclenchant les modifications et un type de transformation proprement dit. Notre approche a également permis de réduire les mises à jour du modèle mécanique en cas de déchirure/fractureThe physical simulation of deformable objects is at the core of several computer graphics applications. In this context, we are interested in the creation of a framework, that combines a topological model, namely Generalized Maps, with one or several mechanical models, for the physical animation of deformable meshed objects that can undergo topological modifications such as tearing or fractures.To obtain a general framework, we chose to rely on graph manipulation and transformation rules, proposed by the JERBOA software. This environment provided us with fast prototyping facilities for different mechanical models. It allowed us to precisely define how to store mechanical properties in the topological description of a mesh and simulate its deformation in a topologically-based manner for interaction computation and force distribution. All mechanical properties are stored in the topological model without any external structure.This framework is general. It allows for the simulation of 2D or 3D objects, with different types of meshes, including non homogeneous ones. It also allowed for the simulation of several, continuous or discrete, mechanical models with various properties of homogeneity and isotropy. Furthermore, different methods to simulate topological modifications have been implemented in the framework. They include both the selection of a criterion to trigger topological modifications and a transformation type. Our approach also managed to reduce the number of updates of the mechanical model after tearing / fracture
29
Sidère, Nicolas. "Contribution aux méthodes de reconnaissance structurelle de formes : approche à base de projections de graphes." Thesis, Tours, 2012. http://www.theses.fr/2012TOUR4009/document.
Full textAbstract:
Les travaux exposés dans cette thèse portent sur une contribution aux techniques de projection de graphes, appliquées à la reconnaissance de formes, visant à tirer parti de la richesse des méthodes structurelles et de l’efficacité des outils statistiques. Nous présentons une nouvelle projection s’inscrivant dans la catégorie des sondages de graphes. La première contribution de cette thèse porte sur l’encapsulation de la topologie du graphe dans une représentation vectorielle, en s’appuyant sur le dénombrement de motifs (sous-graphes) issus d’un lexique généré indépendamment du contexte. Ces motifs permettent de minimiser les pertes de l’information topologique lors de la projection. La deuxième contribution porte sur l’intégration de l’information relative aux étiquettes au sein de notre projection par l’adjonction de leurs dénombrements. Aux problèmes liés à la nature et la variabilité des attributs, nous proposons deux solutions dans le but de constituer des classes d’étiquettes moins nombreuses. La première consiste à discrétiser les attributs numériques puis à les combiner. La deuxième vise à former ces classes par un partitionnement global de l’ensemble des étiquettes. Ces propositions sont ensuite évaluées sur différentes bases de graphes et dans différents contextesThe work exposed in this thesis focuses on a contribution to techniques of graph embedding, applied to pattern recognition, aiming to take advantages of the richness of structural methods and the efficiency of statistical tools. We present a new embedding, joining the category of graph probing. The first contribution of this thesis deals with the embedding of the graph topology in a vectorial representation, based on the counting of patterns (subgraphs) stemming of a lexicon generated independently of the context. These patterns permit the minimization of losses of the topological information during the embedding. The second contribution focuses on the integration of the information related to labels inside our embedding by adding their counting. To deal with problems linked to the nature and the variability of the attributes, we suggest two solutions to reduce the number of label classes. The first one consists of discretizing numeral attributes and combining them The second one aims to build these classes by a global clustering on the set of labels. Then, these proposals are evaluated on different datasets of graphs and in different contexts
30
Delhommé, Christian. "Propriétés de projection." Lyon 1, 1995. http://www.theses.fr/1995LYO10159.
Full textAbstract:
La propriete de projection a ete introduite par ernest corominas pour les ensembles ordonnes : un ensemble ordonne est 2-projectif si les projections sont ses seules operations binaires, croissantes et identiques sur la diagonale. L'objet de cette these est l'etude d'extensions de cette notion, a des operations d'arite superieure (projectivite de hamming finie et projectivite cartesienne infinie) et a des structures plus generales. Notre etude des proprietes de projection de hamming (relatives a des operations regulieres par rapport a chaque argument) est fondee sur des idees de topologie algebrique de base. Nous introduisons divers complexes de chaines, dont les proprietes nous fournissent des criteres de projectivite. Ainsi, nous etablissons par exemple, qu'un graphe fini, connexe, sans sommet pendant, est hamming 2-projectif des qu'il n'a ni triangle ni carre, et plus generalement pour n>2, qu'il est hamming n-projectif, quand il n'a pas cycle de longueur inferieure ou egale a n + 1 et qu'il n'est pas lui-meme un cycle. En particulier, cela fournit les premiers exemples de graphes verifiant la propriete de 3-projection de hamming. Notre point de vue va egalement nous permettre d'introduire les proprietes de n-projection simple et double. Notre approche des proprietes de projection infinies (relatives a des operations infinitaires) est de nature plus ensembliste. Nous montrons en particulier, qu'un graphe projectif de diametre fini est denombrablement projectif, des qu'il n'est pas compact pour les systemes atomiques a un nombre fini d'inconnues. Cette these est partagee en sept chapitres regroupes en trois parties. La premiere est consacree a l'expose de generalites. Nous y etablissons egalement la projectivite de certaines structures homogenes, qui nous permettront d'illustrer la suite de notre propos. Dans une seconde partie, nous mettons en place un cadre algebrique pour l'etude des proprietes de projection de hamming. Dans la troisieme, nous etudions des proprietes de projection infinie, que nous illustrons notamment par les exemples des shift-graphs et des structures homogenes.
31
Yang, Huanqing. "Automatisation de l'analyse mécanique des mécanismes." Lyon, INSA, 1989. http://www.theses.fr/1989ISAL0016.
Full textAbstract:
Les analyses cinématique et dynamique sont souvent menées d'une manière imparfaite dans la conception des machines complexes car les concepteurs n'ont pas toujours des outils d'analyse efficaces, souples et rapides. Dans une démarche de Conception Assistée par Ordinateur, ces analyses doivent être faites à l'aide de logiciels. L'objet de cette thèse était donc de trouver une formulation automatisable d'analyse des comportements cinématique et dynamique des machines. Cette formulation devait aboutir naturellement à des outils de calcul informatiques permettant de simuler les comportements cinématique et dynamique des machines. C'est dans ce contexte qu'a été effectué notre travail dont l'objectif était de cerner explicitement tous les aspects de l'automatisation et de l'informatisation d'un processus de calcul. Dans un premier temps, l'objectif était de proposer un formalisme qui comprend trois parties d'analyse : analyse structurale (théorie des graphes) et géométrique (paramétrage et repérage), analyse dynamique (principe de d'Alembert). Dans un deuxième temps, l'objectif était de réaliser un logiciel basé sur le formalisme établi et de qualifier la démarche. Enfin, l'aboutissement de ce travail était aussi de réaliser un logiciel exploitable pour les mécanismes 2D, et qui s'intègre bien dans un processus de Conception Assistée par Ordinateur. De nombreux cas (chaîne ouverte, boucle fermée, cinématique, statique, dynamique, modèle direct ou inverse) ont été considérés pour qualifier le logiciel et définir une méthodologie de travail.
32
Bera, Roderic. "L'Adjacence relative. Une Etude contextuelle de l'influence de l'environnement spatial dans l'appréhension de la notion de proximité." Rennes 1, 2004. https://hal.archives-ouvertes.fr/tel-01276691.
Full textAbstract:
En information géographique, la notion de relation spatiale est primordiale, puisqu'elle conditionne la compréhension des interactions entre entités spatiales. Il est courant de décrire une scène par l'utilisation de grandeurs géomètriques (relation de distance, relations cardinales). Ceci permet de quantifier la relation d'une entité à une autre. Cependant, une telle approche ne prend pas en compte l'environnement spatial, dans la mesure où des entités tierces ne peuvent exercer une influence médiatrice. De plus, si la géométrie mesure, elle ne dit rien sur la nature d'une relation. L'approche topologique en revanche, si elle permet la description qualitative des relations ne permet pas de quantifier les relations spatiales. Elle a cependant l'avantage de faciliter la prise en compte du contexte spatial. Après avoir précisé les notions d'entités et de relations, nous prenons donc la topologie comme point de de départ pour l'étude et l'analyse de l'influence de l'environnement spatial dans la relation entre deux entitées données. Etudiant plus particulièrement la relation d'adjacence dans une partition spatiale, nous proposons un opérateur de proximité(l'adjacence relative) intégrant l'influence du contexte spatial avec une intensité modulable. Il est ensuite possible d'enrichir cet opérateur par l'intégration de grandeurs géomètriques et/ou attributaires (distance entre deux entités, superficie, ou encore périmètre). De plus, comme l'approche topologique permet une représentation sous forme de graphe relationnel, il est possible d'appliquer l'adjacence relative dans toute situation modélisable par un tel graphe(nous étudipons plus particulièrement les relations de voisinage entre territoires ainsi que les réseaux urbains). De ce point de vue, l'adjacence reletive émerge comme un nouvel outil d'analyse en syntaxe spatiale. Cependant, il reste difficile de représenter sur un même graphe des relations hétérogènes (c'est-à-dire principalement entre entités appartenant à des thématiques différentes). Nous explorons donc aussi cette voie dans le cas de l'interaction entre les entités de deux couches thématiqiues.
33
Razafindramanana, Octavio. "Low-dimensional data analysis and clustering by means of Delaunay triangulation." Thesis, Tours, 2014. http://www.theses.fr/2014TOUR4033/document.
Full textAbstract:
Les travaux présentés et discutés dans cette thèse ont pour objectif de proposer plusieurs solutions au problème de l’analyse et du clustering de nuages de points en basse dimension. Ces solutions s’appuyent sur l’analyse de triangulations de Delaunay. Deux types d’approches sont présentés et discutés. Le premier type suit une approche en trois-passes classique: 1) la construction d’un graphe de proximité contenant une information topologique, 2) la construction d’une information statistique à partir de ce graphe et 3) la suppression d’éléments inutiles au regard de cette information statistique. L’impact de différentes measures sur le clustering ainsi que sur la reconnaissance de caractères est discuté. Ces mesures s’appuyent sur l’exploitation du complexe simplicial et non pas uniquement sur celle du graphe. Le second type d’approches est composé d’approches en une passe extrayant des clusters en même temps qu’une triangulation de Delaunay est construiteThis thesis aims at proposing and discussing several solutions to the problem of low-dimensional point cloudanalysis and clustering. These solutions are based on the analysis of the Delaunay triangulation.Two types of approaches are presented and discussed. The first one follows a classical three steps approach:1) the construction of a proximity graph that embeds topological information, 2) the construction of statisticalinformation out of this graph and 3) the removal of pointless elements regarding this information. The impactof different simplicial complex-based measures, i.e. not only based on a graph, is discussed. Evaluation is madeas regards point cloud clustering quality along with handwritten character recognition rates. The second type ofapproaches consists of one-step approaches that derive clustering along with the construction of the triangulation
34
Daniel, Frédéric. "Sur les communications globales dans les réseaux à topologie de de Bruijn et de Kautz." Toulouse 3, 1996. http://www.theses.fr/1996TOU30248.
Full textAbstract:
Les performances d'algorithmes de communication globale dans une machine multi-processeurs reconfigurable dependent de ses caracteristiques, son environnement de programmation et sa topologie. Des graphes de degre fixe tels que le ccc (cube-connected cycles) sont etudies et utilises pour la configurer. Les notions elementaires de la theorie des graphes et de l'arithmetique des nombres entiers nous permettent d'etudier les proprietes des familles de graphes de de bruijn et de kautz. Ces graphes sont de degre fixe mais en plus d'ordre quelconque, de diametre presque optimal et orientes. Les differents cas de figure de communications globales ont entre eux des relations d'equivalence ou de sous-jacence. C'est donc sur les communications les plus complexes (tous vers tous) que sont recherchees les ameliorations des algorithmes classiques. Un modele d'evaluation des performances d'un algorithme de communication est utilise afin de les comparer par simulation. L'implementation sur un t-node dans les environnements helios et 3lc est realisee par deux systemes de tables qui permettent de decrire tous les algorithmes proposes et qui rendent chaque processeur autonome dans sa gestion des messages. La comparaison des performances reelles des diverses solutions topologiques et algorithmiques permet de les evaluer entre eux mais aussi de discuter de la validite du modele utilise pour la simulation
35
Mesmay, Arnaud de. "Topics in low-dimensional computational topology." Paris, École normale supérieure, 2014. https://theses.hal.science/tel-04462650v1.
Full textAbstract:
La topologie, c’est-à-dire l’étude qualitative des formes et des espaces, constitue un domaine classique des mathématiques depuis plus d’un siècle, mais il n’est apparu que récemment que pour de nombreuses applications, il est important de pouvoir calculer informatiquement les propriétés topologiques d’un objet. Ce point de vue est la base de la topologie algorithmique, un domaine très actif à l’interface des mathématiques et de l’informatique auquel ce travail se rattache. Les trois contributions de cette thèse concernent le développement et l’étude d’algorithmes topologiques pour calculer des décompositions et des déformations d’objets de basse dimension, comme des graphes, des surfaces ou des 3-variétés. Le premier problème auquel nous nous attaquons traite de déformations : comment peut-on tester si deux graphes dessinés sur une même surface sont isotopes, c’est-à-dire si l’on peut déformer continûment l’un en l’autre ? Ce type de question est relié à des problèmes pratiques que l’on rencontre par exemple dans les systèmes d’information géographique ou les métamorphoses (morphings). En nous appuyant sur des concepts de géométrie hyperbolique et de la théorie des mapping class groups, nous établissons d’abord un critère combinatoire pour caractériser l’isotopie, ce qui reprouve et améliore un résultat de Ladegaillerie de 1984. Ensuite, en combinant ceci avec des algorithmes antérieurs pour tester l’homotopie de courbes, nous fournissons des algorithmes efficaces pour résoudre ce problème d’isotopie de graphes. Nous déplaçons ensuite notre étude vers des problèmes de décompositions, en nous intéressant à la découpe de surfaces le long de courbes ou de graphes respectant certaines propriétés topologiques, ce qui est une routine importante en algorithmique des graphes ou en infographie, parmi d’autres domaines. En établissant une forte connexion avec le cas continu, ainsi qu’en étudiant un modèle discret de surfaces aléatoires, nous améliorons les meilleures bornes connues pour plusieurs schémas de découpe. Cela prouve en particulier une conjecture de Przytycka et Przytycki datant de 1993, et fournit également un nouvel algorithme pour calculer des décompositions en pantalons courtes. Enfin, nous montons d’une dimension, où les meilleurs algorithmes connus pour de nombreux problèmes topologiques (comme le célèbre problème du noeud) sont exponentiels. La plupart de ces algorithmes reposent sur les surfaces normales, un objet omniprésent pour étudier les surfaces plongées dans une 3-variété. Nous étudions une relaxation naturelle de cette notion, les surfaces normales immergées, dont la meilleure structure algébrique en fait de bons candidats pour obtenir des algorithmes polynomiaux pour des problèmes topologiques. Dans ce travail, nous montrons qu’utiliser des surfaces normales immergées mène naturellement à un problème de détection de singularités, et nous prouvons que celui-ci est NP-dur ; c’est un résultat notable car l’on dispose de très peu de preuves de difficulté en topologie en 3 dimensions. Notre réduction s’appuie sur une connexion avec une classe restreinte de problèmes de satisfaction de contraintes qui a été partiellement classifiée par FederTopology is the area of mathematics investigating the qualitative properties of shapes and spaces. Although it has been a classical field of study for more than a century, it only appeared recently that being able to compute the topological features of various spaces might be of great value for many applications. This idea forms the core of the blossoming field of computational topology, to which this work belongs. The three contributions of this thesis deal with the development and the study of topological algorithms to compute deformations and decompositions of low-dimensional objects, such as graphs, surfaces or 3-manifolds. The first question we tackle concerns deformations: how can one test whether two graphs embedded on the same surface are isotopic, i. E. , whether one can be deformed continuously into the other? This kind of problems is relevant to practical problems arising with morphings or geographic information systems, for example. Relying on hyperbolic geometry and ideas from the theory of mapping class groups, we first establish a combinatorial criterion to characterize isotopy, reproving and strengthening a result of Ladegaillerie (1984). Combined with earlier algorithms on the homotopy of curves, this allows us in turn to provide efficient algorithms to solve this graph isotopy problem. We then shift our focus to decompositions, by investigating how to cut surfaces along curves or graphs with prescribed topological properties, which is an important routine in graph algorithms or computer graphics, amongst others domains. By establishing a strong connection with the continuous setting, as well as studying a discrete model for random surfaces, we improve the best known bounds for several instances of this problem. In particular, this proves a conjecture of Przytycka and Przytycki from 1993, and one of our new bounds readily translates into an algorithm to compute short pants decompositions. Finally, we move up one dimension, where the best known algorithms for many topological problems, like for example unknot recognition, are exponential. Most of these algorithms rely on normal surfaces, a ubiquitous tool to study the surfaces embedded in a 3-manifold. We investigate a relaxation of this notion called immersed normal surfaces, whose more convenient algebraic structure makes them good candidates to solve topological problems in polynomial time. We show that when working with immersed normal surfaces, a natural problem on the detection of singularities arises, and we prove it to be NP-hard – this is noteworthy as hardness results are very scarce in 3-dimensional topology. Our reduction works by establishing a connection with a restricted class of constraint satisfaction problems which has been partially classified by Feder
36
Cardot, Anaïs. "Rejeu basé sur des règles de transformation de graphes." Thesis, Poitiers, 2019. http://www.theses.fr/2019POIT2254.
Full textAbstract:
Réaliser des variations d'un même modèle est un besoin en expansion dans de nombreux domaines de modélisation (architecture, archéologie, CAO, etc.). Mais la production manuelle de ces variations est fastidieuse, il faut donc faire appel à des techniques permettant de rejouer automatiquement tout ou partie du processus de construction du modèle, après spécification des modifications. La majorité des approches dédiées à la réalisation du rejeu sont basées sur un système de modélisation paramétrique, composée d’un modèle géométrique et d’une spécification paramétrique permettant d’enregistrer la succession d’opérations l’ayant créé ainsi que leurs paramètres. On peut ensuite faire varier ces paramètres ou éditer cette liste d’opérations afin de modifier le modèle. On utilise pour cela un système de nommage persistant, introduit dans les années 90, et permettant d’identifier et d’apparier les entités d’une spécification initiale et celles d'une spécification rejouée. L’objectif de cette thèse est de proposer un système de nommage persistant général, homogène et permettant de gérer l’édition de spécification paramétriques (déplacer, ajouter et supprimer des opérations). Nous nous basons sur la bibliothèque Jerboa, qui repose sur des règles de transformation de graphes, tant pour utiliser ces règles dans la réalisation de la méthode de nommage que pour lier les notions de spécification paramétrique à ces règles de transformations de graphes. Nous décrivons ensuite comment exploiter notre méthode de nommage pour rejouer et éditer des spécifications paramétriques d’opérations, puis nous la comparons avec les approches de la littératureIn many modelling fields, such as architecture, archaeology or CAD, performing many variations of the same model is an expanding need. But building all those variations manually takes time. It is therefore needed to use automatic technics to revaluate some parts of a model, or even an entire model, after the user specifies the modifications. Most of the existing approaches dedicated to revaluating models are based on a system called parametric modelling. It is made of two parts, a geometric model and a parametric specification, which allows to record the series of operation that created the model, and the different parameters of those operations. This way, the user can change some parameters, or edit the list of operations to modify the model. To do so, we use a system called persistent naming, introduced during the 90ies, that allows us to identify and match the entities of an initial specification and the ones of a revaluated specification. In this thesis, our goal is to propose a persistent naming system that would be general, homogeneous and that would allow the user to edit a parametric specification (which means move, add, or delete some operations). We base our system on the Jerboa library, which uses graph transformation rules. This way, we will be able to use those rules to create our naming system, while also linking the notions of graph transformation rules and parametric specification. We will then describe how to use our naming method to revaluate or edit parametric specifications. Finally, we will compare our method with the other ones from the literature
37
Bongiovanni, Francesco. "Design, formalization and implementation of overlay networks : application to RDF data storage." Nice, 2012. http://www.theses.fr/2012NICE4021.
Full textAbstract:
Les réseaux de recouvrement structurés sont une nouvelle classe de systèmes Pair-à-pair (P2P), qui sont utilisés pour des applications à grande échelle telles que le partage de fichiers, diffusion de l’information ; le stockage et la récupération des différentes ressources… Beaucoup de ces réseaux coexistent sur le Web mais ne coopèrent pas. Afin de promouvoir la coopération, nous proposons deux protocoles, Babelchord et Synapse, dont les objectifs sont de permettre l’interconnexion de réseaux de recouvrement structurés et hétérogènes grâce à des méta-protocoles. Babelchord vise à regrouper les petits réseaux de recouvrement structurés d’une manière non structurée , tandis que Synapse généralise ce concept et prévoit des mécanismes souples reposant sur des nœuds co-localisés, à savoir des nœuds qui appartiennent à plusieurs réseaux en même temps. Nous fournissons les algorithmes derrière ces deux protocoles, ainsi que les résultats des simulations montrant leurs comportements dans le contexte de recherche d’information. Nous avons également développé et expérimenté un prototype de JSynapse sur la plate-forme Grid’50000, confirmant les résultats de simulation obtenus. Une nouvelle génération de ces réseaux fut créée afin de stocker et de récupérer des données sémantiques dans des contextes à larges échelles. En effet, la communauté du Web sémantique a besoin de solutions capables de stocker et récupérer des données RDF, le modèle de données au centre du Web sémantique, passant à l’échelle. La première génération de ces systèmes est monolithique et fournit un support limité pour les requêtes expressives. Nous proposons la conception et l’implémentation d’un système modulaire basé sur du P2P afin de répondre à ces besoins. Nous l’avons construit avec RDF à l’esprit et avons utilisé une infrastructure à trois dimensions, reflétant la nature d’un triplet RDF. Nous avons également fait des choix de design qui permettent de préserver la localité des données mais qui soulèvent des challenges techniques intéressants. Notre conception modulaire réduit le couplage entre les composants formant l’infrastructure et peuvent donc être inter-changé avec d ‘autres. Nous avons expérimenté notre implémentation sur Grid’5000 et présentons les résultats de micro-benchmarks. Enfin, nous nous sommes intéressés de plus près aux performances de ces réseaux. En effet, ils ont une topologie géométrique spécifique qui peut être exploitée de manière à augmenter les performances des applications tournant au-dessus. A cet effet, nous proposons un algorithme de diffusion pour CAN qui est efficace en termes de messages échangés dans le réseau. Cet algorithme a été mis au point en réponse aux résultats trouvés au cours des expériences de notre infrastructure de stockage de données RDF. En parallèle de cet algorithme, nous proposons également un cadre de raisonnement, développé avec l’assistant de preuve Isabelle/HOL, afin de prouver des propriétés d’exactitudes des algorithmes de diffusion pour des réseaux à la CAN. Nous nous sommes concentrés, sur l’ensemble minimal d’abstractions nécessaires afin de concevoir des algorithmes de diffusion efficaces corrects par construction au-dessus de réseaux comme CANStructured Overlay Networks (SONs) are a new class of Peer-to-Peer (P2P) systems which are widely used for large scale applications such as file sharing , information dissemination, storage and retrieval of different resources… Many different SONs co-exist on the Web yet they do not cooperate with each other. In order to promote cooperation, we propose two protocols, Babelchord and Synapse, whose goals are to enable the inter-connection of structured and heterogeneous overlays networks through meta-protocols. Babelchord aims to aggregate small structured overlay networks in an unstructured fashion while Synapse generalizes this concept and provides flexible mechanisms relying on co-located nodes, i. E. Nodes which belong to multiple overlays at the same time. We provides the algorithms behind both protocols, as well as simulations results showing their behaviours in the context of information retrieval. We have also implemented and experimented a prototype of JSynapse on the Grid’5000 platform, confirming the obtained simulation results and giving a proof of concept of our protocol. A novel generation of SONs was created in order to store and retrieve semantic data in large scale settings. The Semantic Web community is in need for scalable solutions which are able to store and retrieve RDF data, the core data model of the Semantic Web. The first generation of these systems is too monolithic and provided limited support for expressive queries. We propose the design and implementation of a new modular P2P-based system for these purposes. We build the system with RDF in mind and used a three-dimensional CAN overlay network, mimicking the nature of an RDF triple. We made specific design choices which preserve data locality but raises interesting technical challenges. Our modular design reduces the coupling between its underlying components, allowing them to be inter-changed with others. We also ran some micro-benchmarks on Grid’50000 which will be discussed. SONs have a specific geometrical topology which could be leveraged in order to increase the overall performance of the system. In this regard we propose a new broadcast efficient algorithm for CAN, developed in response to the results found from running the experiments in the RDF data store we have built, which used too many messages. Along this algorithm, we also propose a reasoning framework, developed with the Isabelle/HOL proof assistant, for proving correctness properties of dissemination algorithms for CAN-like P2P-systems. We focus on providing the minimal set of abstractions needed to devise efficient correct-by-construction dissemination algorithms on top of such overlay
38
Mayrand, Elsa. "Chirurgies de Dehn sur un entrelacs de S3 à deux composantes." Aix-Marseille 1, 2001. http://www.theses.fr/2001AIX11028.
Full textAbstract:
Historiquement, les premiers exemples d'entrelacs de S3 à deux composantes produisant S3 par une chirurgie non triviale (J. H. C. Whitehead, M. Domergue et Y. Mathieu) vérifient une condition de trivialité (une des composantes est triviale, ou il existe un anneau essentiel dans l'extérieur, joignant les deux composantes de bord). Ces entrelacs sont dits "non génériques". Concernant les entrelacs génériques, une conjecture de J. Berge affirme qu'on peut en trouver tels que les deux distances entre les pentes de chirurgie (produisant S3) sont aussi grandes que l'on veut. Nous présentons un procédé pour construire de tels entrelacs. Notre résultat principal tend à borner ces distances. Plus précisément, nous montrons que l'une de ces deux distances est
39
Belhoul, Yacine. "Graph-based Ad Hoc Networks Topologies and Business Process Matching." Thesis, Lyon 1, 2013. http://www.theses.fr/2013LYO10202.
Full textAbstract:
Un réseau mobile ad hoc (Mobile Ad hoc Network, MANET) est un réseau sans fil, formé dynamiquement par un ensemble d'utilisateurs équipés de terminaux mobiles, sans l'utilisation d'une infrastructure préexistante, ou d'une administration centralisée. Les équipements utilisés dans les MANETs sont limités par la capacité de la batterie, la puissance de calcul et la bande passante. Les utilisateurs des MANETs sont libres de se déplacer, ce qui induit à des topologies dynamiques dans le temps. Toutes ces contraintes ajoutent plus de challenges aux protocoles et services de communications afin de fonctionner dans les MANETs. L'évolution des réseaux de 4ème génération (4G) est appelée à intégrer les MANETs avec les autres types de réseaux afin d'étendre leurs portées. Nous nous sommes intéressés dans la première partie de cette thèse à quelques challenges connus dans les MANETs en proposant des solutions novatrices utilisant des propriétés intéressantes des topologies de graphes. Dans un premier temps, nous avons effectué une étude sur la prédiction de la mobilité afin de maintenir une topologie d'ensemble dominant connecté dans les MANETs. Nous avons proposé dans un autre travail comment construire des topologies de graphes ayant des propriétés globales en se basant seulement sur des informations locales des nœuds mobiles. Ces topologies servent comme overlay aux MANETs. Nous avons proposé des algorithmes distribués pour construire des alliances offensives et défensives globales minimales. Nous avons aussi défini des heuristiques pour ces algorithmes afin de réduire les tailles des alliances obtenues. La première partie de cette thèse est achevée par la proposition d'un framework pour la conception et l'analyse des protocoles de contrôle de topologie dans les MANETs. Nous avons identifié les points communs des algorithmes de contrôle de topologie conçus pour les réseaux mobiles ad hoc et nous avons enrichi le simulateur NS-2 avec un ensemble d'extensions pour supporter le contrôle de topologieWe are interested in this thesis to graph-based approaches to deal with some challenges in networking, namely, graph topologies of mobile ad hoc networks (MANETs) and process model matchmaking in large scale web service. We propose in the first part: (1) a generic mechanism using mobility information of nodes to maintain a graph topology of the network. We show particularly, how to use the prediction of future emplacements of nodes to maintain a connected dominating set of a given MANET. (2) distributed algorithms to construct minimal global offensive alliance and global defensive alliance sets in MANETs. We also introduce several heuristics to get a better approximation of the cardinality of the alliance sets which is a desirable property for practical considerations. (3) a framework to facilitate the design and evaluation of topology control protocols in MANETs. We propose in the framework, a common schema for topology control based on NS-2 simulator and inspired from the commonalities between the components of the topology control algorithms in MANETs. In the second part, we focus on process model matchmaking. We propose two graph-based solutions for process model inexact matching to deal with high computational time of existing work in the literature. In the first solution, we decompose the process models into their possible execution sequences. After, we propose generic graph techniques using string comparator metrics for process model matchmaking based on this decomposition. In order to get better optimization of the execution time and to deal with process model matching in large scale web services, the second solution combines a spectral graph matching with structural and semantic proposed approaches. This solution uses an eigen-decomposition projection technique that makes the runtime faster
40
Palesi, Frédéric. "Dynamique sur les espaces de représentations de surfaces non-orientables." Phd thesis, Université Joseph Fourier (Grenoble), 2009. http://tel.archives-ouvertes.fr/tel-00443930.
Full textAbstract:
Nous considérons l'espace de représentations Hom(Pi,G) d'un groupe de surface Pi dans un groupe de Lie G, et l'espace de modules X(Pi,G) des classes de conjugaison de ces représentations. Le groupe modulaire de la surface sous-jacente agit naturellement sur ces espaces, et cette action possède une dynamique très riche qui dépend du choix du groupe de Lie G, et de la composante connexe de l'espace sur laquelle on se place. Dans cette thèse, nous étudions le cas où S est une surface non-orientable. Dans la première partie, nous étudions les propriétés dynamiques de l'action du groupe modulaire sur l'espace de modules X(Pi, SU(2)) et prouvons que cette action est ergodique lorsque la caractéristique d'Euler de la surface est inférieure à -2. Dans la deuxième partie, nous montrons que l'espace des représentations Hom(Pi, PSL(2,R)) possède deux composantes connexes indexées par une classe de Stiefel-Whitney.
41
Dalud-Vincent, Monique. "Modèle prétopologique pour une méthodologie d'analyse de réseaux : concepts et algorithmes." Lyon 1, 1994. http://www.theses.fr/1994LYO10040.
Full textAbstract:
Dans le cadre des problematiques portant sur les reseaux sociaux, on s'interesse plus particulierement aux problemes methodologiques que rencontre le sociologue lorsqu'il cherche, sur la base d'une conceptualisation mathematique de la notion de reseau (un reseau etant percu comme une famille de relations sur une population donnee), a operer une classification des sommets du reseau. On montre que les methodes utilisees jusque-la, qui sont pour la plupart des methodes americaines basees sur les notions d'equivalences structurale ou reguliere, amenent a construire des algorithmes trouvant leur justification en analyse des donnees, notamment par construction d'une distance qui reste de toute facon artificielle et discutable compte tenu de la nature des donnees. Nous proposons une methode qui conserve la nature discrete des donnees et qui, de plus, est basee sur de nouvelles hypotheses sociologiques. Ces dernieres (definition de contextes dans le reseau puis decomposition des contextes en peripheries selon un critere de vulnerabilite/non-vulnerabilite des positions) s'inspirent d'applications deja realisees dans ce domaine, dont une enquete mise en uvre par l'ined. L'outil trouve sa justification en pretopologie, domaine qui recouvre simultanement la theorie des graphes et la topologie. Nous avons pu ainsi demontrer un certain nombre de resultats formels et algorithmiques relatifs a la connexite en pretopologie (notamment dans le cas de pretopologies de type v). Du point de vue des applications, l'outil a permis de traiter plusieurs jeu de donnees relatifs a des enquetes de sociabilite. Les classifications obtenues semblent interessantes pour le sociologue dans le sens ou l'on fait apparaitre une correlation entre les caracteristiques socio-demographiques des individus et leur position dans le reseau (la position etant definie par notre methode)
42
Bourgeau, Thomas. "Capture de la dynamique de la topologie de l'internet au niveau IP." Paris 6, 2013. http://www.theses.fr/2013PA066677.
Full textAbstract:
La cartographie à grande échelle de la topologie de l'Internet au niveau IP est généralement obtenue grâce à des systèmes de mesures distribués qui permettent d'orchestrer l'outil Traceroute afin de mesurer les chemins empruntés depuis plusieurs sources vers plusieurs destinations dans le réseau. Cette information est importante pour les opérateurs de réseaux afin de mieux suivre l'état de leur infrastructure, de réagir à des pannes et de détecter des anomalies tandis que les chercheurs utilisent ces informations pour modéliser et comprendre le comportement de la topologie du réseau sous-jacent. Cependant, les approches existantes pour mesurer la topologie du réseau IPv4 publique nécessitent souvent un ou plusieurs jours pour obtenir un graphe complet, ce qui est trop lent pour capturer une grande partie de la dynamique du réseau. Ainsi, de nouveaux algorithmes de mesure doivent être envisagés pour capturer fidèlement la dynamique du réseau. Cette thèse propose une amélioration fondamentale pour la conception de systèmes de mesure distribués et à large échelle permettant de capturer la topologie du réseau au niveau IP. Ces systèmes se sont orientés sur des mesures exhaustives des routes de bout en bout et par conséquence nécessitent un temps considérable pour obtenir un graphe du réseau. Pour y remédier, notre thèse propose une approche centrée directement sur la capture et l'obtention du graphe du réseau au niveau IP, qui est, par conséquent, beaucoup plus rapide. En plus de la mesure au niveau IP, cette thèse développe une nouvelle approche de services de mesure réseaux à travers la conception et le déploiement d'une infrastructure fédérée de surveillance réseauLarge-scale distributed network route tracing systems obtain the IP-level internet topology by orchestrating Traceroute-like tool on distributed sources that capture the paths to several destinations in the network. This information is important to network operators to better monitor the state of their network, react to failures and detect anomalies while researchers use it to model and understand the behavior of the underlying network topology. However, existing approaches to measuring the public IPv4 network space often require one or more days to obtain a full graph, which is too slow to capture much of the network's dynamics. Thus, new network route tracing system algorithms are highly expected to reach the requirements of scalability, measurement speed, and dynamics capture accuracy. This thesis proposes a fundamental improvement to distributed IP-level Internet topology measurement systems. Such systems have focused on conducting full end-to-end route traces and as a result take a considerable time to obtain a graph of the network. Here, we propose an approach focused directly on obtaining the graph, which is, as a result, much faster (presuming the principal goal is to obtain this graph, rather than full routes). The main benefit of our approach is that we can get a much better view of the dynamics of the network at the IP-level. In addition to IP-level measurement, this thesis develops a novel approach to network topology services by designing a federated monitoring infrastructure that exposes a wide range of measurement metrics for testbed users
43
Garcia, Cantu Ros Anselmo. "Thermodynamic and kinetic aspects of interaction networks." Doctoral thesis, Universite Libre de Bruxelles, 2007. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210420.
Full textAbstract:
In view of the fact that a same complex phenomenon can be approached by different conceptual frameworks, it is natural to inquire on the possibility to find connections between different types of quantities, such as topological, dynamical, statistical or thermodynamical, characterizing the same system. The present work is built on the idea that this line of approach can provide interesting insights on possible universal principles governing complex phenomena. In Chapter I we introduce concepts and tools of dynamical systems and thermodynamics as applied in macroscopic scale description as well as, for a later use, a number of selected representative models. In Chapter II we briefly present the elements of the theory of Markov processes describing a large class of stochastic process and also introduce some important concepts on the probabilistic description of deterministic systems. This chapter ends with a thermodynamic formulation accounting for the evolution of the entropy under the effect of stochastic fluctuations. In Chapter III, after introducing the main concepts and recent advances in network theory, we provide a connection between dynamical systems and network theory, which shows how universal structural properties of evolving networks can arise from deterministic dynamics. More specifically, we show explicitly the relation between the connectivity patterns of these networks and the indicators of the underlying dynamics, such as the local Lyapunov exponents. Our analysis is applied to representative models of chaotic maps, chaotic flows and is finally extended to stochastic processes. In Chapter IV we address the inverse problem, namely, processes whose dynamics is determined, in part, by the structure of the network in which they are embedded. In particular, we focus on systems of particles diffusing on a lattice and reacting instantaneously upon encountering each other. We study the role of the topology, the degree of synchronicity of motion and the reaction mechanism on the efficiency of the process. This lead us to identify a common generic mechanism responsible for the behavior of the efficiency, as a function of the control parameters. Finally, in Chapter V we study the connection between the topology and the thermodynamic properties of reaction networks, with focus on the entropy production and the system’s efficiency at nonequilibrium steady states. We also explore the connection between dynamic and thermodynamic properties of nonlinear feedbacks, as well as the response properties of reaction networks against both deterministic and stochastic external perturbations. We address networks of varying topologies, from regular lattices to complex structures./Le présent travail s’inscrit dans le domaine de recherche sur les systèmes complexes. Différentes approches, basées des systèmes dynamiques, de la thermodynamique des systèmes hors d’équilibre, de la physique statistique et, plus récemment, de la théorie des réseaux, sont combinés afin d’explorer des liens entre différentes types de grandeurs qui caractérisent certaines classes de comportements complexes. Dans le Chapitre I nous introduisons les principaux concepts et outils de systèmes dynamiques et de thermodynamique. Dans le Chapitre II nous présentons premièrement des éléments de la théorie de processus de Markov, ainsi que les concepts à la base de la description probabiliste des systèmes déterministes. Nous finissons le chapitre en proposant une formulation thermodynamique qui décrit l’évolution de l’entropie hors d’équilibre, soumis à l’influence de fluctuations stochastiques. Dans le Chapitre III nous introduisons les concepts de base en théorie des réseaux, ainsi qu’un résumé générale des progrès récents dans le domaine. Nous établissons ensuite une connexion entre la théorie des systèmes dynamiques et la théorie de réseaux. Celle-ci permet d’approfondir la compréhension des mécanismes responsables de l’émergence des propriétés structurelles dans des réseaux crées par des lois dynamiques déterministes. En particulier, nous mettons en évidence la relation entre des motifs de connectivité de ce type de réseaux et des indicateurs de la dynamique sous-jacente, tel que des exposant de Lyapounov locaux. Notre analyse est illustrée par des applications et des flots chaotiques et étendue à des processus stochastiques. Dans le Chapitre IV nous étudions le problème complémentaire, à savoir, celui de processus dont la dynamique est déterminée, en partie, par la structure du réseau dans lequel elle se déroule. Plus précisément, nous nous concentrons sur le cas de systèmes de particules réactives, diffusent au travers d’un réseau et réagissant instantanément lorsqu’un rencontre se produit entre elles. Nous étudions le rôle de la topologie, du degré de synchronicité des mouvements et aussi celui du mécanisme de réaction sur l’efficacité du processus. Dans les différents modèles étudiés, nous identifions un mécanisme générique commun, responsable du comportement de l’efficacité comme fonction des paramètres de contrôle. Enfin, dans le Chapitre V nous abordons la connexion entre la topologie et les propriétés thermodynamiques des réseaux de réactions, en analysant le comportement local et global de la production d’entropie et l’efficacité du système dans des état stationnaires de non-équilibre. Nous explorons aussi la connexion entre la dynamique et les propriétés de boucles de rétroaction non linéaires, ainsi que les propriétés de réponse des réseaux de réaction à des perturbations stochastiques et déterministes externes. Nous considérons le cas de réseaux à caractère régulier aussi bien que celui de réseaux complexes.
Doctorat en Sciences
info:eu-repo/semantics/nonPublished
44
Cuneo, Rémi. "Généralisation d'une méthode de petites simplifications due à Mikhaïl Gromov et Yann Ollivier en géométrie des groupes." Thesis, Aix-Marseille 1, 2011. http://www.theses.fr/2011AIX10026/document.
Full textAbstract:
Dans un article publié en 2003, M.Gromov propose une reformulation de la théorie des petites simplifications en géométrie des groupes. Dans cette version, un graphe fini définit une présentation finie de groupe; les générateurs du groupe sont les étiquettes du graphe; les relateurs sont les mots associés aux cycles; les morceaux, mots "courts " qui permettent les petites simplifications dans un groupe, sont des mots qui étiquettent deux chemins distincts du graphe. Cette thèse prend pour point de départ une brève description de cette théorie publiée par Y. Ollivier en 2006. Le concept de groupe de présentation finie à "petites simplifications", développé par R. Lyndon, M. Greendlinger et autres dans les années 60 et 70, est précurseur des groupes hyperboliques de M.Gromov à la fin des années 80, pour lesquels les propriétés combinatoires de la présentation entraînent des propriétés algébriques du groupe. Dans notre travail, nous fondons de manière rigoureuse la théorie des petites simplifications du point de vue des graphes, et développons le concept de base de "mégatuiles", utilisé implicitement par Y. Ollivier dans son article. Nous étendons ses résultats aux cas non-hyperboliques et non-métriques (par exemple$C(4)-T(4)$). Ce point de vue permet une nouvelle preuve, plus naturelle, de la résolubilité des problèmes du mot et de conjugaison pour les présentations des groupes des entrelacs alternés premiers. Nous prolongeons également les résultats d'un théorème de M. Greendlinger au cas non-métrique, répondant ainsi à une question d'I. KapovichIn a paper published in 2003, M.Gromov proposes a rewording of the small cancellation theory in geometric group theory. In this version, a finite graph defines a finitely presented group; generators of the group are the labels of the graph; relators are the words associated with cycles; pieces, "short" words which allow small cancellations in a group, are words which label two distinct paths in the graph.Our thesis relies on a brief description of this theory published in2006 by Y.Ollivier. The concept of finitely presented "small cancellation" group, developed by R.Lyndon, M.Greendlinger and others in the 60's and 70's, is a precursor of Gromovword-hyperbolic groups in the late of the 80's, for which combinatorial properties of the presentation imply algebraic properties of the group. In our work, we build a rigorous small cancellation theory in terms of graphs, and develop the basic concept of "megatiles", implicitly used by Y. Ollivier in his article. We extend his results to non-hyperbolic and non-metric cases (eg. $C(4)-T(4)$). This point of view allows a new proof, more natural, of thesolvability of word and conjugacy problems for presentations of prime alternating link groups. We also extend the results of a M.Greendlinger theorem to thenon-metric case, in response to a question of I. Kapovich
45
Mokhtarian, Hossein. "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." Thesis, Université Grenoble Alpes (ComUE), 2019. http://www.theses.fr/2019GREAI013/document.
Full textAbstract:
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 FrameworkAdditive 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
46
Caudron, Alain. "Classification des noeuds et des entrelacs." Grenoble 2 : ANRT, 1987. http://catalogue.bnf.fr/ark:/12148/cb37603922w.
Full text
47
Prévost, Stéphanie. "Modélisation implicite et visualisation multi-échelle par squelette à union de boules et graphe de recouvrement." Reims, 2001. http://www.theses.fr/2001REIMS014.
Full textAbstract:
Afin de répondre aux besoins des biologistes face à l'évolution des systèmes d'acquisition de données, nous avons élaboré une plate forme logicielle devant à terme de permettre l'étude, la manipulation et l'analyse des données biomédicales spatio-temporelles, leur besoin ayant guidé nos choix. L'objet de cette thèse est donc de proposer un système hybride et global : hybride par son exploitation d'outils sortis aussi bien du domaine de l'analyse que de la synthèse d'images, comme la carte de distances euclidiennes, preuve d'une collaboration étroite entre ces deux domaines est possible et fructueuse pour l'accélération des processus mis en oeuvre, global pour sa capacité à réaliser, à partir d'un unique modèle, différentes applications utiles aux biologistes. La pierre angulaire de ce système est le modèle implicite d'union de boules dont les principales caractéristiques sont d'être exact, compact, et dual entre les espaces Z3 et R3. Ce modèle, par ses deux premières propriétés, nous permet de répondre aux problèmes de la quantité d'informations à traiter, tout en conservant la même qualité. . .
48
Morvan, Michel. "Algorithmes linéaires et invariants d'ordres." Montpellier 2, 1991. http://www.theses.fr/1991MON20022.
Full textAbstract:
L'algorithmique des ensembles ordonnes occupe une place grandissante en informatique. Elle est etudiee ici sous divers aspects: - etude de la complexite concrete d'algorithmes de fermeture et reduction transitive de graphes sans circuit dans des cas particuliers; - etude du probleme de la dimension des ordres d'intervalles: trois nouvelles bornes sont obtenues ainsi qu'un encadrement a deux pres par le nombre chromatique d'un diagramme associe. Etude du nombre chromatique des diagrammes sur des classes particulieres. - modelisation a l'aide d'ensembles ordonnes de systemes distribues et utilisation du modele pour l'etude de mesures de concurrence; - etude des extensions d'intervalle minimales d'un ensemble ordonne. Caracterisation. Invariance de comparabilite. Algorithmes de generation
49
Martin, Alexandre. "Topologie et géométrie des complexes de groupes à courbure négative ou nulle." Phd thesis, Université de Strasbourg, 2013. http://tel.archives-ouvertes.fr/tel-00821442.
Full textAbstract:
Étant donné un complexe de groupes, quand peut-on déduire une propriété de son groupe fondamental à partir des propriétés analogues de ses groupes locaux ? Ce problème naturel de géométrie des groupes a fait l'objet de nombreux travaux dans le cas des graphes de groupes et des complexes de groupes finis. Cette thèse se propose de développer des outils géométriques pour étudier le cas des complexes de groupes à courbure négative ou nulle. Nous nous intéressons à des propriétés de nature asymptotique : EZ-structures, hyperbolicité. Ce faisant, nous démontrons un théorème de combinaison pour les groupes hyperboliques qui généralise au complexe de groupes de dimension arbitraire un théorème de Bestvina-Feighn.
50
Tetley, Romain. "Analyse mixte de protéines basée sur la séquence et la structure - applications à l'annotation fonctionnelle." Thesis, Université Côte d'Azur (ComUE), 2018. http://www.theses.fr/2018AZUR4111/document.
Full textAbstract:
Dans cette thèse, l'emphase est mise sur la réconciliation de l'analyse de structure et de séquence pour les protéines. L'analyse de séquence brille lorsqu'il s'agit de comparer des protéines présentant une forte identité de séquence (≤ 30\%) mais laisse à désirer pour identifier des homologues lointains. L'analyse de structure est une alternative intéressante. Cependant, les méthodes de résolution de structures sont coûteuses et complexes - lorsque toutefois elles produisent des résultats. Ces observations rendent évident la nécessité de développer des méthodes hybrides, exploitant l'information extraite des structures disponibles pour l'injecter dans des modèles de séquence. Cette thèse produit quatre contributions principales dans ce domaine. Premièrement, nous présentons une nouvelle distance structurale, le RMSDcomb, basée sur des patterns de conservation structurale locale, les motifs structuraux. Deuxièmement, nous avons développé une méthode pour identifier des motifs structuraux entre deux structures exploitant un bootstrap dépendant de filtrations. Notre approche n'est pas un compétiteur direct des aligneurs flexibles mais permet plutôt de produire des analyses multi-échelles de similarités structurales. Troisièmement, nous exploitons les méthodes suscitées pour construire des modèles de Markov cachés hybrides biaisés vers des régions mieux conservées structurellement. Nous utilisons un tel modèle pour caractériser les protéines de fusion virales de classe II, une tâche particulièrement ardue du fait de leur faible identité de séquence et leur conservation structurale moyenne. Ce faisant, nous parvenons à trouver un certain nombre d'homologues distants connues des protéines virales, notamment chez la Drosophile. Enfin, en formalisant un sous-problème rencontré lors de la comparaison de filtrations, nous présentons un nouveau problème théorique - le D-family matching - sur lequel nous démontrons des résultats algorithmiques variés. Nous montrons - d'une façon analogue à la comparaison de régions de deux conformations d'une protéine - comment exploiter ce modèle théorique pour comparer deux clusterings d'un même jeu de donnéesIn this thesis, the focus is set on reconciling the realms of structure and sequence for protein analysis. Sequence analysis tools shine when faced with proteins presenting high sequence identity (≤ 30\%), but are lack - luster when it comes to remote homolog detection. Structural analysis tools present an interesting alternative, but solving structures - when at all possible- is a tedious and expensive process. These observations make the need for hybrid methods - which inject information obtained from available structures in a sequence model - quite clear. This thesis makes four main contributions toward this goal. First we present a novel structural measure, the RMSDcomb, based on local structural conservation patterns - the so called structural motifs. Second, we developed a method to identify structural motifs between two structures using a bootstrap method which relies on filtrations. Our approach is not a direct competitor to flexible aligners but can provide useful to perform a multiscale analysis of structural similarities. Third, we build upon the previous methods to design hybrid Hidden Markov Models which are biased towards regions of increased structural conservation between sets of proteins. We test this tool on the class II fusion viral proteins - particularly challenging because of their low sequence identity and mild structural homology. We find that we are able to recover known remote homologs of the viral proteins in the Drosophila and other organisms. Finally, formalizing a sub - problem encountered when comparing filtrations, we present a new theoretical problem - the D-family matching - on which we present various algorithmic results. We show - in a manner that is analogous to comparing parts of two protein conformations - how it is possible to compare two clusterings of the same data set using such a theoretical model