La racine du problème

racines.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# À la racine du problème\n",
    "\n",
    "## Approche conceptuelle, approche procédurale\n",
    "\n",
    "La [priorité](https://liberalisme-democratique.fr/strategie-numerique-pour-leducation-2023-2027/) donnée au renforcement des compétences numériques dès le cycle 4 aboutira sans doute à une modification des programmes de mathématiques. L'étude de la notion de fonction en 3<sup>e</sup> par exemple concernera des élèves qui manipulent des objets très similaires depuis la 5<sup>e</sup>.\n",
    "\n",
    "Les fonctions informatiques (procédures) peuvent en effet souvent sembler très proches des fonctions mathématiques. Elles spécifient une valeur déterminée par un ou plusieurs paramètres. Par exemple, `square` donne le carré d'un nombre :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4/9"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(define (square x)\n",
    "  (* x x))\n",
    "\n",
    "(square 2/3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et `average` retourne la moyenne des deux nombres donnés en arguments :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13.75"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(define (average x y)\n",
    "  (/ (+ x y) 2))\n",
    "\n",
    "(average 17 10.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mais il y a une différence importante entre les procédures et les fonctions mathématiques. Les procédures doivent être _effectives_.\n",
    "\n",
    "Le calcul de la racine carrée permet d'illustrer la différence. On peut définir la fonction racine carrée comme ça :\n",
    "\n",
    "$$\\sqrt{x}=\\,\\text{le}\\,y \\,\\text{tel que}\\, y \\geq 0\\, \\text{et} \\, y^{2}=x$$\n",
    "\n",
    "Et c'est une description mathématique tout à fait acceptable. On peut s'en servir pour reconnaître si un nombre est la raciné carrée d'un autre ou dériver des faits sur les racines carrées en général. Mais cette définition ne décrit pas une procédure. Elle ne nous dit quasiment rien sur comment trouver la racine carré d'un nombre en pratique. Donner à cette définition la forme de lignes de code ne nous aide évidemment pas."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "ename": "unbound-variable",
     "evalue": "Unbound variable: y",
     "output_type": "error",
     "traceback": [
      "\u001b[31mUnbound variable: y\u001b[0m"
     ]
    }
   ],
   "source": [
    "(define (sqrt x)\n",
    "  (le y (and (>= y 0)\n",
    "             (= (square y) x))))\n",
    "\n",
    "(sqrt 9)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le contraste entre les fonctions et les procédures renvoie à la différence entre le fait de décrire les _propriétés_ d'un objet et le fait d'en décrire une _méthode de construction_. Entre une connaissance conceptuelle et une connaissance procédurale, impérative, de l'objet. Les mathématiques s'intéressent plutôt aux descriptions conceptuelles. Les programmeurs de leur côté manipulent la plupart du temps des descriptions impératives.\n",
    "\n",
    "Comment trouver la racine carrée d'un nombre ? La [méthode de Héron](https://fr.wikipedia.org/wiki/M%C3%A9thode_de_H%C3%A9ron) est une méthode efficace. Pour déterminer la racine carrée du nombre (positif) $a$, on utilise la récurrence suivante : \n",
    "\n",
    "$$ \\forall n \\in \\mathbb{N}\\quad x_{n+1} = \\frac{x_{n} + \\frac{a}{x_n}}{2} $$\n",
    "\n",
    "En d'autres termes, à chaque fois qu'on a une proposition $x$ pour la racine carré d'un nombre a, on peut obtenir une meilleure proposition en prenant la moyenne de $x$ et de $\\displaystyle\\frac{a}{x}$. Chaque nouvelle proposition est une meilleure approximation de la racine carrée. \n",
    "\n",
    "On peut formaliser ce processus itératif avec des procédures. On commence avec le nombre $x$ dont on essaie de trouver la racine carrée et une première approximation (`guess`) qu'on améliore immédiatement (`new-guess`). Si cette nouvelle approximation est acceptable, ce sera notre résultat. Sinon, on répète l'opération mais avec la nouvelle approximation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (sqrt-iter x guess)\n",
    "  (let ((new-guess (improve guess x)))\n",
    "    (if (good-enough? guess new-guess)\n",
    "      new-guess\n",
    "      (sqrt-iter x new-guess))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On améliore une proposition `guess` en prenant la moyenne de `guess` et de $\\displaystyle\\frac{x}{guess}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (improve guess x)\n",
    "  (average guess (/ x guess)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une proposition est satisfaisante quand la différence d'une proposition à l'autre est une toute petite fraction de l'ancienne proposition."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (good-enough? guess new-guess)\n",
    "    (< (/ (abs (- new-guess guess))\n",
    "          guess)\n",
    "       1e-10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "On commence le processus de recherche avec 1 comme première approximation. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (sqrt x)\n",
    "  (sqrt-iter x 1.0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et, bien sûr, on teste notre procédure."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.4142135623730951"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(sqrt 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Abstractions et généralité\n",
    "L'implémentation de l'algorithme est correcte mais son design peut être amélioré — l'idée sous-jacente n'est pas exprimée sous une forme généralisable. La solution telle qu'on l'a écrite n'est pas faite d'éléments qu'on peut isoler et réutiliser pour la solution d'autres problèmes.\n",
    "\n",
    "Les langages de programmation modernes limitent très peu notre capacité à créer des abstractions, notamment procédurales, à les nommer et à les traiter comme des éléments primitifs du langage. Entre autres, il est possible de passer des fonctions (procédure) en paramètre d'autres fonctions. Ou une fonction peut elle-même être le résultat de l'application d'une fonction. C'est cette liberté qui permet une grande flexibilité dans le design des programmes.\n",
    "\n",
    "Il y a une manière plus claire d'exprimer l'algorithme de Héron. On cherche en fait ici un _point fixe_ — la racine carrée de $x$ est le nombre $y$ tel que $y = x/y$. En d'autres termes, $y$ est un point fixe de la fonction $f : y \\to \\frac{x}{y}$, qu'on exprime dans notre langage par"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(lambda (y) (/ x y))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour trouver le point fixe d'une fonction, on peut, dans les cas favorables, itérer la fonction jusqu'à que le résultat soit très proche de l'argument donné. On donne à `fixed-point` une fonction `f` et une valeur initiale et on ne s'arrête d'appliquer `f` que lorsque les valeurs successives sont proches l'une de l'autre (pensez à un élève qui ne cesse d'appuyer sur une touche de sa calculatrice jusqu'à que le résultat ne change plus)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (fixed-point f value)\n",
    "  (let ((new-value (f value)))\n",
    "    (if (good-enough? value new-value)\n",
    "        new-value\n",
    "        (fixed-point f new-value))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cette fonction fonctionne pour trouver le point fixe de cosinus,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ".7390851331949863"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(fixed-point cos 1.0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "mais ne convergera pas si on l'applique à $f : y \\to \\frac{x}{y}$. Elle alternera au contraire sans cesse entre deux pôles opposés de la racine carrée. Cette fonction ne donnera donc jamais aucun résultat :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (sqrt x)\n",
    "  (fixed-point (lambda (y) (/ x y)) 1.0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut forcer la convergence en prenant des moyennes. La fonction `average-damp` prend en argument une fonction `f` et donne comme résultat une fonction qui a le même point fixe que `f` mais dont les oscillations sont amorties en prenant la moyenne des valeurs successives."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (average-damp f)\n",
    "  (lambda (x)\n",
    "    (average x (f x))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et on a enfin une fonction `sqrt` qui est non seulement correcte mais qui est formée par la composition d'éléments plus généraux, utilisables dans d'autres contextes — comment trouver le point fixe d'une fonction et comment encourager la convergence par amortissement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.414213562373095"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(define (sqrt x)\n",
    "  (fixed-point (average-damp (lambda (y) (/ x y)))\n",
    "               1.0))\n",
    "\n",
    "(sqrt 2)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "MIT Scheme",
   "language": "scheme",
   "name": "mit-scheme"
  },
  "language_info": {
   "codemirror_mode": "scheme",
   "file_extension": ".scm",
   "mimetype": "application/x-scheme",
   "name": "MIT Scheme",
   "pygments_lexer": "scheme",
   "version": "9.2.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}