To see the other types of publications on this topic, follow the link: Algorithmique de graphes.
Dissertations / Theses on the topic 'Algorithmique de 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 'Algorithmique de 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
Mazoit, Frédéric. "Décomposition algorithmique des graphes." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2004. http://tel.archives-ouvertes.fr/tel-00148807.
Full textAbstract:
Dans cette thèse, nous nous intéressons à deux types de décompositions des graphes introduits par Robertson et Seymour: les décompositions arborescentes et les décompositions en branches. À ces décompositions sont associés deux paramètres des graphes: la largeur arborescente et la largeur de branches. Nous montrons que ces deux décompositions peuvent être vues comme issues d'une même structure combinatoire; les deux paramètres mentionné ci-dessus sont égaux aux valeurs minimales de deux paramètres de cette structure commune. En poussant plus avant cette analogie, nous montrons comment adapter une technique de calcul de la largeur arborescente au calcul de la largeur de branches. Ceci nous permet de calculer la largeur de branches des graphes de nombre astéroïde borné ayant un nombre polynômial de séparateurs minimaux et celle des graphes d-trapézoïdes circulaires. Ce parallèle nous permet aussi d'adapter certains résultats structurels sur les décompositions en branches aux décompositions arborescentes. Dans le cas des graphes planaires, nous interprétons ces propriétés à l'aide d'outils topologiques. De cette façon, nous donnons une démonstration simple d'un théorème de dualité reliant la largeur arborescente d'un graphe planaire et celle de son dual. Ces outils nous permettent aussi d'énumérer de façon efficace les séparateurs minimaux des graphes planaires.
2
Angelier, Pierre. "Algorithmique des graphes de visibilité." Paris 7, 2002. http://www.theses.fr/2002PA077007.
Full text
3
Godard, Emmanuel. "Réécritures de graphes et algorithmique distribuée." Bordeaux 1, 2002. http://www.theses.fr/2002BOR12518.
Full textAbstract:
Un système distribué peut être représenté par un graphe étiqueté : les sommets correspondent aux processeurs, les arêtes aux liens de communication et les étiquettes associées aux sommets codent les états des processeurs. Un algorithme distribué est alors décrit par un système de règles de transition locale où l'étiquette suivante d'un sommet est fonction de son étiquette actuelle et de celles de ses voisins (réétiquetage local). Les réétiquetages opérant sur des voisinages disjoints se déroulent en parallèle, de manière asynchrone. Dans ce cadre, on étudie la réalisabilité et non-réalisabilité des tâches distribuées. Nous illustrerons notre méthode en nous intéressant en particulier à certains problèmes spécifiques aux systèmes distribués (élection d'un noeud, reconnaissance de certaines propriétés topologiques du graphe sous-jacent au réseau, calcul de métriques du réseau comme par exemple la taille ou le diamètre). Dans tous ces cas, on présente une caractérisation complète de ce qui est réalisable par calcul distribué en fonction de la topologie du graphe sous-jacent mais également du degré de connaissance qu'a le réseau sur lui-même ("connaissance structurelle"). Ces conditions nécessaires et suffisantes sont principalement exprimées en termes de fermetures par s̀̀imilarités'' des familles de réseaux considérées. Ces s̀̀imilarités'' sont décrites de manière combinatoire à l'aide de morphismes de graphes particuliers : les revêtements et les quasi-revêtements. Les preuves des conditions nécessaires emploient des techniques de simulation à base de revêtements et quasi-revêtements. Les algorithmes distribués présentés pour les preuves des conditions suffisantes se fondent essentiellement sur un algorithme de cartographie du réseau sous-jacent. Celui-ci est construit à partir des extensions d'un algorithme d'énumération de A. Mazurkiewicz et d'un algorithme de détection des propriétés stables de Shy, Szymanski et Prywes.
4
Lyaudet, Laurent. "Graphes et hypergraphes : complexités algorithmique et algébrique." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2007. http://tel.archives-ouvertes.fr/tel-00905137.
Full textAbstract:
Attention, ce résumé comporte un peu d'ironie et d'humour. Dans ce mémoire, nous défendons l'idée selon laquelle, pour tout modèle de calcul raisonnable, ce n'est plus tant le modèle qui compte pour caractériser les classes de complexité importantes que la complexité de la structure combinatoire sous-jacente et en définitive d'un graphe sous-jacent. Pour prendre l'exemple des circuits booléens ou algébriques comme modèles, tout ce qui importe est la complexité du graphe orienté sous-jacent au circuit. Par modèle de calcul raisonnable, nous entendons, comme il se doit, un modèle qui étudié sur une classe de graphes standard nous donne la classe de complexité standard attendue afin de satisfaire aux règles élémentaires des tautologies. On pourrait aussi choisir comme modèles raisonnables les modèles Turing-complet (ou une autre notion de complétude plus adaptée selon les objets calculés), formalisables dans une logique simple (afin d'éviter les "tricheries" et les modèles conçus spécialement pour faire échouer la belle idée défendue). Néanmoins, cette seconde option n'étant pas sans risque, nous nous contentons de la proposer. La thèse défendue est une version un peu plus formalisée et précise mathématiquement de cette idée aux contours un peu flous et qui est donc nécessairement un peu fausse telle quelle.
5
Ziti, Soumia. "Classes particulières de graphes : aspects structurels et algorithmique." Orléans, 2006. http://www.theses.fr/2006ORLE2037.
Full textAbstract:
Dans cette thèse nous nous intéressons, d'abord, au principe de la décomposition des graphes qui permet de découper un graphe en sous graphes ayant des propriétés particulières et qui ont des liens spécifiés entre eux. Nous citons ainsi les méthodes de décompositions les plus importantes: décomposition modulaire qui peut être appliquée à un graphe arbitraire, elle est un outil puissant pour résoudre plusieurs problèmes d'optimisation lorsqu’on considère des classes particulières de graphes. Nous abordons aussi, des variantes de cette décomposition modulaire comme la décomposition en split et des classes particulières comme les cographes. Ensuite, la décomposition canonique qui est une adaptation de la décomposition modulaire au cas des graphes bipartis. Puis nous abordons le sujet des algorithmes dynamiques et leurs applications notamment à la classe des graphes bisplits étendus qui sont totalement décomposables par décomposition canonique. Finalement nous évoquons le sujet des graphes avec des configurations clairsemés en se basant sur la structure de P4 (chaîne de quatre sommets) et en étudiant la densité de présence de cette structure dans un graphe général comme les graphes P4-clairsemés ou (P4-clairsemés)-clairsemés, ou des situations analogues dans le cas des graphes bipartis comme le sont les graphes (P7, Star123)-clairsemés ou Star123-clairsemés.
6
Nichitiu, Codrin. "Algorithmique sur graphes d'automates : election d'un chef, simulations." Lyon, École normale supérieure (sciences), 1999. http://www.theses.fr/1999ENSL0138.
Full textAbstract:
Dans cette these, nous presentons quelques contributions a l'algorithmique sur des graphes d'automates, notamment pour le probleme dit d'election d'un chef, ainsi que pour l'etude de simulations d'un graphe par un autre, afin d'aider a eclaircir des questions de complexite. Un graphe d'automates est un graphe (regulier, infini) dont les sommets sont munis d'une copie d'un meme automate fini fixe. Les automates finis sont synchrones, leur alphabet d'entree est l'ensemble de d-uplets des etats des voisins, avec d le degre du graphe, et une configuration est la fonction donnant l'etat courant pour chaque sommet. L'election du chef consiste a trouver un ensemble d'etats et une fonction de transition de l'automate fini afin qu'a partir d'une configuration ou tous les sommets sont dans le meme etat, on aboutisse par iterations a une configuration ou un seul sommet est dans un etat special nomme chef, et les autres, dans des etats speciaux nommes soldats. Nous presentons des algorithmes pour quelques classes de graphes euclidiens et hyperboliques, en temps lineaire et en temps quadratique. Une simulation d'un graphe d'automates par un autre represente le fait de mimer son comportement, c'est-a-dire le fait de pouvoir envoyer le graphe d'evolution d'un des graphes sur celui de l'autre, bijectivement. Le graphe d'evolution est un graphe dont les sommets sont les configurations du graphe d'automates et les arcs donnent les iterations d'une configuration a une autre. Nous prouvons des liens d'equivalence entre l'existence des simulations de types particuliers et des proprietes d'isomorphisme de graphes, et donnons des simulations effectives pour une classe de graphes reguliers hyperboliques, en vue de l'etude d'une hierarchie de complexite.
7
Chalopin, Jérémie. "Algorithmique distribuée, calculs locaux et homomorphismes de graphes." Bordeaux 1, 2006. http://www.theses.fr/2006BOR13257.
Full textAbstract:
Dans cette thèse, on étudie ce qui est calculable dans différents modèles d'algorithmique distribuée. Les modèles considérés correspondent à différents niveaux d'abstraction et à différents niveaux de synchronisation entre les processus d'un système distribué. On s'intéresse en particulier au problèmes de l'élection et du nommage dans ces différents modèles. Pour chaque modèle, on caractérise les systèmes distribués dans lesquels on peut résoudre ces problèmes et on étudie la complexité des problèmes de décision correspondants. Nos caractérisations utilisent des homomorphismes de graphes qui préservent certaines propriétés locales. Nos preuves sont constructives : quand on peut résoudre l'élection (ou le nommage) dans un réseau, on présente un algorithme d'élection (ou de nommage) pour ce réseau. Ces problèmes permettent de mettre en évidence les différences entre les puissances de calculs des différents modèles considérés. De plus, l'étude de ces problèmes permet de mettre à jour les bons outils qui permettent d'étudier ce qui est calculable de manière distribuée dans les différents modèles.
8
Bricage, Marie. "Modélisation et Algorithmique de graphes pour la construction de structures moléculaires." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLV031/document.
Full textAbstract:
Dans cette thèse, nous présentons une approche algorithmique permettant la génération de guides de construction de cages moléculaires organiques. Il s'agit d'architectures semi-moléculaires possédant un espace interne défini capable de piéger une molécule cible appelée substrat. De nombreuses œuvres proposent de générer des cages organiques moléculaires obtenues à partir de structures symétriques, qui ont une bonne complexité, mais elles ne sont pas spécifiques car elles ne prennent pas en compte des cibles précises. L'approche proposée permet de générer des guides de construction de cages moléculaires organiques spécifiques à un substrat donné. Afin de garantir la spécificité de la cage moléculaire pour le substrat cible, une structure intermédiaire, qui est une expansion de l'enveloppe du substrat cible, est utilisée. Cette structure définie la forme de l'espace dans lequel est piégé le substrat. Des petits ensembles d'atomes, appelés motifs moléculaires liants, sont ensuite intégrés à cette structure intermédiaire. Ces motifs moléculaires sont les ensembles d'atomes nécessaires aux cages moléculaires pour leur permettre d’interagir avec le substrat afin de le capturerIn this thesis, we present an algorithmic approach allowing the generation of construction guides of organic molecular cages. These semi-molecular architectures have a defined internal space capable of trapping a target molecule called substrate. Many works propose to generate molecular organic cages obtained from symmetrical structures, which have a good complexity, but they are not specific because they do not take into account precise targets. The proposed approach makes it possible to generate guides for the construction of organic molecular cages specific to a given substrate. In order to ensure the specificity of the molecular cage for the target substrate, an intermediate structure, which is an expansion of the envelope of the target substrate, is used. This structure defines the shape of the space in which the substrate is trapped. Small sets of atoms, called molecular binding patterns, are then integrated into this intermediate structure. These molecular patterns are the sets of atoms needed by molecular cages to allow them to interact with the substrate to capture it
9
Durand-Lepoivre, Carole. "Ordres et graphes pseudo-hiérarchiques : théorie et optimisation algorithmique." Aix-Marseille 1, 1989. http://www.theses.fr/1989AIX11250.
Full textAbstract:
Notre propos est l'etude des pseudo-hierarchies qui etendent la notion des hierarchies. Apres avoir etabli diverses proprietes sur les ordres compatibles avec une dissimilarite, les dissimilarites de robinson sont localisees dans les structures metriques de l'analyse des donnees. Des correspondances biunivoques sont etablies entre diferentes dissimilarites de robinson et des pseudo-hierarchies indicees; elles etendent la bijection entre les ultrametriques et les hierarchies indicees. Dans cette nouvelle structure apparait la notion de classes empietantes. Suivent une caracterisation et le lien existant entre tous les ordres compatibles d'une pseudo-hierarchie ou d'une dissimilarite de robinson. Pour une telle representation des donnees, il est necessaire de posseder une approximation robinsonienne. Le critere d'optimisation est celui d'une dissimilarite de robinson inferieure maximale. La solution optimale trouvee possede la propriete d'admettre la meme sous-dominante ultrametrique que la dissimilarite initiale. Plongees dans d'autres structure metriques, diverses optimisations sont resolues selon ce meme critere. L'etude precedente est etendue au cas des preordonnancezs de robinson en correspondance avec les pseudo-hierarchies stratifiees
10
Gély, Alain. "Algorithmique combinatoire : cliques, bicliques et systèmes implicatifs." Clermont-Ferrand 2, 2005. http://www.theses.fr/2005CLF22622.
Full textAbstract:
Cette thèse traite de l'algorithmique d'énumération. Après avoir présenté les concepts particuliers des algorithmes d'énumération, nous nous intéressons plus particuliérement à deux problèmes, l'énumération des cliques maximales et l'énumération des bicliques maximales d'un graphe. Pour ce dernier problème, trois variantes seront traitées : énumération des bicliques maximales induites, non induites et pour le cas particulier des graphes biparti. Cette thèse propose des liens entre les algorithmes existants pour ces problèmes. On s'intéresse à l'énumération des éléments d'une base minimun d'implications. Comme il n'existe pas à l'heure actuelle d'algorithme d'énumération polynomial pour ce problème, les approches présentées ici utilisent un autre angle d'approche : trouver une base minimun plus petite, ou plus rapide à calculer, permettant de reconstruire la base minimum initiale en temps polynomial. Dans ce but, deux résultats sont présentés : les éléments clones d'une relation et la famille des systèmes de fermeture partageant une certaine partie d'une base minimun
11
Nouleho, ilemo Stefi. "Algorithmique de graphes pour la similarité structurelle de molécules et de réactions." Electronic Thesis or Diss., université Paris-Saclay, 2020. http://www.theses.fr/2020UPASG028.
Full textAbstract:
Un plan de synthèse est, pour une molécule donnée, une séquence de réactions permettant de la produire à partir de molécules commercialisées ou facilement synthétisables. En chémoinformatique, prédire ou aider à la conception de plans de synthèse pour de nouvelles molécules est un défi. Cela consiste à analyser les très grandes bases de données de réactions moléculaires existantes pour construire de nouveaux plans de synthèse à partir de plans existants pour des molécules similaires. Dans ce contexte, la similarité entre molécules repose sur la topologie.Nous introduisons une représentation structurelle des molécules appelée graphe de cycles. Cette représentation est basée sur les cycles du graphe moléculaire et leurs interconnexions.Cette représentation canonique permet de définir une mesure de similarité entre les structures de molécules. Elle nécessite un temps de calcul raisonnable. Nos études montrent qu’elle est plus adaptée pour les travaux sur les plans de synthèse que les autres mesures de similarité existantes.À partir des graphes des cycles, nous proposons une classification des réactions en fonction des effets sur la structure des molécules. Il s'agit de la première étape pour la prédiction des plans de synthèseA synthesis pathway is, for a given molecule, a sequence of reactions making possible to obtain it from purchasable molecules or easily synthesizable. In chemoinformatics, predicting or assisting the conception of synthesis pathways for new molecules is a challenge. It consists in analyzing the very large databases of existing molecular reactions to build new synthesis pathways from existing plans of similar molecules. In this context, the similarity between molecules relies on their topology.We introduce a structural representation of molecules called the graph of cycles. This representation is based on the cycles in the molecular graph and their interconnections.This representation is canonical and allows us to define a similarity measure between structures of molecules and is computable in a reasonable amount of time. Our studies show that it is more adapted for works on synthesis pathways than the other existing similarity measures.Based on the graph of cycles, we proposed a classification of reactions according to the effects on the structure of molecules. This is the first step for the prediction of synthesis pathways
12
Ly, Olivier. "Etude algorithmique de complexes simpliciaux infinis." Bordeaux 1, 2000. http://www.theses.fr/2000BOR10544.
Full textAbstract:
On etudie differentes classes de complexes simpliciaux infinis constructifs, d'un point de vue algorithmique. Premierement, nous etudions les surfaces non-compactes sans bord definies, en termes de triangularisations, par des grammaires de remplacement d'hyperarcs : les surfaces hr-equationnelles. Nous donnons un algorithme pour decider si deux telles surfaces sont homeomorphes ou non. Ensuite, nous abordons le cas des surfaces non-compactes a bord. A cet egard, nous generalisons le theoreme de classification de kerekjarto-richards au cas des surfaces non-compactes planaires a bord. Dans une deuxieme partie, nous etudions le cas de la dimension 3. Nous montrons que les 3-varietes hr-equationnelles qui possedent une structure hyperbolique complete sont essentiellement caracterisees a isometrie pres par leurs groupes fondamentaux. Nous abordons ensuite l'etude de ces groupes qui se revelent etre des produits amalgames arborescents de groupes, en nombre infini, mais neanmoins en nombre fini a isomorphisme pres. On s'attache en particulier a en donner des presentations constructives en termes de langages rationnels. Pour finir, nous abordons le cas des graphes automatiques qui generalisent les graphes hr-equationnels. Nous montrons que determiner le nombre de bouts d'un tel graphe est un probleme indecidable. Par ailleurs, nous montrons que ce probleme est equivalent au probleme de determiner si un dol-systeme de graphes ne donne naissance qu'a des graphes connexes ; cette question devient alors aussi indecidable.
13
Morales, Varela Nelson Víctor. "Algorithmique des réseaux de communication radio modélisés par de [sic] graphes." Nice, 2007. http://www.theses.fr/2007NICE4032.
Full textAbstract:
Cette thèse concerne l'étude de l'algorithmique et de la complexité des communications dans les réseaux radio. La particularité des réseaux radio est que la distance de transmission est limitée et que les transmissions interfèrent entre elles (phénomènes de brouillage). Nous modélisons ces contraintes en disant que deux sommets (équipements radio) peuvent communiquer s'ils sont à distance au plus d_T et qu'un noeud interfère avec un autre si leur distance est au plus d_I. Les distances sont considérées soit dans un graphe représentant le réseau, soit dans le plan euclidien. Une étape de communication consistera en un ensemble de transmissions compatibles (n'interférant pas). Nous nous sommes intéressés au problème de rassembler les informations des sommets du réseau en un noeud central appelé puits. Notre objectif est de trouver le nombre minimum d'étapes nécessaires pour réaliser un tel rassemblement et de concevoir des algorithmes réalisant ce minimum. Ce problème est motivé par une question de France Telecom "comment amener Internet dans les villages". Les sommets représentent les maisons des villages qui communiquent entre elles par radio, le but étant d'atteindre une passerelle centrale connectée à Internet par une liaison satellite. Le même problème se rencontre dans les réseaux de senseurs ou il s'agit de collecter les informations des senseurs dans une station de base. Nous avons considéré le cas où chaque sommet a un nombre fixé de paquets à transmettre et où les distances sont mesurées sur le graphe. Nous avons montré que trouver une solution optimale est en général un problème NP-difficile. Nous avons donné un algorithme 4-approché pour un graphe quelconque. Nous avons aussi établi des résultats optimaux ou quasi optimaux pour des topologies particulières comme la grille ou le chemin. Nous avons aussi considéré le cas systolique où on veut transmettre continuellement des paquets, l'objectif étant de minimiser l'écart entre l'envoi de deux paquets d'un même noeud. Nous avons étudié ce problème quand les distances sont mesurées sur le graphe et aussi dans le cas de sommets dans le plan avec distances euclidiennes. Nous avons montré que ce problème était NP-difficile, avons établi un algorithme 4-approché et obtenu des solutions quasi optimales pour les chemins, arbres et grillesThis thesis studies the algorithmics anc complexity of communications in a radio network. Radio networks are particular, because the transmission distance is limited and because certain transmissions may interfere with each other. We model this constraints by assuming that two nodes (radio equipment) can communicate with each other if they are at a distance smaller or equal than d_T and that a node interferes with any other that is at a distance smaller or equal than "d_I. This distances are considered in both cases: when they nodes belong to the Euclidean space and the distance between the nodes is the usual Euclidean distance, and when the distances are measured over a graph representing the network. A round being a set of transmissions that are compatible (do not interfere) we interest ourselves in the problem of gathering information originated at the nodes in the network into a central node called the sink. Our goal is to find the minimum number of rounds required to gather all the information and to devise algorithms that calculate this minimum. This problem is motivated by a question asked by France Telecom about providing internet to villages in France (internet dans les villages). The nodes represent houses (clients) that communicate with each other by means of radio signals, their objective being to access internet using a central gateway which, in turn, is connected to the internet with by satellite. The same problem is found in sensor networks, where information is collected in sensors (the nodes) and has to be gathered in a base station. We considered the case where each node has a fixed number of packets to transmit and the distances are measured over a base-graph. We have shown that the problem of finding an optimal solution is Np-Hard in the general case, but we provided a four approximation algorithm, valid for any base-graph. We have also studied either optimal or nearly optimal solutions for particular topologies like the path and the 2-D grid. We have also studied the systolic case where packets are transmitted permanently, the objective being to satisfy arbitrary traffic demands, per unit of time, with the smallest possible delay. We have studied this variant of the problem in the case where distances are measured on a graph, but also then they are measured in the Euclidean space. We have shown that the problem is NP-Hard, have established a four approximation and obtained either optimal or nearly optimal solutions for the path, trees and subsets of the 2-D grid
14
Quaddoura, Ruzayn. "Méthodes de décomposition, étude structurelle et algorithmique de nouvelles familles de graphes." Amiens, 2003. http://www.theses.fr/2003AMIE0306.
Full text
15
Dicky, Anne. "Une approche algébrique et algorithmique de l'analyse des systèmes de transition." Bordeaux 1, 1985. http://www.theses.fr/1985BOR10509.
Full textAbstract:
Pour caracteriser certaines proprietes des systemes de transition, on definit une algebre formelle dont les operateurs primitifs s'interpretent, dans tout systeme de transition fini comme des fonctions des ensembles d'etats et de transitions de ce systeme calculables par des algorithmes classiques de graphes
16
Berthomé, Pascal. "Contribution à l'algorithmique des graphes: quelques représentations pertinentes de graphes." Habilitation à diriger des recherches, Université Paris Sud - Paris XI, 2006. http://tel.archives-ouvertes.fr/tel-00460292.
Full textAbstract:
Ce document est divisé en deux parties principales. La première partie concerne les résultats que nous avons obtenu au travers de diverses collaborations sur les communications dans les réseaux. Afin de ne pas multiplier les chapitres dans cette partie, nous avons choisi en premier lieu de présenter l'évolution du contexte des réseaux sur lesquels j'ai travaillé durant ces 10 dernières années. En particulier, nous montrons plusieurs facettes que peut recouvrir l'expression \textbf{communications optiques}. Dans un deuxième temps, nous avons regroupé les problèmes abordés en deux chapitres: - le premier s'intéresse à des aspects structurels des graphes utiles pour la construction de protocoles de communication dans les réseaux. - le second aborde une problématique importante dans le contexte actuel de la recherche de la compétitivité: l'optimisation de ressources. La deuxième partie s'intéresse à deux représentations de graphes qui s'avèrent pertinentes pour les problèmes considérés. Elle présente deux problèmes principaux donnant deux chapitres indépendants. Le premier problème abordé dans cette partie concerne un très vieux (au sens informatique) problème issu de la théorie de flots: les flots multi-terminaux. Nous nous sommes attachés à montrer la puissance d'un outil permettant de représenter ces types de flots: les arbres de Gomory-Hu, ainsi que leur utilité dans une version paramétrée du problème. Le second problème présente au travers du calcul du polynôme chromatique une représentation des graphes sous la forme d'arbre de cliques augmenté.
17
Diot, Emilie. "Etude structurelle et algorithmique des graphes pouvant être séparés avec des plus courts chemins." Thesis, Bordeaux 1, 2011. http://www.theses.fr/2011BOR14425/document.
Full textAbstract:
Les graphes sont des objets couramment utilisés pour modéliser de nombreuses situations réelles comme des réseaux routiers, informatiques ou encore électriques. Ils permettent de résoudre des problèmes sur ces réseaux comme le routage (aller d'un sommet à un autre en suivant les arêtes du graphe) ou encore leur exploration (obtenir une carte du graphe étudié). Les réseaux étudiés, et donc les graphes qui les modélisent, peuvent être grands, c'est-à-dire avoir un très grand nombre de sommets. Dans ce cas, comme dans le cas de l'étude de grandes données en général, nous pouvons utiliser le paradigme << Diviser pour mieux régner >> pour répondre aux questions posées. En effet, en travaillant sur des petites parties du graphe et en fusionnant les résultats obtenus sur ces petites parties, on peut obtenir le résultat sur le graphe global. Dans ce document, nous présenterons une manière de décomposer les graphes en utilisant des plus courts chemins comme séparateurs. Cette décomposition permet d'obtenir, par exemple, un routage efficace, un étiquetage compacte pour pouvoir estimer les distances entre les sommets d'un graphe ou encore une navigation efficace dans les graphes<< petit monde >>. Cette méthode va nous permettre de définir de nouvelles classes de graphesGraphs are widely used to MODELISER a lot of real situations like road networks, computers networks or electricity ones. Using them, we can solve problems on these networks like routing (go from a vertex ti another one) or explore them (to have a map of studied graph).Studied networks, and so graphs which MODELISER them, can be large (i.e. have a lot of vertices). In this case, we can use the paradigm "Divide and conquer" to answer the questions. Indeed, working on small parts of graphs and merging the results on these small parts, we can obtain the result on the whole graph.In this document, we present a way to separate graphs using shortest paths like separators. This decomposition let to obtain a compact routing, a compact labeling to estimate the distance between vertices of the graph. This method let us to define new class of graphs
18
Sbihi, Najiba. "Contribution à l'étude des stables dans un graphe par une approche algorithmique." Grenoble 1, 1987. http://www.theses.fr/1987GRE10111.
Full textAbstract:
Sont presentes des differents travaux ayant trait au probleme de l'independant de poids maximum. Il est decrit un algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans k::(1,3). Les graphes parfaits sont etudies. Un theoreme reduisant la h-perfection d'un graphe g a la h-perfection d'un sous-graphe propre de g est demontre. Il est presente une operation de reduction preservant la h-perfection. Un algorithme polynomial de reconnaissance des graphes sans k::(1,3) parfaits est propose. Presentation de cinq theoremes de decomposition des graphes parfaits en termes de p::(4)-structure
19
Ghaemi, Mohammadreza. "Etude de la complexité algorithmique associée à des opérations de décomposition de graphes." Paris 6, 2008. http://www.theses.fr/2008PA066449.
Full textAbstract:
La thèse porte sur des problèmes de complexitè liés à des opération de décomposition de graphes. Etant donné un graphe donné H (clique, stable, biparti, graphe à seuil) et un graphe G n-apparié, on étudie la complexité algorithmique du problème suivant : Existe-t-il un sous-graphe induit de G qui contient exactement un sommet de chacune des n paires de G isomorphe à H?. On montrera enfin que le problème de décomposition des graphes appelés graphes Stubborn est équivalent au problème précédent pour un cas particulier de graphes n-appariés.
20
Bossart, Timothée. "Modèles pour l'optimisation de la simulation au cycle près de systèmes synchrones." Paris 6, 2006. http://www.theses.fr/2006PA066342.
Full text
21
Manoussakis, Georgios Oreste. "Algorithmes combinatoires et Optimisation." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLS517.
Full textAbstract:
Nous introduisons d'abord la classe des graphes $k$-dégénérés qui est souvent utilisée pour modéliser des grands graphes épars issus du monde réel. Nous proposons de nouveaux algorithmes d'énumération pour ces graphes. En particulier, nous construisons un algorithme énumérant tous les cycles simples de tailles fixés dans ces graphes, en temps optimal.Nous proposons aussi un algorithme dont la complexité dépend de la taille de la solution pour le problème d'énumération des cliques maximales de ces graphes. Dans un second temps nous considérons les graphes en tant que systèmes distribués et nous nous intéressons à des questions liées à la notion de couplage lorsqu’aucune supposition n’est faite sur l'état initial du système, qui peut donc être correct ou incorrect. Dans ce cadre nous proposons un algorithme retournant une deux tiers approximation du couplage maximum.Nous proposons aussi un algorithme retournant un couplage maximal quand les communications sont restreintes de telle manière à simuler le paradigme du passage de message. Le troisième objet d'étude n'est pas directement lié à l'algorithmique de graphe, bien que quelques techniques classiques de ce domaine soient utilisées pour obtenir certains de nos résultats.Nous introduisons et étudions certaines familles de polytopes, appelées Zonotopes Primitifs, qui peuvent être décrits comme la somme de Minkowski de vecteurs primitifs. Nous prouvons certaines propriétés combinatoires de ces polytopes et illustrons la connexion avec le plus grand diamètre possible de l'enveloppe convexe de points à coordonnées entières à valeurs dans$[k]$, en dimension $d$. Dans un second temps,nous étudions des paramètres de petites instances de Zonotopes Primitifs, tels que leur nombre de sommets, entre autresWe start by studying the class of $k$-degenerate graphs which are often used to model sparse real-world graphs. We focus one numeration questions for these graphs. That is,we try and provide algorithms which must output, without duplication, all the occurrences of some input subgraph. We investigate the questions of finding all cycles of some givensize and all maximal cliques in the graph. Ourtwo contributions are a worst-case output sizeoptimal algorithm for fixed-size cycleenumeration and an output sensitive algorithmfor maximal clique enumeration for this restricted class of graphs. In a second part weconsider graphs in a distributed manner. Weinvestigate questions related to finding matchings of the network, when no assumptionis made on the initial state of the system. Thesealgorithms are often referred to as selfstabilizing.Our two main contributions are analgorithm returning an approximation of themaximum matching and a new algorithm formaximal matching when communication simulates message passing. Finally, weintroduce and investigate some special families of polytopes, namely primitive zonotopes,which can be described as the Minkowski sumof short primitive vectors. We highlight connections with the largest possible diameter ofthe convex hull of a set of points in dimension d whose coordinates are integers between 0 and k.Our main contributions are new lower bounds for this diameter question as well as descriptions of small instances of these objects
22
Beeker, Benjamin. "Problèmes géométriques et algorithmiques dans des graphes de groupes." Caen, 2011. http://www.theses.fr/2011CAEN2043.
Full textAbstract:
Cette thèse en théorie géométrique des groupes présente plusieurs résultats géométriques et algorithmiques sur les groupes de Baumslag-Solitar généralisés à rang variable (vGBS). Les groupes vGBS sont les groupes admettant une décomposition en graphe de groupes à groupes de sommet et d'arête abéliens libres de type fini. Nous donnons tout d'abord une description détaillé des décompositions JSJ abéliennes des groupes vGBS. Nous décrivons ensuite les décompositions JSJ de compatibilité de ces groupes. Nous démontrons que dans la classe des groupes vGBS, le JSJ abélien classique est algorithmiquement constructible tandis que le JSJ abélien de compatibilité ne l'est pas. Dans un dernier chapitre nous étudions le problème de conjugaison multiple. Nous montrons que, bien que le problème général soit indécidable, il devient résoluble sous certaines restrictionsThis thesis in geometric group theory gives geometric and algorithmic results on the class of generalized Baumslag-Solitar groups of variable rank (vGBS groups). A vGBS group is one that admits a splitting in a graph of groups where all vertex and edge groups are finitely generated free abelian. We first give a description of the abelian JSJ splittings of vGBS groups. We then describe their abelian compatibility JSJ splittings. We show that, in the class of vGBS groups, the “usual” JSJ splitting is algorithmically constructible, while the compatibility JSJ splitting is not. Finaly we study the multiple conjugacy problem. We show that, although the general problem is undecidable, it is solvable under certain restrictions
23
Hanusse, Nicolas. "Navigation dans les grands graphes." Habilitation à diriger des recherches, Université Sciences et Technologies - Bordeaux I, 2009. http://tel.archives-ouvertes.fr/tel-00717765.
Full text
24
Moncel, Julien. "Codes Identifiants dans les Graphes." Phd thesis, Université Joseph Fourier (Grenoble), 2005. http://tel.archives-ouvertes.fr/tel-00010293.
Full textAbstract:
Ce mémoire présente quelques résultats récents sur les codes identifiants. La thèse est structurée en cinq chapitres. Le Chapitre 1 contient les définitions et présente la notion de code identifiant. Dans le Chapitre 2 nous étudions l'aspect algorithmique des codes identifiants. Le Chapitre 3 contient quelques résultats concernant des classes de graphes particulières, à savoir les hypercubes, les grilles, et les cycles. Nous étudions quelques questions extrémales au Chapitre 4. Enfin, le Chapitre 5 présente quelques résultats récents sur les codes identifiants dans les graphes aléatoires. A la fin du document nous résumons les résultats les plus importants que nous avons présentés et nous donnons quelques problèmes ouverts sur le sujet.
25
Dufresne, Yoann. "Algorithmique pour l’annotation automatique de peptides non ribosomiques." Thesis, Lille 1, 2016. http://www.theses.fr/2016LIL10147/document.
Full textAbstract:
La composition monomérique de polymères joue un rôle essentiel dans la comparaison de structures et dans la biologie de synthèse. Cependant, la plupart des ressources moléculaires en ligne donne accès à la structure atomique des molécules et non à leur structure monomérique. Nous avons donc créé un logiciel appelé smiles2monomers (s2m) pour inférer la structure monomérique passer des atomes aux monomères. L’algorithme sous-jacent se déroule en deux phases : une phase de recherche par isomorphisme de sous graphe des monomères au sein de la structure atomique puis une recherche du meilleur pavage non chevauchant des monomères trouvés. La recherche est basée sur un index markovien améliorant les vitesses de recherche de 30% par rapport à l’état de l’art. Le pavage est lui constitué d’un algorithme glouton couplé à un raffinement par “branch & cut”. s2m a été testé sur deux jeux de données déjà annotés. Il retrouve les annotations manuelles avec une excellente sensibilité en des temps très courts. Notre équipe développe Norine, base de données de référence de polymères particuliers appelés Peptides Non Ribosomiques (NRP). s2m, exécuté sur l’ensemble des données de Norine, a mis à jour de nombreuses annotations erronées en base. s2m est donc à la fois capable de créer de nouvelles annotations et d’en corriger des anciennes. Les nouvelles annotations nous servent à la fois à découvrir de nouveaux NRP, de nouvelles fonctionnalités NRP et potentiellement dans le futur à synthétiser des NRP non naturelsThe monomeric composition of polymers is powerful for structure comparison and synthetic biology, among others. However, most of the online molecular resources only provide atomic structures but not monomeric structures. So, we designed a software called smiles2monomers (s2m) to infer monomeric structures from chemical ones. The underlying algorithm is composed of two steps: a search of the monomers using a subgraph isomorphism algorithm fitted to our data and a tiling algorithm to obtain the best coverage of the polymer by non-overlapping monomers. The search is based on a Markovian index improving the execution time by 30% compared to the state of art. The tiling is performed using a greedy algorithm refined by a “branch & cut” algorithm. s2m had been tested on two different already annotated datasets. The software reconstructed the manual annotations with an excellent sensibility in a very short time. Norine database, the reference knowledge base about specific polymers called Non Ri bosomal Peptides (NRP), is developed by our research group. s2m, executed on the Norine database, alerted us about wrong manual annotations. So, s2m not only creates new annotations, but also facilitates the process of annotation curation. The new annotations generated by the software are currently used for the discovery of new NRP, new activities and may be used to create completely new and artificial NRP
26
Maamra, Khaled. "Algorithmes auto-stabilisants efficaces pour les graphes." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLV065/document.
Full textAbstract:
Le projet scientifique dans lequel s’inscrit ma thèse a pour objectif l’élaboration d’algorithmes distribués et efficaces pour les réseaux informatiques. Ce projet vise une catégorie particulière des algorithmes distribués, dits auto-stabilisants. Il s’agit d’algorithmes ayant pour propriété de retrouver un comportement correct suite à une panne dans le réseau et ce, sans aucune intervention humaine. Le travail effectué en collaboration avec mes directeurs de thèse s’est concentré, plus précisément, autour des problèmes de couplage, de cliques et des paradigmes de publications-souscriptions dans ce domaine de l’informatique théorique. Dans un premier temps on a traité le problème du couplage maximal dans sa version anonyme, en fournissant un algorithme auto-stabilisant probabiliste et efficace. Ces travaux sont parus dans le journal PPL. De plus, on s’est intéressé au problème du couplage dans sa version maximum identifiée. Son travail améliore le dernier algorithme présent dans la littérature pour l’approximation de ce type de couplage au 2/3 de la solution optimale. Ces travaux sont parus dans une conférence internationale OPODIS. Par ailleurs, j'ai eu l’opportunité de collaborer en Allemagne avec Prof. Volker Turau au sein du groupe de télématique de l’Université technique de Hambourg. Le cadre de cette collaboration a été les algorithmes auto-stabilisants pour les paradigmes de publication-souscription. Cela a abouti à un algorithme efficace pour la version en canal de ce problème, introduisant la notion de raccourci pour le routage de messages dans ces paradigmes. Les résultats ont fait l’objet d’un Brief Announcement et d’un papier, publiés dans des conférences internationales, SSS et NetSyS. J'ai aussi bénéficié d’une collaboration avec Mr. Gerry Siegemund qui a été accueilli au laboratoire d’Informatique de l’École Polytechnique. Il a été question de trouver un algorithme efficace et auto-stabilisant pour la partition d’un réseau en cliques. Cette collaboration a eu pour résultat un algorithme pour le problème améliorant le dernier en date. Ce résultat est en cours de rédaction pour soumission à une conférence internationaleThe main focus of my thesis is the design of an efficient kind of distributed algorithms, known as: Self-stabilizing. These algorithms have the property to recover from faults in the environment they're executed in, and this without any human intervention. Recovering here, means converging toward a pre-defined, correct configuration. In this setting, I was mainly interested by the problems of matching in graphs, clique partitions and publication subscription paradigms. For the maximal version of the matching problem in anonymous graphs, we achieved a more efficient randomized, self-stabilizing algorithm. This work is published in a journal version in PPL. The maximum version of the same problem, but in an identified setting, led to the design of an efficient self-stabilizing algorithm that approximates the optimal solution up to the 2/3. This result was published at OPODIS. During a research visit at TUHH, Hamburg, Germany. Together with Pr. Volker Turau we tackled the problem of self-stabilizing publish/subscribe paradigms. This led to an algorithm introducing the new notion of short-cuts in this type of structures and was published under a brief announcement and a regular paper at SSS and NetSyS. In collaboration with Mr. Siegemund, then a visiting researcher at LIX, École Polytechnique, we worked on an efficient self-stabilizing algorithm for clique partitions. This work is still in progress and in preparation for an eventual publication
27
Thiebaut, Jocelyn. "Algorithmic and structural results on directed cycles in dense digraphs." Thesis, Montpellier, 2019. http://www.theses.fr/2019MONTS059.
Full textAbstract:
Dans cette thèse, nous nous intéressons à quelques problèmes algorithmiques et structurels du packing de cycles (orientés) dans les graphes orientés denses. Ces problèmes sont notamment motivés par la compréhension de la structure de tels graphes, mais également car de nombreux problèmes algorithmiques sont faciles (résolubles en temps polynomial) sur des graphes orientés acycliques alors qu'il sont NP-difficiles sur les graphes orientés en général.Plus spécifiquement, nous étudions dans un premier temps le packing de cycles et le packing de triangles dans les tournois. Ces problèmes sont les duaux (d'un point de vue programmation linéaire) des problèmes de feedback arc/vertex set qui ont reçu beaucoup d'attention dans la littérature. Nous montrons entre autres qu'il n'y a pas d'algorithme polynomial pour trouver une collection maximale de cycles (respectivement triangles) sommet ou arc-disjointe dans les tournois, sauf si P = NP. Nous nous intéressons également aux algorithmes d'approximations et de complexité paramétrée de ces différents problèmes.Nous étudions ensuite plus en détail ces problèmes dans le cas spécifique où le tournoi admet un feedback arc set qui est un couplage, appelé sparse. Étonnamment, le problème reste difficile dans le cas des triangles sommet-disjoints, mais devient polynomial pour les triangles et cycles arc-disjoints. Ainsi, nous explorons l'approximation et la complexité paramétrée du cas sommet-disjoints dans les tournois sparses.Enfin, nous répondons positivement à une conjecture structurelle sur les bipartis complets k-réguliers par Manoussakis, Song et Zhang datant de 1994. En effet, nous démontrons que tous les digraphes de cette classe non isomorphes à un digraphe particulier possèdent pour tout p pair avec 4 leq p leq |V(D)| - 4 un cycle C de taille p tel que D V(C) est hamiltonienIn this thesis, we are interested in some algorithmic and structural problems of (oriented) cycle packing in dense digraphs. These problems are mainly motivated by understanding the structure of such graphs, but also because many algorithmic problems are easy (i.e. resolvable in polynomial time) on acyclic digraphs while they are NP-difficult in the general case.More specifically, we first study the packing of cycles and the packing of triangles in tournaments. These problems are the two dual problems (from a linear programming point of view) of feedback arc/vertex set that have received a lot of attention in literature. Among other things, we show that there is no polynomial algorithm to find a maximum collection of cycles (respectively triangles) vertex or arc-disjoint in tournaments, unless P = NP. We are also interested in algorithms of approximations and parameterized complexity of these different problems.Then, we study these problems in the specific case where the tournament admits a feedback arc set which is a matching. Such tournaments are said to be sparse. Surprisingly, the problem remains difficult in the case of vertex-disjoint triangles, but the packing of triangles and the packing of arc-disjoint cycles become polynomial. Thus, we explore the approximation and parameterized complexity of the vertex-disjoint case in sparse tournaments.Finally, we answer positively to a structural conjecture on k-regular bipartite tournaments by Manoussakis, Song and Zhang from 1994. Indeed, we show that all digraphs of this non-isomorphic class to a particular digraph have for every p even with 4 leq p leq |V(D)| - 4 a C cycle of size p such that D V(C) is Hamiltonian
28
Herrbach, Claire. "Etude algorithmique et statistique de la comparaison des structures secondaires d'ARN." Bordeaux 1, 2007. http://www.theses.fr/2007BOR13432.
Full textAbstract:
Notre travail s'inscrit dans la problématique de la comparaison de structures d'ARN. Nous étudions en particulier le cas des structures secondaires sans pseudo-noeud, qu'il est possible de modéliser par des arbres ordonnés étiquetés. Il existe des algorithmes polynomiaux d'édition et d'alignement d'arbres. Cependant, les opérations d'édition utilisées par ces algorithmes ne sont pas adaptées pour l'ARN. D'un autre côté, il a été montré que si l'on utilise un jeu d'opérations réalistes d'un point de vue biologique, le problème de l'édition de structures secondaires sans pseudo-noeud est NP-complet. Dans cette thèse, nous étudions le problème de l'alignement, avec ce même jeu d'opérations réaliste, de structures secondaires d'ARN sans pseudo-noeud. Nous proposons un algorithme polynomial d'alignement global et ses variantes d'alignement local et de recherche d'un motif structurel. Puis nous montrons que cet algorithme, et par le même coup l'algorithme classique d'alignement d'arbres ordonnés, a une complexité moyenne en O(n2). Nous avons implanté notre algorithme d'alignement ainsi que ses variantes afin de comparer notre approche aux outils déjà existants, et nous présentons quelques résultats. Nous présentons ensuite un travail préliminaire sur la construction de matrices de scores pour chaque opération d'édition réaliste pour l'ARN. Enfin, nous étudions le problème de sous-structures secondaires communes à un ensemble de structures tertiaires d'ARN, de façon à maximiser le nombre d'empilements. Nous montrons que dans le cas général, ce problème est NP-complet. Cependant, nous donnons un algorithme polynomial dans le cas où le nombre de structures en entrée est fixé.
29
Tichit, Laurent. "Algorithmique des structures biologiques : l'édition d'arborescences pour la comparaison de structures secondaires d'ARN." Bordeaux 1, 2003. http://www.theses.fr/2003BOR12699.
Full textAbstract:
Les molécules d'ARN jouent un rôle fondamentale dans les processus chimiques mis en jeu au coeur de la cellule. Les travaux présentés dans cette thèse concernent la comparaison des structures secondaires d'ARN. Celles-ci ont été formalisées par M. S. Waterman à la fin des années 70 et capturent une grande partie des informations relative à la structure des molécules d'ARN. En se basant sur une approche similaire à celle de Shapiro et Viennot, nous les représentons par des arborescenes ordonnées étiquetés. L'un des objectifs de cette thèse est d'explorer les algorithmes de comparaison d'arborescences existants et d'envisager différentes extensions. La famille d'algorithme étudiée s'appuie sur la généralisation des méthodes de comparaison entre les mots appliquées au génome. Nous choisissons de nous focaliser sur l'un des meilleurs (en complexité) algorithmes de calcul de la distance d'édition connus à ce jour, celui de Zhang-Shasha, et effectuons une analyse exacte de sa complexité en moyenne. Ensuite, nous transposons aux arborescences quelques avancées en matière de comparaison de séquences. Nous proposons deux algorithmes originaux d'édition locale d'arborescences non-ordonnées et ordonnées, puis une extension à l'algorithme de Zhang-Shasha afin d'effectuer une édition densifiée d'arborescences. Puis, nous présentons les résultats d'un point de vue biologique et appliquons cet ensemble d'améliorations aux structures secondaires d'ARN. Ces améliorations concernent la compression structurelle, l'édition locale et l'édition densifiée de structures secondaires. Pour conclure, nous présentons un protoype d'outil logiciel permettant la comparaison de structures secondaires d'ARN et implémentant les diffférents concepts ayant vu le jour au cours de cette thèse.
30
Coudert, David. "Algorithmique et optimisation dans les réseaux de télécommunications." Habilitation à diriger des recherches, Université de Nice Sophia-Antipolis, 2010. http://tel.archives-ouvertes.fr/tel-00466400.
Full textAbstract:
Le contexte général de mes travaux se situe dans les réseaux orientés connexions, que ce soit des réseaux optiques à multiplexage en longueur d'onde (WDM), des réseaux MPLS (multi-protocol label switching), ou encore des réseaux à faisceaux hertziens (wireless backhaul networks). Dans ces réseaux, je m'intéresse à router les flux d'information, à agréger des flux d'information bas débits dans des flux de plus hauts débits, à faire évoluer le routage en cas de variations dans la quantité de trafic à transporter ou dans la topologie du réseau, et à assurer la continuité du trafic en cas de panne simple ou multiple. Pour aborder ces questions, j'utilise des outils variés de l'algorithmique, de la théorie des graphes et de l'optimisation combinatoire.L'ensemble des résultats présentés dans ce document est le fruit de travaux collaboratifs avec les membres de l'équipe-projet MASCOTTE, des collègues d'autres universités, française ou étrangères, et des collègues de France Télécom, Alcatel-Lucent et 3Roam. L'introduction de ce manuscrit résume nos travaux sur le routage, le groupage de trafic, la tolérance aux pannes et la reconfiguration, ainsi que des travaux plus récents sur la minimisation du nombre d'étiquettes dans les réseaux MPLS, le dimensionnement de réseaux de collecte IP sans fil, et sur le routage disjoints d'ensembles particuliers de requêtes. Ensuite, je détaille nos travaux sur le groupage de trafic au travers d'un état de l'art dans le chapitre 3, nos contributions sur la notion de groupes de ressources partageant un risque dans le chapitre 4, et sur la reconfiguration de routages dans le chapitre 5. Le chapitre 6 conclut ce manuscrit en présentant avec quelques directions de recherches.
31
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
32
Lebhar, Emmanuelle. "Algorithmes de routage et modèles aléatoires pour les graphes petits mondes." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2005. http://tel.archives-ouvertes.fr/tel-00011646.
Full textAbstract:
L'objet de cette thèse est l'étude des aspects algorithmiques de l'effet petit monde dans les grands réseaux d'interaction.Les observations expérimentales ont montré que les grands réseaux d'interactions (sociales, informatiques, biologiques), présentaient des propriétés macroscopiques communes. Une d'elles est l'effet petit monde qui consiste en l'existence de chemins très courts entre toutes les paires de noeuds qui peuvent être découverts en n'utilisant qu'une vue locale du réseau. Nous nous intéressons à cette caractéristique algorithmique de l'effet petit monde, à son application au routage informatique décentralisé, et à son émergence dans les réseaux réels.Nous proposons un nouvel algorithme de routage décentralisé sur le modèle aléatoire de petit monde de Kleinberg, qui calcule des chemins de longueur O(log n.(loglog n)^2), asymptotiquement plus courts que ceux des algorithmes existants (en O((log n)^2)). Cet algorithme pourrait également s'appliquer aux réseaux pair-à-pair. Nous précisons cette étude en comparant les charges induites pas les différents algorithmes proposés sur ce modèle.En tentant d'exhiber les caractéristiques minimales d'un graphe qui permettent de l'augmenter en un petit monde par l'ajout de raccourcis aléatoires, nous proposons un nouveau modèle de petit monde qui généralise celui de Kleinberg. Il s'agit d'ajouter une distribution de liens dépendant de la taille des boules de la métrique des distance sous-jacente. Ce modèle peut par ailleurs être étendu simplement pour produire toute distribution des degrés, dont en particulier la fameuse loi de puissance. Enfin, nous proposons le premier schéma distribué qui permette de transformer un réseau de diamètre quelconque en petit monde en ajoutant un seul nouveau lien par noeud, il s'agit d'un premier pas vers la compréhension de l'émergence naturelle du phénomène dans les réseaux réels.
33
Vialette, Stéphane. "Aspects algorithmiques de la prédiction des structures secondaires d'ARN." Phd thesis, Université Paris-Diderot - Paris VII, 2001. http://tel.archives-ouvertes.fr/tel-00628623.
Full textAbstract:
Cette thèse traite deux types de problèmes algorithmiques : des problèmes de triangularisation de matrices booléennes par permutation des lignes et des colonnes et des problèmes de découverte de structures secondaires d'ARN. Nous étudions des problèmes de triangularisation de matrices booléennes par permutation des lignes et des colonnes. Ce problème apparaît, par exemple, lorsque l'on souhaite calculer "en place" un système d'équations. Une façon naturelle d'aborder ce problème est de se placer dans le cadre général de la théorie des graphes et des graphes bipartis en particulier. Nous présentons de nombreux résultats de complexité - essentiellement de NP-complétude - liés à ce problème et introduisons quelques extensions dont nous précisons toujours la complexité. Certaines familles d'ARN sont très précisément définies par des motifs de séquence, et des contraintes structurelles secondaires et tertiaires. La plupart des outils ne sont pas adaptés puisqu'ils n'intègrent pas toutes les connaissances sur la molécule lors de l'exploration des banques de séquences. D'où l'intérêt d'algorithmes de recherche assurant une recherche en séquence et structure par le biais d'un descripteur défini par l'utilisateur intégrant l'ensemble des connaissances caractérisant l'ARN à détecter. Une nouvelle façon d'aborder ce problème consiste en l'étude de problèmes algorithmiques sur les graphes d'intersection d'un ensemble de 2-intervalles. Cette notion de 2-intervalles se trouve dans la lignée des études actuelles en matière d'algorithmique de graphes où l'on étudie de plus en plus les structures des graphes issues de modèles géométriques. Nous présentons plusieurs résultats de complexité et montrons en particulier que la recherche de motifs dans un ensemble de 2-intervalles est un problème NP-complet. Nous nous intéressons, plus particulièrement, à appliquer ces travaux pour la prédiction de motifs biologiques structurés. Plus spécifiquement, nous avons mis au point l'algorithme ORANGE pour la prédiction des introns auto-catalytiques de groupe 1 dans de grandes séquences génomiques. Cet algorithme est une amélioration de l'algorithme CITRON mis au point par F. Lisacek et F. Michel du point de vue de la rapidité d'exécution. De plus, une mise-en-œuvre de l'algorithme ORANGE est accessible en ligne sur Internet.
34
Coudert, David. "Algorithmique et optimisation de réseaux de communications optiques." Phd thesis, Université de Nice Sophia-Antipolis, 2001. http://tel.archives-ouvertes.fr/tel-00008087.
Full textAbstract:
Dans cette thèse, nous nous intéressons aux réseaux de communications optiques avec d'une part des réseaux en espace libre optique et d'autre part des réseaux à fibres optiques.Dans un premier temps, nous étudions l'implantation en espace libre optique de réseaux de communications à l'aide de l'architecture OTIS (Optical Transpose Interconnection System), proposé dans [MMHE93]. Nous proposons une modélisation de ces réseaux par les graphes H(p,q,d) que nous cherchons ensuite à caractériser. Nous étudions en particulier les isomorphismes entre ces graphes et des graphes connus (de Bruijn, Kautz et autres graphes à alphabet). Nous développons une famille de graphes à alphabet contenant de nombreux graphes isomorphes au de Bruijn, que nous utilisons pour obtenir une implantation optimale, au sens de la minimisation du nombre de lentilles, du de Bruijn avec OTIS. Nous étudions aussi une famille de réseaux modélisés par des hypergraphes orientés, appelées stack-Kautz, pour laquelle nous donnons un algorithme de routage et des protocoles de contrôles.
Dans un deuxième temps, nous nous intéressons au problème de la sécurisation par protection dans les réseaux WDM, qui consiste à utiliser des ressources prédéterminées et dédiées pour assurer la continuité du trafic lors de la rupture d'un faisceau de fibres dans le réseau. Nous décrivons de nombreuses stratégies de protection de l'instance et du réseau. Nous étudions plus particulièrement la protection par sous-réseaux qui consiste au partage de ressources de protection par un ensemble de requêtes formant un sous-réseau particulier (circuit). Nous donnons une solution optimale au problème de la protection par sous-réseaux dans le cas où le réseau est un cycle et les requêtes représentent un échange total.
35
Besombes, Jérôme. "Un modèle algorithmique de la généralisation de structures dans le processus d'acquisition du langage." Nancy 1, 2003. http://www.theses.fr/2003NAN10156.
Full textAbstract:
Le sujet de notre étude est l'apprentissage des langages réguliers d'arbres pour la modélisation algorithmique de l'acquisition du langage. L'hypothèse émise est celle d'une structuration arborescente des données mises à disposition de l'apprenti ; ces données sont des phrases correctes entendues et l'apprentissage est effectif dès lors qu'une représentation du langage auquel appartiennent ces phrases est construite. Cette représentation doit permettre de générer de nouvelles phrases compatibles avec le langage et non présentées en exemples. Considérant que le signal perçu (une phrase entendue) est traduit sous forme d'arbre, il apparaît que la généralisation de ces structures arborescente est un élément constitutif de l'apprentissage. Nous avons développé plusieurs modèles pour cette généralisation sous forme d'algorithmes prenant en compte différents types de structures en entrée et différents niveaux d'apport d'information. Ces nouveaux modèles offrent l'avantage d'unifier des résultats majeurs dans la théorie de l'inférence grammaticale, et d'étendre ces résultats, en particulier par la considération de structures nouvelles non étudiées précédemment pour l'apprentissageThe subject of our study is the learning of regular tree languages for an algorithmic modeling of language acquisition. For this, we suppose that data are structured; these data are heard correct sentences and the learning is effective since a representation of the language to which these sentences belong is built. From this representation the learner is able to generate new sentences compatible with the language and not presented as examples. Considering that heard sentences are translated into trees, it appears that the generalization of these tree structures is a component of the learning. We developed several models for this generalization in the form of algorithms taking into account various types of structures as input and various levels of contribution of information. These new models offer the advantage of unifying major results in the theory of the grammatical inference, and of extending these results, in particular by the consideration of new structures not studied previously in the learnability point of view
36
Garcia, Françoise. "Etude et implémentation en ML/LCF d'un système de déduction pour logique algorithmique." Paris 7, 1985. http://www.theses.fr/1985PA077119.
Full textAbstract:
Contribution aux problèmes de validation du logiciel et d'implémentation de systèmes de preuve. Une première partie est consacrée à l'étude d'une logique des programmes, une seconde a la mise en œuvre d'un outil logiciel d'aide à la déduction dans ce système formel
37
Gambette, Philippe. "Méthodes combinatoires de reconstruction de réseaux phylogénétiques." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2010. http://tel.archives-ouvertes.fr/tel-00608342.
Full textAbstract:
Les réseaux phylogénétiques généralisent le modèle de l'arbre pour décrire l'évolution, en permettant à des arêtes entre les branches de l'arbre d'exprimer des échanges de matériel génétique entre espèces coexistantes. De nombreuses approches combinatoires - fondées sur la manipulation d'ensembles finis d'objets mathématiques - ont été conçues pour reconstruire ces réseaux à partir de données extraites de plusieurs arbres de gènes contradictoires. Elles se divisent en plusieurs catégories selon le type de données en entrée (triplets, quadruplets, clades ou bipartitions) et les restrictions de structure sur les réseaux reconstruits. Nous analysons en particulier la structure d'une classe de réseaux restreints, les réseaux de niveau k, et adaptons ce paramètre de niveau au contexte non enraciné. Nous donnons aussi de nouvelles méthodes combinatoires pour reconstruire des réseaux phylogénétiques, à partir de clades - méthode implémentée dans le logiciel Dendroscope - ou de quadruplets. Nous étudions les limites de ces méthodes combinatoires (explosion de complexité, bruit et silence dans les données, ambiguïté des réseaux reconstruits) et la façon de les prendre en compte, en particulier par un pré-traitement des données. Finalement, nous illustrons les résultats de ces méthodes de reconstruction sur des données réelles avant de conclure sur leur utilisation dans une méthodologie globale qui intègre des aspects statistiques
38
Duhaze-Pradines, Loric. "Reachability problems for general rotor walks in graphs." Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPASG051.
Full textAbstract:
Nous nous intéressons dans cette thèse aux propriétés algorithmiques d'un automate cellulaire, les marches de rotors. Ce modèle a été introduit de deux manières différentes. Tout d'abord comme une opération élémentaire d'un autre automate cellulaire : les Sandpiles qui modélisent l'effondrement d'une pile de sable lorsque celle-ci devient trop haute. Mais également, par sa ressemblance avec des modèles stochastiques très étudiés que sont les marches aléatoires. En effet, de nombreuses propriétés structurelles des marches aléatoires (temps d'atteinte, temps de couverture, etc...) sont similaires à celles de cet automate complètement déterministe qu'est la marche de rotor. Cette forme de "dérandomisation" de processus aléatoire a été la motivation principale de cette thèse. Plus précisément, une marche de rotor correspond au mouvement d'une particule sur un graphe orienté en suivant la règle suivante : au départ on fixe un ordre (une numérotation) sur les arcs sortants de chacun des sommets du graphe puis, une fois qu'on a définit la position de départ de la particule, chaque fois que cette dernière est sur un sommet, elle le quitte par l'arc de valeur la plus faible qu'elle n'a pas déjà utilisé. Bien entendu, si tous les arcs ont été utilisés, on redémarre avec l'arc de plus faible valeur. Il existe une multitude de problèmes d'accessibilité sur les rotors dont nous nous appliquons à faire une liste dans cette thèse. Nous donnerons également des résultats de complexité pour certains d'entre eux. Puis nous nous intéresserons à un problème d'accessibilité particulier : ARRIVAL. Si l'on considère un graphe avec des puits tel qu'il existe un chemin orienté entre chaque sommet du graphe et au moins l'un de ces puits, une marche de rotor se termine forcément. Hélas, le nombre d'étapes avant que ce processus ne termine peut être exponentiel. En 2017, Dorhau et al. ont présenté un problème, nommé ARRIVAL, qui est de savoir si la particule finit bien sa course dans un puits donné. Ils ont montré qu'il appartenait aux classes de complexité NP et co-NP. Etant donc un bon candidat à être résolu par un algorithme polynomial, nous nous intéressons à ce problème sur une sous-classe de graphe pour laquelle le nombre d'étapes du processus peut être exponentiel : les Tree-like multigraphes. Il s'agit de multigraphes donc le graphe non-orienté sous-jacent est un arbre. Dans ce contexte, nous avons pu montrer que ce problème pouvait être résolu en temps linéaire et même étendre ces résultats à des versions décisionnelles du problème ARRIVAL connues pour être respectivement NP-complète et PSPACE-complèteIn this thesis, we focus on the algorithmic properties of a cellular automaton known as rotor walks. This model has been introduced in two distinct ways. Firstly, as a fundamental operation within another cellular automaton known as Sandpiles, which models the collapse of a sand pile when it becomes too high. Secondly, due to its resemblance to well-studied stochastic models, such as random walks. Indeed, numerous structural properties of random walks (hitting times, cover times, etc.) are analogous to those of this completely deterministic automaton called the rotor walk. The main motivation for this thesis stems from this "derandomization" of a random process. More precisely, a rotor walk corresponds to the movement of a particle on a directed graph following the following rule: initially, an order (a numbering) is fixed on the outgoing arcs of each vertex of the graph. Once the starting position of the particle is defined, each time it is on a vertex, it leaves through the arc with the lowest value that it has not already used. Of course, if all arcs have been used, the process restarts with the lowest value arc. There is a multitude of accessibility problems on rotors, and we aim to compile a list of them in this thesis. We also provide complexity results for some of these problems. Subsequently, we turn our attention to a specific accessibility problem: ARRIVAL. Considering a graph with sinks such that there is a directed path between each vertex of the graph and at least one of these sinks, a rotor walk inevitably terminates. Unfortunately, the number of steps before this process concludes can be exponential. In 2017, Dorhau et al. introduced a problem called ARRIVAL, which seeks to determine if the particle successfully reaches a given sink. They demonstrated that it belongs to the complexity classes NP and co-NP. Being a strong candidate for polynomial algorithm resolution, we investigate this problem on a subclass of graphs where the step count of the process can be exponential: Tree-like multigraphs. These are multigraphs whose underlying undirected graph is a tree. In this context, we show that this problem can be solved in linear time, extending these results to decision versions of the ARRIVAL problem, known to be respectively NP-complete and PSPACE-complete
39
David, Vincent. "Algorithmique parallèle sur les arbres de décision et raisonnement en temps contraint : étude et application au minimax." Toulouse, ENSAE, 1993. http://www.theses.fr/1993ESAE0008.
Full textAbstract:
Cette thèse présente un modèle de traitement parallèle pour la mise en œuvre d'algorithmes de raisonnement dans le cadre d'un système temps-réel intelligent, et s'inscrit dans l'étude SATURNE menée au CERT-ONERA. Ce projet se fonde sur l'hypothèse que les tâches de traitement ont la capacité de s'adapter aux échéances temporelles. Pour satisfaire ce modèle, les solutions proposées sont la réduction de l'espace de recherche et l'accélération des traitements grâce au parallélisme. Ces changements devant intervenir durant l'exécution du processus, la gestion du parallélisme devient alors dynamique. Par ailleurs, les arbres de décision représentent une méthode fondamentale pour résoudre de nombreux problèmes d'intelligence artificielle, tels que la théorie des jeux à un joueur, les problèmes d'optimisation, la théorie des jeux à deux joueurs, les graphes Et/Ou et beaucoup d'autres problèmes NP-complets. Aussi, à partir de l'exemple de l'algorithme du minimax sur des arbres de jeux réels, une implémentation est réalisée sur Modulor, une machine à architecture distribuée à base de transputers développée au CERT-ONERA. La méthode de parallélisation se fonde sur une suppression du contrôle entre les processus de recherche, au profit d'un parallélisme spéculatif et du partage complet de l'information réalisé grâce à une mémoire physiquement distribuée mais virtuellement partagée. L’apport de notre approche pour les systèmes temps-réel distribués et tolérants aux fautes est évalué grâce aux résultats expérimentaux obtenus.
40
Figeac, Martin Delahaye Jean-Paul Varré Jean-Stéphane. "Étude de l'ordre des gènes clusters de gènes et algorithmique des réarrangements /." Villeneuve d'Ascq : Université des sciences et technologies de Lille, 2007. https://iris.univ-lille1.fr/dspace/handle/1908/637.
Full text
41
Pigné, Yoann. "Modélisation et traitement décentralisé des graphes dynamiquesApplication aux réseaux mobiles ad hoc." Phd thesis, Université du Havre, 2008. http://tel.archives-ouvertes.fr/tel-00371962.
Full textAbstract:
Les graphes dynamiques sont un outil de plus en plus utilisé dans des contextes variés où il s'avère nécessaire de modéliser des environnements changeants ou incertains. Les modèles aujourd'hui proposés sont dédiés à ces applications précises. Il n'existe pas de modèle général reprenant, hors de tout contexte applicatif, ces caractéristiques. D'autre part la résolution de problèmes liés à ces environnements dynamiques et incertains est problématique. Nous proposons, ici, la formalisation d'un modèle général de graphe dynamique. Nous étudions la résolution de problèmes dans ces graphes à l'aide de méthodes inspirées de mécanismes d'intelligence collective.
Les modèles proposés sont validés dans le contexte applicatif des réseaux mobiles ad hoc. Une approche originale de construction et de maintien de chemins de communication sous plusieurs contraintes est proposée. Le problème de la construction et du maintien d'une forêt couvrante dans un réseau mobile ad hoc est également étudié.
42
Hinge, Antoine. "Dessin de graphe distribué par modèle de force : application au Big Data." Thesis, Bordeaux, 2018. http://www.theses.fr/2018BORD0092/document.
Full textAbstract:
Les graphes, outil mathématique pour modéliser les relations entre des entités, sont en augmentation constante du fait d'internet (par exemple les réseaux sociaux). La visualisation de graphe (aussi appelée dessin) permet d'obtenir immédiatement des informations sur le graphe. Les graphes issus d'internet sont généralement stockés de manière morcelée sur plusieurs machines connectées par un réseau. Cette thèse a pour but de développer des algorithmes de dessin de très grand graphes dans le paradigme MapReduce, utilisé pour le calcul sur cluster. Parmi les algorithmes de dessin, les algorithmes reposants sur un modèle physique sous-jacent pour réaliser le dessin permettent d'obtenir un bon dessin indépendamment de la nature du graphe. Nous proposons deux algorithmes par modèle de forces conçus dans le paradigme MapReduce. GDAD, le premier algorithme par modèle de force dans le paradigme MapReduce, utilise des pivots pour simplifier le calcul des interactions entre les nœuds du graphes. MuGDAD, le prolongement de GDAD, utilise une simplification récursive du graphe pour effectuer le dessin, toujours à l'aide de pivots. Nous comparons ces deux algorithmes avec les algorithmes de l'état de l'art pour évaluer leurs performancesGraphs, usually used to model relations between entities, are continually growing mainly because of the internet (social networks for example). Graph visualization (also called drawing) is a fast way of collecting data about a graph. Internet graphs are often stored in a distributed manner, split between several machines interconnected. This thesis aims to develop drawing algorithms to draw very large graphs using the MapReduce paradigm, used for cluster computing. Among graph drawing algorithms, those which rely on a physical model to compute the node placement are generally considered to draw graphs well regardless of the type of graph. We developped two force-directed graph drawing algorithms in the MapReduce paradigm. GDAD, the fist distributed force-directed graph drawing algorithm ever, uses pivots to simplify computations of node interactions. MuGDAD, following GDAD, uses a recursive simplification to draw the original graph, keeping the pivots. We compare these two algorithms with the state of the art to assess their performances
43
Nisse, Nicolas. "Complexité algorithmique: entre structure et connaissance. Comment les jeux de poursuite peuvent apporter des solutions." Habilitation à diriger des recherches, Université Nice Sophia Antipolis, 2014. http://tel.archives-ouvertes.fr/tel-00998854.
Full textAbstract:
Ce document pr esente les travaux que j'ai r ealis es depuis ma th ese de doctorat. Outre la pr esentation de mes contributions, j'ai essay e de pr esenter des survols des domaines dans lesquels mes travaux s'inscrivent et d'indiquer les principales questions qui s'y posent. Mes travaux visent a r epondre aux nouveaux challenges algorithmiques que posent la croissance des r eseaux de telecommunications actuels ainsi que l'augmentation des donnees et du trafi c qui y circulent. Un moyen de faire face a la taille de ces probl emes est de s'aider de la structure particuliere des r eseaux. Pour cela, je m'attache a d e nir de nouvelles caract erisations des propri et es structurelles des graphes pour les calculer et les utiliser effi cacement a des fins algorithmiques. Autant que possible, je propose des algorithmes distribu es qui ne reposent que sur une connaissance locale/partielle des r eseaux. En particulier, j' etudie les jeux de poursuite - traitant de la capture d'une entit e mobile par une equipe d'autres agents - qui off rent un point de vue int eressant sur de nombreuses propri et es de graphes et, notamment, des d ecompositions de graphes. L'approche de ces jeux d'un point de vue agents mobiles permet aussi l' etude de mod eles de calcul distribu e. Le chapitre 1 est d edi e a l' etude de plusieurs variantes des jeux de gendarmes et voleur. Le chapitre 2 traite des decompositions de graphes et de leur relation avec les problemes d'encerclement dans les graphes. Le chapitre 3 se concentre sur les probl emes d'encerclement dans des contextes a la fois centralis e et distribu e. Finalement, le chapitre 4 traite de probl emes de routage dans diff erents contextes, ainsi que de mod eles de calcul distribu e.
44
Cornet, Alexis. "Algorithmes et résultats de complexité pour des problèmes de graphes avec contraintes additionnelles." Thesis, Université Clermont Auvergne (2017-2020), 2018. http://www.theses.fr/2018CLFAC034/document.
Full textAbstract:
Les problèmes de domination (dominant, dominant indépendant, ...) et de couverture (vertex-cover, arbre de Steiner, ...) sont NP-complets. Pour autant, pour la plupart de ces problèmes, il existe toujours une solution constructible en temps polynomial (potentiellement de valeur objective très mauvaise), ou au moins, il est possible de déterminer facilement (en temps polynomial) l'existence ou non d'une solution. Ces problèmes, initialement issus de situations réelles, sont des modélisations simplistes de ces situations. Nous ajoutons donc des contraintes additionnelles modélisant des contraintes pratiques plausibles : les conflits, des paires d'éléments ne pouvant faire simultanément partie d'une solution (modélisant des incompatibilités diverses), la connexité dans un second graphe (les éléments doivent pouvoir communiquer, et le graphe correspondant à ces liens de communication n'est pas forcément le même) et les obligations, des sous-ensembles d'éléments interdépendants devant être ajoutés simultanément à une solution. Notre but ici n'est pas de modéliser un problème réel précis, mais d'étudier la manière dont ces contraintes modifient la complexité des problèmes étudiés. Nous verrons que dans un grand nombre de cas, déterminer l'existence même d'une solution devient difficile, même sans se préoccuper de leur optimisation. Le problème du firefighter modélise des pompiers tentant de contenir un feu se propageant au tour par tour dans un graphe (potentiellement infini). Nous avons étudié ce problème en ajoutant des contraintes sur le déplacement des pompiers (une vitesse de déplacement limitée entre deux tours). Nous verrons que ces contraintes augmentent en général le nombre de pompiers nécessaires mais ne provoquent pas de changements aussi importants que dans les problèmes précédentsDomination problems (dominating set, independant dominating set, ...) as well as covering problems (vertex-cover, Steiner tree, ...) are NP-complete. However, for most of these problems, it is always possible to construct a (eventually bad) solution in polynomial time, or at least it is possible to determine whether a solution exists. Those problems originally came from industry, but are simplified modelizations of the real life problems. We add additional constraints modeling plausible practical constraints : conflicts which are pairs of elements that cannot apear simultaneously in a solution (to modelize various incompatibilities), connexity in a second graph (elements of the solution must be able to communicate, and the communication links are a second graph), and obligations which are subsets of interdependant vertices which must be added simultaneously in a solution.We don't aim to model a specific real-world problem, but to study how these plausible constraints affect the complexity of the studied problems. We will see that, in many cases, even determining the existence of a solution (regardless of its size) become hard. The firefighter problem models firefighters aiming to contain a fire spreading turn by turn in a (eventually infinite) graph. We studied this problem with the addition of deplacement constraints for the firefighters (a limited moving speed between turns). We will see that, most of the time, this constraint increase the number of firefighters necessary to contain the fire, but does not trigger such major change as constraints studied in the others problems
45
Favreau, Jean-Marie. "Outils pour le pavage de surfaces." Phd thesis, Université Blaise Pascal - Clermont-Ferrand II, 2009. http://tel.archives-ouvertes.fr/tel-00440730.
Full textAbstract:
Alors que l'on observe une disponibilité croissante de données décrivant des objets 3D, il semble essentiel de disposer de moyens de traitement efficaces de ces derniers. Ainsi, nous présentons dans ce mémoire un ensemble d'outils de manipulation de surfaces, qui exploitent à la fois leurs propriétés géométriques et topologiques. Après avoir décrit différents résultats classiques de topologie, et les structures et résultats fondamentaux de la topologie algorithmique, nous présentons les concepts de M-tuiles et M-pavages, offrant notamment une grande souplesse combinatoire, et permettant de décrire finement le résultat d'algorithmes de découpage topologique. En s'appuyant sur les possibilités de description de ce formalisme, nous présentons différents algorithmes de découpage de surface, prenant en compte non seulement la topologie et la géométrie des surfaces, mais également les propriétés des M-tuiles issues de ces découpages. Nous présentons également dans ce mémoire une généralisation des lacets par les n-cets, permettant notamment de décrire une approche originale de pavage de surfaces en cylindres puis en quadrangles. Enfin, deux applications de ces outils de découpage sont présentées. Dans un premier temps, nous déclinons ces algorithmes de découpage dans le contexte de l'infographie, en proposant un ensemble d'outils d'aide à la manipulation de surfaces. Puis nous présentons dans un second temps une chaîne complète de traitement de données issues de l'imagerie médicale, permettant la visualisation dynamique de données complexes sur des cartes planes de la surface du cerveau, en illustrant sa pertinence dans le contexte de la stimulation corticale. En conclusion de ces travaux, nous présentons les perspectives que laissent entrevoir ces développements originaux, notamment en exploitant les possibilités offertes par les n-cets et les M-pavages, qui semblent multiples. Nous soulignons également la richesse qu'assure une exploration des domaines applicatifs par des outils issus de la géométrie algorithmique.
46
Gastineau, Nicolas. "Partitionnement, recouvrement et colorabilité dans les graphes." Thesis, Dijon, 2014. http://www.theses.fr/2014DIJOS014/document.
Full textAbstract:
Nos recherches traitent de coloration de graphes avec des contraintes de distance (coloration de packing) ou des contraintes sur le voisinage (coloration de Grundy). Soit S={si| i in N*} une série croissante d’entiers. Une S -coloration de packing est une coloration propre de sommets telle que tout ensemble coloré i est un si-packing (un ensemble où tous les sommets sont à distance mutuelle supérieure à si). Un graphe G est (s1,... ,sk)-colorable si il existe une S -coloration de packing de G avec les couleurs 1, ...,,k. Une coloration de Grundy est une coloration propre de sommets telle que pour tout sommet u coloré i, u est adjacent à un sommet coloré j, pour chaque ji. Ces résultats nous permettent de déterminer des S-colorations de packings de ces grilles pour plusieurs séries d’entiers. Nous examinons une classe de graphe jamais étudiée en ce qui concerne la S -coloration de packing: les graphes subcubiques. Nous déterminons que tous les graphes subcubiques sont (1,2,2,2,2,2,2)-colorables et (1,1,2,2,3)-colorables. Un certain nombre de résultats sont prouvés pour certaines sous-classes des graphes subcubiques. Pour finir, nous nous intéressons au nombre de Grundy des graphes réguliers. Nous déterminons une caractérisation des graphes cubiques avec un nombre de Grundy de 4. De plus, nous prouvons que tous les graphes r-réguliers sans carré induit ont pour nombre de Grundy de r+1, pour r<5Our research are about graph coloring with distance constraints (packing coloring) or neighborhood constraints (Grundy coloring). Let S={si| i in N*} be a non decreasing sequence of integers. An S-packing coloring is a proper coloring such that every set of color i is an si-packing (a set of vertices at pairwise distance greater than si). A graph G is (s1,... ,sk)-colorable if there exists a packing coloring of G with colors 1,... ,k. A Grundy coloring is a proper vertex coloring such that for every vertex of color i, u is adjacent to a vertex of color j, for each ji. These results allow us to determine S-packing coloring of these lattices for several sequences of integers. We examine a class of graph that has never been studied for S-packing coloring: the subcubic graphs. We determine that every subcubic graph is (1,2,2,2,2,2,2)-colorable and (1,1,2,2,3)-colorable. Few results are proven about some subclasses. Finally, we study the Grundy number of regular graphs. We determine a characterization of the cubic graphs with Grundy number 4. Moreover, we prove that every r-regular graph without induced square has Grundy number r+1, for r<5
47
Casteigts, Arnaud. "Contribution à l'algorithmique distribuée dans les réseaux mobiles ad hoc - Calculs locaux et réétiquetages de graphes dynamiques." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2007. http://tel.archives-ouvertes.fr/tel-00193181.
Full textAbstract:
Les réseaux mobiles ad hoc sont par nature instables et imprévisibles. De ces caractéristiques découle la difficulté à concevoir et analyser des algorithmes distribués garantissant certaines propriétés. C'est sur ce point que porte la contribution majeure de cette thèse. Pour amorcer cette étude, nous avons étudié quelques problèmes fondamentaux de l'algorithmique distribuée dans ce type d'environnement. Du fait de la nature de ces réseaux, nous avons considéré des modèles de calculs locaux, où chaque étape ne fait collaborer que des n\oe uds directement voisins. Nous avons notamment proposé un nouveau cadre d'analyse, combinant réétiquetages de graphes dynamiques et graphes évolutifs (modèle combinatoire pour les réseaux dynamiques). Notre approche permet de caractériser les conditions de succès ou d'échec d'un algorithme en fonction de la dynamique du réseau, autrement dit, en fonction de conditions nécessaires et/ou suffisantes sur les graphes évolutifs correspondants. Nous avons également étudié la synchronisation sous-jacente aux calculs, ainsi que la manière dont une application réelle peut reposer sur un algorithme de réétiquetage. Un certain nombre de logiciels ont également été réalisés autour de ces travaux, notamment un simulateur de réétiquetage de graphes dynamiques et un vérificateur de propriétés sur les graphes évolutifs.
48
Clairet, Pierre. "Approche algorithmique pour l’amélioration des performances du système de détection d’intrusions PIGA." Thesis, Orléans, 2014. http://www.theses.fr/2014ORLE2016/document.
Full textAbstract:
PIGA est un outil permettant de détecter les comportements malicieux par analyse de trace système. Pour cela, il utilise des signatures représentant les comportements violant une ou plusieurs propriétés de sécurité définies dans la politique. Les signatures sont générées à partir de graphes modélisant les opérations entre les différentes entités du système et sont stockées en mémoire pendant la détection d’intrusion. Cette base de signatures peut atteindre une taille de plusieurs Mo et ainsi réduire les performances du système lorsque la détection d’intrusion est active. Durant cette thèse, nous avons mis en place plusieurs méthodes pour réduire la mémoire nécessaire pour stocker les signatures, tout en préservant leur qualité. La première méthode présentée est basée sur la décomposition modulaire des graphes. Nous avons utilisé cet outil de la théorie des graphes pour réduire la taille du graphe et, ainsi, diminuer le nombre de signatures, ainsi que leur longueur. Appliquée à des propriétés de confidentialité sur un système servant de passerelle, cette méthode divise par 20 le nombre de signatures générées. La seconde méthode réduit directement la base de signatures en supprimant des signatures inutiles lorsque PIGA est en mode IPS. Appliquée sur les mêmes propriétés, cette méthode divise par 5 le nombre de signatures générées. En utilisant les deux méthodes, on divise le nombre de signatures par plus de 50. Ensuite, nous avons adapté le mécanisme de détection afin d’utiliser les nouvelles signatures générées. Les expérimentations que nous avons effectuées montrent que notre système est équivalent à l’ancien système. De plus, nous avons réduit le temps de réponse de PIGAPIGA is a tool for detecting malicious behaviour by analysing system activity. This tool uses signatures representing illegal behaviours that violate security properties defined in the policy. The signatures are generated from graphs modelling the operation between different system entities and stored in the memory during the intrusion detection. The signature base can take up several MB (Megabytes). This will reduce system performance when the intrusion detection is running. During this thesis, we set up two methods to reduce the memory used to store the signatures while also preserving their quality. The first method is based on the modular decomposition of graphs. We used this notion of graph theory to reduce the size of the graph and lower the number and length of signatures. Applied to confidentiality properties on a gateway system, this method divides by 20 the number of generated signature. The second method reduces directly the signature base by deleting useless signatures when PIGA is used as an IPS. Applied to the same properties, this method divides by 5 the number of generated signatures. Using both methods together, the number of signatures is divided by more than 50. Next, we adapted the detection mechanism to use the new generated signatures. The experiments show that the new mechanism detects the same illegal behaviours detected by the previous one. Furthermore, we reduced the response time of PIGA
49
Hoché, Toussaint. "Heuristiques pour la gestion d'une flotte de taxis autonomes, électriques, réservables et partageables." Electronic Thesis or Diss., université Paris-Saclay, 2021. http://www.theses.fr/2021UPASG082.
Full textAbstract:
Le transport routier de personnes est actuellement en train de se transformer de multiples manières : automatisation des véhicules, électrification, intégration des Technologies de l'Information et de la Communication (TIC) aux systèmes de gestion, pour n'en nommer que trois. Ces transformations apportent de nouveaux challenges et de nouvelles opportunités dans le domaine de la mobilité individuelle. L'objectif de cette thèse est de mettre au point un service gérant de manière centralisée une flotte de taxis électriques, autonomes, et partagés traitant le plus de clients possible.Du point de vue de l'électrification, trois difficultés sont étudiées. 1) La distance pouvant être parcourue après chaque plein est plus faible que pour les véhicules à combustion. 2) La vitesse à laquelle un plein est effectué est plus faible. 3) L'usage de l'infrastructure de recharge est susceptible d'être limité. La gestion de la recharge des véhicules doit être la plus efficace possible, afin de maximiser le temps de fonctionnement utile des taxis. Nous étudions deux cas : statique et dynamique. Dans le cas statique, les requêtes des clients sont connus longtemps à l'avance, et le gestionnaire de la flotte de taxi peut choisir librement quel client traiter. Dans le cas dynamique, les clients sont découverts au fur et à mesure qu'ils réservent, et le gestionnaire doit indiquer en temps réel à chaque client qui réserve si sa demande est acceptée.Une approche holistique est utilisée dans cette thèse, afin d'intégrer cette gestion de la recharge dans un système complet. On considère ainsi l'impact du stationnement et du partage de course sur le comportement des taxis. Enfin, nos tests sont effectués sur des instances de grande taille, comptant des dizaines de milliers de clients, basées sur des données réelles.Pour résoudre ces instances, nous proposons une heuristique gloutonne myope, améliorée par deux méthode de recherche de voisinage. La première méthode est une montée de colline, et la seconde un recuit simulé. Nos résultats montrent que ces méthodes sont adaptés pour des instances comportant des dizaines de milliers de clients, mais que le temps de calcul requis par le recuit simulé est très élevé. Nos résultats montrent également comment ces méthodes doivent être paramétrées en fonction des caractéristiques de l'instance sur laquelle elles sont utilisées, et diverses pistes permettant d'obtenir de meilleurs résultatsIndividual transportation is currently undergoing multiple transformations: Automation of vehicles, electrification, integration of Information & Communications Technologies (ICT) in management systems, to name only three. These transformations bring new challenges and opportunities to the domain of individual mobility. The objective of this thesis is to develop a centralised system managing a fleet of electrics, autonomous, and shared taxis treating as many customers as possible.Regarding electrification, three difficulties are studied. 1) The range of electric vehicles is lower than for internal combustion vehicles. 2) Refilling is slower. 3) The charging infrastructure usage may be constraint. The recharge of vehicles must therefore be as efficient as possible, to maximise their uptime. We study two cases: static and dynamic. In the static case, clients' requests are known long in advance, and the fleet manager can freely choose the clients to treat. In the dynamic cas, each client is discovered when he formulate his request to the fleet manager, who has to tell in real-time if the client's request is accepted.A holistic approach is used in this thesis, to integrate the recharge management in a complete system. Thus, we consider the impact of parking and ride-sharing on the behaviour of taxis. Finally, our tests are performed on large instances, involving dozens of thousands of clients, based on real data.To solve these instances, we propose a myopic greedy heuristic, improved by two neighbourhood search method. The first method is a hill climbing, and the second one is a simulated annealing. Our results show that these methods are fitting for instances with tens of thousands of customers, but that the computation time required for the simulated annealing is very high. Our results also show how these methods must be parametered depending on the caracteristics of the instances, and we propose various ways to improve these results
50
Gianfrotta, Coline. "Modélisation, analyse et classification de motifs structuraux d'ARN à partir de leur contexte, par des méthodes d'algorithmique de graphes." Electronic Thesis or Diss., université Paris-Saclay, 2022. http://www.theses.fr/2022UPASG056.
Full textAbstract:
Dans cette thèse, nous étudions le contexte structural de motifs structuraux d'ARN dans le but de progresser vers leur prédiction. En effet, certains motifs d'ARN, sous-structures apparaissant de façon récurrente dans les structures d'ARN, restent difficiles à prédire, en raison de la présence d'interactions non canoniques dans ces motifs, et en raison de la distance sur la séquence primaire séparant les différentes parties de ces motifs. Nous modélisons ainsi par des graphes le contexte structural topologique de ces motifs, et comparons les contextes des différentes occurrences en utilisant plusieurs algorithmes de graphes. Nous classifions ensuite les occurrences de motif selon leurs similarités de contexte topologique et selon leurs similarités de contexte 3D, à l'aide d'un algorithme de clustering recouvrant.Dans un premier temps, nous montrons sur un jeu de données de trois motifs structuraux que les similarités observées entre les contextes topologiques sont cohérentes avec les similarités entre les contextes 3D. Cela indique que le contexte topologique peut être suffisant pour déterminer le contexte 3D pour ces trois motifs.Dans un deuxième temps, nous étudions plusieurs classifications d'occurrences du motif A-minor, selon des similarités de contexte 3D. Nous y observons que des similarités de contexte 3D existent entre occurrences non homologues, ce qui pourrait être le signe d'un phénomène de convergence évolutive. De plus, nous observons que certaines parties du contexte 3D semblent mieux conservées que d'autres entre occurrences non homologues.Dans un troisième temps, nous étudions la capacité de prédiction du contexte topologique commun à des occurrences de motif A-minor, partageant des contextes 3D similaires, ainsi que la capacité de prédiction d'un signal de séquence sur ces mêmes occurrences. Pour cela, nous étudions la fréquence d'apparition de cette topologie et de ces séquences dans des structures d'ARN en l'absence de motifs A-minor. Nous en concluons que la topologie et la séquence associées représentent un bon signal pour la majorité des classes d'occurrences homologues étudiéesIn this thesis, we study the structural context of RNA structural motifs in order to make progress in their prediction. Indeed, some RNA motifs, which are substructures appearing recurrently in RNA structures, remain difficult to predict, because of the presence of non-canonical interactions in these motifs, and because of the distance on the primary sequence between the different parts of these motifs. We therefore model the topological structural context of these motifs by graphs, and compare the contexts of the different occurrences using several graph algorithms. We then classify the motif occurrences according to their topological context similarities and according to their 3D context similarities, using an overlapping clustering algorithm.First, we show on a dataset of three structural motifs that the observed similarities between the topological contexts are consistent with the similarities between the 3D contexts. This indicates that the topological context may be sufficient to determine the 3D context for these three motifs.In a second step, we study several classifications of occurrences of the A-minor motif, according to 3D context similarities. We observe that 3D context similarities exist between non-homologous occurrences, which could be a sign of an evolutionary convergence phenomenon. Moreover, we observe that some parts of the 3D context seem to be better conserved than others between non-homologous occurrences.In a third step, we study the predictive ability of the common topological context of A-minor motif occurrences, sharing similar 3D contexts, as well as the predictive ability of a sequence signal on these same occurrences. To this end, we study the occurrence of this topology and sequence in RNA structures in the absence of A-minor motifs. We conclude that the topology and the sequence represent a good signal for the majority of the studied classes