- Non-déterminisme
-
La notion de non-déterminisme est particulière en informatique et apparait, entre autres, dans la théorie des automates d'état finis (Automate fini), on la retrouve également en Prolog et dans le problème "P=NP ?" (Théorie de la complexité des algorithmes). Elle est associée à un ensemble de possibles équivalents sous un certains point de vue qui nécessite une fonction de choix ou une exploration exhaustive de l'ensemble de ces possibles. Elle ne signifie pas qu'il y a imprédictibilité de la situation au sens le plus large du terme, entre autres car l'ensemble des possibles est le plus souvent fini, la situation est donc connue, elle appartient à cet ensemble de possibles. Parfois, il est même démontré qu'il y a équivalence entre le non-déterminisme et le déterminisme (cf. Automate fini).
Sommaire
Automate d'états finis non-déterminisme
(voir Automate fini)
Non-déterminisme Prolog
En Prolog, le non-déterminisme entraine la possibilité de présenter l'ensemble des réponses possibles à une requête donnée. Ceci repose sur la sémantique de Prolog qui utilise un 'ou' logique à la place de l'alternative ou conditionnelle usuellement utilisée dans les langages de programmation (et qui ressemble plus à un 'ou exclusif' ne laissant pas la place aux deux branches de l'alternative) ou au 'ou bien' qui opère de même.
Exemples d'utilisation du non-déterminisme en Prolog
Quelques idées d'exemples :
- La modélisation des automates d'états finis non-déterminisme est parfois un peu difficile avec les langages de programmation usuel, avec Prolog cela vient naturellement en utilisant la non-déterminisme de Prolog.
- La résolution de problèmes combinatoires (ex : le compte est bon)
- La résolution de problèmes NP
Un exemple explicite, construire P une partie de E :
partie([],[]). partie([E|L],P):-partie(L,P). partie([E|L],[E|P]):-partie(L,P).
ainsi
?- partie([1,2,3],R). R = []; R = [3]; R = [2]; R = [2, 3]; R = [1]; R = [1, 3]; R = [1, 2]; R = [1, 2, 3];
P=NP?
(voir Problème P = NP)
Wikimedia Foundation. 2010.
