Problème algorithmique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 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[1] :

  • 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 d'évaluation ou de construction, qui consistent à produire un objet spécifié par l'énoncé du problème.

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.

Analyse en complexité des problèmes algorithmiques décidables[modifier | modifier le code]

Un problème peut ne pas être décidable, cela signifie que bien qu'il soit correctement posé, il n'admet pas de résolution par algorithme.

En revanche s'il est décidable, une deuxième question se pose, concernant l'efficacité 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é. Une possibilité (mais il y en a d'autres[2]) 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.

Taxinomie des problèmes algorithmiques[modifier | modifier le code]

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[3].

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

fR(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[modifier | modifier le code]

  1. Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 1 (« Le modèle de calcul »).
  2. Par exemple, on peut imaginer une représentation des nombres en bâtons ou une présentation des nombres en virgule flottante.
  3. La « relation » d'un problème peut ne peut pas être calculable, auquel cas l'énumération comme dans la relation ci-dessus n'existe pas.