11_Elements_programmation_diapo.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## <p style=\"text-align: center;\">NSI - Éléments de programmation</p>\n",
    "## <p style=\"text-align: center;\">Ensembles et dictionnaires</p>\n",
    "## <p style=\"text-align: center;\">Lycée Beaussier - F. Lagrave</p>\n",
    "\n",
    "[![Binder](https://mybinder.org/badge_logo.svg)](https://mybinder.org/v2/gh/Fklag/NSI_iere/master?filepath=11_Elements_programmation_diapo.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Supports de cours"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<div id=\"top\">\n",
    "    \n",
    "### Un point sur le cours  \n",
    "    \n",
    "Nous avons vu :   \n",
    "1. Les <a href=\"http://lycee.lagrave.free.fr/nsi/programmation/0_Elements_programmation_diapo.pdf\" target=\"_blank\">éléments de bases</a> d'un langage\n",
    "   * Les <a href=\"http://lycee.lagrave.free.fr/nsi/programmation/0_Elements_programmation_diapo.pdf\" target=\"_blank\">expressions (arithmétiques)</a>  \n",
    "   * La <a href=\"http://lycee.lagrave.free.fr/nsi/programmation/0_Elements_programmation_diapo.pdf\" target=\"_blank\">définition de fonctions</a>  \n",
    "   * L'<a href=\"http://lycee.lagrave.free.fr/nsi/programmation/4_Elements_programmation_diapo.pdf\" target=\"_blank\">affectation de variables</a>  \n",
    "   * Les <a href=\"http://lycee.lagrave.free.fr/nsi/programmation/4_Elements_programmation_diapo.pdf\" target=\"_blank\">séquences d'instructions </a> \n",
    "   * Les <a href=\"http://lycee.lagrave.free.fr/nsi/programmation/4_Elements_programmation_diapo.pdf\" target=\"_blank\">alternatives</a>  \n",
    "   * Les <a href=\"http://lycee.lagrave.free.fr/nsi/programmation/5_Elements_programmation_diapo.pdf\" target=\"_blank\">boucles</a>  \n",
    "   \n",
    "2. Un type de structure de données : les **séquences**  \n",
    "   * les intervalles : <a href=\"http://lycee.lagrave.free.fr/nsi/programmation/7_Elements_programmation_diapo.pdf\" target=\"_blank\">séquences d'entiers</a>  \n",
    "   * les chaı̂nes de caractères : <a href=\"http://lycee.lagrave.free.fr/nsi/programmation/7_Elements_programmation_diapo.pdf\" target=\"_blank\">séquences de caractères</a> \n",
    "   * les **listes** : <a href=\"http://lycee.lagrave.free.fr/nsi/programmation/8_Elements_programmation_diapo.pdf\" target=\"_blank\">séquences génériques</a>  \n",
    "\n",
    "→ Point commun : **l'ordre est important !**\n",
    "    \n",
    "\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "###   Un deuxième type de structure de données : les données itérables  \n",
    "• les **ensembles** qui sont l'équivalent informatique des ensembles mathématiques  \n",
    "• les **dictionnaires** qui associent des **clés** de recherche à des **valeurs**. \n",
    "    \n",
    "**Plan du cours**  \n",
    "    \n",
    "1.   Les ensembles \n",
    "     Opérations de base  \n",
    "     Itération  \n",
    "     Test d'égalité  \n",
    "     Opérations ensemblistes  \n",
    "2.   Les dictionnaires  \n",
    "     Opérations de base\n",
    "     Itération  \n",
    "3.   Un exemple complet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Notion d’ensemble  \n",
    "\n",
    "La notion d'ensemble est fondamentale en mathématique.  \n",
    "De fait, l'essentiel des constructions mathématiques sont basées sur *<a href=\"https://fr.wikipedia.org/wiki/Th%C3%A9orie_des_ensembles\" target=\"_blank\">la théorie des ensembles</a>*.\n",
    "\n",
    "Un ensemble désigne intuitivement **une collection d'objets** (les éléments de l'ensemble).  \n",
    "\n",
    "En tant que structure de donnée :  \n",
    "  * collection de valeurs (au même titre qu'une liste)  \n",
    "  * **sans doublons**\n",
    "  * **sans ordre**\n",
    "  \n",
    "Comme toute structure de données, elle est munie :\n",
    "  * d'un **type** : $\\texttt{set}[\\texttt{<type>}]$  \n",
    "  * de **primitives** permettant de manipuler la structure  \n",
    "    - **opérations** habituelles :  \n",
    "      • construction : $\\texttt{set}$ , $\\left\\{\\ldots\\right\\}$  \n",
    "      • ajout d'éléments : $\\texttt{add}$  \n",
    "      • test d'égalité : $\\texttt{==}$  \n",
    "      • test appartenance : $\\texttt{in}$  \n",
    "    - **opérations spécifiques** :  \n",
    "      • intersection d'ensembles : $\\texttt{&}$  \n",
    "      • union d'ensembles : $\\texttt{|}$  \n",
    "      • différences : $\\texttt{--}$  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Définition   \n",
    "Pour notre cours, nous adopterons la définition suivante.    \n",
    "**Définition :**  un ensemble de $\\texttt{type} \\, \\texttt{set}[\\alpha]$ est une collection d'éléments de $\\texttt{type}\\, \\alpha$ et tous distincts (au sens de l'égalité de $\\texttt{Python} ==$)  \n",
    "\n",
    "Pour des raisons techniques, **le $\\texttt{type} \\, \\alpha$** des éléments d'un ensemble doit être **immutable**.  \n",
    "À l'exception des listes et des ensembles eux-mêmes, tous les types que nous avons vus répondent à cette contrainte.  \n",
    "\n",
    "On retiendra donc : **Aucun type $\\texttt{liste}$ ou $\\texttt{ensemble}$ ne peut apparaître dans le $\\alpha$ de $\\texttt{set}[\\alpha]$**.  \n",
    "\n",
    "\n",
    "> Puisqu'un programmeur (même confirmé) doit maîtriser le type des informations qu'il manipule, \n",
    "nous instituons comme pour les listes la règle du typage explicite et précis des éléments d'un ensemble.  \n",
    "**À retenir :** c'est au programmeur (donc à vous) qu'incombe la responsabilité de garantir que\n",
    "les éléments contenus dans un ensemble de $\\texttt{type} \\, \\texttt{set}[\\alpha]$ soient bien tous du même **$\\texttt{type} \\, \\alpha$**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Construction d'un ensemble  \n",
    "* Construction explicite: on énonce tous les éléments  $\\left\\{ e_1, e_2, \\ldots, e_N \\right\\}$  \n",
    "  * les  $e_1$, $e_2$, $\\ldots$, $e_N$ : expressions de $\\texttt{type}\\, \\alpha$  \n",
    "* Construction de l'ensemble vide $\\, \\texttt{set}( \\,)$  \n",
    "  * Pour des raisons historiques , la notation $\\, \\left\\{ \\, \\right\\}$ est en effet réservée aux dictionnaires vides   \n",
    "    (mais pour éviter toute ambiguïté nous utiliserons plutôt $\\, \\texttt{dict}(\\,)$, cf. deuxième partie du cours).\n",
    "* Exemples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{11, 38, 42}"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{42, 11, 38} # set[int]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "set"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type({42, 11, 38}) # set[int]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{11, 38, 42}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{2*3*7, 10+1 , (27+6)+5} # set[int]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0.7071067811865475, 1.6666666666666667, 3.141592653589793, 11.38}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import math\n",
    "{math.pi, 5.0/3.0, 11.38, math.sin(math.pi/4)} # set[float]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Construction d’un ensemble  \n",
    "Important  \n",
    "* les éléments dans un ensemble doivent être du **même $\\texttt{type}$**   \n",
    "  - c'est au programmeur de le garantir  \n",
    "  - il faut donc y veiller lors de la construction  \n",
    "* un ensemble **ne doit pas contenir 2 fois** le même élément  \n",
    "  - c'est $\\texttt{Python}$ qui le garantit: il ne retient que les éléments distincts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{11, 38, 42, 2001}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{42, 11, 38, 42, 42, 42, 2001}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Test d'appartenance  \n",
    "En mathématique, si un élément $e$ appartient à un ensemble $E$ on note : $e \\in E$.  \n",
    "En $\\texttt{Python}$, ceci se traduit par une expression d'appartenance de $\\texttt{type bool}$  \n",
    "\n",
    "**Test d'appartenance**  \n",
    "L'expression $\\texttt{<elem>} \\,\\, \\texttt{in}\\,\\,  \\texttt{<ensemble>}$  $\\qquad$ où :\n",
    "$\\texttt{<elem>}$ de $\\texttt{type}\\, \\alpha$ ; $\\texttt{<ensemble>}$ de $\\texttt{type} \\, \\texttt{set}[\\alpha]$  \n",
    "teste l'appartenance de l'élément $\\texttt{<elem>}$ dans l'ensemble $\\texttt{<ensemble>}$, i.e. :  \n",
    "• renvoie $\\texttt{True}$ si $\\texttt{<elem>}$ appartient à $\\texttt{<ensemble>}$  \n",
    "• renvoie $\\texttt{False}$ sinon  \n",
    "\n",
    "**Non appartenance** \n",
    "L'expression $\\texttt{<elem>} \\,\\, \\texttt{not in} \\,\\, \\texttt{<ensemble>}$  \n",
    "teste la non appartenance de l’élément $\\texttt{<elem>}$ dans l’ensemble $\\texttt{<ensemble>}$.  \n",
    "\n",
    "Exemples :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(False, True, True)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "124 in set(),124 in {9, 124, 2},'b' not in {'c', 'a'}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "L'intérêt majeur du test d'appartenance (ou de non-appartenance) sur les ensembles en $\\texttt{Python}$  est qu'il est d'une grande efficacité.  \n",
    "\n",
    "Si l'on compare aux listes, il faut (**dans le pire cas**) de l'ordre de $n$ tests d'égalité pour vérifier si\n",
    "un élement appartient à une liste de longueur $n$ alors que dans la plupart des cas un seul test suffit pour répondre à la même question dans le cas d'un ensemble de $n$ éléments."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Modification d'un ensemble  \n",
    "**Ajout d'éléments**  \n",
    "L'ajout d'un élément $\\texttt{<elem>}$ de $\\texttt{type}\\, \\alpha$ à un ensemble de $\\texttt{type} \\, \\texttt{set}[\\alpha]$   \n",
    "se fait par :  $\\texttt{<ensemble>}.\\texttt{add}(\\texttt{<elem>})$  \n",
    "\n",
    "Le **principe d'interprétation** est : \n",
    "1. évaluation de l’expression $\\texttt{<elem>}$\n",
    "2. ajout, par **mutation**, de la valeur à l'ensemble $\\texttt{<ensemble>}$  \n",
    "\n",
    "Le **principe d'interprétation** associé est la **modification** de l'$\\texttt{<ensemble>}$ pour ajouter l'$\\texttt{<elem>}$. Cette modification se fait par **effet de bord** c'est-à-dire directement en mémoire,\n",
    "sans reconstruction d'un ensemble résultat. Aucune valeur n'est ainsi retournée par la **méthode** $\\texttt{add}$.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Modification d’un ensemble\n",
    "**Remarques :**  \n",
    "• Opérations très efficaces (temps constant) car on ne reconstruit pas l'ensemble  \n",
    "• Valeur de retour : $\\texttt{None}$ (effet de bord, comme la fonction append $\\ldots$)  \n",
    "• Type de $\\texttt{<elem>}$ doit être compatible avec celui de $\\texttt{<ensemble>}$.  \n",
    "• Ajout d'un élément déjà présent : rien ne se passe  \n",
    "\n",
    "Exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "E = {2, 1, 4}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(None, None, {1, 2, 3, 4})"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E.add(2+1),E.add(4),E"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Complément : retrait d'un élément  \n",
    "L'opération complémentaire de retrait d'un élément dans un ensemble est également disponible. Si le retrait d'un élément dans une liste est coûteux, il s'agit d'une opération très efficace sur les ensembles.  \n",
    "On utilise dans ce cas la **méthode** $\\texttt{remove}$ selon la syntaxe :  \n",
    "$\\texttt{<ensemble>}.\\texttt{remove}(\\texttt{<elem>})$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(None, {1, 2, 4})"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E.remove(3),E"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Exemple : $\\texttt{presences}$  \n",
    "**Problème**  \n",
    "Étant donnée une liste d'éléments, construire l'ensemble des éléments de cette liste.  \n",
    "Étant donnée une liste $L$ d'entiers la fonction $\\texttt{presences}$ retourne l'ensemble des entiers qui apparaissent au moins une fois dans $L$.  \n",
    "\n",
    "• un élément n'est ajouté qu'une seule fois  \n",
    "• l'ensemble résultat doit être initialisé à l'ensemble vide"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def presences(L) :\n",
    "    \"\"\"list[int] -> set[int]\n",
    "    retourne ensemble des entiers qui apparaissent au moins une fois dans L.\"\"\"\n",
    "    # E : set[int]\n",
    "    E = set() # ensemble resultat, initialement vide\n",
    "    for n in L :\n",
    "        E.add(n)\n",
    "    return E\n",
    "\n",
    "# Jeu de tests\n",
    "assert presences([9,11, 11, 2, 5, 9, 2, 2, 1, 3]) == {1, 2, 3, 5, 9, 11}\n",
    "assert presences([1,2, 3, 4]) == {1, 2, 3, 4}\n",
    "assert presences([2,2, 2, 2]) == {2}\n",
    "assert presences([])== set()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Itération sur les ensembles  \n",
    "• Un ensemble n'est pas une séquence  \n",
    "• Mais on peut réaliser une itération sur les éléments d'un ensemble  \n",
    "\n",
    "**Itération sur les ensembles**  \n",
    "$\\texttt{#<var> : alpha}$  \n",
    "$\\texttt{for}\\,\\, \\texttt{<var>} \\,\\, \\texttt{in} \\,\\, \\texttt{<ensemble>}\\, \\texttt{:}$  \n",
    "$\\phantom{.} \\quad \\texttt{<corps>}$  \n",
    "\n",
    "• $\\texttt{<var>}$ : variable d'itération d'élément de $\\texttt{type}\\, \\alpha$  \n",
    "• $\\texttt{<ensemble>}$ : un ensemble d'éléments de $\\texttt{type} \\, \\texttt{set}[\\alpha]$  \n",
    "• $\\texttt{<corps>}$ : suite d'instructions  \n",
    "\n",
    "**Principe d'interprétation**  \n",
    "• le $\\texttt{<corps>}$ est exécuté une fois pour chaque élément de $\\texttt{<ensemble>}$  \n",
    "• $\\texttt{<var>}$ contient l'élément concerné  \n",
    "• $\\texttt{<var>}$ n'est plus utilisable à la sortie de la boucle  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Itération sur les ensembles  \n",
    "**Attention :** l'ordre d'itération est arbitraire  \n",
    "• aucune garantie sur l'ordre de traitement des éléments  \n",
    "• seule garantie : tous les élements seront vus une et une seule fois"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Exemple : somme  \n",
    "**Problème**  \n",
    "Étant donnée un ensemble d'éléments, calculer la somme de ces éléments."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def somme_ensemble(E) :\n",
    "    \"\"\"set[int] -> int\n",
    "    Renvoie la somme des éléments de E.\"\"\"\n",
    "    # s : int\n",
    "    s = 0 # somme\n",
    "    # n : int (element courant)\n",
    "    for n in E :\n",
    "        s = s + n\n",
    "    return s\n",
    "\n",
    "# Jeu de tests\n",
    "assert somme_ensemble({1, 3, 9, 24, 5}) == 42\n",
    "assert somme_ensemble({1, 3, 1, 9, 3, 24, 5, 24, 5}) == 42\n",
    "assert somme_ensemble({-2, -1, 0, 1, 2}) == 0\n",
    "assert somme_ensemble(set()) == 0\n",
    "{1, 3, 9, 24, 5} == {1, 3, 1, 9, 3, 24, 5, 24, 5}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Comparaison d'ensembles  \n",
    "**Sous-ensemble** : $E_1 \\subseteq E_2$  \n",
    "• un ensemble $E_1$ est un sous-ensemble de $E_2$ si tout élément de $E_1$ est un élément de $E_2$  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def est_sous_ensemble(E1, E2) :\n",
    "    \"\"\"set[alpha] * set[alpha] -> bool\n",
    "    Renvoie True si E1 est sous-ensemble de E2, False Sinon.\"\"\"\n",
    "    # e : alpha (element courant)\n",
    "    for e in E1 :\n",
    "        if e not in E2 :\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "# Jeu de tests\n",
    "assert est_sous_ensemble({2, 5}, {2, 5, 9}) == True\n",
    "assert est_sous_ensemble({5}, {2, 5, 9}) == True\n",
    "assert est_sous_ensemble(set(), {2, 5, 9}) == True\n",
    "assert est_sous_ensemble({2, 8}, {2, 5, 9}) == False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Cette relation sous-ensemble correspond en fait à l'odre naturel sur les ensembles, et donc en $\\texttt{Python }$ plutôt que d'écrire : $\\texttt{est\\_sous\\_ensemble}(E1, E2)$ \n",
    "on peut utiliser de façon équivalente (et préférée) $E1 <= E2$  \n",
    "\n",
    "• en $\\texttt{Python}$ : $E1 <= E2$ expression qui rend $\\texttt{True}$ si $E_1 \\subseteq E_2$  \n",
    "\n",
    "Par exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, True, True, False)"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{2, 5} <= {2, 5, 9},{5} <= {2, 5, 9},set() <= {2, 5, 9},{2, 8} <= {2, 5, 9}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Autres comparateurs  \n",
    "**Sous-ensemble strict** : $E_1 \\subset E_2$   $\\qquad$ $E1 <  E2\\, \\, $ ou bien : $\\, \\,E2  >  E1$  \n",
    "**Egalité** de deux ensembles : $E1 == E2$ $\\,$ → $\\texttt{True}$ si on a $E_1 \\subseteq E_2$ **et** $E_2 \\subseteq E_1$  \n",
    "**Inégalité** de deux ensembles : $E1 \\,\\, != \\,\\,E2$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, False, False, True)"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{5, 2, 9} == {2, 5, 9},{5, 2, 9} != {2, 5, 9},{5, 2} == {2, 5, 9},{5, 2} != {2, 5, 9}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Opérations ensemblistes (1)   \n",
    "Pour terminer notre introduction aux ensembles, nous allons présenter les opérations ensemblistes les plus  fondamentales : l'union, l'intersection et la différence entre deux ensembles.  \n",
    "\n",
    "**Union** de deux ensembles : $E_1 \\cup E_2$  \n",
    "• ensemble des éléments de $E_1$ et de $E_2$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def union(E1, E2):\n",
    "    \"\"\"set[alpha] * set[alpha] -> set[alpha]\n",
    "    Retourne union des ensembles E1 et E2.\"\"\"\n",
    "    # U : set[alpha]\n",
    "    U = set() # ensemble resultat  \n",
    "    # e1 : alpha (element de E1)\n",
    "    for e1 in E1 :\n",
    "        U.add(e1)\n",
    "    # e2 : alpha (element de E2)\n",
    "    for e2 in E2 :\n",
    "        U.add(e2)\n",
    "    return U\n",
    "\n",
    "# Jeu de test\n",
    "assert union({'a','e','u'}, {'o','i'}) == {'a', 'e', 'i', 'o', 'u'}\n",
    "assert union({2, 5, 9}, {1, 3, 4,8}) == {1, 2, 3, 4, 5, 8, 9}\n",
    "assert union({1, 2, 5, 9}, {1, 3,4, 8}) == {1, 2, 3, 4, 5, 8, 9}\n",
    "assert union({1, 2, 5, 9}, set())== {1, 2, 5, 9}\n",
    "assert union(set(), {1, 2, 5, 9})== {1, 2, 5, 9}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "L'union ensembliste est une opération fondamentale, et ce n'est donc pas étonnant de la trouver prédéfinie en $\\texttt{Python}$.  \n",
    "\n",
    "• Il existe une instruction Python : $\\mid$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1, 2, 3, 4}"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{1, 2, 3} | {3, 4}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Opérations ensemblistes (2)   \n",
    "L'intersection ensembliste est également une opération courante dans la vie de tous les jours. \n",
    "\n",
    "**Intersection** de deux ensembles : $E_1 \\cap E_2$  \n",
    "• ensemble des éléments qui sont à la fois dans $E_1$ et dans $E_2$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def intersection(E1, E2) :\n",
    "    \"\"\"set[alpha] * set[alpha] -> set[alpha]\n",
    "    Retourne intersection des ensembles E1 et E2.\"\"\"\n",
    "    # I : set[alpha]\n",
    "    I = set() # ensemble intersection\n",
    "    # e1 : alpha (element de E1)\n",
    "    for e1 in E1 :\n",
    "        if e1 in E2 :\n",
    "            I.add(e1)\n",
    "    return I\n",
    "\n",
    "# Jeu de tests\n",
    "assert intersection({'a', 'i','o'}, {'u', 'i', 'o', 'y'}) == {'o', 'i'}\n",
    "assert intersection({2, 5, 9},{1, 2, 3, 4, 5, 8}) == {2, 5}\n",
    "assert intersection({2, 5, 9},{2, 3, 4, 8}) == {2}\n",
    "assert intersection({2, 5, 9},{1, 3, 4, 8}) == set()\n",
    "assert intersection({2, 5, 9}, set()) == set()\n",
    "assert intersection(set(), {2, 5, 9}) == set()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "• Il existe une instruction Python : $\\&$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{3}"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{1, 2, 3} & {3, 4}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Opérations ensemblistes (3)  \n",
    "**Différence** de deux ensembles : $E_1 \\setminus E_2$  \n",
    "• ensemble des éléments de $E_1$ qui ne sont pas dans $E_2$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def difference(E1, E2) :\n",
    "    \"\"\"set[alpha] * set[alpha] -> set[alpha]\n",
    "    Retourne la difference des ensembles E1 et E2.\"\"\"\n",
    "    # D : set[alpha]\n",
    "    D = set() # ensemble difference\n",
    "    # e1 : alpha (element de E1)\n",
    "    for e1 in E1:\n",
    "        if e1 not in E2:\n",
    "            D.add(e1)\n",
    "    return D\n",
    "\n",
    "# Jeu de tests\n",
    "assert difference({'a', 'i', 'o', 'y'}, {'u', 'i', 'o'}) == {'a', 'y'}\n",
    "assert difference({ 2, 5, 9 }, {2, 3, 4, 8}) == {5, 9}\n",
    "assert difference({ 2, 5, 9 }, {2, 3, 5, 8}) == {9}\n",
    "assert difference({ 2, 5, 9 }, {2, 3, 5, 8, 9}) == set()\n",
    "assert difference({ 2, 5, 9 }, {2, 5, 9}) == set()\n",
    "assert difference({2, 5, 9}, set()) == {2, 5, 9}\n",
    "assert difference(set(), {2, 5, 9}) == set()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "• Il existe une instruction Python : $-$  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1, 2}"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{1, 2, 3} - {3, 4}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Les dictionnaires  \n",
    "\n",
    "Les dictionnaires sont sans doute, avec les listes, les structures de données les plus couramment\n",
    "utilisées en $\\texttt{Python}$.  \n",
    "Un dictionnaire $\\texttt{Python}$ exprime une relation entre un ensemble de clés - dites de recherche - et un ensemble de valeurs.  \n",
    "Cette relation est mathématiquement une application (un *mapping*) qui impose qu'à chaque clé corresponde exactement une valeur.  \n",
    "On dit que le couple formé d'une clé et de sa valeur associée forme une association.\n",
    "\n",
    "* Une **association** : liaison entre une **clé de recherche** et une **valeur** associée  \n",
    "* **Dictionnaire** : ensemble d'associations entre  \n",
    "  - une clé de $\\texttt{type}\\, \\alpha$  \n",
    "  - une valeur de $\\texttt{type}\\, \\beta$  \n",
    "* Les clés sont **uniques** : pas de doublons (comme les ensembles)\n",
    "* $\\texttt{Type}$ d'un dictionnaire: $\\texttt{dict}[\\alpha : \\beta]$  \n",
    "  - en fait pas tous les $\\alpha$, uniquement les **objets immutables** ($\\texttt{str}$, $\\texttt{Number}$, $\\texttt{int}$) mais pas les $\\texttt{listes}$ !\n",
    "* Par exemple  \n",
    "  - $\\texttt{'pi'}$ est associée à la valeur $3.14159265$  \n",
    "  - $\\texttt{'rcarre2'}$ est associée à la valeur $1.41421356237$  \n",
    "  - $\\texttt{'phi'}$ est associée à la valeur $1.6180339887$  \n",
    "  \n",
    "On remarque la proximité entre la notion d'ensemble et celle de dictionnaire. En effet, les clés du dictionnaires forment un ensemble au sens de ce que nous avons présenté dans la première partie du cours.  \n",
    "Exemple - un dictionnaire (très partiel) des constantes mathématiques :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'pi': 3.14159265, 'sqrt2': 1.41421356237, 'phi': 1.6180339887}"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{'pi' : 3.14159265, 'sqrt2' : 1.41421356237, 'phi' : 1.6180339887 }"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Le $\\texttt{type}$ de ce dictionnaire est $\\texttt{dict}[\\texttt{str}:\\texttt{float}]$ c'est-à-dire une association entre :  \n",
    "- des noms de constantes mathématiques représentées par des chaînes de caractères pour les clés  \n",
    "- et leur valeur numérique sous la forme d'un flottant.  \n",
    "\n",
    "Avant de passer à la suite, nous allons conserver notre dictionnaire des constantes en l'affectant à une variable permettant de le référencer dans les exemples.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# Consts : dict[str:float]\n",
    "Constantes = {'pi' : 3.14159265,'sqrt2' : 1.41421356237,'phi' : 1.6180339887 }"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Construction de dictionnaires  \n",
    "* Construction explicite: on énonce tous les éléments $\\left\\{k_1 : v_1 , k_2 : v_2 , \\ldots , k_N : v_N\\right\\}$  \n",
    "  - les $k_1 , k_2 , \\ldots , k_N$ : expressions pour les clés de $\\texttt{type}\\, \\alpha$   \n",
    "  - les $v_1 , v_2 , \\ldots , v_N$ : expressions pour les valeurs $\\texttt{type}\\, \\alpha$   \n",
    "* Construction du dictionnaire vide $\\quad \\texttt{dict}(\\,)$\n",
    "* Liaisons créées  \n",
    "  - la valeur $v_1$ est associée à la clé $k_1$, etc.  \n",
    "* Exemple: dictionnaire de $\\texttt{type}$ $\\texttt{dict}[\\texttt{str}:\\texttt{float}]$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'pi': 3.14159265, 'sqrt2': 1.41421356237, 'phi': 1.6180339887}"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Consts : dict[str:float]\n",
    "Constantes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Accès aux valeurs  \n",
    "Lorsque nous utilisons un dictionnaire commun, le cas d'utilisation typique est de rechercher une\n",
    "définition à partir d'un mot. Transposé en termes de dictionnaire $\\texttt{Python}$, ce cas d'utilisation consiste à recherche une valeur à partir de sa clé.  \n",
    "\n",
    "* Accès à une valeur : on utilise la clé de recherche comme référence  \n",
    "  - syntaxe: $\\texttt{<dictionnaire>}[\\texttt{<cle>}]$  \n",
    "  - $\\texttt{<dictionnaire>}$ est un dictionnaire de $\\texttt{type}$ $\\texttt{dict}[\\alpha : \\beta]$  \n",
    "  - $\\texttt{<cle>}$ est une expression de $\\texttt{type}\\, \\alpha$   \n",
    "* Dans un dictionnaire :  \n",
    "  - seule la clé permet d'accéder à une liaison\n",
    "  - **Attention** : la clé doit être présente dans le dictionnaire  \n",
    "    Remarque : il faudra donc savoir à l'avance si une clé est présente ou non dans un dictionnaire $\\ldots$\n",
    "* Exemples  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "ename": "KeyError",
     "evalue": "'e'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyError\u001b[0m                                  Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-24-106ee499398d>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0mConstantes\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'pi'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0mConstantes\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'e'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mKeyError\u001b[0m: 'e'"
     ]
    }
   ],
   "source": [
    "Constantes['pi']\n",
    "Constantes['e']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Test d'appartenance d'une clé  \n",
    "Nous l'avons vu ci-dessus, avant de pouvoir accéder à une valeur associée à une clé dans un dictionnaire, il faut préalablement vérifier si cette clé est bien présente. Si l'on construit explicitement le dictionnaire alors on peut déduire cette information simplement, mais si le dictionnaire est construit de façon algorithmique alors il est nécessaire de pouvoir tester l'appartenance d'une clé à un dictionnaire.  \n",
    "\n",
    "* Présence d'une clé dans un dictionnaire  $\\texttt{<cle>} \\,\\, \\texttt{in} \\,\\, \\texttt{<dictionnaire>}$  \n",
    "  - $\\texttt{<dictionnaire>}$ est un dictionnaire de $\\texttt{type}$ $\\texttt{dict}[\\alpha : \\beta]$  \n",
    "  - $\\texttt{<cle>}$ est une expression de $\\texttt{type}\\, \\alpha$   \n",
    "* **Principe d'évaluation**\n",
    "  - $\\texttt{True}$ si la $\\texttt{<cle>}$  existe dans $\\texttt{<dictionnaire>}$  \n",
    "  - $\\texttt{False}$ sinon  \n",
    "* Non appartenance : $\\quad \\texttt{<cle>}\\,\\, \\texttt{not in} \\,\\, \\texttt{<dictionnaire>}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, False, False, True)"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'pi' in Constantes,'pi' not in Constantes,'e' in Constantes,'e' not in Constantes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Remarque :** le test d'appartenance d'une clé à un dictionnaire revient à tester l'appartenance de cette clé à l'ensemble des clés du dictionnaire, il s'agit donc d'une opération très efficace."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Ajout d'une association  \n",
    "* Ajout d'une association $\\quad \\texttt{<dictionnaire>}[\\texttt{<cle>}] = \\texttt{<valeur>}$  \n",
    "* **Principe d'interprétation**  \n",
    "  - si la $\\texttt{<cle>}$ n'appartient pas au dictionnaire, l'association $\\texttt{<cle> : <valeur>}$ est rajoutée au dictionnaire (- ajout par effet de bord -)  \n",
    "  - sinon, si la $\\texttt{<cle>}$ appartient au dictionnaire, la valeur associée précédente est remplacée par $\\texttt{<valeur>}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'pi': 3.14159265,\n",
       " 'sqrt2': 1.41421356237,\n",
       " 'phi': 1.6180339887,\n",
       " 'e': 2.71828182}"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Constantes['e'] = 2.71828182\n",
    "Constantes\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Dictionnaire $\\texttt{vs.}$ Listes  \n",
    "On aurait pu utiliser une liste d'associations :  \n",
    "> $\\texttt{Const\\_dict}=\\left\\{\\texttt{'pi' : 3.14159265 , 'rcarre2' : 1.41421356237 , 'phi' : 1.6180339887}\\right\\}$\n",
    "> $\\texttt{Const\\_list}=[(\\texttt{'pi', 3.14159265}) , (\\texttt{'rcarre2', 1.41421356237}) , (\\texttt{'phi', 1.6180339887})]$\n",
    "\n",
    "Quel coût cela aurait-il de :  \n",
    "• Vérifier si $\\texttt{'e'}$ est une clef présente  \n",
    "• Récupérer la valeur associée à $\\texttt{'phi'}$   \n",
    "• Ajouter (où ?) une nouvelle association entre $\\texttt{'e'}$ et $\\texttt{2.718281828}$\n",
    "\n",
    "Les dictionnaires sont très efficaces pour effectuer ces opérations  \n",
    "<img src=\"./images/dict.png\" alt=\"dictionnaire\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Exemple : comptage d'occurrences  \n",
    "L'instruction d'ajout/remplacement dans un dictionnaire nous permet d'effectuer des constructions algorithmiques.  Un cas d’utilisation typique des dictionnaires consiste à compter les occurrences des éléments d'une liste.  \n",
    "\n",
    "**Problème** \n",
    "Calculer le nombre d'occurrences de chacune des lettres d'une chaı̂ne de caractères données."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def compte_occurrences(L) :\n",
    "    \"\"\" list[str] -> dict[str:int]\n",
    "    retourne le compte des occurrences des elements de la liste L.\"\"\"\n",
    "    # D : dict[str:int]\n",
    "    D = dict() # le dictionnaire resultat\n",
    "    # e : str (element courant)\n",
    "    for e in L :\n",
    "        if e not in D: # premiere occurrence\n",
    "            D[e] = 1\n",
    "        else: # k-ieme occurrence, k > 1\n",
    "            D[e] = D[e] + 1\n",
    "    return D\n",
    "\n",
    "# Jeu de tests\n",
    "assert compte_occurrences(['b','c','e','b','c','j','d','b','j','a','b'])\\\n",
    "== {'b' : 4, 'c': 2, 'e': 1, 'j': 2, 'd': 1, 'a':1 }\n",
    "assert compte_occurrences(['a', 'a', 'a', 'a', 'a']) == {'a' : 5}\n",
    "assert compte_occurrences([]) == dict()\n",
    "#compte_occurrences(list('anticonstitutionnellement')) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Question** : la signature de la fonction $\\texttt{compte\\_occurrences}$ est-elle la plus générale possible ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': 1,\n",
       " 'n': 5,\n",
       " 't': 5,\n",
       " 'i': 3,\n",
       " 'c': 1,\n",
       " 'o': 2,\n",
       " 's': 1,\n",
       " 'u': 1,\n",
       " 'e': 3,\n",
       " 'l': 2,\n",
       " 'm': 1}"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def compte_occurrences_str(L) :\n",
    "    \"\"\"str -> dict[str:int]\n",
    "    retourne le compte des occurrences des elements de la liste L.\"\"\"\n",
    "    # D : dict[str:int]\n",
    "    D = dict() # le dictionnaire resultat\n",
    "    # e : str (element courant)\n",
    "    for e in L :\n",
    "        if e not in D: # premiere occurrence\n",
    "            D[e] = 1\n",
    "        else: # k-ieme occurrence, k > 1\n",
    "            D[e] = D[e] + 1\n",
    "    return D\n",
    "\n",
    "compte_occurrences('anticonstitutionnellement')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Complément : retrait d'une assocation  \n",
    "De façon symétrique à l'ajout, il est possible de supprimer une association d'un dictionnaire.  \n",
    "On utilise pour cela la syntaxe suivante :  $\\texttt{del} \\,\\, \\texttt{<dictionnaire>}[\\texttt{<cle>}]$  \n",
    "où  \n",
    "* $\\texttt{<dictionnaire>}$ est une expression de dictionnaire de $\\texttt{type}$ $\\texttt{dict}[\\alpha : \\beta]$    \n",
    "* $\\texttt{<cle>}$ est une expression de $\\texttt{type}\\, \\alpha$  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'pi': 3.14159265, 'phi': 1.6180339887, 'e': 2.71828182}"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Consts : dict[str:float]\n",
    "# Constantes = {'pi' : 3.14159265,'sqrt2' : 1.41421356237,'phi' : 1.6180339887 }\n",
    "del Constantes['sqrt2']\n",
    "Constantes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "ename": "KeyError",
     "evalue": "'sqrt2'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyError\u001b[0m                                  Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-30-cbf1bd5bba7a>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;32mdel\u001b[0m \u001b[0mConstantes\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'sqrt2'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mKeyError\u001b[0m: 'sqrt2'"
     ]
    }
   ],
   "source": [
    "del Constantes['sqrt2']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Itération sur un dictionnaire  \n",
    "Après avoir construit un dictionnaire, une opération très courante consiste à le parcourir intégralement. Il n'est donc pas étonnant que les concepteurs du langage $\\texttt{Python}$ aient prévu d'étendre la boucle $\\texttt{for}$  d'itération pour répondre à ce besoin.  \n",
    "En fait, il existe deux types de boucles d'itérations sur les dictionnaires :  \n",
    "- l'**itération sur les clés** du dictionnaire,  \n",
    "- l'**itération sur les associations** clé/valeur."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Itération sur les clés du dictionnaire   \n",
    "**Itération sur les clés**  \n",
    "• Syntaxe de l'itération **sur les clés**    \n",
    "$\\texttt{# <var> : alpha}$  \n",
    "$\\texttt{for <var> in <dictionnaire> :}$  \n",
    "$\\phantom{.} \\qquad \\texttt{<corps>}$\n",
    "\n",
    "• $\\texttt{<var>}$ : variable d'itération sur les clés de $\\texttt{type}\\, \\alpha$  \n",
    "• $\\texttt{<dictionnaire>}$ : un dictionnaire de $\\texttt{type}$ $\\texttt{dict}[\\alpha : \\beta]$   \n",
    "• $\\texttt{<corps>}$ : suite d'instructions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Exemple d'itération  \n",
    "**Problème**  \n",
    "Étant donné un dictionnaire, écrire une fonction qui renvoie l'ensemble des clefs de ce dictionnaire."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def ensemble_des_cles(D) :\n",
    "    \"\"\"dict[alpha:beta] -> set[alpha]\n",
    "    Renvoie ensemble des cles du dictionnaire D.\"\"\"\n",
    "    # K : set[alpha]\n",
    "    K = set()\n",
    "    # k : alpha (cle courante)\n",
    "    for k in D :\n",
    "        K.add(k)\n",
    "    return K\n",
    "\n",
    "# Jeu de tests\n",
    "assert ensemble_des_cles({'a':1, 'z':26, 't':20, 'q':17}) \\\n",
    "== {'a', 'q', 't', 'z'}\n",
    "assert ensemble_des_cles({'e':2.71828182,'pi':3.141592653589793,'phi':1.6180339887})\\\n",
    "== {'e', 'pi', 'phi'}\n",
    "assert ensemble_des_cles(dict()) == set()\n",
    "#{'a':1, 'z':26, 't':20, 'q':17}.keys()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Comme vous le voyez, **si on essaye de parcourir un dictionnaire « simplement », on parcourt en réalité la liste des clés contenues dans le dictionnaire**.  \n",
    "\n",
    "Mais… les clés peuvent ne pas s'afficher pas dans l'ordre dans lequel on les a entrées… c'est normal ?  \n",
    "Les dictionnaires n'ont pas de structure ordonnée, gardez-le à l'esprit. Donc en ce sens oui, c'est tout à fait normal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Comment récupérer les clés d'un dictionnaire $\\texttt{Python}$ par une boucle ?  \n",
    "\n",
    "Une méthode de la classe $\\texttt{dict}$ permet d'obtenir ce même résultat.  \n",
    "Personnellement, je l'utilise plus fréquemment car on est sûr, en lisant l'instruction, que c'est la liste des clés que l'on parcourt.  \n",
    "La méthode $\\texttt{keys}()$  renvoie une **séquence** (qui est donc itérable) **des clés** contenues dans le dictionnaire qui appelle cette méthode.\n",
    "\n",
    "Pour récupérer les clés on utilise la **méthode** $\\texttt{keys}()$ .  \n",
    "\n",
    "$\\texttt{#<cle> : alpha}$  \n",
    "$\\texttt{for}\\,\\, \\texttt{<cle>} \\,\\, \\texttt{in} \\,\\, \\texttt{<dictionnaire>}.\\texttt{keys}()\\, \\texttt{:}$  \n",
    "$\\phantom{.} \\quad \\texttt{<corps>}$  \n",
    "\n",
    "• $\\texttt{<cle>}$ : variable d'itération sur les clés de $\\texttt{type}\\, \\alpha$  \n",
    "• $\\texttt{<dictionnaire>}$ : un dictionnaire de $\\texttt{type}$ $\\texttt{dict}[\\alpha : \\beta]$   \n",
    "• $\\texttt{<corps>}$ : suite d'instructions utilisant la $\\texttt{<cle>}$ courante"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def ensemble_des_cles(D) :\n",
    "    \"\"\"dict[alpha:beta] -> set[alpha]\n",
    "    Renvoie ensemble des cles du dictionnaire D.\"\"\"\n",
    "    # K : set[alpha]\n",
    "    K = set()\n",
    "    # k : alpha (cle courante)\n",
    "    for k in D.keys():\n",
    "        K.add(k)\n",
    "    return K\n",
    "\n",
    "# Jeu de tests\n",
    "assert ensemble_des_cles({'a':1, 'z':26, 't':20, 'q':17}) \\\n",
    "== {'a', 'q', 't', 'z'}\n",
    "assert ensemble_des_cles({'e':2.71828182,'pi':3.141592653589793,'phi':1.6180339887})\\\n",
    "== {'e', 'pi', 'phi'}\n",
    "assert ensemble_des_cles(dict()) == set()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Exemple : liste des valeurs  \n",
    "**Problème** \n",
    "Étant donné un dictionnaire, écrire une fonction qui renvoie la liste des valeurs de ce dictionnaire."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def liste_des_valeurs(D) :\n",
    "    \"\"\" dict[alpha:beta] −> list[beta]\n",
    "    Renvoie la liste des valeurs du dictionnaire D.\"\"\"\n",
    "    # L : list[beta]\n",
    "    L = []\n",
    "    # k : alpha (clef courante)\n",
    "    for k in D :\n",
    "        L.append(D[k])\n",
    "    return L\n",
    "\n",
    "# Jeu de tests\n",
    "assert liste_des_valeurs({'a':1, 'z':26, 't':20, 'q':17}) \\\n",
    "== [1, 26, 20, 17]\n",
    "assert liste_des_valeurs({'e':2.71828182,'pi':3.141592653589793,'phi':1.6180339887})\\\n",
    "== [2.71828182, 3.141592653589793, 1.6180339887]\n",
    "assert liste_des_valeurs(dict()) == []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Notez bien**, comme il est possible de construire cette liste $L$ avant de la renvoyer :  \n",
    "(la valeur du dictionnaire $D$ associée à la clé courante $k$)  $\\longleftrightarrow$  $D[k]$  \n",
    "**Remarque :** le premier cas de test est très «fragile » car il dépend de l'ordre dans lequel les associations du dictionnaire sont parcourues. D'un ordinateur à un autre, et d'une version de $\\texttt{Python}$ à une autre, cet ordre a de fortes chances de changer. Ceci illustre que la récupération des valeurs d'un dictionnaire n'est pas une opération triviale."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Comment récupérer les valeurs d'un dictionnaire $\\texttt{Python}$ par une boucle ?   \n",
    "Cette méthode est peu utilisée pour un parcours car il est plus pratique de parcourir la liste des clés, cela suffit pour avoir les valeurs correspondantes. Mais on peut aussi, bien entendu, **l'utiliser dans une condition**.\n",
    "\n",
    "Pour récupérer les valeurs on utilise la **méthode** $\\texttt{values}()$ .  \n",
    "\n",
    "$\\texttt{#<valeur> : beta}$  \n",
    "$\\texttt{for}\\,\\, \\texttt{<valeur>} \\,\\, \\texttt{in} \\,\\, \\texttt{<dictionnaire>}.\\texttt{values}()\\, \\texttt{:}$  \n",
    "$\\phantom{.} \\quad \\texttt{<corps>}$  \n",
    "\n",
    "• $\\texttt{<valeur>}$ : variable d'itération sur les valeurs de $\\texttt{type}\\, \\beta$  \n",
    "• $\\texttt{<dictionnaire>}$ : un dictionnaire de $\\texttt{type}$ $\\texttt{dict}[\\alpha : \\beta]$   \n",
    "• $\\texttt{<corps>}$ : suite d'instructions utilisant la $\\texttt{<valeur>}$ courante"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def liste_des_valeurs(D) :\n",
    "    \"\"\" dict[alpha:beta] −> list[beta]\n",
    "    Renvoie la liste des valeurs du dictionnaire D.\"\"\"\n",
    "    # L : list[beta]\n",
    "    L = []\n",
    "    # k : beta (valeur courante)\n",
    "    for k in D.values() :\n",
    "        L.append(k)\n",
    "    return L\n",
    "\n",
    "# Jeu de tests\n",
    "assert liste_des_valeurs({'a':1, 'z':26, 't':20, 'q':17}) \\\n",
    "== [1, 26, 20, 17]\n",
    "assert liste_des_valeurs({'e':2.71828182,'pi':3.141592653589793,'phi':1.6180339887})\\\n",
    "== [2.71828182, 3.141592653589793, 1.6180339887]\n",
    "assert liste_des_valeurs(dict()) == []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Une des valeurs du dictionnaire Constantes est une valeur approchée de pi.\n"
     ]
    }
   ],
   "source": [
    "if 3.14159265 in Constantes.values():\n",
    "    print(\"Une des valeurs du dictionnaire Constantes est une valeur approchée de pi.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Itération sur les associations du dictionnaire - Parcours des clés et valeurs simultanément\n",
    "Dans des cas un peu moins fréquents, on peut s'intéresser au parcours des associations $\\texttt{cle/valeur}$ dans un dictionnaire.  \n",
    "**Itération sur les associations**  \n",
    "• Syntaxe de l'itération **sur les associations**    \n",
    "$\\texttt{#}\\,\\, (\\texttt{cvar , vvar}) : \\texttt{tuple[alpha , beta]}$  \n",
    "$\\texttt{for} \\,\\, (\\texttt{<cvar>, <vvar>}) \\,\\, \\texttt{in <dictionnaire>.items}() :$  \n",
    "$\\phantom{.} \\qquad \\texttt{<corps>}$\n",
    "\n",
    "• $\\texttt{<cvar>}$ : variable ditération sur les clés de $\\texttt{type}\\, \\alpha$  \n",
    "• $\\texttt{<vvar>}$ : variable ditération sur les clés de $\\texttt{type}\\, \\beta$  \n",
    "• $\\texttt{<dictionnaire>}$ : un dictionnaire de $\\texttt{type}$ $\\texttt{dict}[\\alpha : \\beta]$   \n",
    "• $\\texttt{<corps>}$ : suite d'instructions  \n",
    "\n",
    "\n",
    "**Principe d'interprétation**  \n",
    "• le $\\texttt{<corps>}$ est exécuté pour chaque association du dictionnaire  \n",
    "• à chaque tour de boucle, la variable $\\texttt{<cvar>}$ est liée à la clé de l'association et la variable $\\texttt{<vvar>}$ est liée à la valeur associée  \n",
    "• les variables $\\texttt{<cvar>}$ et $\\texttt{<vvar>}$ ne sont plus utilisables après le dernier tour de boucle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Retour sur l'exemple : liste des valeurs  \n",
    "**Problème** \n",
    "Étant donné un dictionnaire, écrire une fonction qui renvoie la liste des valeurs de ce dictionnaire."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def liste_des_valeurs(D) :\n",
    "    \"\"\"dict[alpha:beta] −> list[beta]\n",
    "    Renvoie la liste des valeurs du dictionnaire D.\"\"\"\n",
    "    # L : list[beta]\n",
    "    L = []\n",
    "    # (k, v) : tuple[alpha, beta] (couple courant)\n",
    "    for (k, v) in D.items() :\n",
    "        L.append(v)\n",
    "    return L\n",
    "\n",
    "# Jeu de tests\n",
    "assert liste_des_valeurs({'a':1, 'z':26, 't':20, 'q':17}) \\\n",
    "== [1, 26, 20, 17]\n",
    "assert liste_des_valeurs({'e':2.71828182,'pi':3.141592653589793,'phi':1.6180339887})\\\n",
    "== [2.71828182, 3.141592653589793, 1.6180339887]\n",
    "assert liste_des_valeurs(dict()) == []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    ">D'un point de vue stylistique, on peut trouver l'itération sur les associations un peu plus lisible et elle est de fait légèrement plus efficace (on n'a pas besoin de «chercher» la valeur).  \n",
    "\n",
    "**Remarque :** le premier cas de test est très «fragile » car il dépend de l'ordre dans lequel les associations du dictionnaire sont parcourues. La récupération des valeurs d'un dictionnaire n'est pas une opération triviale."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Exemple complet : livre de recettes   \n",
    "On aimerait pouvoir manipuler un livre de recettes numérique, comme par exemple le livre de desserts suivant :\n",
    "\n",
    "| Recette | Ingrédients |\n",
    "|:-------:|:-----------:|\n",
    "| Gâteau au chocolat | chocolat, œuf, farine, sucre, beurre |\n",
    "| Gâteau au yaourt | yaourt, œuf, farine, sucre |\n",
    "| Crêpes | œuf, farine, lait |\n",
    "| Quatre-quarts | œuf, farine, beurre, sucre |\n",
    "| Kouign amann | farine, beurre, sucre |\n",
    "\n",
    "Comment représenter l’information ? $\\texttt{dict}[\\texttt{str}:\\texttt{set}[\\texttt{str}]]$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "Dessert = {\n",
    "'gateau chocolat' : {'chocolat', 'oeuf', 'farine', 'sucre', 'beurre'},\n",
    "'gateau yaourt' : {'yaourt', 'oeuf', 'farine', 'sucre'},\n",
    "'crepes' : {'oeuf', 'farine', 'lait'},\n",
    "'quatre-quarts' : {'oeuf', 'farine', 'beurre', 'sucre'},\n",
    "'kouign amann' : {'farine', 'beurre', 'sucre'}}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Exemple complet: livre de recettes  \n",
    "Écrire les fonctions permettant de :  \n",
    "1. connaı̂tre le nombre d'ingrédients utilisés par une recette\n",
    "2. connaı̂tre l'ensemble des ingrédients mentionnés\n",
    "3. contruire la table des ingrédients\n",
    "4. connaı̂tre l'ingrédient le plus utilisé\n",
    "5. connaı̂tre les recettes utilisant un ingrédient donné\n",
    "6. connaı̂tre les recettes réalisables étant donné un ensemble d'ingrédients\n",
    "7. construire un livre de recettes qui n'utilisent pas un ingrédient donné\n",
    "8. $\\ldots$  \n",
    "\n",
    "Etant donnés deux livres de recettes, écrire les fonctions permettant de :  \n",
    "1. connaı̂tre l'ensemble des ingrédients mentionnés dans ces livres\n",
    "2. connaı̂tre l'ensemble des recettes redondantes (identiques)\n",
    "3. connaı̂tre l'ensemble des recettes incohérentes\n",
    "4. construire le livre de recettes communes avec leurs variantes\n",
    "5. $\\ldots$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Nombre d’ingrédients utilisés par une recette  \n",
    "1. Fonction qui étant donné un livre de recettes et une recette retourne le nombre d'ingrédients utilisés par la recette,   \n",
    "  $0$ si la recette n'est pas dans le livre."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def nb_ingredients(D, r) :\n",
    "    \"\"\"dict[str:set[str ]] ∗ str −> int\n",
    "    retourne le nombre ingredients dans la recette r si elle est dans D, 0 sinon\"\"\"\n",
    "    # res : int\n",
    "    res = 0\n",
    "    # r : str\n",
    "    if r in D :\n",
    "        # s : str\n",
    "        for s in D[r] :\n",
    "            res = res + 1\n",
    "    return res\n",
    "\n",
    "# Jeu de tests\n",
    "assert nb_ingredients(Dessert, 'gateau chocolat') == 5\n",
    "assert nb_ingredients(Dessert, 'crepes') == 3\n",
    "assert nb_ingredients(Dessert, 'flan') == 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Ensemble des ingrédients mentionnés  \n",
    "2. Fonction qui étant donné un livre de recettes retourne l'ensemble des ingrédients utilisés dans le livre de recettes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def ensemble_ing(D) :\n",
    "    \"\"\"dict[str:set[str ]] −> set[str]\n",
    "    retourne ensemble des ingredients apparaissant dans les recettes\"\"\"\n",
    "    # E : set[str]\n",
    "    E = set()\n",
    "    # r : str \n",
    "    # Eingr: set[str]\n",
    "    for r, Eingr in D.items() :\n",
    "        E = E | Eingr\n",
    "    return E\n",
    "\n",
    "#\n",
    "assert ensemble_ing(Dessert) \\\n",
    "== {'chocolat', 'oeuf', 'farine', 'sucre', 'beurre', 'yaourt', 'lait'}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Ensemble des recettes avec un ingrédient\n",
    "...\n",
    "\n",
    "5. Fonction qui étant donné un livre de recettes et un ingrédient retourne l'ensemble des recettes utilisant  l'ingrédient."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def ensemble_recette(ingr , D) :\n",
    "    \"\"\"str ∗ dict[str:set[str ]] −> set[str]\n",
    "    retourne ensemble des recettes utilisant ingredient ingr\"\"\"\n",
    "    # E : set[str]\n",
    "    E = set()\n",
    "    # r : str\n",
    "    # Er : set[str]\n",
    "    for r, Er in D.items() :\n",
    "        if ingr in Er :\n",
    "            E.add(r)\n",
    "    return E\n",
    "\n",
    "# Jeu de tests\n",
    "assert ensemble_recette('chocolat', Dessert) == {'gateau chocolat'}\n",
    "assert ensemble_recette('pistache', Dessert) == set()\n",
    "assert ensemble_recette('beurre', Dessert) == {'gateau chocolat', 'quatre-quarts', 'kouign amann'}\n",
    "assert ensemble_recette('sucre', Dessert) \\\n",
    "== {'gateau chocolat', 'quatre-quarts', 'kouign amann', 'gateau yaourt'}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### $\\texttt{tuple}$ nommé  $\\texttt{vs.}$ dictionnaire  \n",
    "\n",
    "Pour accéder à un élément d'un tuple, il faut utiliser son indice. \n",
    "Le cas de **tuples hétérogènes** (pas toujours très intuitif) n'est **pas au programme de ce cours**. \n",
    "\n",
    "L'exemple d'un tuple qui représenterai un article d'un magasin :  \n",
    "\n",
    "$\\texttt{article\\_nom} = (\\texttt{5449000000996, \"Coca-Cola 33cl\", 0.70})$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tuple"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "article_nom = 5449000000996, \"Coca-Cola 33cl\", 0.70\n",
    "type(article_nom)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Pour accéder au code-barres, il faut écrire $\\texttt{article\\_nom}[0]$, pour accéder à la description de l'article, on utilise $\\texttt{article\\_nom}[1]$ et enfin $\\texttt{article\\_nom}[2]$ permet d'avoir le prix de l'article.\n",
    "\n",
    "Pour rendre plus explicite qu'on a un tuple hétérogène dont chaque élément représente un attribut différent, on peut utiliser un tuple nommé. Pour cela, il faut avant tout déclarer un nouveau type de tuple nommé, avec $\\texttt{namedtuple}$, en déclarant un nom et une liste d'attributs. Voici comment déclarer un tuple nommé $\\texttt{article\\_nom}$ composé d'un code-barres, d'une description et d'un prix :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from collections import namedtuple\n",
    "article_nom = namedtuple('article_nom', ['barcode', 'description', 'price'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Une fois le nouveau type de tuple nommé créé, on peut créer des tuples nommés comme suit :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "coca = article_nom(5449000000996, \"Coca-Cola 33cl\", 0.70)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "La variable $\\texttt{coca}$ contient un tuple nommé qui est illustré par la figure.  \n",
    "<img src=\"./images/named-tuple.png\" alt=\"named-tuple\"/>\n",
    "Toutes les opérations précédemment vues sur les tuples sont également applicables sur les tuples nommés.  \n",
    "\n",
    "Un tuple nommé est un tuple dont les différents éléments sont associés à un nom permettant d'y accéder de façon intuitive. L'avantage apporté par les tuples nommés est qu'on peut accéder à leurs attributs directement avec leur nom avec l'opérateur d'accès $(\\texttt{.})$. On fait donc suivre le nom de la variable du tuple nommé avec le nom de l'attribut, séparé par un point. On peut, par exemple, écrire :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Coca-Cola 33cl'"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coca.description"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4.199999999999999"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sixpackPrice = 6 * coca.price\n",
    "sixpackPrice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### $\\texttt{tuple}$ nommé  $\\texttt{vs.}$ dictionnaire  \n",
    "<a href=\"http://lycee.lagrave.free.fr/nsi/programmation/tuplevsdico.pdf\">$\\texttt{tuple}$ nommé  $\\texttt{vs.}$ dictionnaire</a>  \n",
    "* Éléments d'un tuple nommé ordonnés car séquence\n",
    "  - *Un dictionnaire est un ensemble de paires clé-valeur*  \n",
    "* Tuple nommé non modifiable  \n",
    "  - *On peut modifier et ajouter des valeurs à un dictionnaire*\n",
    "* Champs d'un tuple nommé sont des chaines de caractères cf. $[\\texttt{'barcode', 'description', 'price'}]$  \n",
    "  - *Les clés d'un dictionnaire sont des valeurs non modifiables*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### **Ce qu'on attend de vous dans ce cours pour structurée la donnée qui représenterai un article d'un magasin :**   \n",
    "En $\\texttt{Python}$, les **$p-$uplets nommés** sont implémentés par des dictionnaires."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coca = { 'barcode' : 5449000000996, 'description' : \"Coca-Cola 33cl\", 'price' : 0.70}\n",
    "type(coca)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Coca-Cola 33cl'"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coca['description']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4.199999999999999"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sixpackPrice = 6 * coca['price']\n",
    "sixpackPrice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Conclusion  \n",
    "Ce qu'il faut savoir faire à l'issue de cette partie :  (retenir/utiliser)\n",
    "* Notion d'ensembles :  \n",
    "  * contruction - modification - itération \n",
    "  * opérations ensemblistes de base\n",
    "* Les $p-$uplets nommés permettent les **enregistrements de valeurs de types différents** dans des champs nommés.  \n",
    "  En $\\texttt{Python}$, ils  sont implémentés par des **dictionnaires**.\n",
    "* Les <a href=\"https://pixees.fr/informatiquelycee/n_site/snt_photo_exif.html\" target=\"_blank\">données $\\texttt{EXIF}$ </a> d'une image peuvent-être présentées sous la forme d'un enregistrement ($\\texttt{dict}$).    \n",
    "* Dictionnaires par clés et valeurs  \n",
    "  * Construire une entrée de dictionnaire.\n",
    "  * Itérer sur les éléments d'un dictionnaire\n",
    "  * Utiliser les méthodes $\\texttt{keys}()$, $\\texttt{values}()$ et $\\texttt{items}()$.\n",
    "\n",
    "\n",
    "**Rappel :**   \n",
    "* La structure **itérable** -  \n",
    "  Nous avons vu que les 3 structures de données \"listes, $n-$uplets et chaı̂nes de caractères\"  \n",
    "  sont des cas particuliers d'une structure plus générale qu'on appelle un **itérable**.  \n",
    "  Il s'agit dans les 3 cas, d'une **collection ordonnée de valeurs que l'on peut parcourir** (en particulier à l'aide d'une boucle $\\texttt{for}$).  \n",
    "  Par défaut, un itérable n'a ni la structure de liste, ni de $n-$uplet, ni de chaı̂ne de caractères.  \n",
    "  On peut cependant facilement convertir (**transtyper**) n'importe quel itérable en :  \n",
    "   - une liste avec la fonction $\\texttt{list}()$  \n",
    "   - un tuple avec la fonction $\\texttt{tuple}()$  \n",
    "   - une chaı̂ne de caractères avec la fonction $\\texttt{str}()$."
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Diaporama",
  "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.3"
  },
  "rise": {
   "autolaunch": true,
   "enable_chalkboard": true,
   "scroll": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}