informatique_embarquee_INTRO_FONCTIONS-DILLMANN.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Première introduction aux fonctions et aux algorithmes en langage python\n",
    "\n",
    "\n",
    "**Concept de fonction :**\n",
    "Une fonction est un bloc permettant d’organiser et d’éviter les répétitions de code. Elle joue un rôle important pour la *modularité* du code, c'est à dire la capacité de transporter dans un code des librairies de fonctionalitées qui peuvent être importées. Les fonction présentées ici possèdent un nom, d’eventuels paramètres entre parenthèses (les arguments), un ensemble d’instructions définies dans un bloc délimité, et l'instruction return.\n",
    "\n",
    "Une fonction est un outil fondamental de programmation qui permet de transformer des donnée en entrée (appelés arguments) par des résultats en sortie. Sa syntaxe est très formelle : \n",
    "\n",
    "~~~python\n",
    "def NOM_DE_LA_FONCTION (argument1):\n",
    "    return resultat\n",
    "~~~\n",
    "\n",
    "Notez bien les deux points après la déclaration de l'argument, ainsi que l'indentation (l'espace au début de la ligne où se trouve la commande \n",
    "~~~python\n",
    "    return\n",
    "~~~\n",
    "qui renvoie le produit de la fonction. L'exemple suivant peut être utile."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Des fonctions pour des opérations mathématiques simples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# définition d'une fonction dans python\n",
    "def carre (chiffre):\n",
    "    return chiffre*chiffre"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une fois la fonction déclarée elle peut être appellée à tout moment pour la plus grande joie du programmeur qui n'a plus à réfléchir sur la manière dont on obtient un carré (ici c'est clairement de la paresse...)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "25"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# si vous avez executé la cellule précédente vous pouvez\n",
    "# \"appeler\" votre fonction\n",
    "\n",
    "# Appel de la fonction avec l'argument 'entier'\n",
    "carre(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# programmez une fonction appellée plus_deux\n",
    "# qui renvoie la valeur \n",
    "# donnée en entrée plus deux \n",
    "def plus_deux(chiffre):\n",
    "    pass\n",
    "# En remplaçant le mot clef 'pass' par 'return'\n",
    "# et en ecrivant après return la valeur de sortie"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Par exemple\n",
    "# l'execution de cette cellule doit donner 6\n",
    "plus_deux(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Supposons que l'on veux calculer l'aire d'un cercle $A=\\pi.r^2$, où $r$ est le rayon, qui peux être variable et $\\pi=3.14159$ pour simplifier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "L'aire du disque de rayon 11.2 m, est A = 394.0810495999999 m2\n"
     ]
    }
   ],
   "source": [
    "# Declaration des Variables\n",
    "𝜋 = 3.14159\n",
    "r = 11.2\n",
    "A = 𝜋*r**2\n",
    "\n",
    "print(\"L'aire du disque de rayon \"+ str(r) +\" m, est A = \" + str(A) + \" m2\")\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Ecrivez une fonction qui renvoie l'aire quand \n",
    "# le rayon d'un disque est envoyé\n",
    "def aire(rayon):\n",
    "    #Modifiez la ligne suivante :\n",
    "    # Declaration des Variables locales\n",
    "    A = 0\n",
    "    # fin de la modification\n",
    "    return A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Des fonctions pour afficher des tableaux"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Certaines fonctions n'ont pas pour objectif de renvoyer une variable en particulier. Mais elle peuvent utiliser d'autres fonctions comme `print()` on va voire dans cet exemple que des fonction peuvent appeller d'autre fonctions. Une fonction peut avoir une autre fonction comme argument d'entrée."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Ici une fonction qui imprime quelque chose de visuel\n",
    "# Ces fonctions ne retourne pas de variables de sortie\n",
    "\n",
    "def faire_deux_fois(f):\n",
    "    \n",
    "    \"\"\"\n",
    "    Cette fonction à ce que l'on appelle un \"docstring\"\n",
    "    elle execute deux fois la fonction f\n",
    "    \n",
    "    Ce programme se trouve appellé par les fonctions suivantes :\n",
    "    \n",
    "    - faire_huit_fois()\n",
    "    - imprimer_pilliers()\n",
    "    - imprimer_poutres()\n",
    "\n",
    "    \"\"\"\n",
    "    f()\n",
    "    f()\n",
    "\n",
    "def faire_huit_fois(f):\n",
    "    \n",
    "    \"\"\"\n",
    "    Usage :\n",
    "     faire_huit_fois(function)\n",
    "     L'appel de cette fonction fait appel à une autre fonction\n",
    "     qu'elle appelle huit fois.\n",
    "    \n",
    "    Entrée :\n",
    "     La fonction f est passée à la fonction comme un argument\n",
    "    \n",
    "    Liens de dépendence :\n",
    "     Ce programme est utilisé par la fonction suivante :\n",
    "    \n",
    "    -imprimer_grid()\n",
    "\n",
    "\n",
    "    \"\"\"\n",
    "    faire_deux_fois(f)\n",
    "    faire_deux_fois(f)\n",
    "    faire_deux_fois(f)\n",
    "    faire_deux_fois(f)\n",
    "    \n",
    "\n",
    "def imprimer_poutre():\n",
    "    print('| - - - - ',end=\" \"),\n",
    "\n",
    "def imprimer_pillier():\n",
    "    print('|         ',end=\" \"),\n",
    "\n",
    "def imprimer_poutres():\n",
    "    faire_deux_fois(imprimer_poutre)\n",
    "    print('|',end=\"\\n\")\n",
    "\n",
    "def imprimer_pilliers():\n",
    "    faire_deux_fois(imprimer_pillier)\n",
    "    print('|',end=\"\\n\")\n",
    "\n",
    "def imprimer_ligne():\n",
    "    imprimer_poutres()\n",
    "    \n",
    "def imprimer_tableau():\n",
    "    imprimer_ligne()\n",
    "    faire_huit_fois(imprimer_pilliers)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On utilise au début de chaque fonction un `docstring` en rouge qui permet de définir la fonction et qui est très utile au moment de faire `? fonction` pour demander de l'aide. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|  Premier | Second   |\n",
      "| - - - -  | - - - -  |\n",
      "|          |          |\n",
      "|          |          |\n",
      "|          |          |\n",
      "|          |          |\n",
      "|          |          |\n",
      "|          |          |\n",
      "|          |          |\n",
      "|          |          |\n"
     ]
    }
   ],
   "source": [
    "Titre1='Premier'\n",
    "Titre2='Second '\n",
    "print('|  '+Titre1+' | '+Titre2+'  |')    \n",
    "imprimer_tableau()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recopiez le tableau dans cette cellule affin de voire s'il à été mis en forme correctement."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Des fonctions pour se répartir le travail"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut se poser la question de l'utilité d'une fonction dans des cas aussi simples : un calcul de carré et la fabrication d'un tableau tout cela n'est pas très sérieux... Dans l'exemple suivant on s'interesse à la juste retribution des employés d'une entreprise. Même s'il s'agit d'une exploitation agricole en Galilée il y a deux mille ans, cela ne change pas grand chose au problème.\n",
    "\n",
    "Nous allons voire que la fonction permet de gérer de façon beaucoup plus neutre l'attribution d'un salaire aux différentes personnes de cette explotation.\n",
    "\n",
    "La question qui se pose est la suivante : \n",
    "\n",
    "*\" Comment s'y prendre pour que le nom des employés, arrivés en dernier, et qui vont gagner autant que leurs camarades qui ont été plus ou moins longtemps au service de l'exploitation reste confidentiel. Et cela afin de leur éviter aux derniers d'être proie à la jalousie de leurs colègues ? \"*\n",
    "\n",
    "Cela peut sembler trivial mais les augmentation sont souvent l'objet de conflits dans une entreprise au XXI ème sciècle, et l'histoire prouve que cela n'est pas nouveau : il n'y a qu'a penser aux ouvriers de la dernière heure qui reçoivent le même salaire que ceux du matin (Matthieu XX, 11-12).\n",
    "~~~~\n",
    "En la recevant, ils récriminaient contre le maître du domaine. “Ceux-là, les derniers   venus, n’ont fait qu’une heure, et tu les traites à l’égal de nous, qui avons enduré le poids du jour et la chaleur !”\n",
    "~~~~\n",
    "\n",
    "Donc imaginons que celui qui doit féliciter les employés le fasse avec une fonction..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Voici une première fonction qui prépare la formule de félicitations\n",
    "def salaire_agent(serviteur):\n",
    "    s='Très bien,'+serviteur.upper()+' : tu a gagné une pièce d’argent'\n",
    "    return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Voici maintenant une autre fonction qui appelle la première pour les payer\n",
    "# sans jamais donner le nom des serviteurs, \n",
    "# et surtout en permetant de rajouter quelqu'un en fin de liste.\n",
    "# Tout cela, histoire que ce soit une bonne surprise pour ceux-cis (les derniers)\n",
    "# et une surprise tout court pour ceux-las (les premiers)\n",
    "\n",
    "def fin_de_journee(agents):\n",
    "    for agent in agents:\n",
    "        s=salaire_agent(agent)\n",
    "        print('Pour le sérviteur {}:'.format(agent.upper()))\n",
    "        print(s) \n",
    "        # On appelle cette fonction à l'intérieur\n",
    "        # Mais pour le moment je ne sais pas \n",
    "        # ce que  l'on va faire avec les \"agents\", on ne sait même pas qui ils sont...\n",
    "        # C'est donc vraiment possible de créer un effet surprise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Pour le sérviteur BOB:\n",
      "Très bien,BOB : tu a gagné une pièce d’argent\n",
      "Pour le sérviteur JIM:\n",
      "Très bien,JIM : tu a gagné une pièce d’argent\n",
      "Pour le sérviteur JOE:\n",
      "Très bien,JOE : tu a gagné une pièce d’argent\n"
     ]
    }
   ],
   "source": [
    "# Nous allons confier au contremaitre une liste de serviteurs,\n",
    "# souvennez-vous qu'il ne sait pas par avance ce qui va se passer avec eux \n",
    "# c'est tout l'intérêt d'une fonction : on a séparé les rôles,\n",
    "# on peut rétribuer tout le monde de la même manière sans créer de jaloux\n",
    "\n",
    "\n",
    "agents=['bob','jim','joe']\n",
    "\n",
    "# Maintenant il est temps que le contremaître rétribue les serviteurs\n",
    "fin_de_journee(agents)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Pour le sérviteur BOB:\n",
      "Très bien,BOB : tu a gagné une pièce d’argent\n",
      "Pour le sérviteur JIM:\n",
      "Très bien,JIM : tu a gagné une pièce d’argent\n",
      "Pour le sérviteur JOE:\n",
      "Très bien,JOE : tu a gagné une pièce d’argent\n",
      "Pour le sérviteur JACK:\n",
      "Très bien,JACK : tu a gagné une pièce d’argent\n"
     ]
    }
   ],
   "source": [
    "# Imaginons que Jack est arrivé à la dernière heure... \n",
    "# pas de problème : il suffit de chager l'argument, la fonction s'occupe du reste\n",
    "\n",
    "agents=['bob','jim','joe','Jack']\n",
    "\n",
    "# Au moment où le contremaître rétribue tous les serviteurs...\n",
    "fin_de_journee(agents)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Qu'est ce que l'algorithme ?\n",
    "\n",
    "Si la résolution de problèmes est un élément central de l'informatique, alors les solutions que vous imaginez pour le 'processus de résolution de problèmes' sont l'étape la plus importante. En informatique, nous appelons ces solutions des **algorithmes**. Un algorithme est une liste de tâches à réaliser dans l'ordre, étape par étape en suivant des instructions qui, si elles sont suivies à la lettre, résoudront le problème étudié. C'est somme toute une *recète de cuisine*, mais avec l'aventage de pouvoir prendre en compte des conditions, des boucles qu'un livre de cuisine ne peut pas offrir.\n",
    "\n",
    "Notre but en informatique sera, de prendre un problème et de développer un algorithme qui peut servir pour y apporter une solution. Une fois que nous avons une telle solution, nous pouvons utiliser notre ordinateur pour *automatiser* l'exécution, cela permet de faire travailler l'ordinateur sur des tâches répétitives et ennuyeuses qu'il ne convient pas de confier à un humain. Comme nous l'avons déjà dit, la programmation est une compétence qui permet à un informaticien de prendre un algorithme et de le représenter dans une syntaxe (un programme) qui peut être suivie par un ordinateur. Ces programmes sont écrits en langage de programmation.\n",
    "\n",
    "Source : [How to Think Like a Computer Scientist: Interactive Edition](https://runestone.academy/runestone/books/published/thinkcspy/index.html)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Histoire des algorithmes\n",
    "\n",
    "Même si le nom \"algorithme\" vient perse du IX ème siècle, Al-Khwârizmî il y a quelque preuves que les algorithes existent bien avant, chez les sages grecs. Notament Archimède et Héron d'Alexandrie. Ce dernier et l'auteur d'une méthode très efficace pour le calcul des [racines carrées](https://fr.wikipedia.org/wiki/M%C3%A9thode_de_H%C3%A9ron).  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Héron est un savant qui vit à Alexandrie (Egypte actuelle) où il fait la plupart de ses inventions entre l'an 10 et 70 après J.-C. il utilise une methode qui vient probablement des mathématiciens de mésopotamie (540 avant J.-C.).\n",
    "\n",
    "Sa méthode adaptée à un ordinateur est la suivante :\n",
    "\n",
    "   - > 0 ) On sait quel est le carré dont on veut connaître le coté (racine)\n",
    "   - >1 ) On s'assure que cette valeur est divisible (en le transformant en un nombre flotant) et on appelle ce nombre `val`\n",
    "   - > 2 ) On fait une première estimation de ce que devrait être la racine `racCarreeVal`\n",
    "   - > 3 ) On calcule une seconde valeur de `racCarreeVal` en prenant la moyenne entre `racCarreeVal` trouvée précédament et le rapport de `val` et de `racCarreeVal`.  \n",
    "   - > 4 ) Tant que la différence entre cette valeur et la valeur d'origine `val` et plus grande que la précision que l'on c'est fixée, on recommence l'étape 3\n",
    "   - > 5 ) Dès que l'on dépasse la précision requise on retourne la valeur de la racine approximée par etapes succésives "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $x$ un entier qui s'approche de la racine de la valeur `val`\n",
    "\n",
    "$$ x_{n+1}=\\left(\\frac{x_n+{\\tt{val}}/{x_n}}{2}\\right)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pygraphviz as pgv"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous allons réaliser un algorigramme sommaire qui s'appuie sur six étapes qui sont mises en relation de haut en bas pour parvenir à la détermination de la racine carré. Nous verons ensuite que cet approche doit rentrer dans les détails..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "G=pgv.AGraph(strict=False,directed=True)\n",
    "\n",
    "G.add_node(\"Détermination du  \\n nombre carré\",color='yellow',shape='box')\n",
    "G.add_node(\"Ce carré doit être divisible\",color='blue',shape='box',style=\"rounded\")\n",
    "G.add_node(\"On fait une première estimation \\n de racCarreeVal : x \",color='red',shape='box')\n",
    "G.add_node(\"On calcule la valeur de x à l'itération suivante\",color='black',shape='box')\n",
    "G.add_node(\"Est ce que le carré de cette estimation \\n est suffisament proche de val ?\",color='blue',shape='diamond',style=\"rounded\")\n",
    "G.add_node(\"oui\",color='white')\n",
    "G.add_node(\"non\",color='white')\n",
    "G.add_node(\"On donne la valeur\")\n",
    "\n",
    "\n",
    "G.add_edge(\"Détermination du  \\n nombre carré\",\"Ce carré doit être divisible\")\n",
    "G.add_edge(\"Ce carré doit être divisible\",\"On fait une première estimation \\n de racCarreeVal : x \")\n",
    "G.add_edge(\"On fait une première estimation \\n de racCarreeVal : x \",\"Est ce que le carré de cette estimation \\n est suffisament proche de val ?\")\n",
    "G.add_edge(\"On calcule la valeur de x à l'itération suivante\",\"Est ce que le carré de cette estimation \\n est suffisament proche de val ?\")\n",
    "G.add_edge(\"Est ce que le carré de cette estimation \\n est suffisament proche de val ?\" ,\"non\")\n",
    "G.add_edge(\"non\",\"On calcule la valeur de x à l'itération suivante\")\n",
    "\n",
    "G.add_edge(\"Est ce que le carré de cette estimation \\n est suffisament proche de val ?\" ,\"oui\")\n",
    "G.add_edge(\"oui\",\"On donne la valeur\")\n",
    "\n",
    "G.layout(prog='dot')\n",
    "\n",
    "G.draw('algo.png')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p><img src=\"./algo.png\" alt=\"Un algorigramme simplifié\" /></p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def RacineCarree(unNombre_Carre,unNombre_Estimateur):\n",
    "    # Declaration des Variables locales\n",
    "    \n",
    "    # EPS = 0.0000000000001 # précision\n",
    "    EPS = 1E-13\n",
    "    val = unNombre_Carre\n",
    "    racCarreeVal = unNombre_Estimateur\n",
    "    \n",
    "    # On définit un domaine de recherches tant que l'on \n",
    "    # n'est pas sorti de celui-ci on répete indéfiniment\n",
    "    # l'instruction qui se trouve apres les deux points\n",
    "    \n",
    "    while racCarreeVal * racCarreeVal - val < -EPS or \\\n",
    "          racCarreeVal * racCarreeVal - val > EPS:\n",
    "        \n",
    "        # la valeur absolue de la différence est supérieure à un seuil \n",
    "          racCarreeVal = (racCarreeVal + val / racCarreeVal) / 2\n",
    "    \n",
    "    # Une fois la précision requise atteinte on sort de cette boucle\n",
    "    \n",
    "    return racCarreeVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Entrez une première estimation de la racine de 42.0 : 5\n"
     ]
    }
   ],
   "source": [
    "# Test de la fonction\n",
    "\n",
    "# Etape 0\n",
    "unNombre_Carre = 42\n",
    "\n",
    "# Etape 1 : on déclare la valeur 'val'\n",
    "unNombre_Carre=float(unNombre_Carre)\n",
    "\n",
    "unNombre_Estimateur = input(\"Entrez une première estimation de la racine de {} : \".format(unNombre_Carre))\n",
    "unNombre_Estimateur=float(unNombre_Estimateur)\n",
    "#print(RacineCarree(unNombre_Carre,unNombre_Estimateur))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6.48074069840786"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Etapes 2- 4\n",
    "RacineCarree(unNombre_Carre,unNombre_Estimateur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42.0"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# On vérifie que le carré de ce nombre correspond bien \n",
    "# à ce que l'on cherche en utilisant la fonction vue \n",
    "# dans une leçon antérieure\n",
    "\n",
    "carre(6.48074069840786)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Modifier la fonction RacineCarree\n",
    "En recopiant le code de la fonction `RacineCarree` indiquez le nombre d'itération nécessaires à l'algoritme quand on part d'une valeur proche de la racine recherchée."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}