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).

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)