Auswahl der wissenschaftlichen Literatur zum Thema „Algorithmes de complexité paramétrés“
Geben Sie eine Quelle nach APA, MLA, Chicago, Harvard und anderen Zitierweisen an
Inhaltsverzeichnis
Machen Sie sich mit den Listen der aktuellen Artikel, Bücher, Dissertationen, Berichten und anderer wissenschaftlichen Quellen zum Thema "Algorithmes de complexité paramétrés" bekannt.
Neben jedem Werk im Literaturverzeichnis ist die Option "Zur Bibliographie hinzufügen" verfügbar. Nutzen Sie sie, wird Ihre bibliographische Angabe des gewählten Werkes nach der nötigen Zitierweise (APA, MLA, Harvard, Chicago, Vancouver usw.) automatisch gestaltet.
Sie können auch den vollen Text der wissenschaftlichen Publikation im PDF-Format herunterladen und eine Online-Annotation der Arbeit lesen, wenn die relevanten Parameter in den Metadaten verfügbar sind.
Zeitschriftenartikel zum Thema "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, Nr. 2 (11.05.2009): 35–45. http://dx.doi.org/10.7202/029890ar.
Der volle Inhalt der QuelleHancart, 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, Nr. 2 (1994): 239–52. http://dx.doi.org/10.36045/bbms/1103408548.
Der volle Inhalt der QuelleWilss, Wolfram. „Basic Concepts of MT“. Meta 38, Nr. 3 (30.09.2002): 403–13. http://dx.doi.org/10.7202/004608ar.
Der volle Inhalt der QuelleMichaël Thomazo. „Réponse à des requêtes conjonctives en présence de règles existentielles – décidabilité, complexité et algorithmes“. Bulletin 1024, Nr. 6 (Juli 2015): 117–19. http://dx.doi.org/10.48556/sif.1024.6.117.
Der volle Inhalt der QuelleBenmostefa, Soumia, und 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, Nr. 203 (08.04.2014): 11–17. http://dx.doi.org/10.52638/rfpt.2013.25.
Der volle Inhalt der QuelleKouki, Rahim, und Soumaya Derragi. „Interdisciplinarité et difficulté d’apprentissage des méthodes numériques en programmation“. TANGRAM - Revista de Educação Matemática 6, Nr. 3 (30.09.2023): 2–22. http://dx.doi.org/10.30612/tangram.v6i3.16950.
Der volle Inhalt der QuelleBouchafa, Samia. „Décision cumulative pour la vision dynamique des systèmes“. Revue Française de Photogrammétrie et de Télédétection, Nr. 202 (16.04.2014): 2–26. http://dx.doi.org/10.52638/rfpt.2013.48.
Der volle Inhalt der QuelleJaquet, J. M. „Limnologie et télédétection : situation actuelle et développements futurs“. Revue des sciences de l'eau 2, Nr. 4 (12.04.2005): 457–81. http://dx.doi.org/10.7202/705039ar.
Der volle Inhalt der QuellePoreba, Martyna, und 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, Nr. 207 (24.09.2014): 3–17. http://dx.doi.org/10.52638/rfpt.2014.208.
Der volle Inhalt der QuellePauletto, Christian. „Gestion publique, agilité et innovation : l’expérience suisse du dispositif de crédits COVID-19“. Revue Internationale des Sciences Administratives Vol. 90, Nr. 1 (02.04.2024): 109–25. http://dx.doi.org/10.3917/risa.901.0109.
Der volle Inhalt der QuelleDissertationen zum Thema "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.
Der volle Inhalt der QuelleDaligault, 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.
Der volle Inhalt der QuelleBulteau, 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.
Der volle Inhalt der QuelleIn 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.
Der volle Inhalt der QuelleFradin, Julien. „Graphes complexes en biologie : problèmes, algorithmes et évaluations“. Thesis, Nantes, 2018. http://www.theses.fr/2018NANT4093/document.
Der volle Inhalt der QuelleLn 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.
Der volle Inhalt der QuelleSeveral 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.
Der volle Inhalt der QuelleBergé, Pierre. „Algorithmes pour voyager sur un graphe contenant des blocages“. Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLS480.
Der volle Inhalt der QuelleWe 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.
Der volle Inhalt der QuelleThe 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.
Der volle Inhalt der QuelleThe 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
Bücher zum Thema "Algorithmes de complexité paramétrés"
Wilf, Herbert S. Algorithmes et complexité. Paris: Masson, 1989.
Den vollen Inhalt der Quelle findenL, Selman Alan, Hrsg. Structure in complexity theory: Proceedings of the conference held at the University of California, Berkeley, California, June 2-5, 1986. Berlin: Springer-Verlag, 1986.
Den vollen Inhalt der Quelle findenScandinavian 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.
Den vollen Inhalt der Quelle findenScandinavian 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.
Den vollen Inhalt der Quelle finden1955-, Djidjev H., Bŭlgarska akademii͡a︡ na naukite. Center of Informatics and Computer Technology. und International Symposium on Optimal Algorithms (2nd : 1989 : Varna, Bulgaria), Hrsg. Optimal algorithms: International symposium, Varna, Bulgaria, May 29-June 2 1989 proceedings. Berlin: Springer-Verlag, 1989.
Den vollen Inhalt der Quelle findenWilf, Herbert S. Algorithms and complexity. Englewood Cliffs, N.J: Prentice-Hall, 1986.
Den vollen Inhalt der Quelle findenWilf, Herbert S. Algorithms and complexity. 2. Aufl. Natick, Mass: A.K. Peters, 2002.
Den vollen Inhalt der Quelle findenHromkovič, Juraj. Algorithmics for hard problems: Introduction to combinatorial optimization, randomization, approximation, and heuristics, with 71 figures. 2. Aufl. Berlin: Springer-Verlag, 2004.
Den vollen Inhalt der Quelle findenAlgorithmics for hard problems: Introduction to combinatorial optimization, randomization, approximation, and heuristics. 2. Aufl. Berlin: Springer-Verlag, 2003.
Den vollen Inhalt der Quelle findenAlgorithmics for hard problems: Introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001.
Den vollen Inhalt der Quelle findenBuchteile zum Thema "Algorithmes de complexité paramétrés"
KRYSANDER, Mattias, und 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.
Der volle Inhalt der Quelle