Log in

Relevant bibliographies by topics / Algorithmes de complexité paramétrés / Dissertations / Theses

To see the other types of publications on this topic, follow the link: Algorithmes de complexité paramétrés.

Dissertations / Theses on the topic 'Algorithmes de complexité paramétrés'

Author: Grafiati

Published: 7 July 2024

Last updated: 31 July 2025

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

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.

Full text

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 su

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

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

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

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 dista

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

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 su

APA, Harvard, Vancouver, ISO, and other styles

5

Fradin, Julien. "Graphes complexes en biologie : problèmes, algorithmes et évaluations." Thesis, Nantes, 2018. http://www.theses.fr/2018NANT4093/document.

Full text

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, qu

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

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

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

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 d

APA, Harvard, Vancouver, ISO, and other styles

8

Bergé, Pierre. "Algorithmes pour voyager sur un graphe contenant des blocages." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLS480.

Full text

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 s

APA, Harvard, Vancouver, ISO, and other styles

9

Khosravian, Ghadikolaei Mehdi. "Extension of NP Optimization Problems." Thesis, Paris Sciences et Lettres (ComUE), 2019. http://www.theses.fr/2019PSLED064.

Full text

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

APA, Harvard, Vancouver, ISO, and other styles

10

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.

Full text

Abstract:

La théorie de la NP-complétude nous apprend que pour un certain nombre de problèmes d'optimisation, il est vain d'espérer un algorithme efficace calculant une solution optimale. Partant de ce constat, un moyen pour contourner cet obstacle est de réaliser un compromis sur chacun de ces critères, engendrant deux approches devenues classiques. La première, appelée approximation polynomiale, consiste à développer des algorithmes efficaces et retournant une solution proche d'une solution optimale. La seconde, appelée complexité paramétrée, consiste à développer des algorithmes retou

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

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, CO

APA, Harvard, Vancouver, ISO, and other styles

12

Watel, Dimitri. "Approximation de l'arborescence de Steiner." Thesis, Versailles-St Quentin en Yvelines, 2014. http://www.theses.fr/2014VERS0025/document.

Full text

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

APA, Harvard, Vancouver, ISO, and other styles

13

Garnero, Valentin. "(Méta)-noyaux constructifs et linéaires dans les graphes peu denses." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT328/document.

Full text

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

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

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 tran

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

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

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

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 notam

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

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

APA, Harvard, Vancouver, ISO, and other styles

18

Déprés, Hugues. "Twin-width : lower bounds and approximation algorithms." Electronic Thesis or Diss., Lyon, École normale supérieure, 2024. http://www.theses.fr/2024ENSL0011.

Full text

Abstract:

Cette thèse porte sur l'étude de nouvelles décomposition de graphes, notamment la twin-width qui est un nouveau paramètre permettant de mesurer la complexité d'un graphe, défini en 2020 par Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant et Édouard Bonnet. C’est un paramètre qui s’est révélé être important dans la compréhension de la structure des graphes et de leurs algorithmes. Dans cette thèse, on montre que, décider si la twin-width d’un graphe est au plus 4, est un problème NP-complet. On réussit en effet à contrôler suffisamment la séquence de contraction pour simuler un circuit booléen.

APA, Harvard, Vancouver, ISO, and other styles

19

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.

Full text

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 tran

APA, Harvard, Vancouver, ISO, and other styles

20

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.

Full text

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 distan

APA, Harvard, Vancouver, ISO, and other styles

21

Mhalla, Mehdi. "Informatique quantique, algorithmes et complexité." Grenoble INPG, 2004. http://www.theses.fr/2004INPG0113.

Full text

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é

APA, Harvard, Vancouver, ISO, and other styles

22

Cheikh-Alili, Fahima. "Composition de services: algorithmes et complexité." Phd thesis, Université Paul Sabatier - Toulouse III, 2009. http://tel.archives-ouvertes.fr/tel-00459114.

Full text

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é

APA, Harvard, Vancouver, ISO, and other styles

23

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.

Full text

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.

APA, Harvard, Vancouver, ISO, and other styles

24

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.

Full text

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. T

APA, Harvard, Vancouver, ISO, and other styles

25

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Dehry, Nicolas. "Multicoupes et sous-graphes induits : complexité et algorithmes." Paris, CNAM, 2008. http://www.theses.fr/2008CNAM0598.

Full text

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 partic

APA, Harvard, Vancouver, ISO, and other styles

27

Markey, Nicolas. "Logiques temporelles pour la vérification : expressivité, complexité, algorithmes." Orléans, 2003. http://www.theses.fr/2003ORLE2004.

Full text

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 checkin

APA, Harvard, Vancouver, ISO, and other styles

28

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.

Full text

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

APA, Harvard, Vancouver, ISO, and other styles

29

Romero-Meléndez, Cutberto. "Complexité métrique sous-riemannienne." Dijon, 2004. http://www.theses.fr/2004DIJOS028.

Full text

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 e

APA, Harvard, Vancouver, ISO, and other styles

30

Nicolas, François. "Alignement, séquence, consensus, recherche de similarités : complexité et approximabilité." Montpellier 2, 2005. http://www.theses.fr/2005MON20179.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Hadjiat, Malika. "Problèmes de tension sur un graphe : algorithmes et complexité." Aix-Marseille 2, 1996. http://www.theses.fr/1996AIX22061.

Full text

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 p

APA, Harvard, Vancouver, ISO, and other styles

32

Covanov, Svyatoslav. "Algorithmes de multiplication : complexité bilinéaire et méthodes asymptotiquement rapides." Thesis, Université de Lorraine, 2018. http://www.theses.fr/2018LORR0057/document.

Full text

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

APA, Harvard, Vancouver, ISO, and other styles

33

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.

Full text

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

APA, Harvard, Vancouver, ISO, and other styles

34

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.

Full text

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

APA, Harvard, Vancouver, ISO, and other styles

35

Revol, Nathalie. "Complexité de l'évaluation parallèle de circuits arithmétiques." Grenoble INPG, 1994. http://tel.archives-ouvertes.fr/tel-00005109.

Full text

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

APA, Harvard, Vancouver, ISO, and other styles

36

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.

Full text

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 calc

APA, Harvard, Vancouver, ISO, and other styles

37

Atig, Mohamed Faouzi. "Vérification de Programmes Concurrents : Décidabilité et Complexité." Paris 7, 2010. http://www.theses.fr/2010PA077066.

Full text

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 devien

APA, Harvard, Vancouver, ISO, and other styles

38

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.

Full text

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

APA, Harvard, Vancouver, ISO, and other styles

39

Faik, Taoufik. "La b-continuite des b-colorations : complexité, propriétés structurelles et algorithmes." Paris 11, 2005. http://www.theses.fr/2005PA112047.

Full text

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 (p<br>THE B-COLORING OF A

APA, Harvard, Vancouver, ISO, and other styles

40

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.

Full text

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 distinct

APA, Harvard, Vancouver, ISO, and other styles

41

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.

Full text

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 so

APA, Harvard, Vancouver, ISO, and other styles

42

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.

Full text

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écodeu

APA, Harvard, Vancouver, ISO, and other styles

43

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.

Full text

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é

APA, Harvard, Vancouver, ISO, and other styles

44

Trystram, Denis. "Quelques résultats de complexité en algorithmique parallèle et systolique." Grenoble INPG, 1988. http://tel.archives-ouvertes.fr/tel-00009202.

Full text

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 para

APA, Harvard, Vancouver, ISO, and other styles

45

Bhouri, Mounir. "Algorithmes adaptatifs parallèles à complexité réduite, application au filtrage adaptatif multi-canal." Paris 5, 1999. http://www.theses.fr/1999PA05S003.

Full text

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 adaptat

APA, Harvard, Vancouver, ISO, and other styles

46

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.

Full text

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

APA, Harvard, Vancouver, ISO, and other styles

47

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.

Full text

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 cruel

APA, Harvard, Vancouver, ISO, and other styles

48

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.

Full text

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

APA, Harvard, Vancouver, ISO, and other styles

49

Chapelle, Mathieu. "Décompositions de graphes : quelques limites et obstructions." Phd thesis, Université d'Orléans, 2011. http://tel.archives-ouvertes.fr/tel-00659666.

Full text

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

APA, Harvard, Vancouver, ISO, and other styles

50

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.

Full text

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

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!