Добірка наукової літератури з теми "Algorithmes de complexité paramétrés"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Algorithmes de complexité paramétrés".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Статті в журналах з теми "Algorithmes de complexité paramétrés":
1
Atlan, Henri. "Complexité des systèmes naturels et sous-détermination des théories : une possible limite de la modélisation." Nouvelles perspectives en sciences sociales 4, no. 2 (May 11, 2009): 35–45. http://dx.doi.org/10.7202/029890ar.
Анотація:
Résumé Dans la théorie de l’information probabiliste comme dans la théorie des algorithmes de programmation, l’on n’a pas à s’occuper de la question de savoir comment nous comprenons ni comment les significations sont créées. Dans ces deux cas de complexité, nous rencontrons le même paradoxe : une identité formelle entre complexité maximale et aléatoire (c’est-à-dire désordre avec homogé-néité statistique maximale). Et, dans les deux cas, la solution du paradoxe consiste à l’ignorer en supposant qu’un sens et une signification existent a priori, ce qui élimine de ce fait l’hypothèse de l’aléatoire. Ce n’est que très récemment qu’on a tenté de résoudre vraiment ce paradoxe par des travaux sur la complexité algorithmique tenant compte d’une définition de la complexité porteuse de signification. Une première approche concerne le principe de complexité par le bruit. Une seconde, plus récente, utilise des simulations de réseaux d’automates pour tenter de surprendre l’émergence de significations fonctionnelles dans les réseaux d’automates à propriétés auto-organisatrices. Parmi les résultats obtenus, on trouve une large sous-détermination des théories par les faits, et la petite taille de ces réseaux permet d’en analyser clairement l’origine et même de la quantifier. Cette sous-détermination des théories apparaît comme l’expression probablement la plus spectaculaire de ce qu’est la com-plexité naturelle.
2
Hancart, Christophe. "Des bornes exactes de la complexité des algorithmes séquentiels de recherche d'un motif." Bulletin of the Belgian Mathematical Society - Simon Stevin 1, no. 2 (1994): 239–52. http://dx.doi.org/10.36045/bbms/1103408548.
3
Wilss, Wolfram. "Basic Concepts of MT." Meta 38, no. 3 (September 30, 2002): 403–13. http://dx.doi.org/10.7202/004608ar.
Анотація:
Résumé Malgré les progrès réalisés dans l'élaboration des algorithmes de parsage, les systèmes de traduction automatiques, même les plus sophistiqués, se heurtent encore à de nombreux problèmes dont ceux de la complexité syntaxique, de l'ambiguïté lexicale et de l'analyse interphrastique. La compréhension de la corrélation entre les diverses unités syntagmatiques dépend des connaissances linguistiques, extralinguistiques et contextuelles dont la combinaison permet justement au traducteur humain de résoudre de manière quasi automatique les problèmes d'ambiguïté. La mise sur pied d'un système totalement indépendant de l'action humaine relevant aujourd'hui de l'utopie, la recherche en traduction automatique devrait davantage s'orienter vers la conception de micro-systèmes utilisables dans des domaines précis.
4
Michaël Thomazo. "Réponse à des requêtes conjonctives en présence de règles existentielles – décidabilité, complexité et algorithmes." Bulletin 1024, no. 6 (July 2015): 117–19. http://dx.doi.org/10.48556/sif.1024.6.117.
5
Benmostefa, Soumia, and Hadria Fizazi. "Classification automatique des images satellitaires optimisée par l'algorithme des chauves-souris." Revue Française de Photogrammétrie et de Télédétection, no. 203 (April 8, 2014): 11–17. http://dx.doi.org/10.52638/rfpt.2013.25.
Анотація:
Cet article propose une nouvelle approche de classification automatique non supervisée des images. La classification est l'une des opérations les plus importantes dans plusieurs domaines d'analyse d'images telles que la médecine et la télédétection. Elle consiste à rechercher les différents thèmes constituant une scène représentée. Cependant, en raison de sa complexité plusieurs méthodes ont été proposées, spécifiquement des méthodes d'optimisation. Nous nous intéressons à la technique des chauves-souris, une métaheuristique d'optimisation biologique très récente, visant à modéliser le comportement d'écholocation des chauves-souris que nous allons adapter au problème de classification. Elle combine les avantages de plusieurs métaheuristiques telles que l'optimisation par essaims particulaires, les algorithmes génétiques et le recuit simulé.\\Une nouvelle approche de classification automatique basée sur l'algorithme des chauves-souris est implémentée et appliquée sur deux images, la première est synthétique contenant des objets polyédriques, la seconde est satellitaire représentant la région d'Oran ouest en Algérie. Les différentes expérimentations effectuées conduisent à des résultats satisfaisants et montrent l'efficacité de l'approche.
6
Kouki, Rahim, and Soumaya Derragi. "Interdisciplinarité et difficulté d’apprentissage des méthodes numériques en programmation." TANGRAM - Revista de Educação Matemática 6, no. 3 (September 30, 2023): 2–22. http://dx.doi.org/10.30612/tangram.v6i3.16950.
Анотація:
Les algorithmes numériques font l’objet d’un enseignement explicite dans les classes préparatoires à l’entrée aux écoles d’ingénieurs. Le caractère interdisciplinaire de ces derniers, permet de construire un pont entre le langage et l’action et met l’accent sur l’utilité d’une certaine rigueur scientifique expérimentée. Notre recherche s’inscrit dans le cadre d’une démarche réflexive avec une prise de conscience centrée sur les difficultés liées à l’implémentation de la méthode d’Euler comme algorithme numérique pour la résolution des équations différentielles. L’exploration d’un milieu théorique fondé sur les méthodes numériques d’approximation, que nous avons menée, nous a permis de dégager différents types d’obstacles didactique rencontrés lors de l'implémentation de la solution numérique d’ordre sémiotique, organisationnel ou encore psychologique. Elle a aussi dénoté d’une certaine complexité syntaxique des relations de récurrences à analyser dans un aspect sémantique. Nous nous plaçons alors dans le cadre de la théorie des champs conceptuels développée dans les travaux de (Vergnaud, 1990) croisée à la notion de registres développé par (Duval, 1993) afin d’analyser ces difficultés dans une dimension syntaxique/sémantique (Kouki, 2018).
7
Bouchafa, Samia. "Décision cumulative pour la vision dynamique des systèmes." Revue Française de Photogrammétrie et de Télédétection, no. 202 (April 16, 2014): 2–26. http://dx.doi.org/10.52638/rfpt.2013.48.
Анотація:
Les travaux présentés dans cette synthèse portent essentiellement sur l'analyse de scènes à partir de caméras mobiles avec pour application immédiate l'apport d'une vision par ordinateur efficace dans les systèmes autonomes. Ils sont le fruit d'une décennie de recherches menées d'abord à l'INRETS (actuellement IFSTTAR : Institut français des sciences et technologies des transports, de l'aménagement et des réseaux ) puis à l'Université Paris Sud XI (Institut d'Électronique Fondamentale). L'idée initiale est que l'autonomie d'un système implique, ne serait-ce que pour raisons énergétiques, une faible variété d'opérateurs de perception, dont les algorithmes de vision. Les "primitives" extraites des images seront intrinsèquement robustes et stables vis-à-vis de perturbations variées. Elles doivent de plus anticiper, voire faciliter, un processus de décision à divers niveaux voulu systématique. Les lignes de niveaux répondent parfaitement à ces contraintes : on vérifie sans peine leur robustesse et leur abondance dans une image suggère et alimente un processus de décision cumulatif (manipulant un objet de décision unique : l'histogramme généralisé en espace de vote). Nos efforts se sont alors concentrés sur deux aspects : 1) le premier concerne la définition d'une méthodologie cohérente dans laquelle un processus primaire d'extraction de lignes de niveaux est enrichi afin de permettre la construction de primitives plus complexes guidée par un modèle de déformation de l'image. Le nombre de composants donc la forme des primitives est fonction directe du nombre de variables caractérisant le mouvement (déformation) à déterminer. 2) Le second intéresse une méthode de décision cumulative unifiée permettant de traiter des thèmes applicatifs de complexité croissante. Nos travaux se déclinent alors en trois niveaux de cumul, chacun associé de manière à un stade particulier de l'analyse d'images. Les thèmes applicatifs traités pour illustrer notre démarche sont de complexité croissante : détection et estimation du mouvement en caméra fixe, recalage d'images en caméra mobile (type de mouvement connu et profondeur des objets contrainte) puis estimation générale du mouvement propre et de la structure de la scène en caméras embarquées sur un véhicule mobile. Les résultats obtenus montrent comment un choix de primitives robustes associé à un processus de décision cumulatif permet la réutilisation des opérateurs dans plusieurs secteurs. Les systèmes proposés ont la particularité d'être compacts et cohérents, propriété recherchée dans les applications considérées.
8
Jaquet, J. M. "Limnologie et télédétection : situation actuelle et développements futurs." Revue des sciences de l'eau 2, no. 4 (April 12, 2005): 457–81. http://dx.doi.org/10.7202/705039ar.
Анотація:
La télédétection satellitaire est un outil employé couramment et avec succès en océanographie. Il n'en va pas de même en limnologie, où les applications sont encore rares. Par le moyen d'une revue bibliographique, nous tentons d'en analyser les raisons. Après une brève description de l'outil et des satellites en service, l'on met en évidence la spécificité des cibles aquatiques, caractérisées par une réflectance basse et une profondeur d'investigation variable. Ces particularités, jointes à la composition complexe des eaux intérieures, rendent impossible l'extension pure et simple, à la limnologie, des algorithmes développés en océanographie. Néanmoins, nous montrons que la télédétection a été utilisée dans l'étude du bassin versant des lacs, ainsi que pour la cartographie de leurs limites, de la végétation aquatique, des courants, de la thermique et de la couleur de l'eau. Des modèles empiriques, exprimant la matière en suspension ou les paramètres de qualité de l'eau, ont été calculés et appliqués avec succès dans certains lacs. On établit ensuite une typologie des difficultés rencontrées dans l'application de la télédétection à la limnologie : intrinsèques (complexité de la composition), technologiques (capteurs actuels non adaptés aux cibles aquatiques) et institutionnels (coûts élevés et manque de professionnels de ta télédétection dans les cercles limnologiques). Finalement, l'on présente quelques propositions pratiques dans la perspective des nouveaux véhicules spatiaux et capteurs des années 90, qui devraient permettre une exploitation de l'énorme potentiel de la télédétection en limnologie.
9
Poreba, Martyna, and François Goulette. "Recalage rigide de relevé laser par mise en correspondance robuste basée sur des segments." Revue Française de Photogrammétrie et de Télédétection, no. 207 (September 24, 2014): 3–17. http://dx.doi.org/10.52638/rfpt.2014.208.
Анотація:
Le recalage se révèle indispensable pour assembler des relevés laser devant servir à l'analyse, à la documentation et à la reconstruction tridimensionnelle d'environnements. Ce problème apparaît lorsqu'une zone d'intérêt est numérisée, au fil du temps, deux ou plusieurs fois, ou quand sa complexité nécessite un accroissement du nombre de stations de scanner laser fixes. Aussi, en raison de la variété des techniques disponibles d'acquisition, l'intégration multi-données devient une question importante puisqu'elle permet de mettre en cohérence des données contenant souvent une information complémentaire. La vaste majorité des algorithmes existants s'appuient sur les éléments ponctuels. C'est pourquoi les méthodes ICP basées-point demeurent actuellement les plus répandues. Cet article propose l'utilisation des segments sous forme d'intersections entre les plans principaux, pour un recalage rigide des nuages de points mobiles avec d'autres données, qu'elles soient 2D ou 3D. Ces primitives peuvent être aisément extraites, même dans les données laser hétérogènes de faible densité. Quelques méthodes de recalage basées-lignes ont été examinées afin de vérifier leur précision et robustesse au bruit. Les erreurs des paramètres estimés ainsi qu'un nouveau critère — distance modifiée de Hausdorff ont été employés pour les besoins d'une analyse quantitative. Au vu de ces éléments, une chaîne complète nommée RLMR-FMII 2 comprenant un recalage grossier suivi par un recalage fin est proposée pour calculer les paramètres de pose à partir de segments appariés.Étant donné que la mise en correspondance automatique d'entités linéaires est ardue et influence l'estimation des paramètres optimaux de transformation, une méthode d'appariement étudiant la similitude relative est avancée. Enfin, l'efficacité de cette méthode de recalage par mise en correspondance préalable des segments est évaluée et discutée.
10
Pauletto, Christian. "Gestion publique, agilité et innovation : l’expérience suisse du dispositif de crédits COVID-19." Revue Internationale des Sciences Administratives Vol. 90, no. 1 (April 2, 2024): 109–25. http://dx.doi.org/10.3917/risa.901.0109.
Анотація:
Au mois de mars 2020, l’administration suisse a conçu et mis en place en seulement dix jours un programme de crédits cautionnés destiné aux entreprises. La phase de mise en œuvre a également été de courte durée : moins de cinq mois. Cet article étudie comment cela a été possible compte tenu de la complexité du cadre institutionnel et de la nature novatrice du dispositif, notamment en matière de technologies de l’information, avec, en particulier, des avancées majeures dans la pratique suisse de l’administration électronique : le dispositif a utilisé des algorithmes pour vérifier les demandes des entreprises, un numéro d’identification unique des entreprises (IDE) a été créé à grande échelle, les banques suisses ont été associées à l’élaboration du projet et à sa mise en œuvre, et certaines opérations de leurs clients ont été centralisées sur une plateforme gouvernementale en ligne. Nous présentons les caractéristiques essentielles du processus au moyen d’une analyse du déroulement des opérations sur cette période de dix jours. Nous décrivons également les circonstances et le contexte qui ont conduit à des formes radicalement nouvelles de gouvernance publique. Enfin, nous analysons le résultat pour mettre en évidence les caractéristiques novatrices du livrable. L’exemple étudié a été de courte durée et était imprévu, de sorte qu’aucune donnée ni observation n’a pu être recueillie avant ou pendant son déroulement. Cette étude se fonde donc principalement sur des investigations a posteriori . Les participants au projet ont élaboré un système organisationnel informel sans disposer de mandats, de structures ou de rôles clairement définis. Le fait que le livrable était bien défini a joué un rôle moteur dans le processus. Plusieurs caractéristiques du projet, telles que l’efficacité des réseaux, un flux d’informations en temps réel, la flexibilité des fonctions, un management horizontal, et des sous-processus itératifs rapides, se rapprochent de celles des « organisations agiles ». Les tâches ont été exécutées parallèlement et non séquentiellement. Remarques à l’intention des praticiens Il est frappant que peu d’études académiques aient été publiées jusqu’ici sur les leçons tirées de l’expérience unique des paquets de mesures de soutien d’urgence mis en place pendant la pandémie, y compris au niveau intra-organisationnel. Des recherches pourraient être menées sur la reproductibilité de ces mesures, aussi bien dans la perspective de crises futures que d’un ajustement des pratiques usuelles de gestion publique. Notre proposition vise à contribuer à cette discussion et à inspirer les praticiens des administrations publiques et des entités gouvernementales. Elle met l’accent sur les relations entre la gestion gouvernementale des crises et la transformation numérique des procédures administratives à l’aide d’outils informatiques.
Дисертації з теми "Algorithmes de complexité paramétrés":
1
Guillemot, Sylvain. "Approches combinatoires pour le consensus d'arbres et de séquences." Phd thesis, Montpellier 2, 2008. http://www.theses.fr/2008MON20234.
Анотація:
Cette thèse étudie d'un point de vue algorithmique diverses méthodes de consensus portant sur des collections d'objets étiquetés. Les problèmes étudiés impliquent des objets étiquetés sans répétition d'étiquettes ; ces objets peuvent être des arbres enracinés ou des séquences, avec des applications à la bioinformatique. Ainsi, les problèmes sur les arbres considérés dans cette thèse peuvent trouver des applications pour l'estimation de congruence entre phylogénies, pour la construction de superarbres, et pour l'identification de transferts horizontaux de gènes. Pour leur part, les problèmes sur les séquences considérés dans cette thèse ont des applications potentielles pour le calcul de distance génomique basé sur les ordres de gènes. De manière générale, ce travail met à profit les théories de la complexité paramétrique et de l'approximabilité pour obtenir des algorithmes et des résultats de difficulté pour les problèmes étudiés.
2
Daligault, Jean. "Techniques combinatoires pour les algorithmes paramétrés et les noyaux, avec applications aux problèmes de multicoupe." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2011. http://tel.archives-ouvertes.fr/tel-00804206.
Анотація:
Dans cette thèse, nous abordons des problèmes NP-difficiles à l'aide de techniques combinatoires, en se focalisant sur le domaine de la complexité paramétrée. Les principaux problèmes que nous considérons sont les problèmes de Multicoupe et d'Arbre Orienté Couvrant avec Beaucoup de Feuilles. La Multicoupe est une généralisation naturelle du très classique problème de coupe, et consiste à séparer un ensemble donné de paires de sommets en supprimant le moins d'arêtes possible dans un graphe. Le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles consiste à trouver un arbre couvrant avec le plus de feuilles possible dans un graphe dirigé. Les résultats principaux de cette thèse sont les suivants. Nous montrons que le problème de Multicoupe paramétré par la taille de la solution est FPT (soluble à paramètre fixé), c'est-à-dire que l'existence d'une multicoupe de taille k dans un graphe à n sommets peut être décidée en temps f(k) ∗ poly(n). Nous montrons que Multicoupe dans les arbres admet un noyau polynomial, c'est-à-dire est réductible aux instances de taille polynomiale en k. Nous donnons un algorithme en temps O∗(3.72k) pour le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles et le premier algorithme exponentiel exact non trivial (c'est-à-dire meilleur que 2n). Nous fournissons aussi un noyau quadratique et une approximation à facteur constant. Ces résultats algorithmiques sont basés sur des résultats combinatoires et des propriétés structurelles qui concernent, entre autres, les décompositions arborescentes, les mineurs, des règles de réduction et les s−t numberings. Nous présentons des résultats combinatoires hors du domaine de la complexité paramétrée: une caractérisation des graphes de cercle Helly comme les graphes de cercle sans diamant induit, et une caractérisation partielle des classes de graphes 2-bel-ordonnées.
3
Bulteau, Laurent. "Ordre et désordre dans l’algorithmique du génome." Nantes, 2013. http://archive.bu.univ-nantes.fr/pollux/show.action?id=34821dc1-842c-4bdc-a541-2e1752281cf7.
Анотація:
Dans cette thèse, nous explorons la complexité algorithmique de plusieurs problèmes issus de la génomique comparative, et nous apportons des solutions à certains de ces problèmes sous la forme d’algorithmes d’approximation ou paramétrés. Le dénominateur commun aux problèmes soulevés est la mise en commun d’informations génomiques provenant de plusieurs espèces dans le but de tirer des conclusions pertinentes pour l’étude de ces espèces. Les problèmes de tri par transpositions et de tri par inversions préfixes permettent de retrouver l’histoire évolutive des deux espèces. Les problèmes de distance exemplaire et de plus petite partition commune ont pour but de comparer deux génomes dans les cas algorithmiquement difficiles où chaque gène apparait avec plusieurs copies indistinguables dans le génome. Enfin, les problèmes d’extraction de bandes et de linéarisation visent à préciser ou corriger l’information génomique afin qu’elle soit plus pertinente pour des traitements ultérieurs. Les résultats principaux que nous présentons sont la NP-difficulté des problèmes de tri (par transpositions et par inversions préfixes) dont la complexité est restée longtemps une question ouverte; une étude complète de la complexité du calcul des distances exemplaires; un algorithme paramétré pour le calcul de plus petite partition commune (avec un unique paramètre étant la taille de la partition); une étude à la fois large et approfondie des problèmes d’extraction de bandes et enfin une nouvelle structure de données permettant de résoudre plus efficacement le problème de linéarisationIn this thesis, we explore the combinatorial complexity of several problems stemming from comparative genomics, and we provide solutions for some of these problems in the form of parameterized or approximation algorithms. In the problems we consider, we bring together the genomic information of several species and aim at drawing relevant conclusions for the study of these species. Sorting a genome either by transpositions or by prefix reversals leads to the reconstruction of the evolution history regarding the genomes of two species. Exemplar distances and common partition aim at comparing genomes in the algorithmically complex case where duplicated genes are present. Finally, the strip recovery and linearization problems aim at correcting or completing genomic information so that it can be used for further analysis. The main results we expose are the NP-hardness of the sorting problems (both by transpositions and by prefix reversals), of which the computational complexity has been a long-standing open question; an exhaustive study of the computational complexity of exemplar distances; a parameterized algorithm for the minimum common string partition problem; a deep and wide study of strip recovery problems; and finally a new graph structure allowing for a more efficient solving of the linearization problem
4
Guillemot, Sylvain. "Approches Combinatoires pour le Consensus d'Arbres et de Séquences." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2008. http://tel.archives-ouvertes.fr/tel-00401456.
Анотація:
Cette thèse étudie d'un point de vue algorithmique diverses méthodes de consensus portant sur des collections d'objets étiquetés. Les problèmes étudiés impliquent des objets étiquetés sans répétition d'étiquettes ; ces objets peuvent être des arbres enracinés ou des séquences, avec des applications à la bioinformatique. Ainsi, les problèmes sur les arbres considérés dans cette thèse peuvent trouver des applications pour l'estimation de congruence entre phylogénies, pour la construction de superarbres, et pour l'identification de transferts horizontaux de gènes. Pour leur part, les problèmes sur les séquences considérés dans cette thèse ont des applications potentielles pour le calcul de distance génomique basé sur les ordres de gènes. De manière générale, ce travail met à profit les théories de la complexité paramétrique et de l'approximabilité pour obtenir des algorithmes et des résultats de difficulté pour les problèmes étudiés.
5
Fradin, Julien. "Graphes complexes en biologie : problèmes, algorithmes et évaluations." Thesis, Nantes, 2018. http://www.theses.fr/2018NANT4093/document.
Анотація:
Afin de mieux comprendre le fonctionnement d'un système biologique, il est nécessaire d'étudier les différentes entités qui le composent. Pour cela, on peut modéliser ces interactions biologiques sous la forme de graphes. Pour certains de ces graphes, les sommets sont colorés afin d'apporter une information supplémentaire sur la couleur qui leur est associée. Dans ce cadre, une problématique courante consiste à y rechercher un sous-graphe d'intérêt appelé motif. Dans la première partie de ce manuscrit, on présente un état de l'art d'un point de vue algorithmique sur le problème GRAPH MOTIF, qui consiste à rechercher des motifs dits fonctionnels dans ce type de graphes. La modélisation de systèmes biologiques sous la forme de graphes peut également être appliquée em spectrométrie de masse. Ainsi, on introduit le problème MAXIMUM COLORFUL ARBORESCENCE (MCA) dans le but de déterminer de novo la formule moléculaire de métabolites inconnus. Dans la deuxième partie de ce manuscrit, on réalise une étude algorithmique du problème MCA. Alors que MCA est algorithmiquement difficile à résoudre même dans des classes de graphes très contraintes, notre modélisation nous permet notamment d'obtenir de nouveaux algorithmes d'approximation dans ces mêmes classes, ainsi que de déterminer une nouvelle classe de graphes dans laquelle MCA se résout en temps polynomial. On montre également des résultats de complexité paramétrée pour ce problème, que l'on compare ensuite à ceux de la littérature sur des instances issues de données biologiquesLn order to better understand how a biological system works, it is necessary to study the interactions between the different entities that compose it. To this aim, these biological interactions can be modelled in the form of graphs. ln some of these graphs, the vertices are colored in order to provide additional information on the entity which is associated with them. ln this context, a common subproblem consists in searching for a subgraph of interest, called a motif, in these graphs. ln the first part of this manuscript, we present a state of the art from an algorithmical point of view of the GRAPH MOTIF problem, which consists in searching for so-called functional motifs in vertex-colored graphs. The modeling of biological systems in graphs form can also be applied in mass spectrometry. Thus, we introduce the MAXIMUM COLORFUL ARBORESCENCE problem (MCA) in order to de novo determine the molecular formula of unknown metabolites. ln the second part of this manuscript, we carry out an algorithmic study of the MCA problem. While MCA is algorithmically difficult to solve even in very constrained graph classes, our modeling allows us to obtain new approximation algorithms in these same classes, as well as to determine a new graph class in which MCA is solved in polynomial time. Parameterized complexity results for this problem are also shown, which are then compared to those in the literature on instances from biological data
6
Bonnet, Edouard. "Résultats Positifs et Négatifs en Approximation et Complexité Paramétrée." Thesis, Paris 9, 2014. http://www.theses.fr/2014PA090040/document.
Анотація:
De nombreux problèmes de la vie réelle sont NP-Difficiles et ne peuvent pas être résolus en temps polynomial. Deux paradigmes notables pour les résoudre quand même sont: l'approximation et la complexité paramétrée. Dans cette thèse, on présente une nouvelle technique appelée "gloutonnerie-Pour-La-Paramétrisation". On l'utilise pour établir ou améliorer la complexité paramétrée de nombreux problèmes et également pour obtenir des algorithmes paramétrés pour des problèmes à cardinalité contrainte sur les graphes bipartis. En vue d'établir des résultats négatifs sur l'approximabilité en temps sous-Exponentiel et en temps paramétré, on introduit différentes méthodes de sparsification d'instances préservant l'approximation. On combine ces "sparsifieurs" à des réductions nouvelles ou déjà connues pour parvenir à nos fins. En guise de digestif, on présente des résultats de complexité de jeux comme le Bridge et HavannahSeveral real-Life problems are NP-Hard and cannot be solved in polynomial time.The two main options to overcome this issue are: approximation and parameterized complexity. In this thesis, we present a new technique called greediness-For-Parameterization and we use it to improve the parameterized complexity of many problems. We also use this notion to obtain parameterized algorithms for some problems in bipartite graphs. Aiming at establishing negative results on the approximability in subexponential time and in parameterized time, we introduce new methods of sparsification that preserves approximation. We combine those "sparsifiers" with known or new reductions to achieve our goal. Finally, we present some hardness results of games such as Bridge and Havannah
7
Chopin, Morgan. "Problèmes d'optimisation avec propagation dans les graphes : complexité paramétrée et approximation." Phd thesis, Université Paris Dauphine - Paris IX, 2013. http://tel.archives-ouvertes.fr/tel-00933769.
Анотація:
Dans cette thèse, nous étudions la complexité algorithmique de problèmes d'optimisation impliquant un processus de diffusion dans un graphe. Plus précisément, nous nous intéressons tout d'abord au problème de sélection d'un ensemble cible. Ce problème consiste à trouver le plus petit ensemble de sommets d'un graphe à "activer" au départ tel que tous les autres sommets soient activés après un nombre fini d'étapes de propagation. Si nous modifions ce processus en permettant de "protéger" un sommet à chaque étape, nous obtenons le problème du pompier dont le but est de minimiser le nombre total de sommets activés en protégeant certains sommets. Dans ce travail, nous introduisons et étudions une version généralisée de ce problème dans laquelle plus d'un sommet peut être protégé à chaque étape. Nous proposons plusieurs résultats de complexité pour ces problèmes à la fois du point de vue de l'approximation mais également de la complexité paramétrée selon des paramètres standards ainsi que des paramètres liés à la structure du graphe.
8
Bergé, Pierre. "Algorithmes pour voyager sur un graphe contenant des blocages." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLS480.
Анотація:
Nous étudions des problèmes NP-difficiles portant sur les graphes contenant des blocages.Nous traitons les problèmes de coupes du point de vue de la complexité paramétrée. La taille p de la coupe est le paramètre. Étant donné un ensemble de sources {s1,...,sk} et une cible t, nous proposons un algorithme qui construit une coupe de taille au plus p séparant au moins r sources de t. Nous nommons ce problème NP-complet Partial One-Target Cut. Notre algorithme est FPT. Nous prouvons également que la variante de Partial One-Target Cut, où la coupe est composée de noeuds, est W[1]-difficile. Notre seconde contribution est la construction d'un algorithme qui compte les coupes minimums entre deux ensembles S et T en temps $2^{O(plog p)}n^{O(1)}$.Nous présentons ensuite plusieurs résultats sur le ratio de compétitivité des stratégies déterministes et randomisées pour le problème du voyageur canadien.Nous prouvons que les stratégies randomisées n'utilisant pas de mémoire ne peuvent pas améliorer le ratio 2k+1. Nous apportons également des éléments concernant les bornes inférieures de compétitivité de l'ensemble des stratégies randomisées. Puis, nous étudions la compétitivité en distance d'un groupe de voyageurs avec et sans communication. Enfin, nous nous penchons sur la compétitivité des stratégies déterministes pour certaines familles de graphes. Deux stratégies, avec un ratio inférieur à 2k+1 sont proposées: une pour les graphes cordaux avec poids uniformes et l'autre pour les graphes où la taille de la plus grande coupe minimale séparant s et t est au plus kWe study NP-hard problems on graphs with blockages seen as models of networks which are exposed to risk of failures.We treat cut problems via the parameterized complexity framework. The cutset size p is taken as a parameter. Given a set of sources {s1,...,sk} and a target $t, we propose an algorithm which builds a small edge cut of size p separating at least r sources from t. This NP-complete problem is called Partial One-Target Cut. It belongs to the family of multiterminal cut problems. Our algorithm is fixed-parameter tractable (FPT) as its execution takes $2^{O(p^2)}n^{O(1)}$. We prove that the vertex version of this problem, which imposes cuts to contain vertices instead of edges, is W[1]-hard. Then, we design an FPT algorithm which counts the minimum vertex (S,T)-cuts of an undirected graph in time $2^{O(plog p)}n^{O(1)}$.We provide numerous results on the competitive ratio of both deterministic and randomized strategies for the Canadian Traveller Problem. The optimal ratio obtained for the deterministic strategies on general graphs is 2k+1, where k is a given upper bound on the number of blockages. We show that randomized strategies which do not use memory cannot improve the bound 2k+1. In addition, we discuss the tightness of lower bounds on the competitiveness of randomized strategies. The distance competitive ratio for a group of travellers possibly equipped with telecommunication devices is studied. Eventually, a strategy dedicated to equal-weight chordal graphs is proposed while another one is built for graphs with small maximum (s,t)-cuts. Both strategies outperform the ratio 2k+1
9
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.
Анотація:
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
10
Khosravian, Ghadikolaei Mehdi. "Extension of NP Optimization Problems." Thesis, Paris Sciences et Lettres (ComUE), 2019. http://www.theses.fr/2019PSLED064.
Анотація:
Le problème de la détermination de la qualité d’une solution partielle se pose dans la majeure partie des approches algorithmiques cherchant à calculer progressivement une solution globale. L’élagage des arbres de recherche, la preuve de garanties d’approximation et l’efficacité des stratégies d’énumération sont des approches algorithmiques qui exigent souvent un moyen approprié de décider si une solution partielle donnée est un bon candidat pour l’étendre à une solution globale de bonne qualité. Dans cette thèse, nous étudions un type particulier de problèmes d’optimisation, appelés problèmes d’extension pour un grand nombre de problèmes basés sur des graphes. Contredisant peut-être l’intuition, ces problèmes ont tendance à être NP-difficile, même quand le problème d’optimisation sous-jacent peut être résolu en temps polynomial. Nous présentons de nombreux résultats positifs et négatifs de NP-difficulté et d’approximation pour différents scénarios d’entrée. De plus, nous étudions la complexité paramétrée des problèmes d’extension par rapport à la taille des pré-solutions, ainsi que l’optimalité de certains algorithmes exacts sous l’hypothèse du temps exponentielleThe problem of determining the quality of a partial solution occurs in almost every algorithmic approach that gradually computes a global solution. Pruning search trees, proving approximation guarantees, or the efficiency of enumeration strategies usually require a suitable way to decide if a given partial solution is a reasonable candidate to pursue for extension to a global one, of assured quality. In this thesis, we study a special type of optimization problems, called extension problems for a large number of optimization problems on graphs. Possibly contradicting intuition, these problems tend to be NP-hard, even for problems where the underlying optimization problem can be solved in polynomial time. We present many positive/negative hardness and approximation results for different input scenarios. Moreover, the parameterized complexity of extension problems with respect to size of partial solutions, as well as the optimality of some exact algorithms under the Exponential-Time Hypothesis (ETH) are studied
Книги з теми "Algorithmes de complexité paramétrés":
1
Wilf, Herbert S. Algorithmes et complexité. Paris: Masson, 1989.
2
L, Selman Alan, ed. Structure in complexity theory: Proceedings of the conference held at the University of California, Berkeley, California, June 2-5, 1986. Berlin: Springer-Verlag, 1986.
3
Scandinavian Workshop on Algorithm Theory (7th 2000 Bergen, Norway). Algorithm theory - SWAT 2000: 7th Scandinavian Workshop on Algorithm Theory, Stockholm, Sweden, July 5-7, 2000 ; proceedings. Berlin: Springer, 2000.
4
Scandinavian Workshop on Algorithm Theory (7th 2000 Bergen, Norway). Algorithm theory-- SWAT 2000: 7th Scandinavian Workshop on Algorithm Theory, Bergen, Norway, July 5-7, 2000 : proceedings. Berlin: Springer, 2000.
5
1955-, Djidjev H., Bŭlgarska akademii͡a︡ na naukite. Center of Informatics and Computer Technology., and International Symposium on Optimal Algorithms (2nd : 1989 : Varna, Bulgaria), eds. Optimal algorithms: International symposium, Varna, Bulgaria, May 29-June 2 1989 proceedings. Berlin: Springer-Verlag, 1989.
6
Wilf, Herbert S. Algorithms and complexity. Englewood Cliffs, N.J: Prentice-Hall, 1986.
7
Wilf, Herbert S. Algorithms and complexity. 2nd ed. Natick, Mass: A.K. Peters, 2002.
8
Hromkovič, Juraj. Algorithmics for hard problems: Introduction to combinatorial optimization, randomization, approximation, and heuristics, with 71 figures. 2nd ed. Berlin: Springer-Verlag, 2004.
9
Hromkovič, Juraj. Algorithmics for hard problems: Introduction to combinatorial optimization, randomization, approximation, and heuristics. 2nd ed. Berlin: Springer-Verlag, 2003.
10
Hromkovič, Juraj. Algorithmics for hard problems: Introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001.
Частини книг з теми "Algorithmes de complexité paramétrés":
1
KRYSANDER, Mattias, and Erik FRISK. "Analyse structurelle." In Diagnostic et commande à tolérance de fautes 1, 87–114. ISTE Group, 2024. http://dx.doi.org/10.51926/iste.9058.ch2.
Анотація:
Ce chapitre explore les méthodes de conception de systèmes de diagnostic basés sur des modèles mathématiques. Il examine l'analyse des diagnostics de défauts des modèles, la complexité croissante avec le modèle, et l'approche structurale pour les problèmes non linéaires à grande échelle. L'analyse structurelle évalue la détectabilité et l'isolabilité des défauts, aidant à placer les capteurs et à concevoir des détecteurs. Des outils informatiques, notamment une Toolbox MATLAB et Python, sont disponibles pour faciliter cette analyse. La formalisation de la détection et de l'isolation des défauts est discutée, suivie d'une exploration des modèles structurels et des algorithmes graphiques pour l'analyse de diagnostic.