Academic literature on the topic 'Algorithmes de complexité paramétrés'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic '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.
Journal articles on the topic "Algorithmes de complexité paramétrés":
Atlan, Henri. "Complexité des systèmes naturels et sous-détermination des théories : une possible limite de la modélisation." Nouvelles perspectives en sciences sociales 4, no. 2 (May 11, 2009): 35–45. http://dx.doi.org/10.7202/029890ar.
Hancart, Christophe. "Des bornes exactes de la complexité des algorithmes séquentiels de recherche d'un motif." Bulletin of the Belgian Mathematical Society - Simon Stevin 1, no. 2 (1994): 239–52. http://dx.doi.org/10.36045/bbms/1103408548.
Wilss, Wolfram. "Basic Concepts of MT." Meta 38, no. 3 (September 30, 2002): 403–13. http://dx.doi.org/10.7202/004608ar.
Michaël Thomazo. "Réponse à des requêtes conjonctives en présence de règles existentielles – décidabilité, complexité et algorithmes." Bulletin 1024, no. 6 (July 2015): 117–19. http://dx.doi.org/10.48556/sif.1024.6.117.
Benmostefa, Soumia, and Hadria Fizazi. "Classification automatique des images satellitaires optimisée par l'algorithme des chauves-souris." Revue Française de Photogrammétrie et de Télédétection, no. 203 (April 8, 2014): 11–17. http://dx.doi.org/10.52638/rfpt.2013.25.
Kouki, Rahim, and Soumaya Derragi. "Interdisciplinarité et difficulté d’apprentissage des méthodes numériques en programmation." TANGRAM - Revista de Educação Matemática 6, no. 3 (September 30, 2023): 2–22. http://dx.doi.org/10.30612/tangram.v6i3.16950.
Bouchafa, Samia. "Décision cumulative pour la vision dynamique des systèmes." Revue Française de Photogrammétrie et de Télédétection, no. 202 (April 16, 2014): 2–26. http://dx.doi.org/10.52638/rfpt.2013.48.
Jaquet, J. M. "Limnologie et télédétection : situation actuelle et développements futurs." Revue des sciences de l'eau 2, no. 4 (April 12, 2005): 457–81. http://dx.doi.org/10.7202/705039ar.
Poreba, Martyna, and François Goulette. "Recalage rigide de relevé laser par mise en correspondance robuste basée sur des segments." Revue Française de Photogrammétrie et de Télédétection, no. 207 (September 24, 2014): 3–17. http://dx.doi.org/10.52638/rfpt.2014.208.
Pauletto, Christian. "Gestion publique, agilité et innovation : l’expérience suisse du dispositif de crédits COVID-19." Revue Internationale des Sciences Administratives Vol. 90, no. 1 (April 2, 2024): 109–25. http://dx.doi.org/10.3917/risa.901.0109.
Dissertations / Theses on the topic "Algorithmes de complexité paramétrés":
Guillemot, Sylvain. "Approches combinatoires pour le consensus d'arbres et de séquences." Phd thesis, Montpellier 2, 2008. http://www.theses.fr/2008MON20234.
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.
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.
In 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
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.
Fradin, Julien. "Graphes complexes en biologie : problèmes, algorithmes et évaluations." Thesis, Nantes, 2018. http://www.theses.fr/2018NANT4093/document.
Ln 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
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.
Several 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
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.
Bergé, Pierre. "Algorithmes pour voyager sur un graphe contenant des blocages." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLS480.
We 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
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.
The 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
Khosravian, Ghadikolaei Mehdi. "Extension of NP Optimization Problems." Thesis, Paris Sciences et Lettres (ComUE), 2019. http://www.theses.fr/2019PSLED064.
The 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
Books on the topic "Algorithmes de complexité paramétrés":
Wilf, Herbert S. Algorithmes et complexité. Paris: Masson, 1989.
L, Selman Alan, ed. Structure in complexity theory: Proceedings of the conference held at the University of California, Berkeley, California, June 2-5, 1986. Berlin: Springer-Verlag, 1986.
Scandinavian Workshop on Algorithm Theory (7th 2000 Bergen, Norway). Algorithm theory - SWAT 2000: 7th Scandinavian Workshop on Algorithm Theory, Stockholm, Sweden, July 5-7, 2000 ; proceedings. Berlin: Springer, 2000.
Scandinavian Workshop on Algorithm Theory (7th 2000 Bergen, Norway). Algorithm theory-- SWAT 2000: 7th Scandinavian Workshop on Algorithm Theory, Bergen, Norway, July 5-7, 2000 : proceedings. Berlin: Springer, 2000.
1955-, Djidjev H., Bŭlgarska akademii͡a︡ na naukite. Center of Informatics and Computer Technology., and International Symposium on Optimal Algorithms (2nd : 1989 : Varna, Bulgaria), eds. Optimal algorithms: International symposium, Varna, Bulgaria, May 29-June 2 1989 proceedings. Berlin: Springer-Verlag, 1989.
Wilf, Herbert S. Algorithms and complexity. Englewood Cliffs, N.J: Prentice-Hall, 1986.
Wilf, Herbert S. Algorithms and complexity. 2nd ed. Natick, Mass: A.K. Peters, 2002.
Hromkovič, Juraj. Algorithmics for hard problems: Introduction to combinatorial optimization, randomization, approximation, and heuristics, with 71 figures. 2nd ed. Berlin: Springer-Verlag, 2004.
Hromkovič, Juraj. Algorithmics for hard problems: Introduction to combinatorial optimization, randomization, approximation, and heuristics. 2nd ed. Berlin: Springer-Verlag, 2003.
Hromkovič, Juraj. Algorithmics for hard problems: Introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001.
Book chapters on the topic "Algorithmes de complexité paramétrés":
KRYSANDER, Mattias, and Erik FRISK. "Analyse structurelle." In Diagnostic et commande à tolérance de fautes 1, 87–114. ISTE Group, 2024. http://dx.doi.org/10.51926/iste.9058.ch2.