Requête à un oracle

En algorithmique, on appelle oracle une source d’information sur une donnée nécessaire à un calcul. C’est en général la seule source d’information dont l’algorithme dispose sur cette donnée, et le fonctionnement interne de l’oracle n’a pas à être connu. Chaque fois qu’une nouvelle information sur cette donnée est nécessaire, l’algorithme soumet une requête à l’oracle, sous un format fixé. La réponse de l’oracle, elle-même sous un format fixé, ne dépend que des paramètres de la requête. Ainsi, un graphe dont les sommets sont numéroté de 1 à n peut n’être accessible par un algorithme qu’au moyen des réponses qu’un oracle donnera à des requêtes de la forme « quel est le k^e voisin du sommet numéro p ? », à laquelle l’oracle répondra par un numéro de sommet.