thesis

Algorithmes linéaires et invariants d'ordres

Defense date:

Jan. 1, 1991

Edit

Institution:

Montpellier 2

Disciplines:

Authors:

Directors:

Abstract EN:

Pas de résumé disponible.

Abstract FR:

L'algorithmique des ensembles ordonnes occupe une place grandissante en informatique. Elle est etudiee ici sous divers aspects: - etude de la complexite concrete d'algorithmes de fermeture et reduction transitive de graphes sans circuit dans des cas particuliers; - etude du probleme de la dimension des ordres d'intervalles: trois nouvelles bornes sont obtenues ainsi qu'un encadrement a deux pres par le nombre chromatique d'un diagramme associe. Etude du nombre chromatique des diagrammes sur des classes particulieres. - modelisation a l'aide d'ensembles ordonnes de systemes distribues et utilisation du modele pour l'etude de mesures de concurrence; - etude des extensions d'intervalle minimales d'un ensemble ordonne. Caracterisation. Invariance de comparabilite. Algorithmes de generation