Problème algorithmique

Un problème algorithmique est, en informatique théorique, un objet mathématique qui représente une question ou un ensemble de questions auxquelles un ordinateur devrait être en mesure de répondre. Le plus souvent, ces problèmes sont de la forme : étant donné un objet (l'instance), effectuer une certaine action ou répondre à telle question.

Par exemple, le problème de la factorisation est le problème suivant : étant donné un nombre entier, trouver un facteur premier de cet entier.

On distingue en particulier deux types de problèmes :

• les problèmes de décision, qui consistent à répondre oui ou non à une question (par exemple, cet entier est-il premier ?) ;
• les problèmes à promesse, qui consistent à répondre oui ou non à une question uniquement sous une hypothèse (la promesse) ;
• les problèmes de recherche (ou de fonction), qui consistent à produire un objet spécifié par l'énoncé du problème (par exemple, la factorisation).

Les problèmes algorithmiques jouent un rôle central en informatique théorique et forment un domaine à part entière, à côté de celui des algorithmes qui étudient les méthodes efficaces de résolution de problèmes décidables et de celui de l'analyse de la complexité des algorithmes qui cherche à comprendre les performances de ces algorithmes.

Vocabulaire

Un problème algorithmique est le plus souvent formulé par un ensemble d'entrées possibles, appelées instances, et des contraintes sur la sortie. L'algorithme doit pouvoir calculer, à partir de l'instance, une sortie qui satisfait les contraintes en question.

En d'autres termes, une instance est un ensemble de données d'entrée qui satisfont les contraintes imposées par l'énoncé d'un problème algorithmique.

Classification par difficulté

Décidabilité

Un problème peut être décidable ou indécidable. Un problème est décidable s'il existe un algorithme pour le résoudre.

Complexité

Une fois la décidabilité démontrée, une deuxième question se pose, concernant l'efficience de la recherche d'une solution. Dans ce cas il faut fixer une représentation des données et des solutions du problème pour pouvoir dire quelque chose sur la complexité. Il y a deux cas.

Nombre d'opérations

Une possibilité (mais il y en a d'autres) est de postuler que les instances et les solutions sont représentées par un tableau binaire (contenant donc uniquement des éléments de {0, 1}^*). Par exemple, les nombres sont représentés de façon binaire, les graphes sont codés de façon binaire ainsi que les machines de Turing. Dans la suite, nous nous concentrerons sur cette façon d'exprimer la complexité et nous identifierons les nombres, les graphes, les machines, etc. à leur représentation binaire.

Nombre de solutions

Dans ce cas, il s'agit de compter le nombre de solutions ou plus précisément le nombre de certificats. La principale complexité dans ce cas est la complexité #P.

Taxonomie des problèmes algorithmiques

Un problème de décision est un problème où la réponse de chaque instance est soit « oui », soit « non ». Ainsi le test de primalité d'un nombre entier est un problème algorithmique :

« Soit un nombre entier naturel, n, déterminer si n est premier. »

Un problème de décision est souvent assimilé à l'ensemble des instances pour lesquelles la réponse est « oui ». Dans l'exemple précédent, le problème de primalité est assimilé à l'ensemble des nombres premiers :

L = {2, 3, 5, 7, 11, …}

Dans un problème de recherche, la réponse est un élément associé à l'élément d'entrée par la relation qui apparaît dans l'énoncé du problème. Par exemple, le problème de factorisation ci-dessus cherche des solutions dont la donnée est un nombre et le résultat est un couple de nombres dont la première composante est un nombre premier et le produit des composantes est le nombre donné dans l'énoncé.

Un problème de recherche est donné par une relation binaire appelée relation de recherche. Par exemple, la factorisation est la relation

R = {(4, 2), (6, 2), (6, 3), (8, 2), (9, 3), (10, 2), (10, 5)…}

qui comprend toutes les paires de nombres (n, p), où p est un facteur premier non trivial de n.

Un problème de dénombrement vise à déterminer le nombre de solutions d'un problème de recherche donné. Par exemple, le problème de dénombrement associé à celui de la factorisation est

« Soit un entier n, déterminer le nombre de facteurs premiers non triviaux de n. »

Un problème de dénombrement a pour résultat un entier naturel. Pour chaque relation de recherche R, le problème de dénombrement associé à R est une fonction

f_R(x) = |{y : R(x, y)}|.

Un problème d'optimisation cherche une solution « meilleure » que les autres parmi toutes les solutions possibles d'un problème de recherche. On peut citer comme exemple, la recherche du plus grand facteur premier d'un nombre.

Un problème d'optimisation contient dans son énoncé sa relation de recherche à laquelle on ajoute la contrainte de trouver une solution optimale.

Dans un problème de fonction, un seul résultat au plus est attendu pour chaque entrée, mais sa nature est plus complexe que celle d'un problème de décision puisque le résultat est une valeur et non pas « oui » ou « non » comme dans un problème de décision.

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Computational problem » (voir la liste des auteurs).