Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Answer set programming
Résumé
L’answer set programming (ASP) est une forme de programmation déclarative adaptée aux problèmes de recherche combinatoires (par exemple, sudoku et coloration de graphes).
Dans le contexte de la programmation logique, cette approche distingue deux types de négation — la négation par manque d'information, dite négation par défaut, et la négation forte ou négation logique. La négation par défaut permet de raisonner en l'absence d'information et rend l'ASP non monotone. L'exemple suivant, illustre le fonctionnement de la négation par défaut:
Si « X est un oiseau » mais pas « X est une autruche » alors « X vole »
« Titi est un oiseau »
On peut déduire de ce programme le fait « Titi vole ». En effet, ici nous n'avons aucune information qui nous indique que Titi est une autruche. Cependant, si nous avions les informations «Lola est un oiseau et une autruche », alors nous ne pouvons pas déduire que Lola vole.
La négation forte quant à elle demande une preuve qu'un fait est faux. Dans cet exemple, il faudrait donc prouver que Titi n'est pas une autruche pour en déduire qu'il vole.
En ASP, la résolution de problème se réduit à calculer des modèles stables, c'est-à-dire où la négation par défaut produit des modèles logiquement consistants. Dans un sens plus général, ASP inclut des techniques de représentation des connaissances et l’évaluation de requêtes dans le style Prolog, pour résoudre les problèmes qui se posent dans ces applications. ASP permet de décider les problèmes dans NP et plus généralement les problèmes de la classe NPNP (voir hiérarchie polynomiale, l'existence d'un modèle stable est NPNP-complet).
Dans cette section, nous donnons des programmes ASP écrits en AnsProlog, le langage de Lparse, adopté par nombre d'autres outils.
vignette|Coloration d'un graphe avec trois couleurs.
Le problème de coloration de graphe consiste à attribuer des couleurs à des sommets d'un graphe non orienté de façon que deux sommets reliés n'aient pas la même couleur. Le problème ASP suivant permet de savoir si un tel graphe est coloriable ou non et d'obtenir une coloration :
c(1.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.