TP1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Programmation Python \n",
    "[**Paul Liautaud**](https://perso.lpsm.paris/~liautaud), [Sorbonne Université](http://www.sorbonne-universite.fr/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Mise en jambes et rappels\n",
    "## Structures de données et application"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ce TP a pour but principalement de refaire le point sur les premières structures de données en `Python`, et de manipuler les éléments qui nous seront essentiels dans la suite du cours.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div id=\"ch:structures\"></div>\n",
    "\n",
    "Pour représenter des structures de données, `Python` propose quatre types de base: les listes (type `list`), les tuples (type `tuple`), les ensembles (type `set`) et les dictionnaires (type `dict`). Le but  de ce chapitre est de montrer les différences fondamentales entre les 2 premières structures de données et d'expliquer à quoi elles sont le plus adaptées. La documentation détaillée sur les structures de données est disponible [ici](https://docs.python.org/fr/3/tutorial/datastructures.html).\n",
    "\n",
    "> **Concepts abordés:**\n",
    ">* structures de données (liste, tuple)\n",
    ">* types mutable et immutable\n",
    ">* type hashable\n",
    ">* compréhensions de liste\n",
    ">* suites numériques\n",
    ">* recherche dichotomique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 1 - Listes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div id=\"exer:structures-listes\"></div>\n",
    "\n",
    "Une liste est une structure permettant de stocker des éléments hétérogènes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list0 = [0, 5.4, \"chaîne\", True]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les listes sont mutables, c'est-à-dire qu'il est possible d'y modifier un élément, d'en rajouter un ou d'en supprimer un sans avoir à redéfinir toute la liste."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list0[3] = False # remplace True par False\n",
    "list0.append(\"nouveau\") # ajoute la chaîne de caractères \"nouveau\" à la liste\n",
    "list0.insert(2, 34) # insère 34 à la place 2\n",
    "list0.remove(0) # enlève 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En particulier, il faut faire attention en copiant une liste. Si l'on exécute le code suivant:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list1 = list0\n",
    "list1[2] = \"change\"\n",
    "list0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "alors `list0` est aussi modifié et est égal à `list1`.\n",
    "En effet, exécuter `list1 = list0` ne crée pas un nouvel objet (dans la mémoire vive de l'ordinateur), mais crée simplement une autre variable pointant vers le même objet.\n",
    "Pour le vérifier, il est possible d'utiliser la command `id` qui renvoie l'identifiant unique d'une variable : si deux variables ont le même identifiant, alors elles pointent vers le même objet.\n",
    "C'est le cas avec le code `list1 = list0`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "id(list0) == id(list1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour créer une vraie copie, il faut utiliser la méthode `copy`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list2 = list0.copy()\n",
    "list2[2] = \"rechange\"\n",
    "list0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "qui ne modifie pas `list0`.\n",
    "À noter qu'il est possible de modifier les éléments d'une liste à l'intérieur d'une fonction:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(l):\n",
    "    l[0] = 0\n",
    "f(list0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Enfin il est possible de créer des listes à l'aide de la compréhension de listes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list1 = [2*i+1 for i in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### It's your turn now !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**a)**\n",
    "Chercher dans la documentation la syntaxe pour concaténer deux listes.\n",
    "\n",
    "**Indication:**\n",
    "Voir la documentation [ici](https://docs.python.org/fr/3/library/stdtypes.html#sequence-types-list-tuple-range).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**b)**\n",
    "Chercher dans la documentation la syntaxe pour extraire une tranche d'une liste, c'est-à-dire: si `a` est par exemple une liste de longueur 10, retourner les éléments de 6 à 9.\n",
    "\n",
    "**Indication:**\n",
    "Voir la documentation [ici](https://docs.python.org/fr/3/library/stdtypes.html#sequence-types-list-tuple-range).\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**c)**\n",
    "Chercher dans la documentation la syntaxe pour retourner la longueur d'une liste.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**d)**\n",
    "Écrire une fonction `fibonacci(N)` qui retourne la liste des $N\\geq2$ premiers termes de la suite de Fibonacci définie par $u_{n+2} = u_{n+1}+u_n$ avec $u_0=0$ et $u_1=1$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**e)**\n",
    "Écrire une fonction `pascal(N)` qui retourne la $N$-ième ligne du triangle de Pascal:\n",
    "\n",
    "<center><img src=\"https://python.guillod.org/fig/pascal.png\" style=\"width:90%;max-width:150px;\"></center>\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**f)**\n",
    "Soit les suites $(u_n)_{n\\in\\mathbb{N}}$ et $(v_n)_{n\\in\\mathbb{N}}$ définies par $u_0=1$, $v_0=1$, et"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{align*}\n",
    "u_{n+1} &= u_n + v_n \\,, & v_{n+1} &= 2u _n - v_n \\,,\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "pour $n\\geq0$. Calculer $u_{100}$ et $v_{100}$.\n",
    "\n",
    "**Réponse:**\n",
    "$u_{100}=v_{100}=717897987691852588770249$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**g)**\n",
    "Écrire une fonction `vk(n0,K)`, qui pour deux entiers $n_0$ et $K\\geq1$ calcule la suite des valeurs $v_k$ définies par $v_0 = n_0$ et"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "v_{k+1}=\\begin{cases}\n",
    "3v_{k}+1 & \\text{si $v_{k}$ est impair},\\\\ \n",
    "\\frac{v_{k}}{2} & \\text{si $v_{k}$ est pair},\n",
    "\\end{cases}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "pour $0 \\leq k < K$. Pour $K = 1 000$ et diverses valeurs de $n_0 \\in \\{10, 100, 1 000, 10 000\\}$, afficher les cinq dernières\n",
    "valeurs calculées, c'est-à-dire $(v_{K-4},v_{K-3},v_{K-2},v_{K-1},v_K)$.\n",
    "\n",
    "**Réponse:**\n",
    "Les assertions suivantes sont vraies:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vk(10,1000) == [1, 4, 2, 1, 4]\n",
    "vk(100,1000) == [2, 1, 4, 2, 1]\n",
    "vk(1000,1000) == [1, 4, 2, 1, 4]\n",
    "vk(10000,1000) == [4, 2, 1, 4, 2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "<!-- --- end exercise --- -->\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "<!-- --- begin exercise --- -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 2 - Tuples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div id=\"exer:structures-tuples\"></div>\n",
    "\n",
    "Les tuples permettent tout comme les listes de stocker des éléments hétérogènes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tuple0 = (0, 5.4, \"chaîne\", True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mais au contraire des listes, les tuples ne sont pas mutables. Il n'est pas possible d'y modifier un élément, d'en rajouter un ou d'en supprimer un sans redéfinir tout le tuple.\n",
    "L'avantage d'un tuple sur une liste est qu'il est hashable, ce qui implique qu'il peut être utilisé comme clef dans un dictionnaire ou inclus dans un ensemble.\n",
    "\n",
    "Une fonction de hachage est une fonction injective permettant de calculer un identifiant unique pour chaque entrée,\n",
    "et donc de vérifier si deux entrées sont identiques en comparant leurs identifiants, ce qui est beaucoup plus rapide que de comparer toutes les entrées.\n",
    "Une fonction de hashage ne peut s'appliquer que sur des éléments pas mutables car sinon il faudrait modifier l'identifiant à chaque modification de l'élément.\n",
    "\n",
    "Enfin il est possible d'affecter des variables à l'intérieur d'un tuple, par exemple:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(a,b) = (1,9)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cela est en particulier très utile pour échanger deux variables sans avoir à utiliser une variable supplémentaire:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(a,b) = (b,a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**a)**\n",
    "Vérifier qu'un tuple est bien immutable.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**b)**\n",
    "Définir une fonction `mdlast(lst,val)` ayant pour argument une liste de tuples d'entiers `lst` et un entier `val` et retourner la liste de tuples avec le dernier élément de chaque tuple remplacé par `val`. Par exemple si `lst = [(10, 20), (30, 40, 50, 60), (70, 80, 90)]` alors `mdlast(lst,100)` doit retourner `[(10, 100), (30, 40, 50, 100), (70, 80, 100)]`.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**c)**\n",
    "Comment convertir un tuple en liste et réciproquement ?\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problème - Recherche d'un élément dans une liste triée\n",
    "\n",
    "**Problème :** On se donne une liste `liste` triée et contenant des éléments de type `float`ou `int` (on la supposera non vide pour la bonne définition du problème). On cherche alors à savoir si la valeur `a` est contenue dans `liste`.\n",
    "\n",
    ">**Principe :** On se propose alors d'effectuer une recherche par dichotomie. Le principe est simple mais permet >de réduire la complexité algorithmique.\n",
    ">\n",
    ">On compare la valeur `a` au terme central d'indice `moy`, dont les indices minimum et maximum sont `gauche` et >`droite`. Trois cas sont alors possibles :\n",
    ">* ils sont identiques (i.e. `a`= `liste[moy]`) : la recherche est terminée;\n",
    ">* `a` < `liste[moy]` (il est inférieur à ce terme) : on reprend la recherche dans la moitié de la liste précédent >ce terme central `liste[moy]` (i.e. à gauche), dont le premier terme est toujours d'indice `gauche`, le dernier >terme devenant maintenant d'indice `moy - 1`;\n",
    ">* `a` > `liste[moy]` (il est supérieur à ce terme) : on reprend la recherche dans la moitié de la liste suivant >ce terme central `liste[moy]` (i.e. à droite) dont le premier terme est maintenant d'indice `moy + 1` et le >dernier étant d'indice `droite`.\n",
    ">\n",
    ">Le procédé est alors à poursuivre jusqu'à ce que l'intervalle soit réduit à un seul terme !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On considèrera alors la liste suivante pour l'étude de ce principe :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "liste = [1, 100, 10.5, 12.36, 18.49, 0.46, 19.3, 2600.45, 36.37, 20, 78.15, 99.99, 90]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**a)** Coder une première fonction `naive(liste, a)` qui effectue une recherche classique (donc non dichotomique) de l'élément `a` dans `liste`. Elle retournera un booléen (`True` si `a` est bien contenu dans `liste`, et `False` sinon)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**b)** Vérifier que votre fonction `naive` vérifie les assertions suivantes :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(naive(liste, 99.99) == 1)\n",
    "print(naive(liste, 22) == 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**c)** Implémenter maintenant une fonction `dicho(liste, a)` qui effectue une recherche dans `liste` de l'élément `a` selon le principe de dichotomie expliqué."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Section Bonus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour les plus rapides, vous pouvez vous amuser à découvrir 2 autres structures en `Python`. Celles-ci n'étant cependant pas mentionnées dans le programme officiel."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 1 - Ensembles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div id=\"exer:structures-ensembles\"></div>\n",
    "\n",
    "Les ensembles permettent de stocker des éléments hétérogènes au sens mathématique de la théorie des ensembles:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "set0 = {0, 5.4, \"chaîne\", True}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il est possible de tester si un élément appartient à un ensemble:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if \"chaîne\" in set0:\n",
    "    print(\"dedans\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les ensembles sont mutables, il est donc possible de rajouter ou retirer un élément d'un ensemble:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "set0.add(18) # ajoute 18 à l'ensemble\n",
    "set0.add(0) # ajoute 0 à l'ensemble (ne fait rien car 0 est déjà dedans)\n",
    "set0.remove(\"chaîne\") # retire \"chaîne de l'ensemble"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En revanche les ensembles ne peuvent contenir que des éléments hashables, c'est-à-dire immutables.\n",
    "La raison est que les ensembles utilisent des [tables de hachage](https://fr.wikipedia.org/wiki/Table_de_hachage) permettant de calculer très rapidement si un élément est présent dans un ensemble, bien plus rapidement que dans une liste ou un tuple. \n",
    "En particulier un ensemble ne peut pas contenir un autre ensemble:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "set1 = {{1,2},{3},{4}}\n",
    "TypeError: unhashable type: 'set'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "À noter qu'il existe également en Python des ensembles immutables `frozenset`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "frozenset0 = frozenset([0, 5.4, \"chaîne\", True])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une chaîne de caractères peut être transformée en ensemble:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "set1 = set('abracadabra')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comme pour les listes, il est possible de faire des compréhensions d'ensembles:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "set2 = {x for x in 'abracadabra' if x not in 'abc'}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans cet exemple les chaînes de caractères sont automatiquement transformées en ensemble.\n",
    "À noter que l'ensemble vide est défini par `set()`.\n",
    "\n",
    "**a)**\n",
    "Définir une fonction `divisible(n)` qui retourne l'ensemble des nombres entiers divisibles par `n` inférieurs ou égaux à 100.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**b)**\n",
    "Chercher dans la documentation comment faire l'intersection, l'union, et la différence de deux ensembles. Déterminer les nombres inférieurs ou égaux à 100 qui sont non divisibles par 2 mais divisibles par 3 et 5.\n",
    "\n",
    "**Indication:**\n",
    "Voir la documentation de `set` [ici](https://docs.python.org/fr/3/library/stdtypes.html#set).\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 2 - Dictionnaires"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div id=\"exer:structures-dictionnaires\"></div>\n",
    "\n",
    "Les dictionnaires sont une structure permettant de stocker des éléments hétérogènes indexés par des clefs (elles aussi hétérogènes):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dict0 = {\"pommes\": 0, \"poires\": 4, 12: 2}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les éléments d'un dictionnaire sont accessibles par les clefs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dict0[\"pommes\"]\n",
    "dict0[12]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un dictionnaire peut être vu comme un tableau associatif associant à chaque clef une valeur. La liste des clefs et celle des valeurs sont accessibles respectivement avec `dict0.keys()` et `dict0.values()`.\n",
    "Les dictionnaires sont mutables, il est donc possible de modifier une association clef-valeur et d'en rajouter ou supprimer une:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dict0[\"pommes\"] = 3 # modifie la valeur associée à pommes\n",
    "dict0[\"oranges\"] = \"beaucoup\" # rajoute oranges comme clef avec la valeur \"beaucoup\"\n",
    "del dict0[\"poires\"] # supprime le couple clef-valeur associé à poires\n",
    "dict0.pop(\"pommes\") # supprime le couple clef-valeur associé à pommes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bien qu'un dictionnaire soit mutable, les clefs qui le composent doivent être des objets hashables, c'est-à-dire immutables.\n",
    "La raison est que Python utilise une fonction de hashage sur les clefs pour des questions de performance.\n",
    "Ainsi une liste ou un ensemble ne peuvent pas servir de clefs dans un dictionnaire:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dict0[list0] = \"test\"\n",
    "TypeError: unhashable type: 'list'\n",
    "dict0[set0] = \"retest\"\n",
    "TypeError: unhashable type: 'set'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En revanche il est possible d'avoir un tuple ou un frozenset comme clef:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dict0[tuple0] = \"test\"\n",
    "dict0[frozenset0] = \"rest\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "d'où l'intérêt des frozensets.\n",
    "Comme pour les listes et les ensembles, il est possible de faire des compréhensions de dictionnaires:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dict1 = {x: x**2 for x in range(5)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finalement une chose intéressante avec les dictionnaires est l'unpaking illustré par l'exemple suivant:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def add(a=0, b=0):\n",
    "    return a + b\n",
    "d = {'a': 2, 'b': 3}\n",
    "add(**d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**a)**\n",
    "Comment définir un dictionnaire vide ?\n",
    "\n",
    "**b)**\n",
    "Comment concaténer plusieurs dictionnaires entre eux ?\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**c)**\n",
    "On considère une liste de mots:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mots = ['Abricot', 'Airelle', 'Ananas', 'Banane', 'Cassis', 'Cerise', 'Citron',\\\n",
    "'Clémentine', 'Coing', 'Datte', 'Fraise', 'Framboise', 'Grenade', 'Groseille',\\\n",
    "'Kaki', 'Kiwi', 'Litchi', 'Mandarine', 'Mangue', 'Melon', 'Mirabelle', 'Nectarine',\\\n",
    "'Orange', 'Pamplemousse', 'Papaye', 'Pêche', 'Poire', 'Pomme', 'Prune', 'Raisin']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Écrire une fonction `position(mots, x, n)` qui retourne la liste des mots ayant le caractère `x` comme `n`-ième lettre.\n",
    "\n",
    "**Réponse:**\n",
    "Par exemple `position(mots,'e',4)` doit retourner la liste:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "['Clémentine', 'Datte', 'Groseille', 'Pêche', 'Poire', 'Pomme', 'Prune']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**d)**\n",
    "En imaginant que la liste des mots soit très longue, alors à chaque évaluation de la fonction `position` l'ensemble des mots est parcouru, ce qui prend pas mal de temps. Pour améliorer cela, construire un dictionnaire `mots_dict` ayant pour clefs les tuples `(x,n)` et comme valeurs la liste des mots ayant le caractère `x` comme `n`-ième lettre, c'est-à-dire tel que `mots_dict[x,n]` retourne la même chose que `position(mots, x , n)` à l'ordre près. Ainsi la liste `mots` n'est parcourue qu'une seule fois lors de la construction du dictionnaire et ensuite l'évaluation du dictionnaire est extrêmement rapide pour n'importe quelle requête.\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}