Si un algorithme décrit sans ambiguïté une méthode de résolution de problème (le « comment »), il convient d’être capable de décrire le problème à résoudre (le « quoi ») avec le moins d’ambiguïté possible.
Distinguons tout d’abord deux types de problèmes :
Encadrer la racine carrée de 10 par deux entiers successifs. | Encadrer la racine carrée d’un nombre réel positif x par deux entiers successifs. |
Alice a dix bonbons. Elle en donne deux à Bob. Calculer combien il reste de bonbons à Alice. | Alice a n bonbons. Elle en donne p à Bob. Calculer combien il reste de bonbons à Alice. |
Trouver le plus court chemin de l’IUT à la place Bellecour. | Trouver le plus court chemin entre deux adresses a et b à Lyon. |
Les problèmes de la colonne de gauche ne sont pas intéressants d’un point de vue algorithmique, car ils ont une réponse unique. Résoudre le problème consiste donc simplement à donner la bonne réponse.
Les problèmes de la colonne de droite, en revanche, sont plus intéressants. En effet, le résultat variera en fonction de paramètres (x, n, p, a, b dans les exemples ci-dessus) non spécifiés dans l’énoncé du problème. Un algorithme répondant à chacun de ces problèmes devra donc fonctionner quelles que soient les valeurs prises par ces paramètres.
On remarque par ailleurs que, si on dispose d’un algorithme permettant de résoudre chaque problème de droite, on est alors en mesure de résoudre, en particulier, le problème de gauche correspondant. On dit que le problème de droite est plus général que le problème de gauche, et que le problème de gauche est plus spécifique que le problème de droite. On dit également que le problème de gauche est une instance du problème de droite. Enfin, lorsqu’on parle d’un problème général (comme ceux de la colonne de droite) on parle parfois d’une classe de problèmes (pour bien faire ressortir le fait que le problème admet plusieurs instances).
Cette relation de généralisation ne se limite pas à deux niveaux. On peut par exemple trouver des problèmes encore plus généraux que ceux de la colonne de droite, respectivement :
Encadrer la racine carrée d’un nombre réel positif x par deux nombres distants de δ. |
Alice a n bonbons. Elle en donne p à Bob et q à Charles. Calculer combien il reste de bonbons à Alice. |
Trouver le plus court chemin entre deux adresses a et b en France. |
Tout problème peut se décrire par un ensemble d’éléments de ces quatre types :
Si une spécification est complète :
Dans la suite, on rédigera les spécifications ainsi :
:entrée x:
(où x
est le nom de ce paramètre)
suivi d’une description de ce paramètre ;:pré-cond:
;:sortie x:
(où x
est le nom de ce paramètre)
suivi d’une description de ce paramètre ;:post-cond:
.Reprenons le premier problème de nos exemples précédents : « encadrer la racine carrée d’un nombre réel positif ». On écrira ainsi sa spécification :
:entrée x: réel
:pré-cond: x ≥ 0
:sortie inf: entier
:sortie sup: entier
:post-cond: inf ≤ √x < sup
:post-cond: |sup - inf| = 1
Le problème porte sur n’importe quel nombre réel positif, donc toute valeur de x vérifiant la pré-condition décrit bien une instance du problème. Tout couple de valeur vérifiant les post-conditions représente bien la solution du problème : la première post-condition garantit que inf et sup encadrent bien la racine carrée de x, tandis que la seconde garantit qu’ils sont successifs.
Prenons le deuxième problème, concernant les bonbons d’Alice :
:entrée n: entier
:entrée p: entier
:pré-cond: 0 ≤ p ≤ n
:sortie r: entier
:post-cond: r + p = n
Dans la spécification ci-dessus, on remarque plusieurs choses. Tout d’abord, certaines pré-conditions ne sont pas explicites dans l’énoncé en français du problème, mais en ont été déduites :
Sous ces conditions, tout couple de valeurs pour n et p représente bien une situation possible entre Alice et Bob. Par ailleurs, tout entier r vérifiant la post-condition est bien la solution au problème.
Le troisième exemple de problème, recherchant un chemin dans Lyon, peut se spécifier ainsi :
:entrée a: adresse
:entrée b: adresse
:pré-cond: a est à Lyon, b est à Lyon
:sortie c: chemin
:post-cond: c va de a vers b ;
pour tout chemin c' allant de a vers b,
longueur(c') > longueur(c)
Cette spécification est plus complexe que les précédentes, notamment parce qu’elle fait appel à des notions (adresse, chemin) qui ne sont en général pas directement connues de l’ordinateur (comme on le verra au chapitre Valeurs, expressions et variables).
Gardons cependant en tête que la spécification d’un problème et l’écriture d’un algorithme ne sont pas des tâches spécifiques à l’informatique. En toute généralité, cette spécification est donc correcte. De plus, vous verrez plus tard qu’il est possible de définir de nouveaux types de données et ainsi d’« apprendre » à l’ordinateur ce qu’est une adresse ou un chemin. Dans ce cas, notre spécification deviendrait utilisable même dans un contexte informatique, et on pourrait écrire l’algorithme correspondant [1].
Rappelons que la spécification n’est pas destinée à l’exécutant de l’algorithme, mais à celui ou celle qui écrira cet algorithme. Dans un contexte informatique, elle est donc destinée au programmeur, et non à l’ordinateur. Or le programmeur, contrairement à l’ordinateur, est capable d’initiative, et est donc capable d’interpréter l’énoncé d’un problème, même en français. D’ailleurs la notation proposée ci-dessus pour décrire la spécification d’un problème ne fait pas partie de la syntaxe de Python [2]. On pourrait donc être tenté de négliger l’étape de spécification.
Cette étape est pourtant extrêmement importante. Tout d’abord, elle sert à identifier les paramètres d’entrée et de sortie, qui sont obligatoires pour l’écriture de l’algorithme.
De plus, elle force à interpréter l’énoncé du problème (voir l’exemple des bonbons d’Alice ci-dessus) et à se poser des questions sur les ambiguïtés qui pourraient demeurer. Par exemple, est-ce qu’Alice peut ne donner aucun bonbon à Bob (p = 0) ; est-ce qu’Alice peut n’avoir aucun bonbon au départ (n = 0) ? À ce titre, la spécification est un outil très utile de communication et de négociation entre les différentes personnes amenées à travailler sur un algorithme.
La rédaction des post-conditions est notamment particulièrement importante,
puisque ce sont elles qui permettront de vérifier
si l’algorithme fournit des solutions correctes ou non.
Dans certains cas simples,
la post-condition peut d’ailleurs sembler se confondre avec la solution.
Prenons l’exemple des bonbons d’Alice ;
quiconque ayant quelques notions d’algèbre verra que
la post-condition qu’on a écrite (r + p = n
)
nous donne un moyen d’écrire la solution (r = p - n
).
Notons cependant que :
La proximité entre post-condition et solution est donc relative aux capacités de l’exécutant de l’algorithme.
Comme nous l’avons mentionné plus haut, les entrées sont les données du problème et les sorties sont les résultats, ou les réponses au problème. Si l’on considère un algorithme comme une boîte dont le rôle est de résoudre un problème, alors les entrées sont les données transmises à la boîte et les sorties sont les résultats retournés par la boîte.
Il est important d’observer que les entrées et les sorties peuvent prendre des formes différentes.
Lorsque l’on écrit nos premiers algorithmes,
on a souvent besoin de demander des données
à l’utilisateur (on parle souvent d’inputs
,
et on affiche souvent les résultats directement
à l’écran.
Par exemple, si vous écrivez l’algorithme qui permet de calculer la factorielle d’un nombre, vous demanderez à l’utilisateur de saisir un nombre, et vous afficherez à l’écran la factorielle de ce nombre.
En Python, on utilise les instructions input
et print
respectivement pour demander une
valeur à un utilisateur et pour afficher un
résultat à l’écran (sortie standard.
On formalise ce mode de passage dans le contrat de la façon suivante
:entrée n: entier, SAISI au clavier
:pré-cond: n ≥ 0
:sortie f: entier, AFFICHÉ à l'écran
:post-conf: f = n! = 1×2×3×...×n
Très souvent, nos algorithme vont utiliser des données qui proviennent d’un autre algorithme et vont également devoir transmettre leurs résultats de sorte à ce qu’ils puissent être exploités par la suite.
Par exemple, imaginons que l’on souhaite calculer
la factorielle de la valeur absolue d’un nombre.
On va d’abord demander à l’algorithme valeur_absolue
de calculer la valeur absolue du nombre, puis ensuite,
on va passer ce nombre à l’algorithme de factorielle
qui va nous en calculer la factorielle.
Dans ce cas, on va écrire un contrat un peu différent
:entrée n: entier, AFFECTÉ précédemment
:pré-cond: n ≥ 0
:sortie f: entier, AFFECTÉ pour la suite
:post-conf: f = n! = 1×2×3×...×n
Lorsque l’on définit une fonction ou une procédure, le contrat explicite les entrées et aux sorties de la fonction ou de la procédure.
En Python, au sein de la fonction, les sorties sont
retournées grâce au mot clé return
Voici le squelette général d’un contrat (ou spécification formelle) d’une fonction (en l’occurrence, il s’agit de factorielle)
:entrée n: entier, PASSÉ en paramètre
:pré-cond: n ≥ 0
:sortie f: entier, RETOURNÉ
:post-conf: f = n! = 1×2×3×...×n
Notes de bas de page
[1] | C’est d’ailleurs ce qui est fait dans les logiciels de navigation par GPS. |
[2] | Elle est cependant compatible avec certains générateurs de documentation utilisés avec Python. |