Dissertations / Theses on the topic 'Algorithmes de complexité paramétrés'
To see the other types of publications on this topic, follow the link: Algorithmes de complexité paramétrés.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Algorithmes de complexité paramétrés.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Guillemot, Sylvain. "Approches combinatoires pour le consensus d'arbres et de séquences." Phd thesis, Montpellier 2, 2008. http://www.theses.fr/2008MON20234.
Abstract:
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.
Abstract:
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.
Abstract:
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.
Abstract:
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.
Abstract:
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.
Abstract:
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.
Abstract:
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.
Abstract:
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.
Abstract:
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.
Abstract:
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
11
Perez, Anthony. "Algorithmes de noyau pour des problèmes d'édition de graphes et autres structures." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2011. http://tel.archives-ouvertes.fr/tel-00660089.
Abstract:
Dans le cadre de cette thèse, nous considérons la complexité paramétrée de problèmes NP- complets. Plus précisément, nous nous intéressons à l'existence d'algorithmes de noyau polynomiaux pour des problèmes d'édition de graphes et de relations. Nous introduisons en particulier la notion de branches, qui permet d'obtenir des algorithmes polynomiaux pour des problèmes d'édition de graphes lorsque la classe de graphes cible respecte une décomposition d'adjacence. Cette technique nous permet ainsi d'élaborer les premiers algorithmes de noyaux polynomiaux pour les problèmes CLOSEST 3-LEAF POWER, COGRAPH EDITION et PROPER INTERVAL COMPLETION. Concernant les problèmes d'édition de relations, nous étendons la notion de Conflict Packing, qui a déjà été utilisée dans quelques problèmes paramétrés et permet d'élaborer des algorithmes de noyau linéaires pour différents problèmes. Nous présentons un noyau linéaire pour le problème FEEDBACK ARC SET IN TOURNAMENTS, et adaptons les techniques utilisées pour obtenir un noyau linéaire pour le problème DENSE ROOTED TRIPLET INCONSISTENCY. Dans les deux cas, nos résultats améliorent la meilleure borne connue, à savoir un noyau quadratique. Finalement, nous appliquons cette tech- nique sur les problèmes DENSE BETWEENNESS et DENSE CIRCULAR ORDERING, obtenant à nouveau des noyaux linéaires, qui constituent les premiers algorithmes de noyau polynomiaux connus pour ces problèmes.
12
Watel, Dimitri. "Approximation de l'arborescence de Steiner." Thesis, Versailles-St Quentin en Yvelines, 2014. http://www.theses.fr/2014VERS0025/document.
Abstract:
Dans un graphe orienté contenant un nœud appelé racine, un sous ensemble de nœuds appelés terminaux et une pondération sur les arcs, le problème de l’arborescence de Steiner (DST) consiste en la recherche d’une arborescence de poids minimum contenant pour chaque terminal un chemin de la racine vers ce terminal. Ce problème est NP-Complet. Cette thèse se penche sur l’étude de l’approximabilité de ce problème. Sauf si P=NP, il n’existe pas pour ce problème d’approximation de rapport constant ou logarithmique en k, oú k est le nombre de terminaux. Le plus petit rapport d’approximation connu est O (k") où " est un réel strictement positif. Dans la première partie, nous donnons trois algorithmes d’approximation : un algorithme glouton efficace qui associe deux techniques d’approximations connues pour DST, un algorithme dans le cas des graphes structurés en paliers qui étudie l’approximabilité du problème quand les terminaux sont éloignés de la racine, et un algorithme exponentiel qui combine un algorithme d’approximation et un algorithme exact, dont le rapport d’approximation et la complexité temporelle sont paramétrés par le nombre de terminaux couverts par l’algorithme exact. Dans la seconde partie, nous étudions deux problèmes issus de DST auquel est ajoutée une contrainte sur les nœuds de branchement. Cette contrainte réduit le nombre de solutions réalisables et peut faciliter la recherche d’une solution optimale parmi ce sous-ensemble de solutions. En fonction de la contrainte, nous étudions la possibilité de la trouver en temps polynomial et quel est le rapport d’approximation entre cette solution et la solution du problème non contraintThe directed Steiner tree problem (DST) asks, considering a directed weighted graph, a node r called root and a set of nodes X called terminals, for a minimum cost directed tree rooted in r spanning X. DST is an NP-complete problem. We are interested in the search for polynomial approximations for DST. Unless P = NP, DST can not be approximated neither within a constant ratio nor a logarithmic ratio with respected to k, where k is the number of terminals. The smallest known approximation ratio is O(kԑ)$ where ԑ is a positive real.In the first part, we provide three new approximation algorithms : a practical greedy algorithm merging two of the main approximation techniques for DST, an algorithm for the case where the graph is layered and where the distance between the terminals and the root is high, and an exponential approximation algorithm combining an approximation algorithm and an exact algorithm, parameterized with the number of terminals the exact algorithm must cover.In the last part we study DST with two branching constraints. With this technique, we are able to reduce the number of feasible solutions, and possibly facilitate the search for an optimal solution of the constraint problem. We study how it is possible to build such a solution in polynomial time and if this solution is a good approximation of an optimal solution of the non-constraint problem
13
Garnero, Valentin. "(Méta)-noyaux constructifs et linéaires dans les graphes peu denses." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT328/document.
Abstract:
En algorithmique et en complexité, la plus grande part de la recherche se base sur l’hypothèse que P ≠ NP (Polynomial time et Non deterministic Polynomial time), c'est-à-dire qu'il existe des problèmes dont la solution peut être vérifiée mais non construite en temps polynomial. Si cette hypothèse est admise, de nombreux problèmes naturels ne sont pas dans P (c'est-à-dire, n'admettent pas d'algorithme efficace), ce qui a conduit au développement de nombreuses branches de l'algorithmique. L'une d'elles est la complexité paramétrée. Elle propose des algorithmes exacts, dont l'analyse est faite en fonction de la taille de l'instance et d'un paramètre. Ce paramètre permet une granularité plus fine dans l'analyse de la complexité.Un algorithme sera alors considéré comme efficace s'il est à paramètre fixé, c'est-à-dire, lorsque sa complexité est exponentielle en fonction du paramètre et polynomiale en fonction de la taille de l'instance. Ces algorithmes résolvent les problèmes de la classe FPT (Fixed Parameter Tractable).L'extraction de noyaux est une technique qui permet, entre autre, d’élaborer des algorithmes à paramètre fixé. Elle peut être vue comme un pré-calcul de l'instance, avec une garantie sur la compression des données. Plus formellement, une extraction de noyau est une réduction polynomiale depuis un problème vers lui même, avec la contrainte supplémentaire que la taille du noyau (l'instance réduite) est bornée en fonction du paramètre. Pour obtenir l’algorithme à paramètre fixé, il suffit de résoudre le problème dans le noyau, par exemple par une recherche exhaustive (de complexité exponentielle, en fonction du paramètre). L’existence d'un noyau implique donc l'existence d'un algorithme à paramètre fixé, la réciproque est également vraie. Cependant, l’existence d'un algorithme à paramètre fixé efficace ne garantit pas un petit noyau, c'est a dire un noyau dont la taille est linéaire ou polynomiale. Sous certaines hypothèses, il existe des problèmes n’admettant pas de noyau (c'est-à-dire hors de FPT) et il existe des problèmes de FPT n’admettant pas de noyaux polynomiaux.Un résultat majeur dans le domaine des noyaux est la construction d'un noyau linéaire pour le problème Domination dans les graphes planaires, par Alber, Fellows et Niedermeier.Tout d'abord, la méthode de décomposition en régions proposée par Alber, Fellows et Niedermeier, a permis de construire de nombreux noyaux pour des variantes de Domination dans les graphes planaires. Cependant cette méthode comportait un certain nombre d’imprécisions, ce qui rendait les preuves invalides. Dans la première partie de notre thèse, nous présentons cette méthode sous une forme plus rigoureuse et nous l’illustrons par deux problèmes : Domination Rouge Bleue et Domination Totale.Ensuite, la méthode a été généralisée, d'une part, sur des classes de graphes plus larges (de genre borné, sans-mineur, sans-mineur-topologique), d'autre part, pour une plus grande variété de problèmes. Ces méta-résultats prouvent l’existence de noyaux linéaires ou polynomiaux pour tout problème vérifiant certaines conditions génériques, sur une classe de graphes peu denses. Cependant, pour atteindre une telle généralité, il a fallu sacrifier la constructivité des preuves : les preuves ne fournissent pas d'algorithme d'extraction constructif et la borne sur le noyau n'est pas explicite. Dans la seconde partie de notre thèse nous effectuons un premier pas vers des méta-résultats constructifs ; nous proposons un cadre général pour construire des noyaux linéaires en nous inspirant des principes de la programmation dynamique et d'un méta-résultat de Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh et ThilikosIn the fields of Algorithmic and Complexity, a large area of research is based on the assumption that P ≠ NP(Polynomial time and Non deterministic Polynomial time), which means that there are problems for which a solution can be verified but not constructed in polynomial time. Many natural problems are not in P, which means, that they have no efficient algorithm. In order to tackle such problems, many different branches of Algorithmic have been developed. One of them is called Parametric Complexity. It consists in developing exact algorithms whose complexity is measured as a function of the size of the instance and of a parameter. Such a parameter allows a more precise analysis of the complexity. In this context, an algorithm will be considered to be efficient if it is fixed parameter tractable (fpt), that is, if it has a complexity which is exponential in the parameter and polynomial in the size of the instance. Problems that can be solved by such an algorithm form the FPT class.Kernelisation is a technical that produces fpt algorithms, among others. It can be viewed as a preprocessing of the instance, with a guarantee on the compression of the data. More formally, a kernelisation is a polynomial reduction from a problem to itself, with the additional constraint that the size of the kernel, the reduced instance, is bounded by a function of the parameter. In order to obtain an fpt algorithm, it is sufficient to solve the problem in the reduced instance, by brute-force for example (which has exponential complexity, in the parameter). Hence, the existence of a kernelisiation implies the existence of an fpt algorithm. It holds that the converse is true also. Nevertheless, the existence of an efficient fpt algorithm does not imply a small kernel, meaning a kernel with a linear or polynomial size. Under certain hypotheses, it can be proved that some problems can not have a kernel (that is, are not in FPT) and that some problems in FPT do not have a polynomial kernel.One of the main results in the field of Kernelisation is the construction of a linear kernel for the Dominating Set problem on planar graphs, by Alber, Fellows and Niedermeier.To begin with, the region decomposition method proposed by Alber, Fellows and Niedermeier has been reused many times to develop kernels for variants of Dominating Set on planar graphs. Nevertheless, this method had quite a few inaccuracies, which has invalidated the proofs. In the first part of our thesis, we present a more thorough version of this method and we illustrate it with two examples: Red Blue Dominating Set and Total Dominating Set.Next, the method has been generalised to larger classes of graphs (bounded genus, minor-free, topological-minor-free), and to larger families of problems. These meta-results prove the existence of a linear or polynomial kernel for all problems verifying some generic conditions, on a class of sparse graphs. As a price of generality, the proofs do not provide constructive algorithms and the bound on the size of the kernel is not explicit. In the second part of our thesis, we make a first step to constructive meta-results. We propose a framework to build linear kernels based on principles of dynamic programming and a meta-result of Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh and Thilikos
14
Cochefert, Manfred. "Algorithmes exacts et exponentiels pour les problèmes NP-difficiles sur les graphes et hypergraphes." Electronic Thesis or Diss., Université de Lorraine, 2014. http://www.theses.fr/2014LORR0336.
Abstract:
Dans cette thèse, nous nous intéressons à la résolution exacte de problèmes NP-difficiles sur les graphes et les hypergraphes. Les problèmes que nous étudions regroupent dans un premier temps des variantes du problème classique du nombre chromatique. Les variantes de ce problème se distinguent par la difficulté introduite par les relations entre les classes de couleurs, ou la difficulté de reconnaissance des classes de couleurs elles-mêmes. Puis nous ferons le lien avec les problèmes de transversaux sur les hypergraphes. Plus particulièrement, il s’agira de s’intéresser à l’énumération de transversaux minimaux dans un hypergraphe de rang borné. Outre la résolution exacte, nous nous intéressons à la résolution à paramètre fixe. Le problème de racine carrée de graphe est un problème important en théorie des graphes. Nous proposons et montrons la solubilité à paramètre fixe de deux problèmes d’optimisation reliés. Finalement, nous nous intéresserons à la résolution de problèmes de graphe, soit en lien avec les problèmes de colorations, soit pour montrer les performances possibles de différents algorithmes en fonction de l’espace mémoire disponible. Dans cette thèse, nous aurons à cœur d’appliquer judicieusement la grande majorité des techniques essentielles en algorithmique exacte exponentielle. Principalement, nous appliquerons la programmation dynamique ou le principe d’inclusion-exclusion pour les problèmes de coloration. La technique de programmation dynamique se retrouvera pour d’autres problèmes de cette thèse, aux côtés d’autres méthodes comme la technique de branchement ou de mesurer et conquérirIn this thesis, we are interested in the exact computation of np-hard problems on graphs and hypergraphs. Firstly, we study several variants of colorings. Those variants appear harder than the famous chromatic number problem, by adding difficulty in recognizing the color classes, or more often by introducing various relationships between them. Then we link to problems of transversals in hypergraphs. More precisely, we are interested in enumerating minimal transversals in bounded ranked hypergraphs. Besides the exact computation, we are also interested in fixed parameter tractability. For this area, we study two optimization versions of the famous square root of graphs problem. Finally, we will be interested in solving other problems of graphs related to colorings, or in order to compare efficiencies of algorithms depending on the memory space available. In this thesis, we will apply most of major techniques in designing exact exponential algorithms. The main techniques we use are dynamic programming, inclusion-exclusion, branching, or measure and conquer
15
Sikora, Florian. "Aspects algorithmiques de la comparaison d'éléments biologiques." Phd thesis, Université Paris-Est, 2011. http://pastel.archives-ouvertes.fr/pastel-00667797.
Abstract:
Pour mieux saisir les liens complexes entre génotype et phénotype, une méthode utilisée consiste à étudier les relations entre différents éléments biologiques (entre les protéines, entre les métabolites...). Celles-ci forment ce qui est appelé un réseau biologique, que l'on représente algorithmiquement par un graphe. Nous nous intéressons principalement dans cette thèse au problème de la recherche d'un motif (multi-ensemble de couleurs) dans un graphe coloré, représentant un réseau biologique. De tels motifs correspondent généralement à un ensemble d'éléments conservés au cours de l'évolution et participant à une même fonction biologique. Nous continuons l'étude algorithmique de ce problème et de ses variantes (qui admettent plus de souplesse biologique), en distinguant les instances difficiles algorithmiquement et en étudiant différentes possibilités pour contourner cette difficulté (complexité paramétrée, réduction d'instance, approximation...). Nous proposons également un greffon intégré au logiciel Cytoscape pour résoudre efficacement ce problème, que nous testons sur des données réelles.Nous nous intéressons également à différents problèmes de génomique comparative. La démarche scientifique adoptée reste la même: depuis une formalisation d'un problème biologique, déterminer ses instances difficiles algorithmiquement et proposer des solutions pour contourner cette difficulté (ou prouver que de telles solutions sont impossibles à trouver sous des hypothèses fortes)
16
Yacoub, Taher. "Développement et implémentation d'une approche par fragments pour le design d'ARNs modifiés simple brin avec évaluation sur des protéines de liaison à l'ARN et un modèle d'étude la Bêta-Sécrétase 1." Electronic Thesis or Diss., université Paris-Saclay, 2024. http://www.theses.fr/2024UPASL002.
Abstract:
De nouvelles stratégies thérapeutiques ont émergé grâce aux aptamères qui sont des ligands à haute affinité générés par une méthode expérimentale appelée SELEX. Toutefois, leur utilisation demeure limitée en raison de leur manque de sélectivité et de leur liaison à d'autres cibles. Ces effets hors-cibles ("off-target") sont fréquemment observés dans toutes les stratégies thérapeutiques basées sur l'ARN. Pour accroître leur spécificité et sélectivité, des aptamères modifiés chimiquement in situ ont été générés par SELEX (SOMAmers). Néanmoins, des limitations techniques de SELEX persistent notamment dans le nombre et le type de modifications chimiques utilisables. Nous proposons donc une stratégie de conception in silico d'oligonucléotides modifiés pour s'affranchir de certaines de ces limitations. Pour ce faire, nous avons développé une nouvelle méthode de reconstruction d'ARN simple brin (ARNsb) basée sur l'approche par fragments, sur la connaissance 3D de la structure cible et sur la technique du Color-Coding développé par Alon, Yuster et Zwick. Celle-ci repose sur une modélisation de la connectivité des poses sous la forme d'un graphe permettant la mise en œuvre d'un algorithme combinatoire efficace par programmation dynamique. Cette approche est implémentée pour le « Docking » (recherche du mode de liaison natif) à partir d'une distribution donnée de fragments, pour le « Design » thérapeutique de-novo d'un ARNsb et pour l'analyse statistique de caractéristiques afin d'obtenir des informations entre les poses et la protéine (par exemple, l'analyse de profils de séquence ou la probabilité d'une pose d'appartenir à une chaine ARNsb). Cette nouvelle approche a fait l'objet d'une preuve de concept sur sept complexes ARNsb/protéines et a démontré des résultats pertinents, robustes et exploitables dans une perspective de design.Pour mettre à l'épreuve cette nouvelle méthodologie, une étude de cas a été faite sur l'enzyme Beta-Sécrétase 1 (BACE1, impliquée dans la maladie d'Alzheimer) et son homologue Beta-Sécrétase 2 (BACE2) afin de concevoir un ARNsb sélectif de BACE1. Pour ce faire, une étude a été réalisée afin de déterminer les caractéristiques clés de la spécificité et sélectionner des nucléotides modifiés pouvant se lier aux sites et sous-sites fonctionnels de BACE-1. Ces résultats pourront servir de base pour le design d'ARNsb sélectif et pour l'évaluation de la méthodologie basée sur le Color-CodingNew therapeutic strategies have emerged using aptamers that are high-affinity ligands generated using a procedure called SELEX. Nevertheless, their use are limited due to the lack of selectivity and off-target effects frequently observed as in all RNA-based therapeutic strategies. In order to increase their specificity and selectivity, a class of chemically modified aptamers has been designed in-situ by SELEX (“SOMAmers”). But, various limitations remain due to technical constraints in SELEX, in particular the number and the type of chemical modifications that can be used. We propose a new fragment-based strategy to design in-silico modified aptamers that will overcome some of these limitations, based on the knowledge of 3D structure and the color-coding technique introduced by Alon, Yuster and Zwick. This approach is based on the modeling of pose connectivity in the form of a graph, enabling the implementation of an efficient combinatorial algorithm using dynamic programming. It is used for the “Docking” from a given fragment distribution, the “Design” and the equilibrium statistics for learning features between fragments and the 3D protein, and has been the subject of a proof of concept on 7 ssRNA/protein complexes.To test this new approach on a real therapeutic case study, an analysis has been carried out on the Beta-Secretase 1 (BACE1), an enzyme involved in Alzheimer's disease, and the Beta-Secretase 2 (a homologous protein to BACE1) to determine the key features of specificity and to select the modified nucleotides that bind sites and subsites of BACE1. These results can provide a basis for the design of selective ssRNA and for the evaluation of the Color-Coding based methodology
17
Ayad, Ali. "Complexité de résolution de systèmes algébriques paramétrés." Rennes 1, 2006. https://tel.archives-ouvertes.fr/tel-00127383.
Abstract:
On présente trois algorithmes dans cette thèse. Le premier algorithme résout des systèmes polynomiaux homogènes et paramétrés zéro-dimensionnels avec un temps simplement exponentiel en le nombre n des inconnus. Cet algorithme décompose l'espace des paramètres en un nombre fini d'ensembles constructibles et calcule le nombre fini de solutions par des représentations rationnelles paramétriques uniformes sur chaque ensemble constructible. Le deuxième algorithme factorise absolument des polynômes multivariés paramétrés avec un temps simplement exponentiel en n et en la borne supérieure d de degrés de polynômes à factoriser. Le troisième algorithme décompose les variétés algébriques définies par des systèmes algébriques paramétrés de dimensions positives en composantes absolument irréductibles d'une manière uniforme sur les valeurs des paramètres. La complexité de cet algorithme est doublement exponentielle en n. D'autre part, la borne inférieure du problème de résolution de systèmes algébriques paramétrés est doublement exponentielle en n.
18
Cochefert, Manfred. "Algorithmes exacts et exponentiels pour les problèmes NP-difficiles sur les graphes et hypergraphes." Thesis, Université de Lorraine, 2014. http://www.theses.fr/2014LORR0336/document.
Abstract:
Dans cette thèse, nous nous intéressons à la résolution exacte de problèmes NP-difficiles sur les graphes et les hypergraphes. Les problèmes que nous étudions regroupent dans un premier temps des variantes du problème classique du nombre chromatique. Les variantes de ce problème se distinguent par la difficulté introduite par les relations entre les classes de couleurs, ou la difficulté de reconnaissance des classes de couleurs elles-mêmes. Puis nous ferons le lien avec les problèmes de transversaux sur les hypergraphes. Plus particulièrement, il s’agira de s’intéresser à l’énumération de transversaux minimaux dans un hypergraphe de rang borné. Outre la résolution exacte, nous nous intéressons à la résolution à paramètre fixe. Le problème de racine carrée de graphe est un problème important en théorie des graphes. Nous proposons et montrons la solubilité à paramètre fixe de deux problèmes d’optimisation reliés. Finalement, nous nous intéresserons à la résolution de problèmes de graphe, soit en lien avec les problèmes de colorations, soit pour montrer les performances possibles de différents algorithmes en fonction de l’espace mémoire disponible. Dans cette thèse, nous aurons à cœur d’appliquer judicieusement la grande majorité des techniques essentielles en algorithmique exacte exponentielle. Principalement, nous appliquerons la programmation dynamique ou le principe d’inclusion-exclusion pour les problèmes de coloration. La technique de programmation dynamique se retrouvera pour d’autres problèmes de cette thèse, aux côtés d’autres méthodes comme la technique de branchement ou de mesurer et conquérirIn this thesis, we are interested in the exact computation of np-hard problems on graphs and hypergraphs. Firstly, we study several variants of colorings. Those variants appear harder than the famous chromatic number problem, by adding difficulty in recognizing the color classes, or more often by introducing various relationships between them. Then we link to problems of transversals in hypergraphs. More precisely, we are interested in enumerating minimal transversals in bounded ranked hypergraphs. Besides the exact computation, we are also interested in fixed parameter tractability. For this area, we study two optimization versions of the famous square root of graphs problem. Finally, we will be interested in solving other problems of graphs related to colorings, or in order to compare efficiencies of algorithms depending on the memory space available. In this thesis, we will apply most of major techniques in designing exact exponential algorithms. The main techniques we use are dynamic programming, inclusion-exclusion, branching, or measure and conquer
19
Bulteau, Laurent. "Ordres et désordres dans l'algorithmique du génome." Phd thesis, Université de Nantes, 2013. http://tel.archives-ouvertes.fr/tel-00906929.
Abstract:
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é xes 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 di ciles où chaque gène apparait avec plusieurs copies indistinguables dans le génome. En n, les problèmes d'extraction de bandes et de linéarisation visent à préciser ou corriger l'information génomique a n qu'elle soit plus pertinente pour des traitements ultérieurs. Les résultats principaux que nous présentons sont la NP-di culté des problèmes de tri (par transpositions et par inversions pré xes) 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 en n une nouvelle structure de données permettant de résoudre plus e cacement le problème de linéarisation.
20
Mhalla, Mehdi. "Informatique quantique, algorithmes et complexité." Grenoble INPG, 2004. http://www.theses.fr/2004INPG0113.
Abstract:
Nous présentons dans ce travail plusieurs résultats dans différents domaines de l'information quantique. Après une première partie où nous proposons une introduction au domaine, nous proposons des caractérisations simples et efficaces du phénomène de l'intrication des états purs. Les deux formes de séparabilité étudiées sont la séparabilité totale et la p-q séparabilité. Ces caractérisations nous ont permis de donner des algorithmes optimaux de détection de la séparabilité ayant un gain quadratrique par rapport aux méthodes connues. La troisième partie s'intéresse aux jeux quantiques. Nous présentons tout d'abord une analyse fine des jeux octaux classiques et donnons une stratégie optimale pour le jeu des dominos. Nous proposons ensuite une quantisation de certains jeux combinatoires, définissant ainsi la famille des jeux octaux quantiques. Nous présentons ainsi un modèle formel permettant de parler des jeux quantiques à information totale et proposons une approche qui utilise des pièges pour des jeux quantiques très étudiés, appelés jeux de dés à distance. La dernière partie étudie des problèmes d'optimisation, en développant pour cela des outils optimaux de recherche de minima. Ces outils nous ont permis d'analyser la complexité en requêtes de certains problèmes de graphes. Nous avons ainsi trouvé des algorithmes quantiques pour les problèmes de connectivité, forte connectivité, arbre couvrant de poids minimal et plus courts chemins à une source donnée. Puis, nous avons prouvé leur optimalité en utilisant des techniques de bornes inférieures, déterminant ainsi les limites du facteur de gain qu'offre l'informatique quantique pour résoudre ce problèmeThis work consists in several results in different domains of quantum computing. First, we propose an introduction to the quantum computing theory. Then we give efficient characterizations of entanglement for pure states. We define the full separability and the p-q separability, and give optimal algorithms that improve by a quadratic factor the detection of entanglement. The third part is dedicated to quantum game theory. We analyse some classical combinatorial games, and find an optimal strategy for the 0. 07 octal game. Then we propose a quantisation of the family of octal games, and of some other combinatorial games, defining by the way a formalism that permits to study such games. We also provide some new ideas for the study of the well know coin flip game. In the last part, we study optimisation problems, and give an optimal minima finding algorithm based on the quantum search. Then we apply this tool to design algorithms for some graph problems (connectivity, strong connectivity, minimum spanning tree and single source shortest paths. We prove the optimality of our algorithms by using the quantum adversary lower bound method, giving therefore a characherisation of the speed-up given by quantum computing for these problems
21
Cheikh-Alili, Fahima. "Composition de services: algorithmes et complexité." Phd thesis, Université Paul Sabatier - Toulouse III, 2009. http://tel.archives-ouvertes.fr/tel-00459114.
Abstract:
Le problème de la combinaison des services, autrement appelé problème de la composition, constitue le foyer d'une intense activité de recherche. Composer les services entre eux, c'est entrelacer leurs séquences d'actions, de manière à obtenir des séquences qui satisfassent les exigences des clients. Le problème de la composition de services est difficile à résoudre en général. Dans cette thèse nous considérons des services qui peuvent à la fois exécuter des actions de communications ainsi que des actions internes. De plus, des conditions peuvent être exigées et des effets peuvent être appliqués sur les transitions. Formellement, les services sont représentés par des automates communicants conditionnels. Nous définissons, pour ce modèle, le problème de la composition et nous étudions sa décidabilité pour différentes relations d'équivalence et de préordre à savoir : l'inclusion de traces, l'équivalence de traces, la simulation et la bisimulation. Suite aux résultats de décidabilité obtenus, nous proposons trois variantes pour le modèle initial. Pour chacune d'elles, nous définissions le problème de la composition et nous étudions sa complexité pour les relations citées ci-dessus.
22
Duflot, Marie. "Algorithmes distribués sur des anneaux paramétrés - Preuves de convergence probabiliste et déterministe." Phd thesis, École normale supérieure de Cachan - ENS Cachan, 2003. http://tel.archives-ouvertes.fr/tel-00091429.
Abstract:
Cette thèse se situe dans le cadre de la vérification de systèmes distribués. Plus précisément, nous nous intéressons aux méthodes de preuve de convergence d'algorithmes distribués s'exécutant sur des réseaux en anneau de taille paramétrée. Cette étude distingue de plus le cas des algorithmes probabilistes de celui des algorithmes déterministes.
23
Derhy, Nicolas. "Multicoupes et sous-graphes induits : complexité et algorithmes." Phd thesis, Conservatoire national des arts et metiers - CNAM, 2008. http://tel.archives-ouvertes.fr/tel-00367626.
Abstract:
Dans ce travail de thèse, nous nous intéressons à plusieurs problèmes de théorie des graphes. Dans un premier temps, nous étudions différents problèmes de coupes et de multicoupes puis, dans un second temps, nous nous focalisons sur des problèmes de recherche de sous-graphes induits. Néanmoins, ces deux parties suivent la même ligne directrice : donner une vue d'ensemble de la complexité des problèmes en établissant leur NP-complétude ou en déterminant un algorithme polynomial de moindre complexité. Dans la première partie de la thèse, nous abordons les problèmes de coupes et de multicoupes. Tout d'abord, nous étudions la conséquence de l'ajout d'une contrainte de cardinalité à ces deux types de problèmes et démontrons leur NP- complétude dans le cas général. Puis, nous déterminons leur complexité dans plusieurs classes de graphes particuliers telles que les étoiles orientées et les chaînes en élaborant, pour les cas polynomiaux, différents algorithmes reposant principalement sur la programmation dynamique et l'utilisation de relaxations lagrangiennes. Nous généralisons ensuite cette approche en considérant les versions multicritères des problèmes de coupes et de multicoupes. Nous prouvons que ces derniers sont NP-complets même dans des topologies très simples comme les chaînes ou les cycles. Dans la seconde partie de ce mémoire, nous abordons des problèmes de recherche de sous-graphes induits. Nous nous intéressons principalement à la recherche d'arbres, de chaînes et de cycles induits couvrant un ensemble T de sommets donnés. Après avoir prouvé la NP-complétude des cas généraux, nous nous focalisons davantage sur les cas où la cardinalité de T est fixée. Nous donnons également plusieurs résultats structurels pour les graphes de maille suffisamment large.
24
Tapp, Alain. "Informatique quantique, algorithmes et complexité de la communication." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2000. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape3/PQDD_0018/NQ51978.pdf.
25
Dehry, Nicolas. "Multicoupes et sous-graphes induits : complexité et algorithmes." Paris, CNAM, 2008. http://www.theses.fr/2008CNAM0598.
Abstract:
In this thesis, we consider some problems of graph theory. First, we deal with cut and multicut probems and then, we study induced subgrpah problems. Nevertheless, these two parts share a common purpose : detremining a general overview of the cimplexity of theses problems by proving NP-completeness results or by d"esigning polynomial algrotithms with low running times. In the first part, we tackle cut and multicut problems. We study the consequences of the addition of a cardinality constraint and show the NP-completeness of the general cases. Besides, we give complexity results for some particular graphs such as directed stars and undirected paths, and for the polynomial cases, we design several algorithms using dynamic programming or lagrangian relaxations. Next, we generalize these problems by considering multicriteria versions of the (multi)cut problems. We obtain some NP-completeness results in some very specific classes of graphs like undirected paths and cycles. In the secon part, we focus on the detection of specific induced subgraphs. More precisely, we look for induced paths, induced cycles or induced trees covering a given set of vertices. After proving the NP-completeness of the general cases, we consider the cases where the number of prescribed vertives is fixed. Finally , we also some structural results for C3 free graphsDans ce travail de thèse, nous nous intéressons à plusieurs problèmes de théorie des graphes. Dans un premier temps, nous étudions différents problémes de coupes et de multicoupes pouis, dans un second temps, nous nous focalisons sur des problèmes de recherche de sous-graphes induits. Néammoins, ces deux parties suivent la même ligne directrice : donner une vue d'ensemble de la complexité des problémes en établissant leur NP-complétude ou en déterminant un algorithme polynomial de moindre complexité. Dans la première partie de la thèse, nous abordons les problèmes de coupes et de multicoupes. Tout d'abord, nous étudions la conséquence de l'ajout d'une contrainte de cardinalité à ces deux types de problèmes et démontrons leur NP-complètude dans le cas général. Puis, nous déterminons leur complexité dans plusieurs classes de graphes particuliers telles que les étoiles orientées et les chaînes en élaborant, pour les cas polynominaux, différents algorithmes reposant principalement sur la programmation dynamique et l'utilisation de relaxations lagrangiennes. Nous généralisons ensuite cette approche en considérant les versions multicritères des problèmes de coupes et de multicoupes. Nous prouvons que ces derniers sont NP-complets même dans des typologies très simples comme les chaînes ou les cycles. Dans la seconde partie de ce mémoire, nous abordons des problèmes de recherche de sous-graphes induits. Nous nous intéressons principalement à la recherche d'arbres, de chaînes et de cycles induits ouvrant un ensemble T de sommets donnés. Après avouir prouvé la NP-complétude des cas généraux, nous nous focalisons davantage sur les cas ou la cardinalité de T est fixée. Nous donnons également plusieurs résultats structurels pour les graphes de maille suffisamment large
26
Markey, Nicolas. "Logiques temporelles pour la vérification : expressivité, complexité, algorithmes." Orléans, 2003. http://www.theses.fr/2003ORLE2004.
Abstract:
Ce travail s'inscrit dans le cadre de la vérification formelle de programmes: le model checking est une technique qui permet de s'assurer qu'une propriété, exprimée en logique temporelle, est vérifiée par le modèle d'un système. Cette thèse étudie plusieurs logiques temporelles, du point de vue de l'expressivité et de la complexité. Nous étudions trois grands types de logiques temporelles : - concernant la logique temporelle du temps linéaire, nous prouvons que l'ajout de modalités du passé permet de simplifier l'écriture des formules sans augmenter la complexité des problèmes de model checking. Nous étudions également l'impact de l'ajout de la modalité Now ; - concernant la logique temporelle du temps arborescent, nous établissons la complexité du model checking pour plusieurs extensions classiques de CTL ; - enfin, nous montrons qu'il est possible, sous certaines conditions, de vérifier efficacement des propriétés quantitatives sur la durée séparant deux évènements.
27
Montealegre, Barba Pedro. "Algorithmes de graphes séquentiels et distribués : algorithmes paramétrés via des cliques maximales potentielles : modèle de diffusion dans une clique congestionnée." Thesis, Orléans, 2017. http://www.theses.fr/2017ORLE2001/document.
Abstract:
Cette thèse porte sur des aspects structuraux et algorithmiques des graphes. Elle est divisée en deux parties, qui comportent deux études différentes : une partie sur des algorithmes centralisés-séquentiels, et une autre sur des algorithmes distribués. Dans la première partie, on étudie des aspects algorithmiques de deux structures de graphes appelés séparateurs minimaux et cliques maximales potentielles. Ces deux objets sont au coeur d'un méta-théorème dû à Fomin, Todinca and Villanger (SIAM J. Comput. 2015), qui affirme qu'une grande famille des problèmes d'optimisation peut être résolue en temps polynomial, si le graphe d'entrée contient un nombre polynomial de séparateurs minimaux. La contribution de cette partie consiste à prolonger le méta-théorème de Fomin et al. de deux manières : d'un côté, on l'adapte pour qu'il soit valide pour une plus grande famille des problèmes ; de l'autre, on étend ces résultats à des version paramétrées, pour certains paramètres des graphes. La deuxième partie de la thèse correspond à une étude du modèle appelé « Diffusion dans une Clique Congestionnée ». Dans ce modèle, les sommets d'un graphe communiquent entre eux dans des rondes synchrones, en diffusant un message de petite taille, visible par tout autre sommet. L'objectif ici est d'élaborer des protocoles qui reconnaissent des classes de graphes, en minimisant la taille des messages et le nombre de rondes. La contribution de cette partie est l'étude du rôle du hasard dans ce modèle, et la conception de protocoles pour la reconnaissance et la reconstruction des certaines classes des graphesThis thesis is about structural and algorithmic aspects of graphs. It is divided in two parts, which are about two different studies: one part is about centralized-sequential algorithms, and the other part is about distributed algorithms. In the first part of the thesis we study algorithmic applications of two graph structures called minimal separators and potential maximal cliques. These two objects are in the core of a meta-theorem due to Fomin, Todinca and Villanger (SIAM J. Comput. 2015), which states that a large family of graph optimization problems can be solved in polynomial time, when the input is restricted to the family of graphs with polynomially many minimal separators. The contribution of this part of the thesis is to extend the meta-theorem of Fomin et al. in two ways. On one hand, we adapt it to be valid into a larger family of problems. On the other hand, we extend it into a parameterized version, for several graph parameters. In the second part of this thesis we study the broadcast congested clique model. In this model, the nodes of a graph communicate in synchronous rounds, broadcasting a message of small size visible to every other node. The goal is to design protocols that recognize graph classes minimizing the number of rounds and the message sizes. The contribution of this part is to explore the role of randomness on this model, and provide protocols for the recognition and reconstruction of some graph classes
28
Romero-Meléndez, Cutberto. "Complexité métrique sous-riemannienne." Dijon, 2004. http://www.theses.fr/2004DIJOS028.
Abstract:
Le sujet de cette thèse est la complexité métrique, au sens de Kolmogorov-Jean, de courbes horizontales pour une métrique sous-Riemannienne générique de co-rang un, qui est définie sur une variété de dimension N. On établit le problème dans le cadre du problème de planification de trajectoires. Premièrement, pour N plus grand ou égal à 4, en utilisant principalement des formes normales pour des structures sous-Riemanniennes de contact et quasi-contact, on donne explicitement des expressions pour la complexité métrique en termes des invariants élémentaires du problème. Dans le cas N=3, lequel est le plus compliqué s' il y a des points de Martinet, on ne donne que des bornes pour la complexité métrique. Deuxièmement, on construit la synthèse optimale asymptotique du problème de planification de trajectoires. Dans un troisième temps on présente quelques algorithmes qui donnent une solution au problème de planification de trajectoires, et leur mise en oeuvre au modèle de l'uni-cycleThe subject of this thesis is the metric complexity in the sense of Kolmogorov-Jean for horizontals curves of generic sub-Riemannian metrics of co-rank one, defined on a manifold of dimension N. We set the problem in the context of the motion planning problem. At the first place, for N bigger than 3, by aking use of the normal forms for the contact and quasi-contact sub-Riemannian structures, we provide explicit expressions for the metric complexity in terms of elementary invariants of the problem. The case N equal 3, turns out to be the more complicated, and in this case, in the presence of Martinet points, we provide bounds for the metric complexity. Secondly, we construct the asymptotic optimal syntheses for the motion planning problem. At the end, we present some algorithms that solve the motion planning problem and their corresponding implementation for the model of the unicycle
29
Nicolas, François. "Alignement, séquence, consensus, recherche de similarités : complexité et approximabilité." Montpellier 2, 2005. http://www.theses.fr/2005MON20179.
30
Hadjiat, Malika. "Problèmes de tension sur un graphe : algorithmes et complexité." Aix-Marseille 2, 1996. http://www.theses.fr/1996AIX22061.
Abstract:
Un grand nombre d'applications pratiques concernants les reseaux, tels que l'ordonnancement, peuvent etre modelises par un probleme de determination d'une tension de cout minimum (tcm) dans un graphe oriente. Ce probleme d'optimisation combinatoire, issu de la theorie des graphes et de la programmation lineaire, a ete relativement ignore par la litterature scientifique. L'objectif de cette these est d'entreprendre une etude algorithmique plus complete du probleme de la tcm, en developpant de nouveaux algorithmes de complexite pseudo-polynomiale, polynomiale et fortement polynomiale. Un autre probleme plus connu d'optimisation combinatoire sur les graphes est celui du flot de cout minimum (fcm). Les problemes de tcm et de fcm sont tres lies puisque nous prouvons qu'il existe entre eux une relation de dualite indirecte. Les algorithmes de tcm que nous proposons dans ce document sont des adaptations de methodes resolvant le probleme du fcm. En particulier, nous decrivons les versions primale et duale de la methode simplex, ainsi que l'applicatiion sur l'algorithme de mise a conformite de la technique polynomiale de mise a l'echelle des couts et celle des capacites. Nous proposons aussi le premier algorithme fortement polynomial combinatoire qui determine directement une tcm. Cet algorithme, s'inspirant des idees recentes de goldberg et tarjan pour le flot, est base sur la saturation de cocycles residuels de couts moyens minimums. Une methode pour la recherche de tels cocycles est egalement donnee. D'autre part, nous montrons comment determiner une tension compatible, et s'il en existe une, comment calculer celle de valeur maximale sur un arc particulier du graphe. Enfin, nous nous interessons a l'etude de la complexite theorique de certain algorithmes classiques de tcm. En particulier, nous prouvons que la version tension de l'algorithme de mise a conformite est non polynomiale. En plus de l'analyse theorique de complexite des divers algorithmes de tcm, une etude empirique et comparative de leurs implementations est decrite dans ce rapport
31
Covanov, Svyatoslav. "Algorithmes de multiplication : complexité bilinéaire et méthodes asymptotiquement rapides." Thesis, Université de Lorraine, 2018. http://www.theses.fr/2018LORR0057/document.
Abstract:
Depuis 1960 et le résultat fondateur de Karatsuba, on sait que la complexité de la multiplication (d’entiers ou de polynômes) est sous-quadratique : étant donné un anneau R quelconque, le produit sur R[X] des polynômes a_0 + a_1 X et b_0 + b_1 X, pour tous a_0, a_1, b_0 et b_1 dans R, peut être calculé en seulement trois et non pas quatre multiplications sur R : (a_0 + a_1 X)(b_0 + b_1 X) = m_0 + (m_2 - m_0 - m_1)X + m_1 X^2, avec les trois produits m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1). De la même manière, l’algorithme de Strassen permet de multiplier deux matrices 2nx2n en seulement sept produits de matrices nxn. Les deux exemples précédents tombent dans la catégorie des applications bilinéaires : des fonctions de la forme Phi : K^m x K^n -> K^l, pour un corps donné K, linéaires en chacune des deux variables. Parmi les applications bilinéaires les plus classiques, on trouve ainsi la multiplication de polynômes, de matrices, ou encore d’éléments d’extensions algébriques de corps finis. Étant donnée une application bilinéaire Phi, calculer le nombre minimal de multiplications nécessaires au calcul de cette application est un problème NP-difficile. L'objectif de cette thèse est de proposer des algorithmes minimisant ce nombre de multiplications. Deux angles d'attaques ont été suivis. Un premier aspect de cette thèse est l'étude du problème du calcul de la complexité bilinéaire sous l'angle de la reformulation de ce problème en termes de recherche de sous-espaces vectoriels de matrices de rang donné. Ce travail a donné lieu à un algorithme tenant compte de propriétés intrinsèques aux produits considérés tels que les produits matriciels ou polynomiaux sur des corps finis. Cet algorithme a permis de trouver toutes les décompositions possibles, sur F_2, pour le produit de polynômes modulo X^5 et le produit de matrices 3x2 par 2x3. Un autre aspect de ma thèse est celui du développement d’algorithmes asymptotiquement rapides pour la multiplication entière. Une famille particulière d'algorithmes récents ont été proposés suite à un article de Fürer publié en 2007, qui proposait un premier algorithme, reposant sur la transformée de Fourier rapide (FFT) permettant de multiplier des entiers de n bits en O(n log n 2^{O(log^* n)}), où log^* est la fonction logarithme itéré. Dans cette thèse, un algorithme dont la complexité dépend d'une conjecture de théorie des nombres est proposé, reposant sur la FFT et l'utilisation de premiers généralisés de Fermat. Une analyse de complexité permet d'obtenir une estimation en O(n log n 4^{log^* n})Since 1960 and the result of Karatsuba, we know that the complexity of the multiplication (of integers or polynomials) is sub-quadratic: given a ring R, the product in R[X] of polynomials a_0 + a_1 X and b_0 + b_1 X, for any a_0, a_1, b_0 and b_1 in R, can be computed with three and not four multiplications over R: (a_0 + a_1X)(b_0 + b_1X) = m_0 + (m_2 - m_0 - m_1)X + m_1X^2, with the three multiplications m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1). In the same manner, Strassen's algorithm allows one to multiply two matrices 2nx2n with only seven products of matrices nxn. The two previous examples fall in the category of bilinear maps: these are functions of the form Phi : K^m x K^n -> K^l, given a field K, linear in each variable. Among the most classical bilinear maps, we have the multiplication of polynomials, matrices, or even elements of algebraic extension of finite fields. Given a bilinear map Phi, computing the minimal number of multiplications necessary to the evaluation of this map is a NP-hard problem. The purpose of this thesis is to propose algorithms minimizing this number of multiplications. Two angles of attack have been studied. The first aspect of this thesis is to study the problem of the computation of the bilinear complexity under the angle of the reformulation of this problem in terms of research of matrix subspaces of a given rank. This work led to an algorithm taking into account intrinsic properties of the considered products such as matrix or polynomial products over finite fields. This algorithm allows one to find all the possible decompositions, over F_2, for the product of polynomials modulo X^5 and the product of matrices 3x2 by 2x3. Another aspect of this thesis was the development of fast asymptotic methods for the integer multiplication. There is a particular family of algorithms that has been proposed after an article by Fürer published in 2007. This article proposed a first algorithm, relying on fast Fourier transform (FFT), allowing one to multiply n-bit integers in O(n log n 2^{O(log^* n)}), where log^* is the iterated logarithm function. In this thesis, an algorithm, relying on a number theoretical conjecture, has been proposed, involving the use of FFT and generalized Fermat primes. With a careful complexity analysis of this algorithm, we obtain a complexity in O(nlog n 4^{log^* n})
32
Covanov, Svyatoslav. "Algorithmes de multiplication : complexité bilinéaire et méthodes asymptotiquement rapides." Electronic Thesis or Diss., Université de Lorraine, 2018. http://www.theses.fr/2018LORR0057.
Abstract:
Depuis 1960 et le résultat fondateur de Karatsuba, on sait que la complexité de la multiplication (d’entiers ou de polynômes) est sous-quadratique : étant donné un anneau R quelconque, le produit sur R[X] des polynômes a_0 + a_1 X et b_0 + b_1 X, pour tous a_0, a_1, b_0 et b_1 dans R, peut être calculé en seulement trois et non pas quatre multiplications sur R : (a_0 + a_1 X)(b_0 + b_1 X) = m_0 + (m_2 - m_0 - m_1)X + m_1 X^2, avec les trois produits m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1). De la même manière, l’algorithme de Strassen permet de multiplier deux matrices 2nx2n en seulement sept produits de matrices nxn. Les deux exemples précédents tombent dans la catégorie des applications bilinéaires : des fonctions de la forme Phi : K^m x K^n -> K^l, pour un corps donné K, linéaires en chacune des deux variables. Parmi les applications bilinéaires les plus classiques, on trouve ainsi la multiplication de polynômes, de matrices, ou encore d’éléments d’extensions algébriques de corps finis. Étant donnée une application bilinéaire Phi, calculer le nombre minimal de multiplications nécessaires au calcul de cette application est un problème NP-difficile. L'objectif de cette thèse est de proposer des algorithmes minimisant ce nombre de multiplications. Deux angles d'attaques ont été suivis. Un premier aspect de cette thèse est l'étude du problème du calcul de la complexité bilinéaire sous l'angle de la reformulation de ce problème en termes de recherche de sous-espaces vectoriels de matrices de rang donné. Ce travail a donné lieu à un algorithme tenant compte de propriétés intrinsèques aux produits considérés tels que les produits matriciels ou polynomiaux sur des corps finis. Cet algorithme a permis de trouver toutes les décompositions possibles, sur F_2, pour le produit de polynômes modulo X^5 et le produit de matrices 3x2 par 2x3. Un autre aspect de ma thèse est celui du développement d’algorithmes asymptotiquement rapides pour la multiplication entière. Une famille particulière d'algorithmes récents ont été proposés suite à un article de Fürer publié en 2007, qui proposait un premier algorithme, reposant sur la transformée de Fourier rapide (FFT) permettant de multiplier des entiers de n bits en O(n log n 2^{O(log^* n)}), où log^* est la fonction logarithme itéré. Dans cette thèse, un algorithme dont la complexité dépend d'une conjecture de théorie des nombres est proposé, reposant sur la FFT et l'utilisation de premiers généralisés de Fermat. Une analyse de complexité permet d'obtenir une estimation en O(n log n 4^{log^* n})Since 1960 and the result of Karatsuba, we know that the complexity of the multiplication (of integers or polynomials) is sub-quadratic: given a ring R, the product in R[X] of polynomials a_0 + a_1 X and b_0 + b_1 X, for any a_0, a_1, b_0 and b_1 in R, can be computed with three and not four multiplications over R: (a_0 + a_1X)(b_0 + b_1X) = m_0 + (m_2 - m_0 - m_1)X + m_1X^2, with the three multiplications m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1). In the same manner, Strassen's algorithm allows one to multiply two matrices 2nx2n with only seven products of matrices nxn. The two previous examples fall in the category of bilinear maps: these are functions of the form Phi : K^m x K^n -> K^l, given a field K, linear in each variable. Among the most classical bilinear maps, we have the multiplication of polynomials, matrices, or even elements of algebraic extension of finite fields. Given a bilinear map Phi, computing the minimal number of multiplications necessary to the evaluation of this map is a NP-hard problem. The purpose of this thesis is to propose algorithms minimizing this number of multiplications. Two angles of attack have been studied. The first aspect of this thesis is to study the problem of the computation of the bilinear complexity under the angle of the reformulation of this problem in terms of research of matrix subspaces of a given rank. This work led to an algorithm taking into account intrinsic properties of the considered products such as matrix or polynomial products over finite fields. This algorithm allows one to find all the possible decompositions, over F_2, for the product of polynomials modulo X^5 and the product of matrices 3x2 by 2x3. Another aspect of this thesis was the development of fast asymptotic methods for the integer multiplication. There is a particular family of algorithms that has been proposed after an article by Fürer published in 2007. This article proposed a first algorithm, relying on fast Fourier transform (FFT), allowing one to multiply n-bit integers in O(n log n 2^{O(log^* n)}), where log^* is the iterated logarithm function. In this thesis, an algorithm, relying on a number theoretical conjecture, has been proposed, involving the use of FFT and generalized Fermat primes. With a careful complexity analysis of this algorithm, we obtain a complexity in O(nlog n 4^{log^* n})
33
Ayad, Ali. "Complexité de la résolution des systèmes algébriques paramétriques." Phd thesis, Université Rennes 1, 2006. http://tel.archives-ouvertes.fr/tel-00127383.
Abstract:
On présente trois algorithmes dans cette thèse: Le premier algorithme résout de systèmes polynomiaux homogènes et paramétrés zéro-dimensionnels avec un temps simplement exponentiel en le nombre n des inconnus, cet algorithme décompose l'espace des paramètres en un nombre fini d'ensembles constructibles et calcule le nombre fini de solutions par de représentations rationnelles paramétriques uniformes sur chaque ensemble constructible. Le deuxième algorithme factorise absolument de polynômes multivariés paramétrés avec un temps simplement exponentiel en n et en la borne supérieure d de degrés de polynômes à factoriser. Le troisième algorithme décompose les variétés algébriques définies par de systèmes algébriques paramétrés de dimensions positives en composantes absolument irréductibles d'une manière uniforme sur les valeurs des paramètres. La complexité de cet algorithme est doublement exponentielle en n. D'autre part, la borne inférieure du problème de résolution de systèmes algébriques paramétrés est doublement exponentielle en n.
34
Revol, Nathalie. "Complexité de l'évaluation parallèle de circuits arithmétiques." Grenoble INPG, 1994. http://tel.archives-ouvertes.fr/tel-00005109.
Abstract:
Les algorithmes d'évaluation parallèle des expressions et des circuits arithmétiques peuvent être vus comme des extracteurs du parallélisme intrinsèque contenu dans les programmes séquentiels, parallélisme qui dépasse celui qui peut être lu sur le graphe de précédence et qui tient à la sémantique des opérateurs utilisés. La connaissance des propriétés algébriques, comme l'associativité ou la distributivité, permet une réorganisation des calculs qui n'affecte pas les résultats. Plus la structure algébrique utilisée sera riche en propriétés simples, plus il sera possible d'en tirer parti pour améliorer les algorithmes d'évaluation. Généralisant les algorithmes conçus pour les semi-anneaux, nous proposons un algorithme qui améliore les majorations précédemment connues pour la contraction de circuits arithmétiques dans un treillis. Des simulations de cet algorithme ont permis de mettre en évidence ses qualités de prédicteur automatique de complexité. Réorganiser explicitement les calculs à l'aide de ces algorithmes, c'est-à-dire réaliser un compilateur complet, permet de comparer la réalité des algorithmes parallèles sur machines à mémoire distribuée et la puissance des algorithmes théoriques. Un prototype a été réalisé, basé sur une simplification/extension du langage C. Enfin, l'intérêt de ces techniques dans le domaine de la parallélisation des nids de boucles, pour guider la recherche de réductions cachées dans ces nids, semble prometteuse, parce qu'elle est peu coûteuse à mettre en oeuvre et fournit des informations de qualité. En cela, les recherches en algorithmique parallèle théorique rejoignent les préoccupations de la parallelisation effective
35
Spaenlehauer, Pierre-Jean. "Résolution de systèmes multi-homogènes et déterminantiels algorithmes - complexité - applications." Paris 6, 2012. http://www.theses.fr/2012PA066467.
Abstract:
De nombreux systèmes polynomiaux multivariés apparaissant en Sciences de l'Ingénieur possèdent une structure algébrique spécifique. En particulier, les structures multi-homogènes, déterminantielles et les systèmes booléens apparaissent dans une variété d'applications. Une méthode classique pour résoudre des systèmes polynomiaux passe par le calcul d'une base de Gröbner de l'idéal associé au système. Cette thèse présente de nouveaux outils pour la résolution de tels systèmes structurés. D'une part, ces outils permettent d'obtenir sousdes hypothèses de généricité des bornes de complexité du calcul debase de Gröbner de plusieurs familles de systèmes polynomiauxstructurés (systèmes bilinéaires, systèmes déterminantiels, systèmesdéfinissant des points critiques, systèmes booléens). Ceci permetd'identifier des familles de systèmes pour lequels la complexité arithmétique de résolution est polynomiale en le nombre de solutions. D'autre part, cette thèse propose de nouveaux algorithmequi exploitent ces structures algébriques pour améliorer l'efficacité du calcul de base de Gröbner et de la résolution (systèmes multi-homogènes, systèmes booléens). Ces résultats sontillustrés par des applications concrètes en cryptologie (cryptanalyse des systèmes MinRank et ASC), en optimisation et en géométrie réelle effective (calcul de points critiques)Multivariate polynomial systems arising in Engineering Science often carryalgebraic structures related to the problems they stem from. Inparticular, multi-homogeneous, determinantal structures and booleansystems can be met in a wide range of applications. A classical method to solve polynomial systems is to compute a Gröbner basis ofthe ideal associated to the system. This thesis provides new tools forsolving such structured systems in the context of Gröbner basis algorithms. On the one hand, these tools bring forth new bounds on the complexity of thecomputation of Gröbner bases of several families of structured systems(bilinear systems, determinantal systems, critical point systems,boolean systems). In particular, it allows the identification of families ofsystems for which the complexity of the computation is polynomial inthe number of solutions. On the other hand, this thesis provides new algorithms which takeprofit of these algebraic structures for improving the efficiency ofthe Gröbner basis computation and of the whole solving process(multi-homogeneous systems, boolean systems). These results areillustrated by applications in cryptology (cryptanalysis of MinRank),in optimization and in effective real geometry (critical pointsystems)
36
Atig, Mohamed Faouzi. "Vérification de Programmes Concurrents : Décidabilité et Complexité." Paris 7, 2010. http://www.theses.fr/2010PA077066.
Abstract:
Cette thèse porte sur la vérification des programmes concurrents, en nous intéressant en particulier à l'étude la décidabilité et la complexité des problèmes d'accessibilité. Dans la plus grande partie de cette thèse, nous considérons des programmes concurrents où les processus séquentiels correspondent à des threads pouvant faire des appels de procédures (potentiellement récursives). La difficulté vient de l'interaction entre la récursivité et de la concurrence qui rend le problème de l'accessibilité indécidable en général. Nous étudions alors les conditions sous lesquelles ce problème devient décidable. Ces conditions peuvent être vues comme des contraintes à poser sur l'ordonnancement des actions le long des exécutions du programme analysé. Ainsi, les résultats de décidabilité peuvent être utilisés pour définir des procédures d'analyse sous-approchée permettant de détecter de manière efficace des comportements illicites des programmes. Dans un second temps, nous nous intéressons aux programmes s'exécutant selon un modèle faible de la mémoire partagée (weak memory model). Dans de tels programmes, l'ordre entre les actions d'un même processus est relâché pour des besoins de performance en permettant la permutation entre certains types d'actions. Cela rend alors le conception des programmes concurrents encore plus difficile du fait que la sémantique de la concurrence devient hautement complexe et contre-intuitive. Nos travaux montrent qu'en effet selon le type des relaxations d'ordre entre actions, le problème de l'accessibilité peut être décidable mais hautement complexe dans certains cas, et il peut même être indécidable dans d'autresThis thesis addresses the verification problems in both, concurrent and recursive Systems as well as concurrent Systems with store buffers. We establish the required theoretical basis for automated analyses: decidability and complexity results for reachability problems. In a first time, we are interested in verifying concurrent programs where each process corresponds to a sequential program with (recursive) procedure calls. The difficulty in analyzing such programs cornes from the interaction between recursion and concurrency which makes the reachability problems undecidable in general. However, in practice programs obey additional constraints that can be exploited to turn the reachability problem decidable. Their study is subject of this thesis. These conditions may be seen as constraints to impose on the order between the actions of the analyzed programs. Moreover, these decidability results can be used to perform an under-approximation analysis to effectively detect bad behaviors of the analyzed programs. In a second time, we study concurrent programs running under weak memory models. In such kind of programs, the order between actions of the same process is relaxed (for performance reasons) by allowing the permutation between certain types of memory operations. This makes reasoning about the behaviors of concurrent programs much more difficult. Moreover, it is not clear how to apply standard reasoning techniques. Our works show that indeed according to the type of relaxation, the reachability problem becomes décidable (but with a highly complexity) in other cases, it even turns out undecidability
37
Bagan, Guillaume. "Algorithmes et complexité des problèmes d'énumération pour l'évaluation de requêtes logiques." Phd thesis, Université de Caen, 2009. http://tel.archives-ouvertes.fr/tel-00424232.
Abstract:
Cette thèse est consacrée à l'évaluation de requêtes logiques du point de vue de l'énumération. Nous étudions quatre classes de requêtes. En premier lieu, nous nous intéressons aux formules conjonctives acycliques avec inégalités pour lesquelles nous améliorons un résultat de Papadimitriou et Yannakakis en montrant que de telles requêtes logiques peuvent être évaluées à délai linéaire en la taille de la structure. Nous exhibons ensuite la sous-classe des formules connexe-acycliques pour lesquelles l'évaluation de requêtes s'effectue à délai constant après prétraitement linéaire. Nous montrons que cette classe est maximale pour ce résultat dans le sens suivant: si le produit de matrices booléennes ne peut pas être calculé en temps linéaire alors toute requête conjonctive acyclique est évaluable à délai constant après prétra itement linéaire si et seulement si elle est connexe-acyclique. En second lieu, nous démontrons que toute requête MSO sur une classe de structures de largeur arborescente bornée peut être évaluée à délai linéaire en la taille de chaque solution produite après un prétraitement linéaire en la taille de la structure. En troisième lieu, nous montrons que, pour chaque requête en logique du premier ordre sur des structures de degré borné, il est possible de trouver en temps constant la j-ème solution dans un certain ordre après un prétraitement linéraire. Enfin, nous établissons que les graphes d'intervalles unitaires ont une largeur de clique localement bornée. D'où nous déduisons que tout énoncé du premier ordre sur ces graphes est décidable en temps linéaire; là encore, nous démontrons une certaine maximalité de ce résultat.
38
Faik, Taoufik. "La b-continuite des b-colorations : complexité, propriétés structurelles et algorithmes." Paris 11, 2005. http://www.theses.fr/2005PA112047.
Abstract:
LA B-COLORATION D'UN GRAPHE G EST UNE COLORATION TELLE QUE POUR CHAQUE COULEUR c, IL EXISTE AU MOINS UN SOMMET v COLORE c DONT LE VOISINAGE EST COLORE PAR TOUTES LES AUTRES COULEURS. LE SOMMET v EST DIT UN SOMMET B-CHROMATIQUE. UNE F-COLORATION EST UNE B-COLORATION OU TOUS LES SOMMETS SONT B-CHROMATIQUEUNE COLORATION AVEC LE NOMBRE CHROMATIQUE EST UNE B-COLORATION, EN REVANCHE IL EXITE DES GRAPHES QUI N'ADMETTES AUCUNE F-COLORATIONS. CONTRAIREMENT A TOUTES LES AUTRES COLORATIONS, IL PEUT EXISTER UNE B-COLORATION D'UN GRAPHE AVEC p COULEURS ET UNE AUTRE AVEC q COULEURS (pTHE B-COLORING OF A GRAPH G IS A COLORING SUCH OF G SUCH THAT FOR EACH COLOR c, THERE EXISTS AT LEAST A VERTEX v (CALLED COLORFUL VERTEX) COLORED c HAVING EACH OTHER COLOR ON ITS NEIGHBORHOOD. AN F-COLORING IS A B-COLORING WHERE ALL THE VERTICES ARE COLORFUL. IT IS CLEAR THAT ANY COLORING WITH THE CHROMATIC NUMBER OF COLORS IS A B-COLORING. WHOEVER, THE F-COLORING DO NOT EXIST IN ANY GRAPH. ^ONE PECULIAR CHARACTERISTIC OF B-COLORINGS (RESP; F-COLORINGS) IS THAT FOR SOME GRAPHS, THERE EXISTS A p AND A q B-COLORING (RESP. F-COLORING) WITH p
39
Abouelaoualim, Abdelfattah. "Exploration des graphes arêtes-colorées : topologie, algorithmes, complexité et (non)-approximabilité." Paris 11, 2007. https://tel.archives-ouvertes.fr/tel-00281533.
Abstract:
Les graphes dont les arêtes sont coloriées par c>1 couleurs, avec c un entier donné, autrement dit les graphes c-arêtes-colorées, connaissent un nombre grandissant de champs d’applications notamment en biologie moléculaire et en technologie intégrée à très grande échelle sans oublier leur intérêt théorique puisqu’ils sont une généralisation des graphes orientés. Dans cette thèse nous explorons ces graphes pour extraire et étudier les structures (i. E. , les sous-graphes) dites proprement-arêtes-coloriées c'est-à-dire dans lesquelles chaque paire d’arêtes adjacentes sont de couleurs distinctes. Tout d’abord, nous avons jugé nécessaire de réserver la première partie de la thèse à un état de l’art qui présente les travaux les plus importants et couvre la majorité des questions traitées dans ce domaine depuis les années soixante. En suite, dans une deuxième partie, nous avons commencé par donner des caractérisations de certaines structures proprement-arêtes-coloriées telles que les chaînes et les cycles, et puis nous nous sommes orientés vers la construction des algorithmes, l’étude de l’aspect de la complexité et l’approximabilité d’une variété de structuresThe graphs which edges are colored with c>1 colors, with c is a given integer, in other words c-edge-colored graphs, have a growing number of fields of applications particularly in molecular biology and VLSI. Their theoretical motivation is obvious sine they are a generalization of digraphs. In the present work, we explore these graphs to extract and study structures (i. E. Subgraphs) called properly-edge-colored which every pair of adjacent edges differ in color. We start this work by a part introducing the most notable results in the literature and cover the majority of questions treated in this topic since the sixties. In the second part, first we give characterizations of certain properly-edge-colored structures such as paths and cycles. After that, we were interested by the construction of polynomial algorithms, the study of complexity and approximability aspect of a variety of structures
40
Ouertani, Rym. "Algorithmes de décodage pour les systèmes multi-antennes à complexité réduite." Phd thesis, Paris, Télécom ParisTech, 2009. https://pastel.hal.science/pastel-00718214.
Abstract:
Les systèmes à antennes multiples permettent d’accroitre significativement la capacité. Toutefois, le décodage de tels systèmes présente une grande complexité qui croit en fonction du nombre d'antennes et de la taille de la constellation. Nous proposons un décodeur, appelé SB-Stack basé sur la stratégie de recherche du décodeur séquentiel Stack et la région de recherche du décodeur par sphères. Ce décodeur a une complexité moindre par rapport aux décodeurs existants tout en offrant des performances optimales. Une version paramétrée de ce décodeur est aussi proposée, offrant des performances sous-optimales avec des complexités décroissantes. L’utilisation de codes correcteurs d'erreurs nécessite des sorties souples fournies par le décodeur espace-temps, qui seront utilisées comme entrées par les premiers décodeurs. Nous proposons alors une version modifiée du décodeur SB-Stack délivrant des sorties souples sous forme de taux de vraisemblance logarithmiques. En pratique, il est important d'avoir une complexité faible mais également constante dans certaines applications. Nous proposons alors un décodeur adaptatif qui permet de sélectionner le décodeur le plus adéquat selon la qualité du canal de transmission et la qualité de service souhaitée. Nous présentons une implémentation pratique du décodage adaptatif utilisant le décodeur SB-Stack paramétré. Le décodage des codes espace-temps peut être amélioré en le précédant par une phase de pré-traitement. Nous présentons et nous étudions alors les performances d'une chaine complète de décodage utilisant diverses techniques de pré-traitement combinées avec les décodeurs espace-temps étudiés précédemmentMIMO systems offer large capacity. Several decoders of such systems exist in the literature. Unfortunately, their complexity increases drastically with the lattice dimension and the constellation size. Then, we propose a sequential algorithm (SB-Stack) based on the stack decoder search strategy and the sphere decoder search region. The proposed decoder outperforms the existing ones in term of complexity while achieving ML performance. Furthermore, introducing a bias parameter, the SB-Stack gives a range of performances from ML to ZF-DFE with proportional complexities. So, different performance/complexity trade-offs could be obtained. When channel coding is used, soft decoding becomes necessary. The SB-Stack is then extended to support soft-output detection. A straightforward idea was to exploit the nodes stored in the stack at the end of hard decoding process to calculate LLR. The gain of such method is rather large then classical soft decoders. The big variation of the complexity between low and high SNR is an additional problem because of the variable decoding time. We propose an adaptive decoder based on the SB-Stack that switches between several decoders according to the channel realization and the system specifications. This decoder has an almost constant complexity while keeping good performance. Lattice reduction is used to accelerate the decoding of infinite lattice. Using the MMSE-GDFE, it becomes possible to apply lattice reduction when finite constellations are considered. Therefore, interesting results are obtained when considering MIMO schemes combining the lattice reduction, the MMSE-GDFE process and the sequential decoders given previously
41
Ouertani, Rym. "Algorithmes de décodage pour les systèmes multi-antennes à complexité réduite." Phd thesis, Télécom ParisTech, 2009. http://pastel.archives-ouvertes.fr/pastel-00718214.
Abstract:
Durant ces dernières années, un grand intérêt a été accordé aux systèmes de communication sans fil ayant plusieurs antennes en émission et en réception. Les codes espace-temps permettent d'exploiter tous les degrés de liberté de tels systèmes. Toutefois, le décodage de ces codes présente une grande complexité qui croit en fonction du nombre d'antennes déployées et de la taille de la constellation utilisée. Nous proposons un nouveau décodeur, appelé SB-Stack (Spherical Bound-Stack decoder) basé sur un algorithme de recherche dans l'arbre. Ce décodeur combine la stratégie de recherche du décodeur séquentiel Stack (dit également décodeur à pile) et la région de recherche du décodeur par sphères. Nous montrons que ce décodeur présente une complexité moindre par rapport à tous les décodeurs existants tout en offrant des performances optimales. Une version paramétrée de ce décodeur est aussi proposée, offrant une multitude de performances allant du ZF-DFE au ML avec des complexités croissantes, ainsi plusieurs compromis performances-complexités sont obtenus. Comme pour tous les systèmes de communication, les codes espace-temps pour les systèmes à antennes multiples peuvent être concaténés avec des codes correcteurs d'erreurs. Généralement, ces derniers sont décodés par des décodeurs à entrées et sorties souples. Ainsi, nous avons besoin de sorties souples fournies par le décodeur espace-temps qui seront utilisées comme entrées par les premiers décodeurs. Nous proposons alors une version modifiée du décodeur SB-Stack délivrant des sorties souples sous forme de taux de vraisemblance logarithmiques (Log-Likelihood Ratio - LLR). Pour la mise en oeuvre pratique des décodeurs, il est important d'avoir une complexité faible mais avoir également une complexité constante est indispensable dans certaines applications. Nous proposons alors un décodeur adaptatif qui permet de sélectionner, parmi plusieurs algorithmes de décodage, celui qui est le plus adéquat selon la qualité du canal de transmission et la qualité de service souhaitée. Nous présentons une implémentation pratique du décodage adaptatif utilisant le décodeur SB-Stack paramétré. Le décodage des codes espace-temps peut être amélioré en le précédant par une phase de pré-traitement. En sortie de cette phase, la matrice du canal équivalente est mieux conditionnée ce qui permet de réduire la complexité d'un décodeur optimal et d'améliorer les performances d'un décodeur sous-optimal. Nous présentons et nous étudions alors les performances d'une chaine complète de décodage utilisant diverses techniques de pré-traitement combinées avec les décodeurs espace-temps étudiés précédemment.
42
Moroz, Guillaume. "Sur la décomposition réelle et algébrique des systèmes dépendant de paramètre." Paris 6, 2008. https://tel.archives-ouvertes.fr/tel-00812436.
Abstract:
Cette thèse traite des systèmes paramétrés. Ils modélisent des applications dans divers domaines, comme la robotique ou la calibration. Soit S un système paramétré. Nous cherchons à décrire les ouverts connexes U de l’espace des paramètres tels que S restreint à U admet un nombre constant de solutions réelles. En robotique, nous détectons les positions cuspidales des robots plan 3-RPR. En calibration photographique, nous décrivons le nombre de solutions réalisables du problème Perspective-3- Points. D’un point de vue théorique, nous montrons que sous certaines hypothèses, le calcul de la variété discriminante d'un système paramétré peut se réduire à un calcul de projection. Dans le cas des systèmes quelconques, nous introduisons la décomposition équidimensionnelle régulière. Notre algorithme possède de bonnes performances en pratique et nous permet par ailleurs de déduire un nouvel algorithme pour le calcul du radical d’un idéal.
43
Trystram, Denis. "Quelques résultats de complexité en algorithmique parallèle et systolique." Grenoble INPG, 1988. http://tel.archives-ouvertes.fr/tel-00009202.
Abstract:
L'objet de cette thèse est l'étude de la parallélisation d'algorithmes du calcul scientifique et leur implémentation sur des ordinateurs parallèles à mémoire partagée et sur des réseaux systoliques. Un accent particulier est mis sur l'obtention de résultats de complexité. La thèse est organisée autour d'articles et textes de conférences qui sont analysés et discutés dans une première partie de façon à permettre de replacer les problèmes traités dans leur contexte. Dans le premier chapitre, nous présentons les principaux résultats théoriques concernant l'étude de complexité des algorithmes parallèles, ainsi qu'une description critique de l'architecture de référence, qui est une machine de type MIMD à mémoire partagée. Le chapitre suivant est dédie" à l'ensemble des résultats de complexité concernant les algorithmes de diagonalisation et l'élimination de Gauss, il a pour but d'illustrer la méthodologie. Il existe en tout dix écritures possibles de la méthode de Gauss, qui conduisent principalement à deux grandes classes de graphes de précédente, conceptuellement différents : les graphes de type "glouton" et ceux du type "2 pas". Ces types de graphes se rencontrent d'une manière plus générale dans d'autres problèmes d'algèbre linéaire et même dans certaines méthodes non numériques de la théorie des graphes. Nous développons les résultats de complexité concernant ces deux types de graphes sur les exemples les plus courant (versions kji et kij de Gauss en parallèle), puis nous montrons comment adapter l'étude en prenant en compte t'es temps de communication entre tes processeurs, ce qui rend le modèle théorique plus réaliste. Le chapitre 6 est consacré aux architectures systoliques. Le problème du chemin algébrique permet d'unifier plusieurs problèmes informatiques. Nous présentons un réseau résolvant ce problème en Sn-2 pas sur un réseau de taille n(n+l ). De plus, quelques modifications permettent de calculer des projections en filtrage adaptatif en vu d'obtenir une solution en temps réel pour le traitement numérique des signaux. Avant de conclure, nous présentons des résultats complémentaires de parallélisation effective sur d'autres types d'architectures : l'étude de l'algorithme du gradient conjugué sur des super calculateurs (CRAY-XMP et IBM 3090-VF).
44
Bhouri, Mounir. "Algorithmes adaptatifs parallèles à complexité réduite, application au filtrage adaptatif multi-canal." Paris 5, 1999. http://www.theses.fr/1999PA05S003.
Abstract:
Les algorithmes adaptatifs sont utilisés dans différentes applications de traitement du signal. Ainsi dans les applications telles que l'annulation d'écho acoustique, on utilise des algorithmes robustes et à faible complexité à cause des fortes contraintes imposées (temps réel, signaux complexes). Toutefois, les approches existantes de réduction de la complexité des moindres carrés concernent exclusivement les algorithmes issus du RLS, ils présentent, par conséquent, des problèmes d'instabilité numérique. Nous abordons dans cette thèse, la dérivation d'une nouvelle classe d'algorithmes adaptatifs. Ces algorithmes sont issus de l’algorithme QR-RLS par l'introduction de transformations itératives dans le schéma d'adaptation des matrices de l'algorithme. Ils présentent de ce fait d'excellentes propriétés numériques. Nous développons, également, des implémentations parallèles ainsi que des versions rapides de ces algorithmes. Les simulations dans le contexte de filtrage adaptatif multicanal, pour les applications : annulation d'écho acoustique stéréophonique et égalisation d'un canal numérique, permettent de mettre en évidence un comportement robuste des algorithmes bloc-GR. De même, cette approche s'applique au filtrage adaptatif à réponse impulsionnelle infinie (IIR), nous dérivons alors des algorithmes IIR rapides et efficaces. Finalement, nous définissons un cadre plus général d'algorithmes adaptatifs square-root qui intègre les algorithmes des moindres carrés, les algorithmes du gradient et les algorithmes bloc-QR. Ces derniers sont alors identifiés comme des intermédiaires entre les algorithmes des moindres carrés à convergence rapide et les algorithmes du gradient à convergence robuste.
45
Moataz, Fatima Zahra. "Vers des réseaux optiques efficaces et tolérants aux pannes : complexité et algorithmes." Thesis, Nice, 2015. http://www.theses.fr/2015NICE4077/document.
Abstract:
Nous étudions dans cette thèse des problèmes d’optimisation avec applications dans les réseaux optiques. Les problèmes étudiés sont liés à la tolérance aux pannes et à l’utilisation efficace des ressources. Les résultats obtenus portent principalement sur la complexité de calcul de ces problèmes. La première partie de cette thèse est consacrée aux problèmes de trouver des chemins et des chemins disjoints. La recherche d’un chemin est essentielle dans tout type de réseaux afin d’y établir des connexions et la recherche de chemins disjoints est souvent utilisée pour garantir un certain niveau de protection contre les pannes dans les réseaux. Nous étudions ces problèmes dans des contextes différents. Nous traitons d’abord les problèmes de trouver un chemin et des chemins lien ou nœud- disjoints dans des réseaux avec nœuds asymétriques, c’est-à-dire des nœuds avec restrictions sur leur connectivité interne. Ensuite, nous considérons les réseaux avec des groupes de liens partageant un risque (SRLG) en étoile : ensembles de liens qui peuvent tomber en panne en même temps suite à un événement local. Dans ce type de réseaux, nous examinons le problème de recherche des chemins SRLG-disjoints. La deuxième partie de cette thèse est consacrée au problème de routage et d’allocation de spectre (RSA) dans les réseaux optiques élastiques (EONs). Les EONs sont proposés comme la nouvelle génération des réseaux optiques et ils visent une utilisation plus efficace et flexible des ressources optiques. Le problème RSA est central dans les EONs. Il concerne l’allocation de ressources aux requêtes sous plusieurs contraintesWe study in this thesis optimization problems with application in optical networks. The problems we consider are related to fault-tolerance and efficient resource allocation and the results we obtain are mainly related to the computational complexity of these problems. The first part of this thesis is devoted to finding paths and disjoint paths. Finding a path is crucial in all types of networks in order to set up connections and finding disjoint paths is a common approach used to provide some degree of protection against failures in networks. We study these problems under different settings. We first focus on finding paths and node or link-disjoint paths in networks with asymmetric nodes, which are nodes with restrictions on their internal connectivity. Afterwards, we consider networks with star Shared Risk Link Groups (SRLGs) which are groups of links that might fail simultaneously due to a localized event. In these networks, we investigate the problem of finding SRLG-disjoint paths. The second part of this thesis focuses on the problem of Routing and Spectrum Assignment (RSA) in Elastic Optical Networks (EONs). EONs are proposed as the new generation of optical networks and they aim at an efficient and flexible use of the optical resources. RSA is the key problem in EONs and it deals with allocating resources to requests under multiple constraints. We first study the static version of RSA in tree networks. Afterwards, we examine a dynamic version of RSA in which a non-disruptive spectrum defragmentation technique is used. Finally, we present in the appendix another problem that has been studied during this thesis
46
Abelard, Simon. "Comptage de points de courbes hyperelliptiques en grande caractéristique : algorithmes et complexité." Thesis, Université de Lorraine, 2018. http://www.theses.fr/2018LORR0104/document.
Abstract:
Le comptage de points de courbes algébriques est une primitive essentielle en théorie des nombres, avec des applications en cryptographie, en géométrie arithmétique et pour les codes correcteurs. Dans cette thèse, nous nous intéressons plus particulièrement au cas de courbes hyperelliptiques définies sur des corps finis de grande caractéristique $p$. Dans ce cas de figure, les algorithmes dérivés de ceux de Schoof et Pila sont actuellement les plus adaptés car leur complexité est polynomiale en $\log p$. En revanche, la dépendance en le genre $g$ de la courbe est exponentielle et se fait cruellement sentir même pour $g=3$. Nos contributions consistent principalement à obtenir de nouvelles bornes pour la dépendance en $g$ de l'exposant de $\log p$. Dans le cas de courbes hyperelliptiques, de précédents travaux donnaient une borne quasi-quadratique que nous avons pu ramener à linéaire, et même constante dans le cas très particuliers de familles de courbes dites à multiplication réelle (RM). En genre $3$, nous avons proposé un algorithme inspiré de ceux de Schoof et de Gaudry-Harley-Schost dont la complexité, en général prohibitive, devient très raisonnable dans le cas de courbes RM. Nous avons ainsi pu réaliser des expériences pratiques et compter les points d'une courbe hyperelliptique de genre $3$ pour un $p$ de 64 bitsCounting points on algebraic curves has drawn a lot of attention due to its many applications from number theory and arithmetic geometry to cryptography and coding theory. In this thesis, we focus on counting points on hyperelliptic curves over finite fields of large characteristic $p$. In this setting, the most suitable algorithms are currently those of Schoof and Pila, because their complexities are polynomial in $\log q$. However, their dependency in the genus $g$ of the curve is exponential, and this is already painful even in genus 3. Our contributions mainly consist of establishing new complexity bounds with a smaller dependency in $g$ of the exponent of $\log p$. For hyperelliptic curves, previous work showed that it was quasi-quadratic, and we reduced it to a linear dependency. Restricting to more special families of hyperelliptic curves with explicit real multiplication (RM), we obtained a constant bound for this exponent.In genus 3, we proposed an algorithm based on those of Schoof and Gaudry-Harley-Schost whose complexity is prohibitive in general, but turns out to be reasonable when the input curves have explicit RM. In this more favorable case, we were able to count points on a hyperelliptic curve defined over a 64-bit prime field
47
Abelard, Simon. "Comptage de points de courbes hyperelliptiques en grande caractéristique : algorithmes et complexité." Electronic Thesis or Diss., Université de Lorraine, 2018. http://www.theses.fr/2018LORR0104.
Abstract:
Le comptage de points de courbes algébriques est une primitive essentielle en théorie des nombres, avec des applications en cryptographie, en géométrie arithmétique et pour les codes correcteurs. Dans cette thèse, nous nous intéressons plus particulièrement au cas de courbes hyperelliptiques définies sur des corps finis de grande caractéristique p. Dans ce cas de figure, les algorithmes dérivés de ceux de Schoof et Pila sont actuellement les plus adaptés car leur complexité est polynomiale en \log p. En revanche, la dépendance en le genre g de la courbe est exponentielle et se fait cruellement sentir même pour g=3. Nos contributions consistent principalement à obtenir de nouvelles bornes pour la dépendance en g de l'exposant de \log p. Dans le cas de courbes hyperelliptiques, de précédents travaux donnaient une borne quasi-quadratique que nous avons pu ramener à linéaire, et même constante dans le cas très particuliers de familles de courbes dites à multiplication réelle (RM). En genre 3, nous avons proposé un algorithme inspiré de ceux de Schoof et de Gaudry-Harley-Schost dont la complexité, en général prohibitive, devient très raisonnable dans le cas de courbes RM. Nous avons ainsi pu réaliser des expériences pratiques et compter les points d'une courbe hyperelliptique de genre 3 pour un p de 64 bitsCounting points on algebraic curves has drawn a lot of attention due to its many applications from number theory and arithmetic geometry to cryptography and coding theory. In this thesis, we focus on counting points on hyperelliptic curves over finite fields of large characteristic p. In this setting, the most suitable algorithms are currently those of Schoof and Pila, because their complexities are polynomial in \log q. However, their dependency in the genus g of the curve is exponential, and this is already painful even in genus 3. Our contributions mainly consist of establishing new complexity bounds with a smaller dependency in g of the exponent of \log p. For hyperelliptic curves, previous work showed that it was quasi-quadratic, and we reduced it to a linear dependency. Restricting to more special families of hyperelliptic curves with explicit real multiplication (RM), we obtained a constant bound for this exponent.In genus 3, we proposed an algorithm based on those of Schoof and Gaudry-Harley-Schost whose complexity is prohibitive in general, but turns out to be reasonable when the input curves have explicit RM. In this more favorable case, we were able to count points on a hyperelliptic curve defined over a 64-bit prime field
48
Chapelle, Mathieu. "Décompositions de graphes : quelques limites et obstructions." Phd thesis, Université d'Orléans, 2011. http://tel.archives-ouvertes.fr/tel-00659666.
Abstract:
Les décompositions de graphes, lorsqu'elles sont de petite largeur, sont souvent utilisées pour résoudre plus efficacement des problèmes étant difficiles dans le cas de graphes quelconques. Dans ce travail de thèse, nous nous intéressons aux limites liées à ces décompositions, et à la construction d'obstructions certifiant leur grande largeur. Dans une première partie, nous donnons un algorithme généralisant et unifiant la construction d'obstructions pour différentes largeurs de graphes, en temps XP lorsque paramétré par la largeur considérée. Nous obtenons en particulier le premier algorithme permettant de construire efficacement une obstruction à la largeur arborescente en temps O^{tw+4}. La seconde partie de notre travail porte sur l'étude du problème Ensemble [Sigma,Rho]-Dominant, une généralisation des problèmes de domination sur les graphes et caractérisée par deux ensembles d'entiers Sigma et Rho. Les diverses études de ce problème apparaissant dans la littérature concernent uniquement les cas où le problème est FPT, lorsque paramétré par la largeur arborescente. Nous montrons que ce problème ne l'est pas toujours, et que pour certains cas d'ensembles Sigma et Rho, il devient W[1]-difficile lorsque paramétré par la largeur arborescente. Dans la dernière partie, nous étudions la complexité d'un nouveau problème de coloration appelé k-Coloration Additive, combinant théorie des graphes et théorie des nombres. Nous montrons que ce nouveau problème est NP-complet pour tout k >= 4 fixé, tandis qu'il peut être résolu en temps polynomial sur les arbres pour k quelconque et non fixé.
49
Lavault, Christian. "Algorithmique et complexité distribuées : applications à quelques problèmes fondamentaux de complexité, protocoles distribués à consensus, information globale, problèmes distribués d'élection et de routage." Paris 11, 1987. http://www.theses.fr/1987PA112392.
Abstract:
Présentation d'un cadre général pour l'étude et l'analyse des algorithmes répartis et résolution de plusieurs problèmes de fond relatifs à la complexité dans les systèmes répartis. Développement de divers outils d'analyse en moyenne de la complexite en messages de protocoles généraux à consensus. Résolution par l'analyse mathématique d'un problème ouvert sur les performances comparées des anneaux uni et bidirectionnels pour la complexité en moyenne en messages d'algorithmes d'élection déterministes. Un algorithme probabiliste de construction d'un arbre couvrant sur un système distribué anonyme et quelconque est développé. Deux théorèmes sont proposés qui bornent la faille des messages en fonction de la complexite en messages des algorithmes distribués asynchrones du point de vue de la quantité d'information.
50
Cornet, Alexis. "Algorithmes et résultats de complexité pour des problèmes de graphes avec contraintes additionnelles." Thesis, Université Clermont Auvergne (2017-2020), 2018. http://www.theses.fr/2018CLFAC034/document.
Abstract:
Les problèmes de domination (dominant, dominant indépendant, ...) et de couverture (vertex-cover, arbre de Steiner, ...) sont NP-complets. Pour autant, pour la plupart de ces problèmes, il existe toujours une solution constructible en temps polynomial (potentiellement de valeur objective très mauvaise), ou au moins, il est possible de déterminer facilement (en temps polynomial) l'existence ou non d'une solution. Ces problèmes, initialement issus de situations réelles, sont des modélisations simplistes de ces situations. Nous ajoutons donc des contraintes additionnelles modélisant des contraintes pratiques plausibles : les conflits, des paires d'éléments ne pouvant faire simultanément partie d'une solution (modélisant des incompatibilités diverses), la connexité dans un second graphe (les éléments doivent pouvoir communiquer, et le graphe correspondant à ces liens de communication n'est pas forcément le même) et les obligations, des sous-ensembles d'éléments interdépendants devant être ajoutés simultanément à une solution. Notre but ici n'est pas de modéliser un problème réel précis, mais d'étudier la manière dont ces contraintes modifient la complexité des problèmes étudiés. Nous verrons que dans un grand nombre de cas, déterminer l'existence même d'une solution devient difficile, même sans se préoccuper de leur optimisation. Le problème du firefighter modélise des pompiers tentant de contenir un feu se propageant au tour par tour dans un graphe (potentiellement infini). Nous avons étudié ce problème en ajoutant des contraintes sur le déplacement des pompiers (une vitesse de déplacement limitée entre deux tours). Nous verrons que ces contraintes augmentent en général le nombre de pompiers nécessaires mais ne provoquent pas de changements aussi importants que dans les problèmes précédentsDomination problems (dominating set, independant dominating set, ...) as well as covering problems (vertex-cover, Steiner tree, ...) are NP-complete. However, for most of these problems, it is always possible to construct a (eventually bad) solution in polynomial time, or at least it is possible to determine whether a solution exists. Those problems originally came from industry, but are simplified modelizations of the real life problems. We add additional constraints modeling plausible practical constraints : conflicts which are pairs of elements that cannot apear simultaneously in a solution (to modelize various incompatibilities), connexity in a second graph (elements of the solution must be able to communicate, and the communication links are a second graph), and obligations which are subsets of interdependant vertices which must be added simultaneously in a solution.We don't aim to model a specific real-world problem, but to study how these plausible constraints affect the complexity of the studied problems. We will see that, in many cases, even determining the existence of a solution (regardless of its size) become hard. The firefighter problem models firefighters aiming to contain a fire spreading turn by turn in a (eventually infinite) graph. We studied this problem with the addition of deplacement constraints for the firefighters (a limited moving speed between turns). We will see that, most of the time, this constraint increase the number of firefighters necessary to contain the fire, but does not trigger such major change as constraints studied in the others problems