.. index:: problème Problème ======== .. highlight:: none 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 : .. list-table:: * - 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, la solution 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. .. index:: single: problème; plus général single: problème; plus spécifique pair: problème; classe pair: problème; instance 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 : .. list-table:: * - 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. Spécification d'un problème +++++++++++++++++++++++++++ .. index:: pair: problème; spécification see: entrée; paramètre d'entrée see: sortie; paramètre de sortie Tout problème peut se décrire par un ensemble d'éléments de ces quatre types : .. glossary:: paramètre d'entrée un paramètre nommé qui caractérise une instance du problème ; en d'autres termes, c'est un élément variable de l'*énoncé* du problème. pré-condition une condition que doivent vérifier les paramètres d'entrée ; en dehors de cette condition, le problème n'a pas de sens. paramètre de sortie un paramètre qui caractérise la solution à une instance du problème ; en d'autre terme, c'est un élément de la *réponse* au problème. post-condition une condition que doivent vérifier les paramètres d'entrée et de sortie ; en dehors de cette condition, la solution apportée au problème n'est pas correcte. Si une spécification est complète : * toute instance du problème doit pouvoir être décrite par un ensemble de valeurs pour les paramètres d'entrée ; * inversement, tout jeu de valeur données aux paramètres d'entrée et vérifiant les pré-conditions doit correspondre à une instance du problème. Dans la suite, on rédigera les spécifications ainsi : * chaque paramètre d'entrée est introduit par le texte ``:entrée x:`` (où ``x`` est le nom de ce paramètre) suivi du type d'information concerné ; * chaque pré-condition est introduite par le texte ``:pré-cond:``\  ; * chaque paramètre de sortie est introduit par le texte ``:sortie x:`` (où ``x`` est le nom ou le numéro d'ordre de ce paramètre) suivi du type d'information concerné ; * chaque post-condition est introduite par le texte ``:post-cond:``. Application aux exemples ++++++++++++++++++++++++ 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 : * `n`, `p` et `r` sont des entiers positifs (on ne peut pas avoir ou donner un nombre négatif de bonbons, et on considère en général qu'on ne partage pas un bonbon en deux) ; * `p` est nécessairement inférieur ou égal à `n` (Alice ne peut pas donner plus de bonbons qu'elle n'en possède). 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 `variables`:doc:). 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\ [#gps]_. .. _specif≠code: Importance et limites de la spécification +++++++++++++++++++++++++++++++++++++++++ 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\ [#syntaxe-spec]_. 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 : * pour un ordinateur, le passage de la première à la deuxième expression n'est pas trivial ; * pour un élève de CP, même la deuxième expression n'est pas triviale, puisqu'il doit poser la soustraction et appliquer, étape après étape, l'algorithme correspondant. La proximité entre post-condition et solution est donc *relative* aux capacités de l'exécutant de l'algorithme. Différentes façon de transmettre les valeurs des paramètres +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Comme nous l'avons mentionné plus haut, les entrées sont les données du problème et les sorties sont les solutions, ou les réponses au problème. Si l'on considère un algorithme comme une boîte noire 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. Données saisies par l'utilisateur, affichage à l'écran `````````````````````````````````````````````````````` Lorsque l'on écrit nos premiers algorithmes, c'est souvent l'utilisateur qui fournit les valeurs des paramètres d'entrées, et les valeurs en sortie sont simplement affichées à l'écran. 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 Données transmises par un autre algorithme `````````````````````````````````````````` Plus tard, nos algorithme vont utiliser des données qui proviennent d'autres algorithmes, et vont également devoir transmettre leurs résultats de sorte à ce qu'ils puissent être exploités ensuite par d'autres algorithmes. 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 .. hint:: Le term « affecté » fait référence à la notion d'`affectation`:term:, qui sera présentée au chapitre suivant. Fonctions, procédures ````````````````````` Lorsque l'on définit une `fonction `:ref: ou une `procédure`:term:, le contrat explicite ses entrées et ses sorties. 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 la fonction `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 On vera dans le chapitre `fonction`:ref: qu'en pratique, on peut simplifie cette écriture. .. rubric:: Notes de bas de page .. [#gps] C'est d'ailleurs ce qui est fait dans les logiciels de navigation par GPS. .. [#syntaxe-spec] Elle est cependant compatible avec certains générateurs de documentation utilisés avec Python.