Home
About

Problème algorithmique

Cours/Algorithmie/Écrire des Algorithmes/Problème algorithmique

Nous n'avons pour l'instant décrit les algorithmes que comme des fonctions permettant de calculer des nombres. La principale utilité de ceux-ci est cependant ailleurs. Les algorithmes sont utilisés parce ce qu'il permettent de répondre à des questions, de résoudre des problèmes. Bref, le résultat d'un algorithme a un sens.

Problème

Formalisons cette intuition en définissant la notion de problème.

Définition

Un problème est un texte composé de 3 parties :

  • nom : le nom du problème
  • données : les paramètres dont on a besoin
  • question : ce que l'on cherche à résoudre

Par exemple :

Problème

  • nom : maximum
  • données : un tableau d'entiers
  • question : quel est l'entier maximum du tableau ?

Une importante classe de problème est les problèmes de décision :

Définition

Un problème de décision est un problème dont la réponse est soit OUI, soit NON.

Par exemple :

Problème de décision

  • nom : présence
  • données :
    • v : un entier
    • t : un tableau d'entiers
  • question : v est-elle une valeur du tableau t ?

On se placera dans ce cours dans un cadre algorithmique. On se posera donc uniquement des questions sérieuses comme la recherche d'un éléments dans un tableau ou l'existence d'un algorithme pour résoudre un problème. On laissera de côté les problèmes futiles comme "quand est-ce qu'on mange ?" ou encore "quel est le sens de la vie ?".

Définition

Un problème est algorithmique s'il existe un algorithme pour le résoudre, c'est à dire que cet algorithme :

  • prend en paramètres les entrées du problème
  • donne la réponse à la question.

Dans la suite de ce cours nous allons nous concentrer sur les problèmes algorithmique et voir comment les résoudre le plus vite possible. Mais avant de conclure cette courte partie examinons quelques problèmes non décidables mais informatisable.

Décidabilité

On peut très souvent se restreindre aux problèmes de décision solvable par un algorithme :

Définition

Un problème de décision est décidable s'il existe un algorithme pour le résoudre (on dit un décideur), c'est à dire que cet algorithme :

  • prend en paramètres les entrées du problème
  • répond OUI ou NON selon la véritable réponse à donner.

Définition

Un décideur est un algorithme qui pour toute entrée, répond OUI ou NON.

Vous verrez parfois des décideurs qui à la place de répondre OUI rendent 1 et à la place de répondre NON, rendent 0.

L'important est que la sortie du décideur soit binaire et que l'on puisse associer une sémantique de vérité à la sortie.

En effet, on peut très souvent se ramener à un problème décidable pour prouver qu'un problème est algorithmique. Par exemple le problème maximum peut être associé au problème de décision maximum-v :

Problème de décision

  • nom : maximum-v
  • données :
    • t : un tableau d'entiers
    • v un entier
  • question : v est-elle l'entier maximum du tableau ?

Si maximum-v est décidable, il suffit d'exécuter l'algorithme décideur pour chaque valeur de t.

En revanche le problème de décision suivant n'est pas décidable :

Problème de décision

  • nom : arrêt
  • données :
    • a : un entier représentant un programme
    • n : un entier
  • question : a(n) s'arrête-t-il ?

On défini par extension les ensembles décidables comme étant ceux pouvant être énumérés par un algorithme :

Définition

Un ensemble $E$ d'entiers est décidable s'il existe un algorithme $A$ qui tel que :

  • $A(n)$ vaut OUI si $n \in E$
  • $A(n)$ vaut NON si $n \notin E$

Reconnaissabilité

Il existe un cas plus faible que la décidabilité, c'est la reconnaissabilité, qui permet d'utiliser des programmes plutôt que des algorithme pour décider :

Définition

Un problème de décision est reconnaissable s'il existe un programme qui prend en paramètres les entrées du problème et :

  • s'arrête que pour les réponse OUI
  • ne s'arrête pas les réponses NON

Il est clair qu'un problème décidable est reconnaissable, il suffit de laisser tourner indéfiniment le décideur plutôt que de lui faire répondre NON, mais la réciproque est fausse, le problème de l'arrêt étant clairement reconnaissable (il suffit de laisser tourner l'algorithme et s'il s'arrête répondre OUI).

De même que pour les ensembles décidables, on défini par extension les ensembles reconnaissables comme étant ceux pouvant être énumérés par un programme :

Définition

Un ensemble $E$ d'entiers est reconnaissable s'il existe un programme $A$ qui tel que :

  • $A(n)$ vaut OUI si $n \in E$
  • $A(n)$ ne s'arrête pas si $n \notin E$

Il existe bien sur des ensembles reconnaissable et non décidable, par exemple l'ensemble des numéros de programmes qui sont des algorithmes.

Exemple

Nous allons finir cette partie en montrant deux exemples de problèmes qui ont fait grand bruit à l'époque.

Racines de polynômes à coefficients dans $\mathbb{Z}$

Problème de décision

  • nom : racine polynôme
  • données : $P(X)$ un polynôme à coefficients dans $\mathbb{Z}$
  • question : $P(X)$ Possède-t-il une racine dans $\mathbb{N}$ (un entier $a$ tel que $P(a) = 0$) ?

Ce problème est reconnaissable :

Proposition

Le problème de décision racine polynôme est reconnaissable.

preuve

On peut facilement créer un algorithme qui, à partir d'un polynôme $P(x)$ à coefficients dans $\mathbb{Z}$ et d'un entier $a$ calcule $P(a)$.

Il suffit ensuite d'essayer tous les entiers un à un. Si le polynôme en entrée admet une racine entière, on va bien tomber dessus à un moment donné.

Il est même décidable !

Proposition

Les racine d'un polynôme $P(X) = \sum_{i=0}^na_iX^i$ (avec $a_n \neq 0$) sont bornées par $\max( 1, \frac{\sum_{i=0}^{n-1}\mid a_i\mid}{\mid a_n\mid})$.

preuve

On va montrer que pour tout $\mid X \mid > \max( 1, \frac{\sum_{i=0}^{n-1}\mid a_i\mid}{\mid a_n\mid})$, on a $\mid P(X)\mid > 0$.

On a en effet la suite d'implications suivantes :

$$ \begin{array}{lcll} \mid X \mid & > & \frac{\sum_{i=0}^{n-1}\mid a_i\mid}{\mid a_n\mid}&\mbox{et } \mid X \mid > 1\\ \mid a_n X^n \mid & > & \sum_{i=0}^{n-1}(\mid a_i X^{n-1} \mid)&\\ \mid a_n X^n \mid & > & \mid a_{n-1}X^{n-1}\mid + \mid X \mid \cdot \sum_{i=0}^{n-2}(\mid a_i X^{n-2} \mid)&\\ \mid a_n X^n \mid & > & \mid a_{n-1}X^{n-1}\mid + \sum_{i=0}^{n-2}(\mid a_i X^{n-2} \mid)& \mbox{car } \mid X \mid > 1\\ \mid a_n X^n \mid & > & \dots&\\ \mid a_n X^n \mid & > & \sum_{i=0}^{n-1}\mid a_i X^{i} \mid&\\ \mid a_n X^n \mid & > & \mid \sum_{i=0}^{n-1} a_i X^{i} \mid&\\ \end{array} $$

Ce qui prouve que $\mid P(X) \mid = \mid a_nX^n + \sum_{i=0}^{n-1} a_i X^{i}\mid$ sera toujours non nul et du signe de $a_n$ pour tout $\mid X \mid > \max( 1, \frac{\sum_{i=0}^{n-1}\mid a_i\mid}{\mid a_n\mid})$

Corollaire

Le problème de décision racine polynôme est décidable.

preuve

Toutes les racines du polynôme sont bornées par un nombre calculable, on pourra stopper l'algorithme d'énumération au bout d'un nombre déterminé d'itérations.

Racines de polynômes à plusieurs variables à coefficients dans $\mathbb{Z}$

En revanche les choses se corsent pour le problème ci-après, généralisation de racine polynôme :

Problème de décision

  • nom : racine polynôme plusieurs variables
  • données : $P(X)$ un polynôme à plusieurs variables à coefficients dans $\mathbb{Z}$
  • question : $P(X)$ Possède-t-il une racine dans $\mathbb{N}$ (un entier $a$ tel que $P(a) = 0$) ?

Théorème

Le problème Racine polynôme plusieurs variables est un problème reconnaissable mais indécidable.

éléments de preuve

Cela a été démontré en 1970 par Matiiassevitch en prouvant que tout ensemble reconnaissable peut constituer les racines d'un polynôme à plusieurs variables. De là, si le problème Racine polynôme plusieurs variables était décidable, tout ensemble reconnaissable le serait aussi, ce qui est impossible.

Ce cas est historiquement important car il correspond au dixième problème de Hilbert.