In dieser Arbeit verbinden wir die Theorie der Quasi-Ordnungen mit der Theorie der Algorithmen einiger kombinatorischer Objekte. Zuerst entwickeln wir die Theorie der Wohl-Quasi-Ordnungen, WQO, im Zusammenhang zur maximalen Komplexität. Dann geben wir ein allgemeines 0-1-Gesetz für erbliche Eigenschaften, das Auswirkungen für die mittlere Komplexität hat. Dieses Ergebnis für mittlere Komplexität wird auf die Klasse der endlichen Graphen, versehen mit der Relation ``induzierter Subgraph'', angewendet. Wir erhalten, daß eine große Klasse von Problemen, welche z.B. Perfektheit umfaßt, Algorithmen mit im Mittel konstanter Laufzeit haben. Dann zeigen wir, indem wir ein Ergebnis von Damaschke für Cographen veralgemeinern, daß die Klassen der endlichen Ordnungen bzw. Graphen mit beschränktem Dekompositionsdurchmesser bzgl. der Relation ``induzierte Subordnung'' bzw. ``induzierter Subgraph'' WQO sind. Dies führt uns zu linearen Erkennungsalgorithmen für alle erblichen Eigenschaften über diesen Objekten. Unser Hauptresultat ist dann, daß die Menge der endlichen partiellen Ordnungen eine Wohl-Quasi-Ordnung bzgl. einer gewissen Relation &leq; , der sogenannten Ketten-Minor-Relation, ist. Um dies zu beweisen, führen wir eine verwandte Relation auf endlichen formalen Sprachen ein, die die gleiche Eigenschaft hat. Als Folgerung erhalten wir, daß jede Eigenschaft, die erblich bzgl. &leq; ist, einen Test in <em>O(|P|^c)</em> Zeit zuläßt, wobei $c$ von der Eigenschaft abhängt. Dieser Test läßt sich leicht parallelisieren. Auf einer parallelen Maschine (\CRCW\ \PRAM) kann er so implementiert werden, daß er konstante Zeit auf <em>O(|P|^c)</em> Prozessoren benötigt.

Cette thèse a pour objet les ordres, les valuations et les C-relations sur les groupes, ainsi que les corps différentiels valués tels qu’étudiés par Rosenlicht. Elle accomplit trois objectifs principaux. Le premier est d’introduire et d’étudier une notion de quasi-ordre sur les groupes qui a pour but de réunir les ordres et les valuations dans un même cadre. Nous donnons un théorème de structure des groupes munis d’un tel quasi-ordre, ce qui nous permet ensuite de donner un “théorème de plongement de Hahn” pour ces groupes. Le second objectif de cette thèse est de décrire les C-groupes à l’aide des quasi-ordres. Nous donnons un théorème de structure pour les C-groupes, qui énonce que tout C-groupe est un “mélange” de groupes ordonnés et de groupes valués. Nous utilisons ensuite ce résultat pour caractériser les groupes C-minimaux à l’intérieur de la classe des C-groupes. Le troisième objectif de cette thèse est d’introduire et d’étudier une notion de rang différentiel d’un corps différentiel valué. Nous définissons cette notion par analogie avec les notions de rang exponentiel d’un corps exponentiel et de rang de différence d’un corps aux différences. Nous montrons que cette notion de rang n’est pas tout à fait satisfaisante, et introduisons donc une meilleure notion de rang appelée le rang différentiel déployé. Nous donnons ensuite une méthode pour définir une dérivation “de type Hardy” sur un corps de séries formelles généralisées, ce qui nous permet de construire des corps différentiels valués dont le rang différentiel et le rang différentiel déployé ont été arbitrairement choisis. / This thesis deals with orders, valuations and C-relations on groups, and with differential-valued fields à la Rosenlicht. It achieves three main objectives. The first one is to introduce and study a notion of quasi-order on groups meant to encompass orders and valuations in a common framework. We give a structure theorem for groups endowed with such a quasi-order, which then allows us to give a “Hahn’s embedding theorem” for these groups. The second objective of this thesis is to describe C-groups via quasi-orders. We give a structure theorem for C-groups, which basically states that any C-group is a “mix” of ordered groups and valued groups. We then use this result to characterize C-minimal groups inside the class of C-groups. The third objective of this thesis is to introduce and study a notion of differential rank for differential-valued fields. We define this notion by analogy with the exponential rank of an exponential field and with the difference rank of a difference field. We show that this notion of rank is not quite satisfactory, so we introduce a better notion of rank called the unfolded differential rank. We then give a method to define “Hardy-type” derivations on fields of generalized power series, which allows us to build differential-valued fields of arbitrary given differential rank and unfolded differential rank.