Les travaux de cette thèse s'inscrivent dans le contexte de la coordination des décisions de planification survenant dans une chaîne logistique à deux acteurs: un fournisseur et un producteur souhaitant chacun diminuer leur propre coût. Les décisions de planification prises de manière indépendante par chaque acteur peuvent amener à une mauvaise performance de la chaîne logistique en terme de coûts, d'où la nécessité d'une coordination. Nous étudions des mécanismes de partage de coûts entre des acteurs en définissant des stratégies de coordination entre les acteurs par la mise en place de contrats. Nous considérons le cas où le producteur (resp. fournisseur) peut imposer son plan de production optimal au fournisseur (resp. distributeur). Différentes hypothèses de partage de coûts, ainsi que la problématique d'asymétrie d'information sont prises en compte dans ces travaux. Nous effectuons également des analyses expérimentales mesurant la diminution du coût de la chaîne logistique obtenue quand les acteurs coopèrent. Ce contexte nous amène à étudier de nouveaux problèmes de lot-sizing pour lesquels nous proposons une analyse de complexité et des algorithmes de programmation dynamique pour les résoudre. Nous proposons également une étude théorique des problèmes de lot-sizing à deux niveaux avec une capacité de stockage limitée. / This thesis focus on the coordination of planning decisions in a two-level supply chain composed of one supplier and one retailer. Each actor wants to minimize his own cost. The planning decisions independently took by the actors can lead to a poor performance in terms of costs, hence the necessity of coordination. We study cost sharing mechanisms between the actors by designing contracts. In this work, we consider the case where the retailer (resp. supplier) can impose his optimal production plan to the supplier (resp. retailer). Different cost sharing hypothesis, as well as the asymmetric information problem are taking into account in this thesis. We also perform an experimental analysis in order to evaluate the decrease of the supply chain cost obtained when the actors cooperate. This context leads us to study new lot-sizing problems for which we propose a complexity analysis and dynamic programming algorithms in order to solve them. We also propose a theoritical study of two-level lot-sizing problems with inventory bounds.

Cette thèse porte sur des minorants pour des mesures de complexité liées à des sous-classes de la classe P de langages pouvant être décidés en temps polynomial par des machines de Turing. Nous considérons des modèles de calcul non uniformes tels que les programmes sur monoïdes et les programmes de branchement. Notre première contribution est un traitement abstrait de la méthode de Nečiporuk pour prouver des minorants, indépendamment de toute mesure de complexité spécifique. Cette méthode donne toujours les meilleurs minorants connus pour des mesures telles que la taille des programmes de branchements déterministes et non déterministes ou des formules avec des opérateurs booléens binaires arbitraires ; nous donnons une formulation abstraite de la méthode et utilisons ce cadre pour démontrer des limites au meilleur minorant obtenable en utilisant cette méthode pour plusieurs mesures de complexité. Par là, nous confirmons, dans ce cadre légèrement plus général, des résultats de limitation précédemment connus et exhibons de nouveaux résultats de limitation pour des mesures de complexité auxquelles la méthode de Nečiporuk n'avait jamais été appliquée. Notre seconde contribution est une meilleure compréhension de la puissance calculatoire des programmes sur monoïdes issus de petites variétés de monoïdes finis. Les programmes sur monoïdes furent introduits à la fin des années 1980 par Barrington et Thérien pour généraliser la reconnaissance par morphismes et ainsi obtenir une caractérisation en termes de semi-groupes finis de NC^1 et de ses sous-classes. Étant donné une variété V de monoïdes finis, on considère la classe P(V) de langages reconnus par une suite de programmes de longueur polynomiale sur un monoïde de V : lorsque l'on fait varier V parmi toutes les variétés de monoïdes finis, on obtient différentes sous-classes de NC^1, par exemple AC^0, ACC^0 et NC^1 quand V est respectivement la variété de tous les monoïdes apériodiques finis, résolubles finis et finis. Nous introduisons une nouvelle notion de docilité pour les variétés de monoïdes finis, renforçant une notion de Péladeau. L'intérêt principal de cette notion est que quand une variété V de monoïdes finis est docile, nous avons que P(V) contient seulement des langages réguliers qui sont quasi reconnus par morphisme par des monoïdes de V. De nombreuses questions ouvertes à propos de la structure interne de NC^1 seraient réglées en montrant qu'une variété de monoïdes finis appropriée est docile, et, dans cette thèse, nous débutons modestement une étude exhaustive de quelles variétés de monoïdes finis sont dociles. Plus précisément, nous portons notre attention sur deux petites variétés de monoïdes apériodiques finis bien connues : DA et J. D'une part, nous montrons que DA est docile en utilisant des arguments de théorie des semi-groupes finis. Cela nous permet de dériver une caractérisation algébrique exacte de la classe des langages réguliers dans P(DA). D'autre part, nous montrons que J n'est pas docile. Pour faire cela, nous présentons une astuce par laquelle des programmes sur monoïdes de J peuvent reconnaître beaucoup plus de langages réguliers que seulement ceux qui sont quasi reconnus par morphisme par des monoïdes de J. Cela nous amène à conjecturer une caractérisation algébrique exacte de la classe de langages réguliers dans P(J), et nous exposons quelques résultats partiels appuyant cette conjecture. Pour chacune des variétés DA et J, nous exhibons également une hiérarchie basée sur la longueur des programmes à l'intérieur de la classe des langages reconnus par programmes sur monoïdes de la variété, améliorant par là les résultats de Tesson et Thérien sur la propriété de longueur polynomiale pour les monoïdes de ces variétés. / This thesis deals with lower bounds for complexity measures related to subclasses of the class P of languages that can be decided by Turing machines in polynomial time. We consider non-uniform computational models like programs over monoids and branching programs.Our first contribution is an abstract, measure-independent treatment of Nečiporuk's method for proving lower bounds. This method still gives the best lower bounds known on measures such as the size of deterministic and non-deterministic branching programs or formulae{} with arbitrary binary Boolean operators; we give an abstract formulation of the method and use this framework to prove limits on the best lower bounds obtainable using this method for several complexity measures. We thereby confirm previously known limitation results in this slightly more general framework and showcase new limitation results for complexity measures to which Nečiporuk's method had never been applied.Our second contribution is a better understanding of the computational power of programs over monoids taken from small varieties of finite monoids. Programs over monoids were introduced in the late 1980s by Barrington and Thérien as a way to generalise recognition by morphisms so as to obtain a finite-semigroup-theoretic characterisation of NC^1 and its subclasses. Given a variety V of finite monoids, one considers the class P(V) of languages recognised by a sequence of polynomial-length programs over a monoid from V: as V ranges over all varieties of finite monoids, one obtains different subclasses of NC^1, for instance AC^0, ACC^0 and NC^1 when V respectively is the variety of all finite aperiodic, finite solvable and finite monoids. We introduce a new notion of tameness for varieties of finite monoids, strengthening a notion of Péladeau. The main interest of this notion is that when a variety V of finite monoids is tame, we have that P(V) does only contain regular languages that are quasi morphism-recognised by monoids from V. Many open questions about the internal structure of NC^1 would be settled by showing that some appropriate variety of finite monoids is tame, and, in this thesis, we modestly start an exhaustive study of which varieties of finite monoids are tame. More precisely, we focus on two well-known small varieties of finite aperiodic monoids: DA and J. On the one hand, we show that DA is tame using finite-semigroup-theoretic arguments. This allows us to derive an exact algebraic characterisation of the class of regular languages in P(DA). On the other hand, we show that J is not tame. To do this, we present a trick by which programs over monoids from J can recognise much more regular languages than only those that are quasi morphism-recognised by monoids from J. This brings us to conjecture an exact algebraic characterisation of the class of regular languages in P(J), and we lay out some partial results that support this conjecture. For each of the varieties DA and J, we also exhibit a program-length-based hierarchy within the class of languages recognised by programs over monoids from the variety, refining Tesson and Thérien's results on the polynomial-length property for monoids from those varieties.

Dans cette thèse nous appliquons des techniques provenant du calcul formel et de la théorie des langages afin d'améliorer les opérations élémentaires dans certaines tours de corps finis. Nous appliquons notre construction au problème du calcul d'isogénies entre courbes elliptiques et obtenons une variante plus rapide (à la fois en théorie et en pratique) de l'algorithme de Couveignes. Le document est divisé en quatre parties. Dans la partie I nous faisons des rappels d'algèbre et de théorie de la complexité. La partie II traite du principe de transposition : nous généralisons des idées de Bostan, Schost et Lecerf et nous montrons qu'il est possible de transposer automatiquement des programmes sans pertes en complexité-temps et avec une petite perte en complexité-espace. La partie III combine les résultats sur le principe de transposition avec des techniques classiques en théorie de l'élimination ; nous appliquons ces idées pour obtenir des algorithmes asymptotiquement optimaux pour l'arithmétique des tours d'Artin-Schreier de corps finis. Nous décrivons aussi une implantation de ces algorithmes. Enfin, dans la partie IV nous utilisons les résultats précédents afin d'accélérer l'algorithme de Couveignes et de comparer le résultat avec les autres algorithmes pour le calcul d'isogénies qui font l'état de l'art. Nous présentons aussi une nouvelle généralisation de l'algorithme de Couveignes qui calcule des isogénies de degré inconnu.

.

Les gènes sont les parties du génome qui codent pour les protéines. Les gènes d’une ou plusieurs espèces peuvent être regroupés en "familles", en fonction de leur similarité de séquence. Cependant, pour connaître les relations fonctionnelles entre ces copies de gènes, la similarité de séquence ne suffit pas. Pour cela, il est important d’étudier l’évolution d’une famille par duplications et pertes afin de pouvoir distinguer entre gènes orthologues, des copies ayant évolué par spéciation et susceptibles d’avoir conservé une fonction commune, et gènes paralogues, des copies ayant évolué par duplication qui ont probablement développé des nouvelles fonctions. Étant donnée une famille de gènes présents dans n espèces différentes, un arbre de gènes (obtenu par une méthode phylogénétique classique), et un arbre phylogénétique pour les n espèces, la "réconciliation" est l’approche la plus courante permettant d’inférer une histoire d’évolution de cette famille par duplications, spéciations et pertes. Le degré de confiance accordé à l’histoire inférée est directement relié au degré de confiance accordé à l’arbre de gènes lui-même. Il est donc important de disposer d’une méthode préliminaire de correction d’arbres de gènes. Ce travail introduit une méthodologie permettant de "corriger" un arbre de gènes : supprimer le minimum de feuilles "mal placées" afin d’obtenir un arbre dont les sommets de duplications (inférés par la réconciliation) sont tous des sommets de "duplications apparentes" et obtenir ainsi un arbre de gènes en "accord" avec la phylogénie des espèces. J’introduis un algorithme exact pour des arbres d’une certaine classe, et une heuristique pour le cas général. / Genes are segments of genomes that code for proteins. Genes of one or more species can be grouped into gene families based on their sequence similarity. In order to determine functional relationships among these multiple gene copies of a family, sequence homology is insufficient as no direct information on the evolution of the gene family by duplication, speciation and loss can be inferred directly from a family of homologous genes. And it is precisely this information that allows us to distinguish between orthologous gene copies, that have evolved by speciation and are more likely to preserve the same function and paralogous gene copies that have evolved by duplication and usually acquire new functions. For a given gene family contained within n species, a gene tree (inferred by typical phylogenetic methods) and a phylogenetic tree of the considered species, reconciliation between the gene tree and the species tree is the most commonly used approach to infer a duplication, speciation and loss history for the gene family. The main criticism towards reconciliation methods is that the inferred duplication and loss history for a gene family is strongly dependent on the gene tree considered for this family. Indeed, just a few misplaced leaves in the gene tree can lead to a completely different history, possibly with significantly more duplications and losses. It is therefore important to have a preliminary method for "correcting” the gene tree, i.e. removing potentially misplaced branches. N. El-Mabrouk and C. Chauve introduced "non-apparent duplications" as nodes that are likely to result from the misplacement of one leaf in the gene tree. Simply put, such a node indicates that one or more triplets contradict the phylogeny given by the species tree. In this work, the problem of eliminating non-apparent duplications from a given gene tree by a minimum number of leaf removals is considered. Depending on the disposition of this type of nodes in the gene tree, the algorithm introduced leads to an O(nlogn) performance and an optimal solution in a best case scenario . The general case however is solved using an heuristic method.

L'alignement de macromolécules biologiques comme les protéines, l'ADN ou encore l'ARN est une problématique biologique et bio-informatique qui a pour but de révéler une partie des mystères du fonctionnement des cellules, constituants des êtres vivants. Les ARN non-codant sont des macromolécules intervenant dans le métabolisme de tout être vivant et les deux problématiques majeurs les concernant sont: la prédiction de leur structure pour mieux comprendre leur fonctionnement et leur détection dans des bases de données ou des génomes. L'une des approches: l'alignement structure-séquence d'ARN, répond à ces deux problématiques. Le problème d'alignement structure-séquence consiste à aligner une structure connue d'un premier ARN avec la séquence d'un deuxième ARN.La structure est représentée sous la forme d'un graphe ou de façon équivalente sous la forme d'une séquence arc-annotées et la séquence représente la suite des nucléotides de l'ARN.Pour résoudre ce problème, nous cherchons à optimiser l'alignement selon une fonction de coût. C'est donc un problème d'optimisation, qui malheureusement se révèle NP-Difficile.En conséquence différents travaux définissent des classes d'instances réduites pour lesquelles ils proposent des algorithmes spécifiques mais à complexités polynomiales.Les travaux de ma thèse unifient et la généralisent les approches précédentes par la construction d'un algorithme à complexité paramétrée non spécifique à une classe d'instances. En utilisant cet algorithme, il est possible de résoudre le problème d'alignement structure-séquence pour toutes les instances possibles, et aussi efficacement que les précédentes approches sur leur domaine de résolution respectif. Cet algorithme utilise une technique empruntée à la théorie des graphes: la décomposition arborescente, c'est-à-dire qu'il transforme la structure donnée en une décomposition arborescente et c'est ensuite cette décomposition qui est alignée avec la séquence donnée. L'alignement entre une décomposition arborescente et une séquence se fait par programmation dynamique.Sa mise en place a nécessité une reformulation du problème ainsi qu'une modification importante de l'utilisation classique de la programmation dynamique pour les décompositions arborescentes. Au final, cela conduit à un algorithme paramétré dont le paramètre est entièrement lié à la décomposition arborescente. La construction des décompositions arborescentes pour lesquelles l'alignement s'effectuera plus le efficacement possible est malheureusement un problème lui aussi NP-Difficile. Néanmoins, nous avons créé une heuristique de construction de décompositions adaptée aux structures d'ARN.Nous avons alors défini des nouvelles classes de structures pour lesquelles notre algorithme (décomposition et alignement) possède une faible complexité. Ces classes incluent notamment toutes les autres classes précédemment définies et la complexité de notre algorithme est au moins aussi faible que celles des algorithmes spécifiques sur leurs classes de structures respectives. Ces classes de structures représentent la majorité des structures connues et contiennent de nombreux éléments importants jusqu'alors non pris en compte (tel que les motifs tertiaires d'ARN). Le problème de l'alignement structure-séquence tente de répondre aux problématiques de prédictions de structures et de recherche d'ARN. Néanmoins, la qualité des résultats obtenus par sa résolution dépendent de la fonction de coût utilisée. Durant ma thèse j'ai commencé la mise place de la construction par apprentissage d'une nouvelle fonction de coût, adaptée aux nouvelles classes de structures que nous avons défini. Enfin de par la nature de l'algorithme, le travail réalisé permet des améliorations non négligeables, en terme de qualité des résultats et de rapidité de calcul comme la recherche de solution sous-optimales ou l'utilisation de l'algorithme au sein d'heuristiques dérivées d'heuristiques classiques. / The alignment of biological macromolecules such as proteins, DNA or RNA is a biological and bio-informatics problematic which aims to reveal some of the mysteries of how cells works. The non-coding RNA are involved in the metabolism of all living beings. The two major issues concerning them are: the prediction of their structure to better understand their function and their detection in databases or genomes. One approach, the structure-sequence alignment of RNA, addresses these two issues. The work done during my thesis provides some constructive elements on this problem and led me to call the graph algorithmic for its resolution. The alignment problem is to align a structure of a first RNA with the sequence of a second RNA. The structure on the first RNA is represented as a graph or equivalently as an arc-annotated sequence and the sequence represents the nucleotide sequence of the second RNA.To solve this problem, we aim to compute a minimal cost alignment, according to a given cost function. So, this is an optimization problem, which turns out to be NP-hard.Accordingly, different works define several reduced structure classes for which they propose specific algorithms but with polynomial complexity. The work of my thesis unifies and generalizes previous approaches by the construction of a unique (not class specific) parameterized algorithm. Using this algorithm, it is possible to solve the problem of structure-sequence alignment for all possible instances, and as effectively as previous approaches in their respective field of resolution.This algorithm uses a technique from graph theory: the tree decomposition, that is to say, it transforms the given structure into a tree-decomposition and the decomposition is then aligned with the sequence. The alignment between a tree-decomposition and a sequence is done by dynamic programming. Its implementation requires a reformulation of the problem as well as a substantial modifications to the conventional use of dynamic programming for tree decompositions. This leads to an algorithm whose parameter is entirely related to the tree-decomposition.The construction of tree decompositions for which the alignment is the most effective is unfortunately a NP-Hard problem. Nevertheless, we have developed a heuristic construction of decompositions adapted to RNA structures. We then defined new structure classes which extend existing ones without degrading the complexity of the alignment but which can represent the majority of known structures containing many important elements that had not be taken into account previously (such as RNA tertiary motifs).The sequence-structure alignment problem attempts to answer the problem of prediction of structures and RNA research. However, the quality of the results obtained by its resolution depends on the cost function. During my PhD I started to define new cost functions adapted to the new structure classes by a machine learning approach. Finally, the work allows significant improvements in terms of quality of results and computation. For example the approach directly allows the search for sub-optimal solutions or its use within heuristics derived from traditional heuristic methods.

Dans cette thèse, nous étudions les transformations rigides dans le contexte de l'imagerie numérique. En particulier, nous développons un cadre purement discret pour traiter ces transformations. Les transformations rigides, initialement définies dans le domaine continu, sont impliquées dans de nombreuses applications de traitement d'images numériques. Dans ce contexte, les transformations rigides digitales induites présentent des propriétés géométriques et topologiques différentes par rapport à leurs analogues continues. Afin de s'affranchir des problèmes inhérents à ces différences, nous proposons de formuler ces transformations rigides dans un cadre purement discret. Dans ce cadre, les transformations rigides sont regroupées en classes correspondant chacune à une transformation digitale donnée. De plus, les relations entre ces classes de transformations peuvent être modélisées par une structure de graphe. Nous prouvons que ce graphe présente une complexité spatiale polynômiale par rapport à la taille de l'image. Il présente également des propriétés structurelles intéressantes. En particulier, il permet de générer de manière progressive toute transformation rigide digitale, et ce sans approximation numérique. Cette structure constitue un outil théorique pour l'étude des relations entre la géométrie et la topologie dans le contexte de l'imagerie numérique. Elle présente aussi un intérêt méthodologique, comme l'illustre son utilisation pour l'évaluation du comportement topologique des images sous des transformations rigides / In this thesis, we study rigid transformations in the context of computer imagery. In particular, we develop a fully discrete framework for handling such transformations. Rigid transformations, initially defined in the continuous domain, are involved in a wide range of digital image processing applications. In this context, the induced digital rigid transformations present different geometrical and topological properties with respect to their continuous analogues. In order to overcome the issues raised by these differences, we propose to formulate rigid transformations on digital images in a fully discrete framework. In this framework, Euclidean rigid transformations producing the same digital rigid transformation are put in the same equivalence class. Moreover, the relationship between these classes can be modeled as a graph structure. We prove that this graph has a polynomial space complexity with respect to the size of the considered image, and presents useful structural properties. In particular, it allows us to generate incrementally all digital rigid transformations without numerical approximation. This structure constitutes a theoretical tool to investigate the relationships between geometry and topology in the context of digital images. It is also interesting from the methodological point of view, as we illustrate by its use for assessing the topological behavior of images under rigid transformations

Dans cette thèse, nous nous intéressons à plusieurs problèmes liés à la conception de réseaux géométriques et aux plongements isométriques dans le plan.Nous commençons par étudier la généralisation du problème du réseau de Manhattan classique aux plans normés. Étant donné un ensemble de terminaux, nous recherchons le réseau de longueur totale minimum qui connecte chaque paire de terminaux par un plus court chemin dans la métrique définie par la norme. Nous proposons un algorithme d'approximation facteur 2.5 pour ce problème en temps O(mn^3) avec n le nombre de terminaux et m le nombre de directions de la boule unitaire. Le deuxième problème étudié est une version orientée des réseaux de Manhattan dont le but est de construire un réseau orienté de taille minimum dans lequel pour chaque paire de terminaux u, v est relié par un plus court chemin rectilinéaire de u vers v et un autre de v vers u. Nous proposons un algorithme d'approximation facteur 2 pour ce problème en temps O(n^3) où n est le nombre de terminaux.Nous nous intéressons ensuite à la recherche d'un spanner (un sous-graphe approximant les distances) planaire pour les graphes de disques unitaires (UDG) qui modélise les réseaux ad hoc sans fils. Nous présentons un algorithme qui construit un spanner planaire avec un facteur d'étirement constant en terme de distance de graphe pour UDG. Cet algorithme utilise uniquement des propriétés locales et peut donc être implémenté de manière distribuée.Finalement nous étudions le problème de la reconnaissance des espaces plongeables isométriquement dans le plan l_1 pour lequel nous proposons un algorithme en temps optimal O(n^2) pour sa résolution, ainsi que la généralisation de ce problème aux plans normés dont la boule unitaire est un polygone convexe central symétrique. / In this thesis, we study several problems related to the design of geometric networks and isometric embeddings into the plane.We start by considering the generalization of the classical Minimum Manhattan Network problem to all normed planes. We search the minimum network that connects each pair of terminals by a shortest path in this norm. We propose a factor 2.5 approximation algorithm in time O(mn^3), where n is the number of terminals and m is the number of directions of the unit ball.The second problem presented is an oriented version of the minumum Manhattan Network problem, we want to obtain a minimum oriented network such that for each pair u, v of terminals, there is a shortest rectilinear path from u to v and another path from v to u.We describe a factor 2 approximation algorithm with complexity O(n^3) where n is the number of terminals for this problem.Then we study the problem of finding a planar spanner (a subgraph which approximates the distances) of the Unit Disk Graph (UDG) which is used to modelize wireless ad hoc networks. We present an algorithm for computing a constant hop stretch factor planar spanner for all UDG. This algorithm uses only local properties and it can be implemented in distributed manner.Finally, we study the problem of recognizing metric spaces that can be isometrically embbed into the rectilinear plane and we provide an optimal time O(n^2) algorithm to solve this problem. We also study the generalization of this problem to all normed planes whose unit ball is a centrally symmetric convex polygon.

No description available.

Nous considérons des jeux de congestion sur des graphes. Dans les jeux non-atomiques, nous considérons un ensemble de joueurs infinitésimaux. Chaque joueur veut aller d'un sommet à un autre en choisissant une route de coût minimal. Le coût de chaque route dépend du nombre de joueur la choisissant. Dans les jeux atomiques divisibles, nous considérons un ensemble de joueurs ayant chacun une demande à transférer d'un sommet à un autre, en la subdivisant éventuellement sur plusieurs routes. Dans ces jeux, un équilibre de Nash est atteint lorsque chaque joueur a choisi une stratégie de coût minimal. L'existence d'un équilibre de Nash est assurée sous de faibles hypothèses. Les principaux sujets sont l'unicité, le calcul, l'efficacité et la sensibilité de l'équilibre de Nash. De nombreux résultats sont connus dans le cas où les joueurs sont tous impactés de la même façon par la congestion. Le but de cette thèse est de généraliser ces résultats au cas où les joueurs ont des fonctions de coût différentes. Nous obtenons des résultats sur l'unicité de l'équilibre dans les jeux non-atomiques. Nous donnons deux algorithmes capables de calculer un équilibre dans les jeux non-atomiques lorsque les fonctions de coût sont affines. Nous obtenons une borne sur le prix de l'anarchie pour certains jeux atomiques divisibles et prouvons qu'il n'est pas borné en général, même lorsque les fonctions sont affines. Enfin, nous prouvons des résultats sur la sensibilité de l'équilibre par rapport à la demande dans les jeux atomiques divisibles / We consider congestion games on graphs. In nonatomic games, we are given a set of infinitesimal players. Each player wants to go from one vertex to another by taking a route of minimal cost, the cost of a route depending on the number of players using it. In atomic splittable games, we are given a set of players with a non-negligible demand. Each player wants to ship his demand from one vertex to another by dividing it among different routes. In these games, we reach a Nash equilibrium when every player has chosen a minimal-cost strategy. The existence of a Nash equilibrium is ensured under mild conditions. The main issues are the uniqueness, the computation, the efficiency and the sensitivity of the Nash equilibrium. Many results are known in the specific case where all players are impacted in the same way by the congestion. The goal of this thesis is to generalize these results in the case where we allow player-specific cost functions. We obtain results on uniqueness of the equilibrium in nonatomic games. We give two algorithms able to compute a Nash equilibrium in nonatomic games when the cost functions are affine. We find a bound on the price of anarchy for some atomic splittable games, and prove that it is unbounded in general, even when the cost functions are affine. Finally we find results on the sensitivity of the equilibrium to the demand in atomic splittable games