Abstract FR:

P etant un ordre, le nombre de sauts de p est le nombre minimum de comparaisons qu'il faut rajouter a p pour obtenir un ordre total. Ce parametre intervient dans certains problemes d'ordonnancement de taches, et son calcul est np-difficile en general. Par contre la complexite sur les ordres de dimension 2 (i. E. Les ordres qui sont l'intersection de 2 ordres totaux) est inconnue. Cette these presente des arguments de geometrie du plan qui permettent de resoudre certaines questions reliees au probleme du nombre de sauts sur les ordres de dimension 2. Nous montrons que ce probleme est equivalent au probleme suivant : etant donne un ensemble de rectangles ponderes du plan, quel est le poids maximum d'un sous-ensemble constitue de rectangles 2 a 2 disjoints ? grace a cette interpretation, nous montrons que le calcul est polynomial sur la classe des ordres de hauteur h (meme dans la version ponderee ou on attribue un poids a chaque couverture), alors que cette derniere version ponderee est np-difficile si la hauteur est quelconque, montrant que la complexite du probleme est dependante de la hauteur de l'ordre. D'autre part, nous nous interessons aux 2 ordres totaux dont un ordre p de dimension 2 est l'intersection, vis a vis du nombre de sauts, montrant entre autre que la somme des nombres de sauts produits par l'un et l'autre de ces ordres totaux ne depend que du graphe d'incomparabilite de p. Par ailleurs, nous nous interessons a certains problemes de representation des ordres de dimension 2 et 3. En montrant que les ordres de dimension 3 sont exactement les ordres d'inclusion de triangles isothetiques dans le plan, nous prouvons que la complexite de set packing passe de polynomial a np-complet lorsque le biparti d'adjacence sous-jacent passe de la dimension 2 a la dimension 3.