dbo:abstract
|
- 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. L'exemple suivant, illustrant la différence entre les deux types de négation, est dû à John McCarthy : Un autobus scolaire peut traverser des voies ferrées à condition qu'il n'y ait pas de train qui approche. Comme nous ne savons pas nécessairement si un train approche, la règle qui utiliserait la négation par défaut (comme en Prolog), n’est pas adéquate dans certains contextes : en effet, elle dit qu’il est acceptable de traverser en l’absence d’information sur un train qui approche. La règle la plus faible, qui utilise une négation forte, peut être ici préférable (ne pas traverser si on ne sait pas si un train arrive). 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). (fr)
- 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. L'exemple suivant, illustrant la différence entre les deux types de négation, est dû à John McCarthy : Un autobus scolaire peut traverser des voies ferrées à condition qu'il n'y ait pas de train qui approche. Comme nous ne savons pas nécessairement si un train approche, la règle qui utiliserait la négation par défaut (comme en Prolog), n’est pas adéquate dans certains contextes : en effet, elle dit qu’il est acceptable de traverser en l’absence d’information sur un train qui approche. La règle la plus faible, qui utilise une négation forte, peut être ici préférable (ne pas traverser si on ne sait pas si un train arrive). 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). (fr)
|
rdfs:comment
|
- 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. L'exemple suivant, illustrant la différence entre les deux types de négation, est dû à John McCarthy : Un autobus scolaire peut traverser des voies ferrées à condition qu'il n'y ait pas de train qui approche. (fr)
- 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. L'exemple suivant, illustrant la différence entre les deux types de négation, est dû à John McCarthy : Un autobus scolaire peut traverser des voies ferrées à condition qu'il n'y ait pas de train qui approche. (fr)
|