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 nouvel objet.

Le domaine des problèmes informatique est l'un des nombreux champs d'intérêt de l'informatique théorique. Le domaine des algorithmes étudie les méthodes efficaces de résolution de problème. De son côté, le champ d'étude de l' Analyse de la complexité des algorithmes cherche à comprendre pourquoi certains algorithmes ne sont pas traitables par ordinateur, et à déterminer quels sont les algorithmes les plus efficaces pour un problème donné.

Pour des raisons pratiques, on représente souvent les instances et les solutions par un tableau binaire (contenant donc uniquement des éléments de {0, 1}^*). Par exemple, les nombres sont représentables sous cette forme par Système binaire. (Pour des questions de lecture, on identifiera les nombres à leur représentation binaire dans les exemples ci-dessous).

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