Abstract FR:

Nous etudions certains aspects de plusieurs modeles bases sur la satisfaction de contraintes. D'abord, dans le cadre des problemes de satisfaction de contraintes classiques (csp), nous proposons un nouvel algorithme de filtrage des csp binaires (les contraintes portent sur deux variables): il repose sur la mise en evidence de proprietes structurelles reliees aux inclusions de voisinages dans les graphes. Ce filtrage peut diminuer l'ensemble des solutions, mais il preserve la satisfiabilite du probleme. Des formes affaiblies de ce filtrage sont utilisees pour ameliorer des methodes classiques de resolution. Ensuite, nous etudions deux extensions du modele csp classique, qui permettent l'expression de diverses formes de flexibilite: le modele des csp dynamiques (dcsp), ou le facteur temps est introduit, et celui des csp values (vscp), ou des mesures de preferences ou d'incertitude peuvent etre exprimees. Pour ces deux modeles, nous proposons dans le cas binaire des techniques voisines, basees sur une propagation d'informations, dont l'objet est: pour les dcsp, le maintien de solutions successives optimalement proches (differentes mesures de distance etant possibles). Une premiere version statique est completee par une version incrementale. Pour les vcsp, le calcul de solution optimale pour la version statique, et le maintien de solution optimale pour la version incrementale