Problème algorithmique

En informatique théorique, un problème est un objet mathématique qui représente une question ou un ensemble de questions auxquelles un ordinateur doit être en mesure de répondre. Le plus souvent ces problèmes sont de la forme : étant donné une 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ème d'évaluation ou de construction, qui consiste à produire un objet spécifié par l'énoncé du problème.

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

Souvent 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 et dans la suite on identifiera les nombres à leur représentation binaire.

Types de problèmes algorithmiques

Un problème de décision où la réponse de chaque instance est soit "oui", soit "non". On peut citer comme exemple le problème du test de primalité d'un nombre entier:

"Soit un nombre entier positif, n, déterminer si n est premier."

Un problème de décision est typiquement représenter par l'ensemble des instances pour lesquelles la réponse est "oui". Dans l'exemple précédent, le problème de primalité peut être représenté par l'ensemble des nombres premiers:

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

Dans un problème de recherche, la réponse est une chaîne de caractères. Par exemple, le problème de factorisation ci-dessus cherche des solutions sous forme de chaînes (de bits) représentant les nombres satisfaisant l'instance du problème donné.

Un problème de recherche peut se représenter par une relation définie par toutes les paires (instance,solution), appelée relation de recherche. Par exemple, la factorisation peut être représentée par 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 cherche à déterminer le nombre de solution 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 peut être représenté par une fonction f de {0, 1}^* vers les entiers positifs. Pour chaque relation de recherche R, le problème de dénombrement associé à R est une fonction

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

Un problème d'optimisation cherche la "meilleure" solution parmi toutes les solutions possibles d'un problème de recherche. On peut citer comme exemple le problème du plus grand ensemble indépendant (ou problème de l'ensemble maximal indépendant):

"Soit un graphe G, trouver l'ensemble indépendant de G taille maximale."

Un problème d'optimisation peut être représentée par sa relation de recherche.

Dans un problème de fonction un seul résultat (d'une fonction totale) est attendu pour chaque entrée, mais le résultat est de nature plus complexe que dans le cas du problème de décision : le résultat n'est pas restreint à "oui" ou "non". Un des exemples plus connus est le Problème du voyageur de commerce:

"Soit une liste de villes et distances entre celles-ci, trouver le chemin le plus court qui passe par chaque ville une fois seulement, et revenir à la ville de départ."

Il s'agit d'un problème NP-difficile d'optimisation combinatoire, fréquemment rencontré en recherche opérationnelle etinformatique théorique.

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