Présentation

Article

1 - GÉNÉRALITÉS

  • 1.1 - Programmation avec contraintes (PC)
  • 1.2 - Programmation logique avec contraintes (PLC)
  • 1.3 - Exemple illustratif de la PLC dans le domaine financier
  • 1.4 - Méthodologie de construction de programmes en PLC

2 - LES CONTRAINTES EN PROLOG III

  • 2.1 - Contraintes sur les listes
  • 2.2 - Contraintes numériques
  • 2.3 - Contraintes booléennes

3 - CONTRAINTES SUR LES DOMAINES FINIS ET SUR LES INTERVALLES

  • 3.1 - Contraintes sur les domaines finis
  • 3.2 - Contraintes sur les intervalles

4 - CONCLUSION ET PERSPECTIVES

Article de référence | Réf : H3158 v1

Contraintes sur les domaines finis et sur les intervalles
Programmation logique avec contraintes

Auteur(s) : Laurent TRILLING

Date de publication : 10 mai 1998

Pour explorer cet article
Télécharger l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !

Sommaire

Présentation

Auteur(s)

Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.

Lire l’article

INTRODUCTION

La programmation logique avec contraintes (PLC) se révèle être un nouveau type de programmation promis, à notre avis, à un large succès : la rapidité dans la conception et la mise en œuvre qu’elle permet sont des atouts décisifs dans le monde compétitif que nous connaissons. Son origine remonte à la prise de conscience, dans les années quatre-vingt, par les auteurs de langages de programmation logique comme Prolog qu’un « calcul » peut être considéré comme la démonstration de la satisfiabilité (existence de solutions) d’un système d’équations au sens large.

Les principaux outils disponibles sur le marché tels Prolog III, CHIP (Constraint Handling in Prolog) ou Ilog-Solver datent du début des années quatre-vingt-dix. Si cette programmation reste encore relativement peu connue dans l’industrie informatique, on doit signaler l’essor des entreprises la maîtrisant. On peut signaler aussi que les scientifiques et les industriels européens et, singulièrement, français occupent une place prédominante dans ce secteur qui n’a pas encore autant attiré l’attention des Nord-Américains. Il est dit méchamment que cela est dû au fait que les programmeurs d’outre-Atlantique apprécient moins les mathématiques que leurs collègues européens. Peut-être est-ce exact, mais attention, il est vrai aussi que les Américains sont extrêmement prompts à s’engager dans des technologies de pointe une fois leur intérêt reconnu...

Cet article est organisé de la façon suivante. La première partie est une introduction aux principes essentiels de la PLC. La seconde est consacrée, plus particulièrement, aux contraintes aisément compréhensibles disponibles dans le langage Prolog III. La troisième est dévolue aux contraintes sur les domaines finis, au centre de nombreuses applications, et aux contraintes sur les intervalles qui prennent une place de plus en plus importante. La conclusion a pour objectif de dresser un état de la situation et des perspectives envisageables.

Cet article est réservé aux abonnés.
Il vous reste 94% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

DOI (Digital Object Identifier)

https://doi.org/10.51257/a-v1-h3158


Cet article fait partie de l’offre

Technologies logicielles Architectures des systèmes

(233 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Lecture en cours
Présentation

3. Contraintes sur les domaines finis et sur les intervalles

Nous abordons ici deux types de contraintes numériques qui se distinguent du fait que les résolveurs associés sont moins ambitieux : leurs réponses sont approximatives en ce sens qu'elles fournissent des intervalles possibles pour les variables sans garantir que le système d'équations est effectivement satisfiable. Cependant, un échec garantit que le système est insatisfiable.

L'avantage essentiel de ces résolveurs réside dans leur faible coût. Ils nécessitent l'usage d'énumérations, en général sophistiquées, mais cela est compensé par le fait que les avancées technologiques en ce domaine sont très significatives. Pratiquement, ce sont les contraintes sur domaines finis qui connaissent les succès les plus remarquables sur les problèmes combinatoires. Quant aux contraintes sur intervalles, plus récentes et, d'une certaine façon, plus générales, elles sont très prometteuses dans la mesure où elles peuvent permettre de résoudre finement des équations non linéaires.

3.1 Contraintes sur les domaines finis

Ces contraintes ont été introduites initialement dans le langage CHIP [3].

Les objets sont des objets numériques ou symboliques appartenant à des domaines finis, par exemple {1, 2, 3} ou {bleu, blanc, rouge}.

Les opérations sont des opérations numériques habituelles.

Les contraintes sont les équations, les inéquations et les diséquations mais, de plus, l’expérience a fait introduire des contraintes globales telles que, par exemple :

  • element[N, [X1,...,XK], V] satisfaite si le Nième élément de la liste [X1,...,XK] a la valeur V

  • auPlus(N, [X1,...,XK], V] satisfaite si parmi les variables de la liste [X1,...,XK] au plus N ont la valeur V.

Les algorithmes sous-jacents dérivent des techniques d'intelligence artificielle utilisées pour résoudre des problèmes de satisfaction de contraintes (en anglais CSP, Constraint Satisfaction Problem [4]). Intuitivement, l’idée ressort encore de la propagation d’information : aussitôt qu’une information est tirée d’une équation (une instanciation peut être considérée comme une équation), elle est propagée aux autres équations. L’algorithme de base consiste à considérer une des variables, à lui donner une des valeurs de son domaine et à vérifier que cette valeur est acceptable en restreignant éventuellement les domaines des autres : si elle ne l’est...

Cet article est réservé aux abonnés.
Il vous reste 94% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Technologies logicielles Architectures des systèmes

(233 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Lecture en cours
Contraintes sur les domaines finis et sur les intervalles
Sommaire
Sommaire

1 Bibliographie

###

HAUT DE PAGE

2 Annexe

Dans les Techniques de l’Ingénieur

BOIZUMAULT (P.) - Langage Prolog - . [H 3 098], Technologies logicielles – Architectures des systèmes (2001).

HAUT DE PAGE

Autres références

COLMERAUER (A.) - An introduction to Prolog III - . Communications of the ACM, 33, 7 (1990).

DINCBAS (M.) - VAN HENTENRYCK (P.) - SIMONIS (H.) - AGGOUN (A.) - GRAF (T.) - BERTHIER (F.) - The constraint logic programming language CHIP - . International Conference on Fifth Generation Computer Systems (FGCS’88), Tokyo (1988).

TSANG (E.) - Foundation of constraint satisfaction - . Academic Press (1993).

OLDER (W.) - VELLINO (A.) - Extending prolog with constraint arithmetic on real interval - . Canadian Conference on Electrical and Computer Engineering (1990).

Le manuel Prolog IV - . Compagnie ProloglA Marseille (1996).

ILOG SOLVER User manual Version 3.2 - . Compagnie ILOG, Paris (1996).

Practical application of constraint technology - . Practical Application Company Ldt, Londres (1997).

SIMONIS...

Cet article est réservé aux abonnés.
Il vous reste 93% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Technologies logicielles Architectures des systèmes

(233 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS