Literatura académica sobre el tema "Algorithmes de complexité paramétrés"
Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros
Consulte las listas temáticas de artículos, libros, tesis, actas de conferencias y otras fuentes académicas sobre el tema "Algorithmes de complexité paramétrés".
Junto a cada fuente en la lista de referencias hay un botón "Agregar a la bibliografía". Pulsa este botón, y generaremos automáticamente la referencia bibliográfica para la obra elegida en el estilo de cita que necesites: APA, MLA, Harvard, Vancouver, Chicago, etc.
También puede descargar el texto completo de la publicación académica en formato pdf y leer en línea su resumen siempre que esté disponible en los metadatos.
Artículos de revistas sobre el tema "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, n.º 2 (11 de mayo de 2009): 35–45. http://dx.doi.org/10.7202/029890ar.
Texto completoHancart, 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, n.º 2 (1994): 239–52. http://dx.doi.org/10.36045/bbms/1103408548.
Texto completoWilss, Wolfram. "Basic Concepts of MT". Meta 38, n.º 3 (30 de septiembre de 2002): 403–13. http://dx.doi.org/10.7202/004608ar.
Texto completoMichaël Thomazo. "Réponse à des requêtes conjonctives en présence de règles existentielles – décidabilité, complexité et algorithmes". Bulletin 1024, n.º 6 (julio de 2015): 117–19. http://dx.doi.org/10.48556/sif.1024.6.117.
Texto completoBenmostefa, Soumia y 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, n.º 203 (8 de abril de 2014): 11–17. http://dx.doi.org/10.52638/rfpt.2013.25.
Texto completoKouki, Rahim y Soumaya Derragi. "Interdisciplinarité et difficulté d’apprentissage des méthodes numériques en programmation". TANGRAM - Revista de Educação Matemática 6, n.º 3 (30 de septiembre de 2023): 2–22. http://dx.doi.org/10.30612/tangram.v6i3.16950.
Texto completoBouchafa, Samia. "Décision cumulative pour la vision dynamique des systèmes". Revue Française de Photogrammétrie et de Télédétection, n.º 202 (16 de abril de 2014): 2–26. http://dx.doi.org/10.52638/rfpt.2013.48.
Texto completoJaquet, J. M. "Limnologie et télédétection : situation actuelle et développements futurs". Revue des sciences de l'eau 2, n.º 4 (12 de abril de 2005): 457–81. http://dx.doi.org/10.7202/705039ar.
Texto completoPoreba, Martyna y 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, n.º 207 (24 de septiembre de 2014): 3–17. http://dx.doi.org/10.52638/rfpt.2014.208.
Texto completoPauletto, Christian. "Gestion publique, agilité et innovation : l’expérience suisse du dispositif de crédits COVID-19". Revue Internationale des Sciences Administratives Vol. 90, n.º 1 (2 de abril de 2024): 109–25. http://dx.doi.org/10.3917/risa.901.0109.
Texto completoTesis sobre el tema "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.
Texto completoDaligault, 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.
Texto completoBulteau, 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.
Texto completoIn 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.
Texto completoFradin, Julien. "Graphes complexes en biologie : problèmes, algorithmes et évaluations". Thesis, Nantes, 2018. http://www.theses.fr/2018NANT4093/document.
Texto completoLn 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.
Texto completoSeveral 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.
Texto completoBergé, Pierre. "Algorithmes pour voyager sur un graphe contenant des blocages". Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLS480.
Texto completoWe 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.
Texto completoThe 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.
Texto completoThe 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
Libros sobre el tema "Algorithmes de complexité paramétrés"
Wilf, Herbert S. Algorithmes et complexité. Paris: Masson, 1989.
Buscar texto completoL, 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.
Buscar texto completoScandinavian 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.
Buscar texto completoScandinavian 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.
Buscar texto completo1955-, Djidjev H., Bŭlgarska akademii͡a︡ na naukite. Center of Informatics and Computer Technology. y 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.
Buscar texto completoWilf, Herbert S. Algorithms and complexity. Englewood Cliffs, N.J: Prentice-Hall, 1986.
Buscar texto completoAlgorithms and complexity. 2a ed. Natick, Mass: A.K. Peters, 2002.
Buscar texto completoHromkovič, Juraj. Algorithmics for hard problems: Introduction to combinatorial optimization, randomization, approximation, and heuristics, with 71 figures. 2a ed. Berlin: Springer-Verlag, 2004.
Buscar texto completoAlgorithmics for hard problems: Introduction to combinatorial optimization, randomization, approximation, and heuristics. 2a ed. Berlin: Springer-Verlag, 2003.
Buscar texto completoAlgorithmics for hard problems: Introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001.
Buscar texto completoCapítulos de libros sobre el tema "Algorithmes de complexité paramétrés"
KRYSANDER, Mattias y Erik FRISK. "Analyse structurelle". En Diagnostic et commande à tolérance de fautes 1, 87–114. ISTE Group, 2024. http://dx.doi.org/10.51926/iste.9058.ch2.
Texto completo