Academic literature on the topic 'Optimisation dans des graphes'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Optimisation dans des graphes.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Journal articles on the topic "Optimisation dans des graphes"
1
Jean-Paul Delahaye. "Dynamiques majoritaires dans les graphes." Bulletin 1024, no. 13 (April 2019): 153–58. http://dx.doi.org/10.48556/sif.1024.13.153.
Full text
2
Tabchi, Theresia, Hussein Sabra, and Bernard Riera. "La théorie des graphes dans l’enseignement – au croisement de champs disciplinaires et des formations universitaires." J3eA 23 (2024): 0004. http://dx.doi.org/10.1051/j3ea/20240004.
Full textAbstract:
Dans cet article, nous parlons de la théorie des graphes dans l’enseignement supérieur. Nous allons essayer de présenter des caractéristiques didactiques de cette théorie qui se développe à l’interface entre les mathématiques et l’informatique. La théorie des graphes admet des champs d’application divers et variés dans l’ingénierie, la modélisation, et dans différents domaines de recherche. En effet, son déploiement dans l’enseignement, devenu nécessaire, soulève plusieurs questions. Nous cherchons à caractériser les formes possibles d’un tel enseignement dans divers parcours de formation tels que les mathématiques, l'ingénierie et l'informatique. Ainsi, nous cherchons à caractériser les formes envisageables pour enseigner la théorie des graphes au supérieur, en tenant compte du contexte spécifique de l'enseignement et de l'impact potentiel de ce contexte sur les choix à effectuer pour structurer l'enseignement de cette matière. Pour ce faire, nous étudions huit ouvrages dédiés à cet enseignement. En outre, nous identifions les défis auxquels les enseignants peuvent être confrontés dans la définition des contenus à enseigner, en passant des cours d'introduction aux domaines d'application spécialisés. Par ailleurs, nous illustrons nos propos en nous penchant sur la formation des automaticiens, où la théorie des graphes joue un rôle essentiel dans l’analyse et la modélisation des systèmes complexes, qu'ils soient discrets ou continus. Nous terminons par quelques propositions pour l’enseignement.
3
Genest, David. "Recherche d'information par transformation de graphes dans le modèle des graphes conceptuels." Ingénierie des systèmes d'information 7, no. 1-2 (April 24, 2002): 207–36. http://dx.doi.org/10.3166/isi.7.1-2.207-236.
Full text
4
Foucambert, Denis, Tracy Heranic, Christophe Leblay, Maarit Mutta, and Minjing Zhong. "Intégration de la visualisation dans l’analyse de processus complexes : écritures et réécritures dans un corpus multilingue universitaire." SHS Web of Conferences 138 (2022): 06010. http://dx.doi.org/10.1051/shsconf/202213806010.
Full textAbstract:
Cet article traite des processus d’écriture d’apprenants universitaires de français langue étrangère (L2/L3). Ces écritures ont été recueillies à l’aide du programme GenoGraphiX-Log qui est construit sur les exigences de la génétique textuelle et de la théorie mathématique des graphes. Notre corpus consiste en 44 écritures produites en français par des locuteurs ayant comme L1 soit l’anglais, soit le mandarin soit le finnois. Le premier objectif est de mieux décrire, en fonction des L1 des participants, les opérations d’écriture mises en oeuvre en français lors de la réalisation d’une même tâche. Le second objectif est d’évaluer comment la visualisation, basée sur la théorie des graphes et sur des méthodes statistiques inductives, soutient cette analyse des processus d’écriture. Les résultats se basent sur deux analyses issues des graphes : une analyse en composantes principales (ACP) et la visualisation des écritures exemplaires (les plus proches des centres de gravité de chaque groupe). Ces deux analyses complémentaires nous permettent de mesurer les spécificités des trois groupes et d’approfondir qualitativement l’analyse de signatures scripturales. Notre corpus et nos analyses montrent l’intérêt de l’utilisation des méthodes mixtes dans l’analyse des processus complexes d’écriture à l’aide d’outils de visualisation.
5
Minoux, M. "Optimisation combinatoire: graphes et programmation linéaire and programmation discréte." European Journal of Operational Research 25, no. 1 (April 1986): 144–45. http://dx.doi.org/10.1016/0377-2217(86)90126-8.
Full text
6
Díaz Villalba, Alejandro. "Comment outiller l’étude des autorités avec l’analyse de réseaux dans les grammaires françaises des XVIe et XVIIe siècles." SHS Web of Conferences 138 (2022): 03003. http://dx.doi.org/10.1051/shsconf/202213803003.
Full textAbstract:
L’article propose d’outiller, par le recours à l’analyse de réseaux, l’étude des références, c’est-à-dire les mentions et les citations d’autorités dans les textes métalinguistiques. Il s’agit, d’une part, de présenter les principes méthodologiques qui ont présidé à l’élaboration d’une visualisation sous forme de graphes de réseau : la modélisation et la construction d’une base de données de références et la génération du graphe dans un logiciel approprié. Il est question, d’autre part, de décrire les aspects liés à l’interprétation des graphes de réseaux, le but étant d’explorer le potentiel de l’outil dans l’histoire des idées linguistiques.
7
Jean Claude Derniame. "À propos du cheminement dans les graphes." Bulletin 1024, no. 16 (November 2020): 121–32. http://dx.doi.org/10.48556/sif.1024.16.121.
Full text
8
Lemieux, Vincent. "L'articulation des réseaux sociaux." Recherches sociographiques 17, no. 2 (April 12, 2005): 247–60. http://dx.doi.org/10.7202/055716ar.
Full textAbstract:
Sous l'influence première d'un article de Barnes (1954), les études anthropologiques sur les réseaux sociaux ont ouvert une voie de recherches qui apparaît encore pleine de promesses. Il faut bien avouer, pourtant, que jusqu'à maintenant peu d'analyses fondées sur des données empiriques ont emporté la conviction. Les études de réseaux n'ont pas encore fait la preuve de leur fécondité. Il leur manque un fondement théorique, pourtant disponible dans la théorie des graphes qui est justement une théorie des réseaux, qu'ils soient sociaux ou autres. Comme l'a noté Mitchell, la jonction n'existe pas — ou pas assez — entre les spécialistes de la théorie des graphes et les chercheurs sur le terrain (1969, p. 35). Pourtant, quelques bons exposés ont été écrits par des anthropologues, qui indiquent bien ce qu'on pourrait tirer d'une utilisation plus poussée de la théorie des graphes (en particulier Mitchell, 1969; Barnes, 1969a; et surtout Barnes, 1972). Malgré ces mises en place, la plupart des études empiriques ne dépassent guère l'analyse situationnelle qui, comme le note Barnes (1972, p. 13), peut fort bien se passer de la notion de réseau, en plus d'être inapte au dégagement d'hypothèses générales. Nous allons donner, à la fin de cet article, une brève illustration d'une étude proprement structurale des réseaux sociaux, au sens où l'entendent Harary, Norman et Cartwright (1968), dans leur ouvrage sur les graphes orientés. En utilisant des données recueillies sur le terrain, nous montrerons comment la notion d'articulation, tirée de la théorie des graphes, permet de poser et de traiter des problèmes théoriques, mais aussi pratiques, qui nous semblent propres aux réseaux sociaux. Auparavant, nous voudrions discuter de certaines questions préalables à une analyse vraiment spécifique des réseaux sociaux. Ils ont trait au concept même de réseau, à la constitution des unités d'analyse, et aux différentes voies d'analyse qui s'offrent au chercheur.
9
Vazquez, J., M. François, and D. Gilbert. "Gestion en temps réel d'un réseau d'assainissement : vérification de l'optimalité et de l'applicabilité de la théorie des graphes par rapport à la programmation linéaire mixte." Revue des sciences de l'eau 16, no. 4 (April 12, 2005): 425–42. http://dx.doi.org/10.7202/705516ar.
Full textAbstract:
Dans le cas de la gestion en temps réel des réseaux d'assainissement, la première étape peut, par exemple, consister à vérifier qu'une manipulation des organes de contrôle tels que les vannes et pompes est capable de minimiser les déversements vers le milieu naturel. Cette gestion, que l'on appellera " gestion de référence ", permet de déterminer les stratégies de commande sur toute la durée de l'événement pluvieux connu à l'avance. Ce calcul se fait donc à la fin de l'événement pluvieux et permet de dire ce qui aurait pu être fait avec les organes de régulation en terme de minimisation des volumes déversés. La programmation linéaire par les graphes et la programmation linéaire mixte permettent de déterminer une solution optimale. Cet article s'intéresse à la vérification de l'optimalité et à l'applicabilité de la programmation linéaire par les graphes comparée à la programmation linéaire mixte dans le cas de la " gestion de référence " sur le réseau d'assainissement de Saverne (France). En comparant les volumes déversés par ces deux techniques d'optimisation sur 34 événements pluvieux, nous pouvons confirmer que l'approche par les graphes ne donne pas toujours le minimum global. Les résultats ont montré que la programmation linéaire mixte fournit des temps de calcul qui peuvent atteindre plus de 24 heures. Par contre, l'approche par les graphes permet un temps de calcul de l'ordre de 5 minutes en moyenne avec un minimum global en terme de volume déversé atteint qui n'excède pas 5% par rapport à la solution fournie par la programmation linéaire mixte.
10
Garin, Hélène, Claire Bidart, Rym Ibrahim, Vincent Lorant, Pablo Nicaise, and Paola Tubaro. "Voir et faire voir les graphes de réseaux personnels." L'Année sociologique Vol. 74, no. 2 (September 23, 2024): 441–73. http://dx.doi.org/10.3917/anso.242.0441.
Full textAbstract:
L’analyse des réseaux personnels étudie les relations sociales des individus et utilise de plus en plus la visualisation de ces réseaux en situation d’enquête. Cependant, le fait de voir son réseau objectivé dans une image ne laisse pas une personne inchangée. S’appuyant sur deux protocoles de recherche différents, cet article présente quelques réactions que suscite la co-construction du réseau personnel à l’aide de visualisations et examine l’impact de l’interaction entre personnes enquêtrices et enquêtées dans l’appropriation des résultats finaux. Les enjeux sont éthiques, dans la mesure où ils concernent le sort d’autrui au sens large, au-delà du respect des règles formelles. Nous mobilisons la réflexivité comme un moyen d’apprendre de nos propres expériences de recherche dans les domaines de l’entrepreneuriat et de la santé mentale respectivement. L’article contribue ainsi à un débat plus large sur l’éthique de la recherche en sociologie, qui englobe les impacts et qui, nous croyons, nécessite la participation active des chercheurs et chercheuses de terrain.
Dissertations / Theses on the topic "Optimisation dans des graphes"
1
Murat, Cécile. "Les problèmes d'optimisation combinatoire probabilistes dans les graphes." Paris 9, 1997. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1997PA090054.
Full textAbstract:
L'objet de cette thèse est l'optimisation combinatoire probabiliste de problèmes définis en termes de graphes. Dans ce cadre, un système de probabilités est associé aux sommets du graphe afin de traduire le fait que nous ne connaissons pas le sous-graphe pour lequel le problème sera à résoudre. L'approche utilisée consiste alors à définir une solution dite a priori, qui sous-entend que tous les éléments du graphe d'origine soient présents. Pour une sous-instance donnée, pour laquelle certains éléments du graphe sont absents, il faudra adapter la solution a priori, à l'aide d'un algorithme appelé stratégie de modification, afin qu'elle devienne solution de l'instance considérée. Après avoir situé ces problèmes, par rapport à ceux étudiés dans le cadre de la théorie des graphes aléatoires, nous présentons la méthodologie employée et la formalisons. Nous proposons alors, un état de l'art des travaux réalisés avec cette approche pour les problèmes dont l'instance est un graphe. Puis, nous présentons les résultats que nous avons établis pour les problèmes du stable probabiliste, de la couverture de sommets probabiliste et de plus longs chemins probabilistes. Ceci nous amène a opérer une première classification et structuration de problèmes d'optimisation combinatoire probabilistes selon leur complexité et résolution. La dernière partie de cette thèse, constitue un développement du formalisme du cadre d'étude. Pour cela, nous présentons nos premières réflexions concernant l'utilisation de nouveaux critères. Enfin, nous finissons en introduisant les premières notions nécessaires à la mise en place d'un cadre structure pour l'étude de l'approximation des problèmes d'optimisation combinatoire probabilistes.
2
Watrigant, Rémi. "Approximation et complexité paramétrée de problèmes d’optimisation dans les graphes : partitions et sous-graphes." Thesis, Montpellier 2, 2014. http://www.theses.fr/2014MON20100/document.
Full textAbstract:
La théorie de la NP-complétude nous apprend que pour un certain nombre de problèmes d'optimisation, il est vain d'espérer un algorithme efficace calculant une solution optimale. Partant de ce constat, un moyen pour contourner cet obstacle est de réaliser un compromis sur chacun de ces critères, engendrant deux approches devenues classiques. La première, appelée approximation polynomiale, consiste à développer des algorithmes efficaces et retournant une solution proche d'une solution optimale. La seconde, appelée complexité paramétrée, consiste à développer des algorithmes retournant une solution optimale mais dont l'explosion combinatoire est capturée par un paramètre de l'entrée bien choisi. Cette thèse comporte deux objectifs. Dans un premier temps, nous proposons d'étudier et d'appliquer les méthodes classiques de ces deux domaines afin d'obtenir des résultats positifs et négatifs pour deux problèmes d'optimisation dans les graphes : un problème de partition appelé Sparsest k-Compaction, et un problème de recherche d'un sous-graphe avec une cardinalité fixée appelé Sparsest k-Subgraph. Dans un second temps, nous présentons comment les méthodes de ces deux domaines ont pu se combiner ces dernières années pour donner naissance au principe d'approximation paramétrée. En particulier, nous étudierons les liens entre approximation et algorithmes de noyauxThe theory of NP-completeness tells us that for many optimization problems, there is no hope for finding an efficient algorithm computing an optimal solution. Based on this, two classical approaches have been developped to deal with these problems. The first one, called polynomial- time approximation, consists in designing efficient algorithms computing a solution that is close to an optimal one. The second one, called param- eterized complexity, consists in designing exact algorithms which com- binatorial explosion is captured by a carefully chosen parameter of the instance. The goal of this thesis is twofold. First, we study and apply classical methods from these two domains in order to obtain positive and negative results for two optimization problems in graphs: a partitioning problem called Sparsest k-Compaction, and a cardinality constraint subgraph problem called Sparsest k-Subgraph. Then, we present how the different methods from these two domains have been combined in recent years in a concept called parameterized approximation. In particular, we study the links between approximation and kernelization algorithms
3
Atmani, Dihya. "Affectation dynamique dans les systèmes de transport multimodaux." Thesis, Paris Est, 2015. http://www.theses.fr/2015PESC1132/document.
Full textAbstract:
L'objectif de ce travail consiste à réaliser un système dynamique d'aide aux déplacements multimodal pour les voyageurs équipés d'un système d'information tout en prenant en considération les usagers non équipés de ce type de système. Le travail est alors divisé en deux parties: Une partie conception et développement et une partie étude. La partie développement consiste à construire l'outil informatique d'aide aux déplacements grâce à une modélisation multi-agent et qui renvoie à l'usager un itinéraire qui satisfait ces besoins et ceux du réseau. La partie étude quant à elle, consiste en une approche plus théorique qui consiste à déterminer l'impact de l'information sur les coûts des itinéraires, l'impact de la réorientation des usagers vers les transports en commun sur le réseau routier ainsi que l'intérêt de passer vers des véhicules autonomesThe objective of this work consists on the realization of a dynamic guidance system in a multimodal network for users equipped with an information device while taking into account users that are not equipped with such devices. The work is organized into parts: a conception part and a theoretical study part. The conception part consists on the development of the guidance tool using a multi agent architecture. This tool assists users in their daily travels by giving them the itinerary that suits best not only their needs but also the overall network. The theoretical study emphasizes on how the performance of the network can be enhanced. To do so, three main studies will be presented: the impact of the information on the cost of the itineraries, the impact of the reorientation of users towards transportation systems on the road network and finally the benefits of introducing autonomous vehicles
4
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
5
Travers, Nicolas. "Optimisation extensible dans un médiateur de données semi-structurées." Versailles-St Quentin en Yvelines, 2006. http://www.theses.fr/2006VERS0049.
Full textAbstract:
Cette thèse propose un cadre d'évaluation pour des requêtes XQuery dans un contexte de médiation de données XML. Un médiateur doit fédérer des sources de données distribuées et hétérogènes. A cette fin, un modèle de représentation des requêtes est nécessaire. Ce modèle doit intégrer les problèmes de médiation et permettre de définir un cadre d'optimisation pour améliorer les performances. Le modèle des motifs d'arbres est souvent utilisé pour représenter les requêtes Xquery, mais il ne reconnait pas toutes les spécifications du langage. La complexité du langage XQuery fait qu'aucun modèle de représentation complet n'a été proposé pour reconnaitre toutes les spécifications. Ainsi, nous proposons un nouveau modèle de représentation pour toutes les requêtes XQuery non typées que nous appelons TGV. Avant de modéliser une requête, un étape de canonisation permet de produire une forma canonique pour ces requêtes, facilitant l'étape de traduction vers le modèle TGV. Ce modèle prend en compte le contexte de médiation et facilite l'étape d'optimisation. Les TGV définis sous forme de types abstraits de données facilitent l'intégration du modèle dans tout sytème en fonction du modèle de données. De plus, une algèbre d'évaluation est définie pour les TGV. Grâce à l'intégration d'annotations et d'un cadre pour règles de transformation, un optimisateur extensible manipule les TGV. Celui-ci repose sur des règles de transformations, un modèle de coût générique et une stratégie de recherche. Les TGV et l'optimisateur extensible sont intégrés dans le médiateur XLive, développé au laboratoire PRISMThis thesis proposes to evaluate XQuery queries into a mediation context. This mediator must federate several heterogeneous data sources with an appropriate query model. On this model, an optimization framework must be defined to increase performance. The well-known tree pattern model can represent a subset of XPath queries in a tree form. Because of the complexity of XQuery, no model has been proposed that is able to represent all the structural components of the language. Then, we propose a new logical model for XQuery queries called TGV. It aims at supporting the whole XQuery into a canonical form in order to check more XQuery specifications. This form allows us to translate in a unique way queries into our TGV model. This model takes into account a distributed heterogenous context and eases the optimization process. It integrates transformation rules, cost evaluation, and therefore, execution of XQuery queries. The TGV can be used as a basis for processing XQuery queries, since it is flexible, it provides abstracts data types wich can be implemented according to the underneath data model. Moreover, it allows user-defined annotating ans also cost-related annotating for cost estimation. Althouogh the model will be useful, it relies on XQuery complicates specifications. TGV are illustrated in this thesis with several figures on W3C's uses cases. Finally, a framework to define transformation rules is added to the extensible optimizer to increase the XLive mediator performances. The XLive mediation system has been developped at the PRISM laboratory
6
De, Oliveira Castro Herrero Pablo. "Expression et optimisation des réorganisations de données dans du parallélisme de flots." Phd thesis, Université de Versailles-Saint Quentin en Yvelines, 2010. http://tel.archives-ouvertes.fr/tel-00580170.
Full textAbstract:
Pour permettre une plus grande capacité de calcul les concepteurs de systèmes embarqués se tournent aujourd'hui vers les MPSoC. Malheureusement, ces systèmes sont difficiles à programmer. Un des problèmes durs est l'expression et l'optimisation des réorganisations de données au sein d'un programme. Dans cette thèse nous souhaitons proposer une chaîne de compilation qui : 1) propose une syntaxe simple et haut-niveau pour exprimer le découpage et la réorganisation des données d'un programme parallèle ; 2) définisse une exécution déterministe du programme (critique dans le cadre des systèmes embarqués) ; 3) optimise et adapte les programmes aux contraintes de l'architecture. Pour répondre au point 1) nous proposons un langage haut-niveau, SLICES, qui permet de décrire les réorganisation de données à travers des découpages multidimensionnels. Pour répondre au point 2) nous montrons qu'il est possible de compiler SLICES vers un langage de flots de données, SJD, qui s'inscrit dans le modèle des Cyclostatic Data-Flow et donc admet une exécution déterministe. Pour répondre au point 3) nous définissons un ensemble de transformations qui préservent la sémantique des programmes SJD. Nous montrons qu'il existe un sous-ensemble de ces transformations qui génère un espace de programmes équivalents fini. Nous proposons une heuristique pour explorer cet espace de manière à choisir la variante la plus adaptée à notre architecture. Enfin nous évaluons cette méthode sur deux problèmes classiques : la réduction de la mémoire consommée et la réduction des communications d'une application parallèle.
7
Roupin, Frédéric. "Algorithmes Combinatoires et Relaxations par Programmation Linéaire et Semidéfinie. Application à la Résolution de Problèmes Quadratiques et d'Optimisation dans les Graphes." Habilitation à diriger des recherches, Université Paris-Nord - Paris XIII, 2006. http://tel.archives-ouvertes.fr/tel-00596215.
Full textAbstract:
Cette synthèse de travaux de recherche concerne l'algorithmique dans les graphes et l'utilisation de la pro- grammation linéaire et semidéfinie positive (SDP) dans le cadre de la résolution exacte ou approchée de plusieurs problèmes fondamentaux de l'Optimisation Combinatoire. L'approche semidéfinie, qui conduit à des relaxations convexes mais non-linéaires, a permis d'obtenir de remarquables résultats théoriques en approximation et devient à présent utilisable en pratique (tout comme la programmation linéaire qui en est un cas particulier). Nos travaux comportent une forte composante algorithmique et des études de complexité de plusieurs problèmes d'optimisation dans les graphes. Nous considérons tout d'abord le problème de la recherche d'un sous-graphe dense de taille fixée pour lequel nous présentons un algorithme polynomial avec ga- ranties de performances fondé sur la programmation linéaire et quadratique. Puis, nous étudions les problèmes de multiflots entiers et de multicoupes pour lesquels nous avons identifié de nombreux cas po- lynomiaux dans des graphes particuliers importants en pratique : arborescences, grilles, anneaux. D'une part, les solutions fractionnaires fournies par certaines relaxations linéaires de ces problèmes sont le point de départ d'algorithmes de résolution efficaces. D'autre part, les propriétés des programmes linéaires uti- lisés nous permettent également d'élaborer des algorithmes purement combinatoires et de démontrer leur validité (matrices totalement unimodulaires, théorème des écarts complémentaires). Nous proposons également des approches systématiques pour élaborer des relaxations semidéfinies pour les programmes quadratiques, modèles de très nombreux problèmes combinatoires et continus. Plus précisément, nous étudions les liens entre relaxations semidéfinies et des relaxations lagrangiennes partielles de programmes quadratiques contenant des contraintes linéaires. En particulier, les fonctions quadratiques constantes sur une variété affine sont entièrement caractérisées. Ceci permet de facilement comparer les différentes familles de contraintes redondantes proposées dans la littérature dans l'approche semidéfinie dans le cadre unifié de l'approche lagrangienne. Puis, nous présentons un algorithme pour élaborer des relaxations semidéfinies à partir de relaxations linéaires existantes. L'objectif est de pro- fiter des résultats théoriques et expérimentaux obtenus dans l'approche linéaire. Nous avons développé un logiciel (SDP_S) grâce à ces résultats. Il permet de formuler automatiquement et facilement des relaxations semidéfinies pour tout problème pouvant être formulé comme un programme quadratique en variables bivalentes. Notre méthode peut se généraliser à certains programmes à variables mixtes. Enfin, nous appliquons les méthodes décrites précédemment à une série de problèmes combinatoires classiques. Nos expérimentations montrent que l'approche semidéfinie est à présent pertinente dans la pra- tique sous certaines conditions. Premièrement, nous présentons des méthodes de séparation/évaluation efficaces fondées sur la SDP pour la résolution exacte des problèmes max 2sat et Vertex-Cover. Deuxièmement, nous proposons plusieurs bornes par SDP de grande qualité pour des problèmes particu- lièrement difficiles à résoudre par les approches linéaires : k-cluster, CMAP (un problème de placement de tâches avec contraintes de ressources), et le problème de l'affectation quadratique (QAP). Pour ce dernier nous présentons également un algorithme de coupes performant fondé sur la programmation semidéfinie. Afin d'obtenir des algorithmes efficaces en pratique, nous mettons en oeuvre non seulement nos méthodes d'élaboration de relaxations SDP, mais également des techniques algorithmiques issues de l'approximation polynomiale, ainsi que des outils spécifiques de résolution numérique des programmes semidéfinis.
8
Reyes, Valenzuela Patricio Alejandro. "Collecte d'information dans les réseaux radio." Nice, 2009. http://www.theses.fr/2009NICE4069.
Full textAbstract:
Cette thèse concerne l’étude de l’algorithmique et de la complexité des communications radio. En particulier, nous nous sommes intéressés au problème de rassembler les informations des sommets d’un réseau radio en nœud central. Ce problème est motivé par une question de France Telecom (Orange Labs) : « 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 connectée à Internet par une liaison satellite. Le même problème se rencontre dans les réseaux de senseurs où il s’agit de collecter les informations des senseurs dans une station de base. Une 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 d’interférences). Nous modélisons ces contraintes en disant que deux sommets (équipements radio) peuvent communiquer s’ils sont à distance au plus dT et qu’un nœud interfère avec un autre si leur distance est au plus dI. Les distances sont considérées dans un graphe représentant le réseau. Une étape de communication consistera donc en un ensemble de transmissions compatibles (n’interférant pas). 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. Pour des topologies particulières comme le chemin et la grille, nous avons établi des résultats optimaux ou quasi optimaux. Nous avons aussi considéré le cas systolique (ou continu) où on veut maximiser le débit offert à chaque nœudThis thesis concerns the study of the algorithmic and the complexity of the communication in radio networks. In particular, we were interested in the problem of gathering information from the nodes of a radio network in a central node. This problem is motivated by a question of France Telecom (Orange Labs) “How to bring Internet in villages”. Nodes represent the houses of the villages which communicate between them by radio, the goal being to reach a gateway connected to Internet by a satellite link. The same problem can be found in sensor networks where the question is to collect data from sensors to a base station. A peculiarity of radio networks is that the transmission distance is limited and that the transmissions interfere between them (interference phenomena). We model these constraints by saying that two nodes (radio devices) can communicate if they are at distance at most dT and a node interferes with another one if their distance is at most dI. The distances are considered in a graph representing the network. Thus, a communication step will consist in a compatible (non interfering) set of transmissions. Our goal is to find the minimum number of steps needed to achieve such a gathering and design algorithms achieving this minimum. For special topologies such as the path and the grid, we have proposed optimal or near optimal solutions. We also considered the systolic (or continuous) case where we want to maximize the throughput (bandwidth) offered to each node
9
Pirayre, Aurélie. "Reconstruction et classification par optimisation dans des graphes avec à priori pour les réseaux de gènes et les images." Thesis, Paris Est, 2017. http://www.theses.fr/2017PESC1170/document.
Full textAbstract:
Dans de nombreuses applications telles que la médecine, l'environnement ou les biotechnologies par exemple, la découverte de nouveau processus de régulations de gènes permet une meilleure compréhension des réponses phénotypiques des cellules à des stimuli externes. Pour cela, il est alors d'usage de générer et d'analyser les données transcriptomiques issues d'expériences de types puces à ADN ou plus récemment de RNAseq. Ainsi, pour chaque gène d'un organisme d'étude placé dans différentes conditions expérimentales, un ensemble de niveau d'expression est obtenu. A partir de ces données, les mécanismes de régulation des gènes peuvent être obtenus à travers un ensemble de liens dans des graphes. Dans ces réseaux, les nœuds correspondent aux gènes. A lien entre deux nœuds est identifié si une relation de régulation existent entre les deux gènes correspondant. De tels réseaux sont appelés Réseaux de Régulation de Gènes (RRGs). Malgré la profusion de méthodes d'inférence disponible, leur construction et leur analyse restent encore à ce jour un défi.Dans cette thèse, nous proposons de répondre au problème d'inférence de réseaux par des techniques d'optimisation dans des graphes. A partir d'information de régulation sur l'ensemble des couples de gènes, nous proposons de déterminer la présence d'arêtes dans le RRG final en adoptant une formulation de fonction objectif intégrant des contraintes. Des a priori à la fois biologiques (sur les interactions entre les gènes) et structuraux (sur la connectivité des nœuds) ont été considérés pour restreindre l'espace des solutions possibles. Les différents a priori donnent des fonctions objectifs ayant des propriétés différentes, pour lesquelles des stratégies d'optimisation adaptées (continue et/ou discrète) peuvent être appliquées. Les post-traitement que nous avons développé ont mené à un ensemble de méthodes nommés BRANE, pour "Biologically-Related A priori for Network Enhancement". Pour chacune des méthodes développées (BRANE Cut, BRANE Relax et BRANE Clust), nos contributions sont triples : formulation de la fonction objectif à l'aide d'a priori, développement de la stratégie d'optimisation et validation (numérique et biologique) sur des données de parangonnage issues des challenges DREAM4 et DREAM5, montrant ainsi des améliorations pouvant atteindre 20%.En complément de l'inférence de réseaux, notre travail s'est étendu à des traitements de données sur graphe plus génériques, tels que les problèmes inverses. Nous avons notamment étudié HOGMep, une approche Bayésienne utilisant des stratégies d'approximation Bayésienne variationnelle. Cette méthode a été développée pour résoudre de façon conjointe, des problèmes de restauration et de classification sur des données multi-composantes (signaux et images). Les performances d'HOGMep dans un contexte de déconvolution d'image couleur montrent de bonnes qualités de reconstruction et de segmentation. Une étude préliminaire dans un contexte de classification de données médicales liant génotype et phénotype a également montré des résultats prometteurs pour des adaptions à venir en bioinformatiquesThe discovery of novel gene regulatory processes improves the understanding of cell phenotypicresponses to external stimuli for many biological applications, such as medicine, environmentor biotechnologies. To this purpose, transcriptomic data are generated and analyzed from mi-croarrays or more recently RNAseq experiments. For each gene of a studied organism placed indifferent living conditions, they consist in a sequence of genetic expression levels. From thesedata, gene regulation mechanisms can be recovered by revealing topological links encoded ingeometric graphs. In regulatory graphs, nodes correspond to genes. A link between two nodesis identified if a regulation relationship exists between the two corresponding genes. Such net-works are called Gene Regulatory Networks (GRNs). Their construction as well as their analysisremain challenging despite the large number of available inference methods.In this thesis, we propose to address this network inference problem with recently developedtechniques pertaining to graph optimization. Given all the pairwise gene regulation informa-tion available, we propose to determine the presence of edges in the final GRN by adoptingan energy optimization formulation integrating additional constraints. Either biological (infor-mation about gene interactions) or structural (information about node connectivity) a priorihave been considered to reduce the space of possible solutions. Different priors lead to differentproperties of the global cost function, for which various optimization strategies can be applied.The post-processing network refinements we proposed led to a software suite named BRANE for“Biologically-Related A priori for Network Enhancement”. For each of the proposed methodsBRANE Cut, BRANE Relax and BRANE Clust, our contributions are threefold: a priori-based for-mulation, design of the optimization strategy and validation (numerical and/or biological) onbenchmark datasets.In a ramification of this thesis, we slide from graph inference to more generic data processingsuch as inverse problems. We notably invest in HOGMep, a Bayesian-based approach using aVariation Bayesian Approximation framework for its resolution. This approach allows to jointlyperform reconstruction and clustering/segmentation tasks on multi-component data (for instancesignals or images). Its performance in a color image deconvolution context demonstrates bothquality of reconstruction and segmentation. A preliminary study in a medical data classificationcontext linking genotype and phenotype yields promising results for forthcoming bioinformaticsadaptations
10
Bekkara, Nourouddine Courtois Bernard. "Optimisation et compromis surface-vitesse dans le compilateur de silicium SYCO." S.l. : Université Grenoble 1, 2008. http://tel.archives-ouvertes.fr/tel-00325731.
Full textBooks on the topic "Optimisation dans des graphes"
1
Laignelet, Bernard. Analyse statistique et optimisation dans les bio-industries. Paris: Hermann, 1993.
Find full text
2
Atkinson, Dave. Théorie des graphes et structuralisme: Le sommet de Québec dans une perspective de cohésion. Québec: Université Laval, Laboratoire d'études politiques et administratives, 1988.
Find full text
3
Atkinson, Dave. Theorie des graphes et structuralisme: Le sommet de Quebec dans une perspective de comesion. Quebec: Universite Laval, 1988.
Find full text
4
Nana, Davies C. H. La gestion du régime de change dans les pays à monnaie faiblement convertible: Modélisation, simulation, optimisation. Grenoble: A.N.R.T. Université Pierre Mendès France Grenoble 2, 1990.
Find full text
5
West, Douglas Brent. Introduction to graph theory. Upper Saddle River, NJ: Prentice Hall, 1996.
Find full text
6
Bassat, Jean-Marc. Optimisation des paramètres de croissance et caractérisations des monocristaux de Bi₁₂ Ge O₂₀ purs et dopés en vue d'applications dans le domaine de l'optique cohérente. Grenoble: A.N.R.T, Université Pierre Mendes France (Grenoble II), 1986.
Find full text
7
Fondements de la Recherche Opérationnelle et Optimisation Par Graphes Pour L'Ingénierie. Primedia eLaunch LLC, 2022.
Find full text
8
Recherche Opérationnelle - Tome 1: Programmation linéaire. Optimisation combinatoire. Programmation dynamique. Graphes. Métaheuristiques. ELLIPSES, 2012.
Find full text
9
Berté, Issoufou. Optimisation des ressources humaines dans une administration publique. Presses Academiques Francophones, 2021.
Find full text
10
Jungnickel, Dieter. Graphs, Networks and Algorithms (Algorithms and Computation in Mathematics). 3rd ed. Springer, 2007.
Find full textBook chapters on the topic "Optimisation dans des graphes"
1
Korte, Bernhard, Jens Vygen, Jean Fonlupt, and Alexandre Skoda. "Graphes." In Optimisation combinatoire, 13–50. Paris: Springer Paris, 2010. http://dx.doi.org/10.1007/978-2-287-99037-3_2.
Full text
2
Bretto, Alain, Alain Faisant, and François Hennecart. "Connexité et flots dans les réseaux." In Éléments de théorie des graphes, 99–129. Paris: Springer Paris, 2012. http://dx.doi.org/10.1007/978-2-8178-0281-7_4.
Full text
3
Korte, Bernhard, Jens Vygen, Jean Fonlupt, and Alexandre Skoda. "Flots dans les réseaux." In Optimisation combinatoire, 171–204. Paris: Springer Paris, 2010. http://dx.doi.org/10.1007/978-2-287-99037-3_8.
Full text
4
Colonnelli, Iacopo, Doriana Medić, Alberto Mulone, Viviana Bono, Luca Padovani, and Marco Aldinucci. "Introducing SWIRL: An Intermediate Representation Language for Scientific Workflows." In Lecture Notes in Computer Science, 226–44. Cham: Springer Nature Switzerland, 2024. http://dx.doi.org/10.1007/978-3-031-71162-6_12.
Full textAbstract:
AbstractIn the ever-evolving landscape of scientific computing, properly supporting the modularity and complexity of modern scientific applications requires new approaches to workflow execution, like seamless interoperability between different workflow systems, distributed-by-design workflow models, and automatic optimisation of data movements. In order to address this need, this article introduces SWIRL, an intermediate representation language for scientific workflows. In contrast with other product-agnostic workflow languages, SWIRL is not designed for human interaction but to serve as a low-level compilation target for distributed workflow execution plans. The main advantages of SWIRL semantics are low-level primitives based on the send/receive programming model and a formal framework ensuring the consistency of the semantics and the specification of translating workflow models represented by Directed Acyclic Graphs (DAGs) into SWIRL workflow descriptions. Additionally, SWIRL offers rewriting rules designed to optimise execution traces, accompanied by corresponding equivalence. An open-source SWIRL compiler toolchain has been developed using the ANTLR Python3 bindings.
5
Establet, Colette, and Jean-Paul Pascual. "Liste des graphes." In La gent d’État dans la société ottomane damascène, 327. Presses de l’Ifpo, 2011. http://dx.doi.org/10.4000/books.ifpo.2298.
Full text
6
"7. Dessinons un graphe dans le plan sans croiser les arêtes." In À la découverte des graphes et des algorithmes de graphes, 55–64. EDP Sciences, 2020. http://dx.doi.org/10.1051/978-2-7598-2102-0-007.
Full text
7
"7. Dessinons un graphe dans le plan sans croiser les arêtes." In À la découverte des graphes et des algorithmes de graphes, 55–64. EDP Sciences, 2020. http://dx.doi.org/10.1051/978-2-7598-2102-0.c007.
Full text
8
GUYOMAR, Cervin, and Claire LEMAITRE. "Métagénomique et métatranscriptomique." In Des séquences aux graphes, 151–86. ISTE Group, 2023. http://dx.doi.org/10.51926/iste.9066.ch5.
Full textAbstract:
Ce chapitre propose une étude de la métagénomique, en présentant les méthodes répondant à la question de l'identification des organismes présents dans des communautés microbiennes, avec ou sans références, ainsi qu'à la détermination de l'aspect fonctionnel (métatranscriptomique, inférence de réseaux métaboliques) ou encore à la comparaison d'échantillons métagénomiques.
9
SZENDE, Thomas. "Négociation – Autonomisation – Optimisation." In Des langues calculables à l'homme incalculable, 177–84. Editions des archives contemporaines, 2021. http://dx.doi.org/10.17184/eac.5271.
Full text
10
DE’ FAVERI TRON, Alvise. "La détection d’intrusion au moyen des réseaux de neurones : un tutoriel." In Optimisation et apprentissage, 211–47. ISTE Group, 2023. http://dx.doi.org/10.51926/iste.9071.ch8.
Full textAbstract:
La détection d'intrusion est un concept clé dans la sécurité. Elle vise à analyser l'état actuel d'un réseau en temps réel et à identifier les anomalies potentielles qui se produisent dans le système. Un réseau de neurones à réaction formé sur l'ensemble de données NSL-KDD a pour objectif de maximiser la précision de la reconnaissance de nouveaux échantillons de données.
Conference papers on the topic "Optimisation dans des graphes"
1
Vuichard, L., P. Schouwey, M. Lakhal, M. Ghribi, and A. Kaddouri. "Optimisation Énergétique par Logique Floue Dans un Moteur à Induction Triphasé." In 2006 Canadian Conference on Electrical and Computer Engineering. IEEE, 2006. http://dx.doi.org/10.1109/ccece.2006.277315.
Full text
2
Farruggia, François. "Optimisation du placement de la maintenance sur les marchés de l'électricité." In Place et évolution de l'énergie nucléaire dans le futur. Les Ulis, France: EDP Sciences, 2018. http://dx.doi.org/10.1051/jtsfen/2018pla3.1.
Full text
3
Lajoie, David. "Optimisation du fonctionnement des atténuateurs de houle de type dos de chameau à l’aide de perforations dans la structure." In Journées Nationales Génie Côtier - Génie Civil. Editions Paralia, 2008. http://dx.doi.org/10.5150/jngcgc.2008.071-l.
Full text
4
Daas, M., and K. Dada. "Le flux numérique en implantologie." In 66ème Congrès de la SFCO. Les Ulis, France: EDP Sciences, 2020. http://dx.doi.org/10.1051/sfco/20206601016.
Full textAbstract:
L’optimisation du résultat esthétique et fonctionnel des restaurations implantaires, la simplification des procédures cliniques et de laboratoire et lamélioration de la prévisibilité des traitements sont les principaux objectifs de l’implantologie moderne. Cette prévisibilité est due en grande partie à l’intégration du flux numérique dans les différents étapes du traitement: analyse esthétique virtuel « Digital Smile Design », meilleure communication avec les patients, prise en compte des paramètres biologiques, esthétiques et fonctionnels, prise dempreinte optique, numérisation des modèles, planification implantaire 3D, chirurgie guidée, optimisation du profil démergence avec les piliers anatomiques personnalisés, mise en place d’une restauration implanto-portée se rapprochant le plus possible des dents naturelles absentes, en se fondant dans son environnement tout en respectant la notion de «Biomimétique». Cette démarche permet donc aujourdhui d’anticiper le résultat de nos traitements, devenus de plus en plus complexes, et d’assurer la pérennité de nos restaurations implantaires à long terme. Le but de notre intervention est de présenter l’intégration de ces nouvelles technologies dans notre pratique quotidienne, du cas simple au plus complexe.
5
Hascoet, E., G. Valette, G. Le Toux, and S. Boisramé. "Proposition d’un protocole de prise en charge implanto-portée de patients traités en oncologie tête et cou suite à une étude rétrospective au CHRU de Brest." In 66ème Congrès de la SFCO. Les Ulis, France: EDP Sciences, 2020. http://dx.doi.org/10.1051/sfco/20206602009.
Full textAbstract:
L’organisation de la réhabilitation maxillo-faciale implanto-portée en oncologie tête et cou reste sujet à débat. Il n’existe pas de consensus quant au moment de la réhabilitation implantaire (pendant ou à distance de l’exérèse) ou quant aux prérequis anatomiques qui garantissent son succès. Le but de cette étude est de mettre en place un protocole de prise en charge implanto-portée de patients ayant été traités en oncologie tête et cou. Il s’agit d’une étude rétrospective entre 2013 et 2017, analysant la réhabilitation implantoportée de neuf patients traités pour un cancer tête et cou par chirurgie et radiothérapie (groupe 1 : 5 patients) ou par chirurgie seule (groupe 2 : 4 patients). Les critères étudiés étaient les données personnelles des patients, leurs antécédents oncologiques, les bilans oraux pré-opératoires effectués, les thérapeutiques utilisées ainsi que le suivi. Tous les patients ont été traités pour des carcinomes épidermödes majoritairement situés au niveau du plancher buccal. Ils présentaient tous une limitation de la mobilité linguale, une absence de vestibule et des tissus crestaux mobiles. Les projets prothétiques prévoyaient de réaliser pour sept patients une prothèse amovible complète mandibulaire stabilisée sur implants et pour deux patients des couronnes unitaires sur implant. Les patients ayant recu un lambeau libre de péroné latéral ont bénéficié d’une greffe d’apposition associée à un lambeau de FAMM. Les deux greffes ont permises la pose des implants. Sur neuf patients, cinq ont bénéficié d’une libération linguale, six ont recu une vestibuloplastie et huit ont eu une greffe épithélio-conjonctive péri-implantaire. Les implants ont été posés sous anesthésie générale avec un guide chirurgical pointeur. Il s’agissait d’implants Tissu Level RN SLA Roxolid (Straumann, Basel, Suisse). Pour les patients du groupe 2, la pose des implants a eu lieu en même temps que la vestibuloplastie. Lors de cette étude quatre patients étaient réhabilités par une prothèse sur implants. Le groupe 2 n’a pas présenté de complications. Deux patients du groupe 1 ont nécessité plusieurs libérations linguales et deux implants ne se sont pas ostéointégrés dans ce groupe. Lors de chirurgies en deux temps, des greffes épithélio-conjonctives crestales ont dû être réalisées pendant la vestibuloplastie puis pendant la pose implantaire. Deux greffes osseuses ont été réalisées chez deux patients ayant été irradiés bien que cela soit contre indiqué dans la littérature (Raoul 2009). Une greffe osseuse d’apposition peut donc être une solution viable chez ces patients afin de limiter le bras de levier prothétique. Cette étude a permis de mettre en exergue : l’importance de prévoir en amont la réhabilitation implantoportée lors de la reconstruction pour une optimisation du positionnement du greffon osseux et l’intérêt d’effectuer dans le même temps vestibuloplastie, pose des implants et aménagement péri-implantaire pour la pérennité implantaire. Cette étude rétrospective a permis de proposer un protocole de prise en charge standardisé de la réhabilitation implanto-portée de patients traités pour un cancer tête et cou.
Reports on the topic "Optimisation dans des graphes"
1
Touré, Mustapha, and Thomas G. Poder. Mesure des années de vie ajustées par la qualité de vie globale au Québec : le 13-MD. CIRANO, August 2022. http://dx.doi.org/10.54932/sxao9819.
Full textAbstract:
La demande croissante à laquelle font face les systèmes de santé combinée à la rareté des ressources disponibles rend impératif leur optimisation pour effectuer des choix éclairés. Le concept d’année de vie ajustée par la qualité (AVAQ) s’inscrit dans ce cadre et utilise des instruments de mesure de qualité de vie reliée à la santé (QVRS), parmi lesquels des instruments génériques. Cependant, de nombreuses différences peuvent être observées entre ces instruments. Le constat général est que quasiment tous les instruments génériques contiennent une ou plusieurs dimensions liées à la santé physique (p. ex. incapacité, inconfort, douleur) au détriment d'autres dimensions d’ordre mentales ou sociales. Afin de pallier cette limite, un nouvel instrument a été créé, son but étant d’être plus complet et plus équilibré dans la mesure de la qualité de vie reliée à la santé globale (QVRS-G). Ce rapport présente les étapes clés de la création de cet instrument ainsi que les résultats obtenus dans la mesure de la QVRS-G des québécois au printemps 2021. Ainsi un nouvel outil générique, le 13-MD, composé de 33 items avec 5 à 7 niveaux chacun a été mis sur pieds. La création d’un value set permettant la conversion des états de santé en scores d’utilité permettra son utilisation dans les analyses coût-utilité.
2
J. Caron, Daniel, Vincent Nicolini, Alan Bernardi, and Aude Motulsky. État de situation, constatations et pistes de réflexion pour la transformation des services préhospitaliers vers le numérique. CIRANO, January 2025. https://doi.org/10.54932/vwbb9543.
Full textAbstract:
Dans le but d’accompagner les services préhospitaliers d’urgence du Québec dans leur transformation vers le numérique, ce rapport de recherche examine les défis et les leviers à une transformation vers le numérique réussie selon trois perspectives : la technologie, le fonctionnement et la gouvernance. Sur le plan technologique, les auteurs constatent que plusieurs chantiers sont en cours simultanément et que les solutions technologiques sont développées de manière locale sans normes nationales établies. Au niveau du fonctionnement, la standardisation des opérations est vue positivement, bien qu’il soit important de laisser une marge de manœuvre pour tenir compte des particularités régionales. Une optimisation du fonctionnement des opérations pourrait aussi passer par une meilleure intégration au continuum de soins. Du côté de la gouvernance, les Centres de communication de santé (CCS) s’accommodent généralement bien de la structure de gouvernance actuelle, mais les relations entre les acteurs sont inégales d’une région à l’autre. La conciliation entre les perspectives des différents acteurs impliqués (privés, publics, OBNL) représente un irritant pour la gouvernance des services préhospitaliers dans certaines régions. Leurs analyses et constats s’appuient sur (1) une revue de la littérature scientifique, (2) un inventaire technologique sommaire des différents CCS basé sur des entretiens et une revue documentaire, ainsi que (3) la réalisation d’entretiens semi-dirigés auprès de l’ensemble des intervenants clés des CCS, des CISSS et CIUSS et de représentants du ministère de la Santé et des Services sociaux (MSSS).