Lamiae
Extrait du cours introduction à ASP (Programmation par ensembles réponses)
Remarque sur l’expressivité dans gringo
Les possibilités du langage sont en fait plus complexes mais au-delà des possibilités d’un cours d’introduction.
On peut écrire des programmes disjonctifs, ce qui signifie qu’il peut y avoir une alternative au niveau de la tête des clauses (e.g. p|q. ou p|q:-r.). Il faut alors faire appel à un solveur spécifique (claspD) et la complexité explose…
Notons qu’il est possible d’utiliser la négation classique en utilisant le moins (e.g –p:-q.)
ASP, c’est utile dans quels cas ?
Techniquement, ASP offre un cadre unifié où sont intégrés des aspects bases de données, bases de connaissances, résolution de contraintes et programmation logique.
Il est possible de faire de l’optimisation et d’utiliser différents modes de raisonnement pour chercher une solution, toutes, les meilleures, leur intersection ou leur union.
La résolution des problèmes combinatoires est le cœur de cible d’ASP. En particulier c’est un candidat de choix pour attaquer des problèmes NP-complets et NP-difficiles (graphes, raisonnement,…) du fait de la facilité de mettre au point et tester différents modèles et différentes heuristiques .
ASP ne doit pas être utilisé pour…
remplacer des algorithmes classiques maîtrisés : pour faire du tri, du calcul ou du traitement de séquences, il faut revenir à un langage de programmation classique. Le langage de script Lua est inclus dans gringo pour les pré et post-traitements;
travailler dans des espaces peu structurés et peu contraints ou des espaces difficiles à discrétiser.
résoudre un problème qui nécessiterait de nombreuses étapes successives qui communiquent : un programme ASP ne permet pas d’écrire des procédures.
Et la sémantique ? Programmes positifs
Un programme positif est constitué d’un ensemble de règles (clauses définies) A:-B1,B2,…Bm ou A (la tête de la règle) et les B (le corps) sont des atomes (variables booléennes).
A:-B1,B2,…Bm correspond à la formule ØB1Ú Ø B2 Ú … Ø Bm Ú A
Un ensemble d’atomes X est clos pour un programme positif si pour l’ensemble de ses règles r,
corps(r)ÍX Þ tête(r)ÍX
(C’est un modèle du programme vu comme une formule).
L’ensemble réponse (answer set) d’un programme positif P est le plus petit ensemble d’atomes qui soit clos pour P. Il existe et est unique.
Et la sémantique ? Programmes avec not
Un programme est constitué de manière plus générale d’un ensemble de règles A:-B1,B2,…Bm, not Bm+1, not Bm+2,… not Bm+n
Le réduit d’un programme par rapport à un ensemble d’atomes X est l’ensemble des règles A:-B1,B2,…Bm telles qu’aucun des Bm+1, Bm+2,… Bm+n n’appartient à X.
Un ensemble réponse (on dit aussi modèle stable) d’un programme P est un plus petit ensemble d’atomes clos pour le réduit de P (il peut y en avoir 0, 1 ou plusieurs).
Autrement dit, on ne met dans un modèle l’atome d’une tête de règle que si la règle est un fait (règle réduite à une tête) après en avoir enlevé les littéraux négatifs qui ne sont pas dans le modèle ou si tous les littéraux positifs du corps sont dans le modèle et aucun des littéraux négatifs.
Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)Cours introduction à ASP (Programmation par ensembles réponses) (1.31 MB) (Cours PPT)
