What is a problem?

Reading time5 min

En bref

Résumé de l’article

Les algorithmes sont utilisés pour résoudre des problèmes ? Mais que entend-on par problèmes ? Existe-t-il différents types de problèmes ?

Points clés

Les problèmes peuvent être vus comme des fonctions d’un domaine vers un codomaine.
Une instance d’un problème peut avoir une solution, calculée via un algorithme.
Un problème de décision a un codomaine booléen.
Un problème de recherche est un problème pour lequel il existe plusieurs solutions.

Contenu de l’article

1 — Une définition simple d’un problème comme une fonction

Vous avez déjà implémenté des algorithmes sous forme de fonctions Python, mais on peut aussi considérer que les problèmes sont définis par des fonctions mathématiques. Fondamentalement, on peut dire qu’un problème est défini par une fonction sur un domaine $I$ (pour Input) et un codomaine $S$ (pour Solution).

Un algorithme $A$ résout un problème $f : I \rightarrow S$, si pour tout $e \in I$ tel que $f$ est défini sur $e$, l’algorithme $A$ appliqué à $e$ termine en un temps fini et produit le résultat $f(e)$.

Chaque élément $e$ définit une instance du problème (on dit aussi que $e$ paramètre le problème) et $f(e)$ est la solution du problème. La fonction $f$ est partielle : il existe des éléments $e \in I$ auxquels $f$ ne peut pas être appliquée. Cela correspond à des instances du problème qui n’ont pas de solution. Alternativement, on peut considérer $f$ comme une fonction totale en ajoutant à $S$ un élément spécial, disons fail, qui est retourné s’il n’y a pas de solution.

Un problème de décision est simplement un problème défini par une fonction $f : I \rightarrow \mathbb{B}$, où $\mathbb{B}$ est l’ensemble des booléens. La solution est binaire, elle est soit true soit false.

2 — Problèmes de recherche

Qu’en est-il du cas où il y a plusieurs solutions ? Dans ce cas, on dit que le problème est un problème de recherche. Il est tentant de modéliser un tel problème avec une fonction $f : I \rightarrow 2^S$, où $2^S$, aussi noté $\mathcal{P}(S)$, est l’ensemble des parties de $S$. Un élément de $2^S$ est en effet un ensemble d’éléments de $S$, c’est-à-dire un ensemble de solutions. Un ensemble vide signifie qu’il n’y a pas de solution. Mais nous ne sommes pas toujours intéressés par le calcul de toutes les solutions. On peut aussi imaginer des situations où toutes les solutions ne peuvent pas être calculées en un temps fini !

Une définition plus générale d’un problème de recherche repose sur des relations plutôt que sur des fonctions. Voici une telle définition :

Un problème de recherche avec un domaine d’entrée $I$ et un codomaine de solutions $S$ est défini par une relation $R \subset I \times S$. Un algorithme $A$ résout un problème de recherche $R$ si, pour toute entrée $e \in I$, l’algorithme $A$ appliqué à $e$ produit une solution $s$ telle que $R(e, s)$ (ou $(e, s) \in R$, un ensemble de paires), si une telle solution existe.

Ici, l’algorithme produit une solution unique. Il est aussi possible de définir un problème de recherche exhaustive en utilisant une fonction comme discuté ci-dessus.

3 — Problème d’optimisation

Un problème d’optimisation est un raffinement d’un problème de recherche $R$ où, au lieu d’obtenir n’importe quelle solution, on veut obtenir la meilleure. Ici, meilleure est définie par une fonction de coût, c’est-à-dire une fonction $c: S \rightarrow \mathbb{R}^+$. Résoudre un tel problème pour une entrée $e$ produit une solution $s$ au problème de recherche telle que $c(s)$ est minimale.

Tout problème d’optimisation peut être transformé en problème de décision en définissant une borne et en reformulant le problème comme suit :

Pour une entrée donnée, existe-t-il une solution avec un coût inférieur ou égal à la borne ?

Pour aller plus loin

Il semble que cette section soit vide !

Y a-t-il quelque chose que vous auriez aimé voir ici ? Faites-le nous savoir sur le serveur Discord ! Peut-être pouvons-nous l’ajouter rapidement. Sinon, cela nous aidera à améliorer le cours pour l’année prochaine !

Pour aller au-delà

Il semble que cette section soit vide !