La biologie de synthèse (BS) est une discipline scientifique qui se propose d'être à la biologie ce que la chimie synthétique est à la chimie analytique. La BS adopte des approches de l'ingénierie et vise à élaborer des systèmes biologiques fonctionnels réalisant des tâches techniques. Elle peut donc être qualifiée de technoscience, au sens où la technique est pour elle un débouché de ses recherches mais également une condition de ses découvertes. La BS ne se laisse cependant pas réduire à sa dimension intentionnelle. Elle est une discipline complexe, tant quant à son épistémologie qu'à son ontologie. Son inscription dans la société n'est pas moins complexe : les technosciences mettent toujours en jeu un grand nombre de dimensions de notre existence collective. Les enjeux éthiques de la BS sont donc majeurs, mais les crispations autour des nouvelles technologies rendent les débats difficiles, les positions se radicalisant entre utopies technophiles et dystopies technophobes.L'objectif de cette étude est de clarifier le contexte éthique, sans le simplifier, et d'apporter des éléments d'analyse des problèmes éthiques de la BS par-delà le simplisme rhétorique et le futurisme,qui minent les débats autour de cette technoscience. Il s'agit donc de se confronter à la complexité de la BS, de sa définition à son épistémologie et son ontologie, en passant par ses dimensions sociales et par le statut des êtres qu'elle produit. Les théories de W.V.O. Quine permettent d'éclairer les aspects épistémologiques et leurs conséquences ontologiques ; la philosophie des processus et des relations de Gilbert Simondon permet quant à elle de décrire la complexité des modes d'existence des êtres biosynthétiques entre contraintes techniques et devenir biologique. / Synthetic biology (SB) is a scientific field that aims at being to biology what syntheticchemistry is to analytic chemistry. SB adopts engineering approaches in order to develop functionalbiological systems carrying out technical tasks. It can thus be described as a technoscience, in the sensethat technic is both an outlet for its research and a material condition for its discoveries.However, SB does not let itself be reduced to that intentional dimension. It is a complexdiscipline, considering both its epistemology and its ontology. How SB is inscribed in society is notless complex: technosciences always involve several dimensions of our collective existence. SB's ethicalissues are thus crucial, but tensions about new technologies make the debates difficult, the positionsbeing often split between technophilic utopias and technophobic dystopias.The objective of this study is to clarify the ethical context without simplifying it, and to giveelements of analysis of the ethical problems in SB beyond the rhetorical simplism and the futurismthat undermine the debates about SB. SB's complexity must thus be confronted, from its definition toits epistemology and ontology, and through its social dimensions as well as the status of the beings itproduces. The theories of W.V.O. Quine enable the understanding of the epistemological aspects andtheir ontological consequences; the process and relations philosophy of Gilbert Simondon enables thedescription of the modes of existence of biosynthetic beings caught between their technical constraintsand their biological development.

On s'intéresse dans cette thèse à la complexité bilinéaire de la multiplication dans toute extension de degré $n$ d'un corps $F_{q}$ à $q$ éléments, qui est étroitement liée au rang de tenseur de la multiplication dans $F_{q^n}$. L'algorithme de type évaluation-interpolation, introduit par D.V et G.V Chudnovsky en 1987, est à la base des techniques algorithmiques fournissant actuellement les meilleures bornes uniformes et asymptotiques de la complexité bilinéaire. Pour obtenir ces meilleures bornes, la stratégie adoptée jusqu'à présent consistait à fixer le degré des places en augmentant le genre du corps de fonctions algébriques.Néanmoins, l'étude de la construction effective associée à ce type de stratégie fut jusqu'à présent négligée en raison d'un obstacle, lié à la construction du point de degré $n$, relevé par Shparlinski, Tsfasman et Vladut en 1992.On présente dans cette thèse une nouvelle stratégie qui consiste à fixer le genre du corps de fonctions algébriques tout en augmentant le degré des places.En appliquant cette stratégie aux corps de fonctions elliptiques, on montre d'une part que le rang de tenseur de la multiplication dans $F_{q^n}$ est quasi-linéaire en $n$, et d'autre part que la construction des algorithmes de multiplications bilinéaires issus de cette stratégie est réalisable en temps polynomial. On montre également comment construire explicitement ces algorithmes sur $F_{q^n}$, en les illustrant par un exemple. Enfin, on établit la première construction asymétrique de l'algorithme de type Chudnovsky. / In this thesis, we focus on the bilinear complexity of multiplication in any degree $n$ extension of the finite field $ F_{q}$, which is closely related to the tensor rank of multiplication in $ F_{q^n} $. The evaluation-interpolation type algorithm introduced by D.V and G.V Chudnovsky in 1987, is the basis of all algorithmic technique providing for now, the lower asymptotic and uniform bounds for the bilinear complexity.So far, the strategy to obtain these lower bounds was to fix the degree of places while increasing the genus of algebraic function fields. However, the study of the effective construction associated with this kind of strategy was until now neglected because of an obstacle related to the construction of a degree $n$ point, identified par Shparlinski, Tsfasman and Vladut in 1992. We present a new strategy which consists in fixing the genus of algebraic function fields while increasing the degree of places. Applying this strategy to the elliptic function fields, we show on the one hand that the tensor rank of multiplication in $ F_{q^n} $ is quasi-linear in $ n $, and on the other hand we prove that the construction of bilinear multiplication algorithms with this strategy is feasible in polynomial time. We also show how to construct explicitly these algorithms over $ F_{q^n} $ for large $n$ by illustrating the construction with an example. Finally, we establish the first asymmetric construction of the Chudnovsky type algorithm.

Ce mémoire propose d’explorer trois « expérience de pensée » décrites dans les œuvres de Diderot, en particulier dans la Promenade du sceptique, l’Encyclopédie et le Rêve de D’Alembert, qui laissent entrevoir par leur forme même l’image de l’activité de la pensée. Le but de cette recherche est de tester la possibilité d’une connaissance historique (prise au sens large) au travers de l’expérience de sens que constituent ces œuvres de Diderot conçues comme « fictions », dans le statut ontologique des objets engagés dans l’expérience et la fonction de l’histoire dans ces expériences. La première partie présente une nature fixe et désordonnée, de laquelle l’observateur fait une expérience spatiale et temporelle dont il rend compte dans un discours analogique qui l’interprète, c’est-à-dire la calque. Diderot critique ainsi le cogito de Descartes, uniquement tourné vers le présent de l’énonciation. L’histoire, comme genre littéraire, est pratiquée de manière subversive pour critiquer l’érudition. La deuxième partie présente la complexité de la structure de l’Encyclopédie et son mode de fonctionnement interne qui rend compte d’une conception historicisée de l’expérience (par accumulation de données et redéfinition processuelle des frontières de la connaissance). L’ouvrage a un rapport ambigu avec l’histoire et plusieurs pratiques historiennes se côtoient. La troisième partie, quant à elle, présente une forme de connaissance historique interne à l’expérience du soi dans la mémoire dont il est constitué et fait signe vers une « métaphysique » de la poésie, conçue dans sa possibilité d’accès à la pensée des liaisons nécessaires du monde. / The purpose of this research is to explore three « experiences of thought » described in Diderot’s oeuvres, in particular in the Promenade du sceptique, the Encyclopédie and the Rêve de D’Alembert, each of which reveal in themselves the image of thought’s activity. It proposes to elucidate a kind of historical knowledge (of history in general) by examining the experience of meaning that constitutes these works of “fiction”, in which one uncovers the ontological status for objects supplied by experience, as well as the role that history plays in these experiences. The first chapter presents nature as both a fixed and disordered, something which the observer interprets and even outlines via an analogical narrative. Diderot also criticizes Descartes’ cogito, which is orientated in particular towards to the present, or the moment of enunciation. History, as a literary genre, is practiced subversively and aimed at criticizing intellectual erudition. The second chapter deals with the complexity of the structure of the Encyclopédie as well as its internal operation, which presents a historicist conception of experience in and through the accumulation of facts and successive redefinitions of the limits of knowledge. His work as a whole has an ambiguous relationship with history and entails several historical practices. The third chapter explicates a form of historical knowledge internal to the experience of the self in the memory that constitutes it, and points to a “metaphysics” of poetry. This poetry opens up the possibility of thinking the necessary relations that make up the world.

Le vieillissement est un facteur de risque des maladies cardiovasculaires. Il est associé à des altérations fonctionnelles et structurelles du système vasculaire.Une étude approfondie du processus de vieillissement et le développement de systèmes d’imagerie et des traitements de données associés deviennent donc une priorité. Par l’analyse d’images de contraste par speckle laser (LSCI), l’objectif de cette thèse est d’étudier l’influence de l’âge sur la micro circulation.Pour ce faire, des données de LSCI ont été acquises sur l’avant-bras de sujets sains jeunes et âgés. A partir de modèles mathématiques, nous avons déterminé la vitesse des érythrocytes de la micro circulation chez les deux groupes de sujets. Par ailleurs, nous avons également mené une étude de la complexité de séries temporelles d’ LSCI s’appuyant sur des mesures d’entropie multi échelle. Nos résultats montrent que : 1) le groupe de sujets plus âgés présente des valeurs de vitesse des globules rouges significativement plus élevées que celles des sujets jeunes à l’hyperémie réactive post-occlusive; 2) les fluctuations des séries temporelles de LSCI dans le groupe des sujets jeunes ont une complexité supérieure à celles du groupe de sujets âgés. Ces modifications observées sur la micro circulation pourraient être attribuées à des modifications du système vasculaire dans son ensemble. La compréhension de ces altérations pourrait conduire à de nouvelles perspectives en matière de prévention et de traitement des pathologies liées à l’âge. / Aging is a primary risk factor for cardiovascular diseases. It is associated with functional and structural alterations in the vascular system. Therefore, a deep study of the aging process and the development of imaging systems and associated processing become of the utmost importance. By processing laser speckle contrast images (LSCI), this PhD work aims at studying the influence of age on microcirculation. In our work, LSCI data were acquired from the skin forearm of healthy subjects, subdivided into two age groups (younger and older). From mathematical models, we determined red blood cells velocity in microcirculation in the two groups of subjects. Moreover, we applied multiscale entropy-based algorithms to LSCI time series in order to study the complexity of microvascular signals. Our main findings are: 1) the older group has significantly higher velocity values than the younger group at post-occlusive reactive hyperaemia; 2) LSCI fluctuations in the younger group have significantly higher complexity than those of the older group. Age-related changes in skin microcirculation can be attributed to alterations in the vascular system as a whole. Understanding these changes in the microcirculatory system may give new insights for prevention and treatment of age-related diseases

Soit un réseau comprenant des lignes de communication qui échouent indépendamment, dans lequel tous ou certains sites, appelés terminaux, doivent être capables de communiquer entre eux. Dans le modèle stochastique statique classique le réseau est représenté par un graphe probabiliste dont les arêtes sont présentes selon des probabilités connues. La mesure de fiabilité classique (CLR) est la probabilité que les terminaux appartiennent à la même composante connexe. Dans plusieurs contextes il est utile d'imposer la condition plus forte que la distance entre deux terminaux quelconques soit bornée supérieurement par un paramètre d. La probabilité que ça se produise est connue comme la fiabilité diamètre-bornée (DCR). Il s'agit d'une extension de la CLR. Les deux problèmes appartiennent à la classe NP-difficile de complexité; le calcul exact n'est possible que pour les instances de taille limitée ou topologies spécifiques. Dans cette thèse, nous contribuons des résultats concernant le problème du calcul et l'estimation de la DCR. Nous étudions la complexité de calcul de cas particuliers, paramétré par le nombre de terminaux, nœuds et le paramètre d. Nous passons en revue des méthodes pour le calcul exact et étudions des topologies particulières pour lesquelles le calcul de la DCR a une complexité polynomiale. Nous introduisons des résultats de base sur le comportement asymptotique de la DCR lorsque le réseau se développe comme un graphe aléatoire. Nous discutons sur l'impact de la contrainte de diamètre dans l'utilisation des techniques de Monte Carlo, et adaptons et testons une famille de méthodes basées sur le conditionnement de l'espace d'échantillonnage en utilisant des structures nommées d-pathsets et d-cutsets. Nous définissons une famille de mesures de performabilité qui généralise la DCR, développons une méthode de Monte Carlo pour l'estimer, et présentons des résultats expérimentaux sur la performance de ces techniques Monte Carlo par rapport é l'approche naïve. Finalement, nous proposons une nouvelle technique qui combine la simulation Monte Carlo et l'interpolation polynomiale pour les mesures de fiabilité. / Consider a communication network whose links fail independently and a set of sites named terminals that must communicate. In the classical stochastic static model the network is represented by a probabilistic graph whose edges occur with known probabilities. The classical reliability (CLR) metric is the probability that the terminals belong to a same connected component. In several contexts it makes sense to impose the stronger condition that the distance between any two terminals does not exceed a parameter d. The probability that this holds is known as the diameter-constrained reliability (DCR). It is an extension of the CLR. Both problems belong to the NP-hard complexity class; they can be solved exactly only for limited-size instances or specific network topologies. In this thesis we contribute a number of results regarding the problem of DCR computation and estimation. We study the computational complexity of particular cases parameterized by the number of terminals, nodes and the parameter d. We survey methods for exact computation and study particular topologies for which computing the DCR has polynomial complexity. We give basic results on the asymptotic behavior of the DCR when the network grows as a random graph. We discuss the impact that the diameter constraint has in the use of Monte Carlo techniques. We adapt and test a family of methods based on conditioning the sampling space using structures named d-pathsets and d-cutsets. We define a family of performability measures that generalizes the DCR, develop a Monte Carlo method for estimating it, and present numerical evidence of how these techniques perform when compared to crude Monte Carlo. Finally we introduce a technique that combines Monte Carlo simulation and polynomial interpolation for reliability metrics.

La cohabitation du créole et du français est décrite ici dans un cadre interlectal et dans une épistémologie de la complexité. En assumant l'implication du chercheur dans son objet d'étude, jamais la posture du militant n'est adoptée afin d'écarter toute surenchère idéologique. Les corpus récoltés auprès de locuteurs réunionnais variés sont traités dans leur globalité, comme dans leurs constituants, refusant d'isoler ou de rejeter le moindre élément qui pourrait contrarier les hypothèses. Des formes syntaxiques particulières, différentes de celles des adultes, se réalisent chez de jeunes locuteurs en situation d'apprentissage ou lors de leur phase d'acquisition du langage, ce qui permettrait de mettre en relief des énoncés qui seraient proches des mécanismes de l'interlangue. L'économie d'une approche glottopolitique complexe a été rejetée. À partir des années 1960, et jusqu'à aujourd'hui, de fortes revendications linguistiques sont portées par des intellectuels et des artistes de talent. Depuis l'époque des premiers travaux universitaires en créolistique, les scientifiques font des propositions d'interventions pédagogiques qui accorderaient une place au créole dans les apprentissages. Pourtant, le monde politique ne s'est pas encore emparé de cette question, la laissant ainsi aux mains de forces glottopolitiques autres, autour de la question de la graphie, de la littérature et de l'école. Nous sommes allé jusqu'à proposer les grandes lignes de ce que pourrait être une didactique du plurilinguisme réunionnais. / The cohabitation of Creole and French is described here in an interlectal framework and in an epistemology of complexity. Assuming the researcher's involvement in his study, the militant's inclination is never adopted so as to brush aside any ideological excess. The corpuses gathered from local native speakers are treated in their entirety, as in their constituents, refusing to set apart or to reject the least element that could act against the hypothesis. Specific syntactic forms, different from the grown ups', are created among young local speakers while learning or through their language acquisition, which would allow to bring out utterances close to interlingual mechanisms. A complex glottopolitical approach hasn't been ruled out. From the 1960s and until today strong linguistic demands have been brought forward by intellectuals and talented artists. From the time of the first academic researches in creolistics, scientists have been suggesting educational interventions that would grant room to creole in language learning. However, politicians haven't tackled this question yet, thus leaving it in the hands of other glottopolitical forces focusing on spelling, literature and school. We've been up to suggesting the broad outline of what could be a teaching of reunionese plurilingualism.

Le premier volet de cette thèse porte sur l'étude de graphes dont les sommets sont colorés. Nous étudions comment la recherche d'ensembles particuliers de sommets est affectée lorsqu'on ajoute la contrainte qu'ils soient tropicaux, c'est à dire contiennent au moins un sommet de chacune des couleurs.Cette contrainte additionnelle tend à fortement augmenter la complexité des problèmes. Par exemple, la recherche d'un plus petit ensemble dominant tropical, et celle d'une plus petite couverture par sommet tropicale, sont APX-complets même restreints aux chemins. La recherche du plus petit sous-graphe connexe tropical d'un graphe est elle NP-complète, même restreinte aux arbres. Cependant, ajouter un contrainte sur le nombre de couleurs permet souvent de réduire la complexité. Par exemple, sans restrictions sur le type de graphes en entrée, la recherche d'un sous-graphe connexe tropical s'effectue en temps polynomial pourvu que le nombre de couleurs reste logarithmique en la taille du graphe. De plus, nous montrons divers résultats structurels qui lient la taille d'un sous-graphe connexe tropical minimum à des paramètres du graphe tels que le nombre de couleurs, le nombre d'arêtes, le degré minimum, ... Dans le second volet, nous étudions des jeux sur des graphes, appelés jeux de défense, où des attaquants ciblent des sommets et des défenseurs protègent des sous-graphes. On s'intéresse à l'existence d'un équilibre de Nash lorsque les défenseurs protègent des chemins de taille au plus p. Lorsque chaque défenseur protège exactement une arête, nous montron<s notamment que déterminer si le jeu pour un graphe G, n défenseurs et k attaquants, admet un équilibre de Nash revient à déterminer si G possède un indépendant dominant de taille inférieure ou égale à k, problème NP-complet dans le cas général.Plus généralement, lorsque les défenseurs protègent des chemins de taille p, l'existence d'un équilibre de Nash dans un jeu avec n défenseurs est liée à la notion de p-indépendant. Un ensemble de sommets est p-indépendant si toutes les paires de sommets sont à distance supérieure à p. Déterminer l'existence d'un p-indépendant maximal de taille inférieure ou égale à k dans un graphe quelconque est NP-complet. Notre algorithme Min2stablemax permet de calculer la taille minimum d'un 2-indépendant maximal dans un arbre. / The first pane of this thesis is on the study of vertex-colored graphs. We look at the tractability of asserting the existence of particular sets of vertices on a graph with the added constraint that the sets must be tropical, i.e. they must contain at least one vertex of each of the colors in the graph.This additional constraint tends to make the problems way less tractable. For instance, finding a minimum tropical dominating set, or a minimum tropical vertex cover, are APX-complete problems even when restricted to paths. Finding the smallest tropical connected subgraph is also NP-complete even when restricted to trees. However, restricting the number of colors will usually make problems more tractable. For instance, finding a connected tropical subgraph (on any graph) can be done in polynomial time as long as the number of colors is logarithmic in the size of the graph. Moreover, we show some structural results that links the size of a minimum connected subgraph to parameters such as the number of colors, the number of edges, the minimum degree…The second pane is on the study of some games on graphs, called defense games, in which multiple attackers target vertices and multiple defenders protect subgraphs.We focus on the existence of a Nash equilibrium when defenders protect paths of size at most p.When each defender protects exactly one edge, we show among other results that the game on a graph G with n defenders and k attackers admits a Nash equilibrium if and only if there exists a dominating set of size at most k in G, which is NP-complete in the general case.Similarly, when each defender protects a path of size at most p, the existence of a Nash equilibrium is linked to the notion of p-independent, i.e. a set of vertices such that every pair of elements of the set is at distance greater than p.Determining the existence of a maximal p-independent of size at most k is NP-complete, but our Min2stablemax algorithm can compute the minimum size of a maximal 2-independent set in a tree.

L'objectif de cette thèse est d'identifier les liens entre les facteurs accidentogènes chez les jeunes conducteurs, en analysant les effets de la complexité de la situation et de l'expérience de conduite sur la charge de travail, la tension, la vigilance et les performances. L'hypothèse générale est que les situations coûteuses, i.e. simples et très complexes, ainsi que le manque d'expérience peuvent mener à une forte dépense énergétique. Ainsi, un haut niveau de tension et un faible niveau de vigilance peuvent provoquer des dégradations de performances à travers la hausse de la charge de travail, caractérisant une surcharge du conducteur. Ceci devrait s'observer plus précocement pour les novices ayant suivi un Apprentissage Traditionnel (AT), puis pour ceux ayant suivi un Apprentissage Anticipé de la Conduite (AAC), puis pour les conducteurs arrivant à la fin du permis probatoire, et enfin pour les plus expérimentés. Une première expérimentation menée sur des données subjectives a confirmé les liens entre les niveaux de charge de travail, de tension et de vigilance en fonction de la complexité de la situation. Une seconde expérimentation menée sur des données subjectives et physiologiques a également confirmé les liens entre les niveaux de charge de travail, de tension et de vigilance, avec une sous-estimation du niveau physiologique par les novices AT. Les résultats établissant les liens entre des caractéristiques de la situation de conduite et des caractéristiques individuelles menant à des accidents de la route pourront permettre d'adapter les actions de sensibilisation et les modules de formations à la conduite. / The aim of this thesis is to identify the links between the accidents factors among young drivers, by analyzing the effects of situation complexity and driving experience on workload, tension, vigilance and performance. The general hypothesis is that costly situations, i.e. simple and very complex, and the lack of experience can lead to a high energy expenditure. Thus, a high level of tension and a low level of vigilance can provoke performance impairments through the increase of workload, which characterizes an overload of the driver. This should be early observed for novices who had a traditional learning, then for early-trained novices, then for drivers arriving at the end of the probationnary period, and then for the most experienced ones. A first experiment, carried out on subjective data, has confirmed the links beween the levels of workload, tenion and vigilance depending on situation complexity. A second experiment, carried out on subjective and physiological data, has also confirmed the links between the levels of workload, tension and vigilance, with an underestimation of the pysiological level by the traditionally trained novices. The results establishing the links between the driving situation's characteristics and the individuals' characteristics leading to road accidents will allow adapting the awareness actions and the modules of driving trainings.

Cette thèse concerne l'élaboration de stratégies de commande prédictive pour certaines classes de systèmes dynamiques continus, discrets et hybrides modélisés par des extensions de réseaux de Petri ad hoc. Pour les systèmes continus et en vue de limiter la complexité de calcul inhérente à la forme standard de la commande prédictive, plusieurs améliorations sont proposées. Celles-ci permettent de surmonter le problème de "hill climbing" caractéristique des trajectoires obtenues avec certains réseaux de Petri. Elles assurent également la possibilité d'implémenter la commande en temps réel en adaptant l'horizon de prédiction pour réduire la complexité algorithmique. Enfin, elles permettent de limiter la sollicitation des actionneurs tout en garantissant la stabilité asymptotique du système commandé. Pour les systèmes discrets temporisés et pour éviter l'exploration exhaustive du graphe d'atteignabilité, une méthode de commande est proposée, basée sur la commande prédictive appliquée à une approximation continue du système discret. Enfin pour les systèmes hybrides, une commande prédictive hybride est développée, inspirée de la commande prédictive continue. Les performances de ces différentes stratégies de commande sont évaluées et comparées avec différentes simulations numériques / This thesis concerns the development of predictive control strategies for some classes of continuous, discrete and hybrid dynamic systems modeled by specific extensions of Petri nets. For continuous systems and in order to limit the computational complexity inherent to the standard form of the predictive control, several improvements are proposed. These improvements allow overcoming the problem of hill climbing that characterizes trajectories obtained with some Petri nets. They also ensure the possibility to implement real-time control by adapting the prediction horizon in order to reduce the algorithmic complexity. Finally, they limit actuators solicitation while ensuring the asymptotic stability of the controlled system. For timed discrete systems and in order to avoid the exhaustive exploration of the reachability graph, a control method is proposed, based on the predictive control applied to a continuous approximation of the discrete system. Finally for hybrid systems, hybrid predictive control is developed, inspired by the continuous predictive control. The performance of these different control strategies are evaluated and compared to different numerical simulations.

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 contraint / The 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