Abstract FR:

Cette these est principalement dediee a l'etude des proprietes algorithmiques et combinatoires des ensembles ordonnes. Les travaux qui y sont exposes peuvent etre regrouper suivant quatre principaux themes: -les executions reparties: nous definissons un cadre adapte au calcul de mesurs attachees a une execution repartie. Puis nous proposons une mesure de concurrence et nous etudions ses proprietes combinatoires; -les extensions d'intervalles d'un ensemble ordonne: nous caracterisons les extensions d'intervalles minimales d'un ordre, nous etudions leurs proprietes et nous proposons des algorithmes permettant d'en calculer le nombre; -le nombre chromatique du diagramme d'un ensemble ordonne: nous exhibons des classes d'ordres pour lesquelles le nombre chromatique cherche est borne et d'autres pour lesquelles ce nombre est arbitrairement grand; -la reduction et la fermeture transitive d'un graphe oriente sans circuit: nous proposons des algorithmes permettant de calculer la reduction ou la fermeture transitive en temps lineaire sur certaines classes de graphes