{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 1A.e - Correction de l'interrogation \u00e9crite du 10 octobre 2014\n", "\n", "dictionnaire et co\u00fbt algorithmique"]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["\n", ""], "text/plain": [""]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Enonc\u00e9 1"]}, {"cell_type": "markdown", "metadata": {}, "source": ["#### Q1\n", "\n", "Ecrire une fonction qui prend une cha\u00eene de caract\u00e8res en argument et la retourne sans ses voyelles."]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [{"data": {"text/plain": ["('bnjr', ' rvr')"]}, "execution_count": 3, "metadata": {}, "output_type": "execute_result"}], "source": ["def pas_de_voyelle(mot):\n", " s = \"\"\n", " for c in mot :\n", " if c not in \"aeiouy\" : \n", " s += c\n", " return s\n", "\n", "pas_de_voyelle(\"bonjour\"), pas_de_voyelle(\"au revoir\")"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Cette r\u00e9ponse n'est qu'une r\u00e9ponse parmi d'autres. Certains utilisaient la m\u00e9thode [replace](https://docs.python.org/3.4/library/stdtypes.html#str.replace), d'autres un test ``c == \"a\" or c == \"e\" ...``."]}, {"cell_type": "markdown", "metadata": {}, "source": ["#### Q2\n", "\n", "Transformer une matrice repr\u00e9sent\u00e9e sous forme de double liste (exemple : ``[[0,1,0],[0,0,1]]``) en un dictionnaire dont les cl\u00e9s sont les coordonn\u00e9es et les valeurs les coefficients (soit autant d'\u00e9l\u00e9ments que de valeurs non nulles)."]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [{"data": {"text/plain": ["{(0, 1): 1, (1, 2): 1}"]}, "execution_count": 4, "metadata": {}, "output_type": "execute_result"}], "source": ["mat = [[0,1,0],[0,0,1]]\n", "\n", "mat_dict = { }\n", "for i,line in enumerate(mat) :\n", " for j,c in enumerate(line) :\n", " if c != 0 :\n", " mat_dict[i,j] = c\n", "\n", "mat_dict"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Pour cette question, le code \u00e9crit fonction doit fonctionner pour n'importe quelle matrice."]}, {"cell_type": "markdown", "metadata": {}, "source": ["#### Q3\n", "\n", "Calculer $\\sum_{i=1}^{10} \\frac{1}{i}$"]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [{"data": {"text/plain": ["2.9289682539682538"]}, "execution_count": 5, "metadata": {}, "output_type": "execute_result"}], "source": ["sum ( 1/i for i in range(1,11) )"]}, {"cell_type": "markdown", "metadata": {}, "source": ["#### Q4\n", "\n", "Quel le co\u00fbt du programme suivant en $O(N)$ ?"]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["581.4676254832484\n"]}], "source": ["from math import log\n", "s = 0\n", "N = 100\n", "while N > 1 :\n", " for i in range(1, N):\n", " s += log(i)\n", " N //= 2\n", "print(s)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["La premi\u00e8re boucle s'ex\u00e9cute pour les valeurs $N$, $N/2$, $N/4$, ... jusqu'\u00e0 ce que $N \\leqslant 1$. La boucle imbriqu\u00e9e fait la somme des $log$ de 1 \u00e0 $N$. Le nombre des op\u00e9rations est en $O(N + N/2 + N/4 + ...)$, soit quelque chose comme $N \\sum_{i=1}^{\\ln_2 N} \\frac{1}{2^i} \\leqslant N \\sum_{i=1}^{\\infty} \\frac{1}{2^i} \\leqslant 2N$ (c'est une somme g\u00e9om\u00e9trique). On v\u00e9rifie avec le code suivant qui compte le nombre de fois o\u00f9 on ajoute un logarithme."]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["10000 19981 20000\n", "20000 39980 40000\n", "30000 59978 60000\n", "40000 79979 80000\n", "50000 99978 100000\n", "60000 119977 120000\n", "70000 139977 140000\n", "80000 159978 160000\n", "90000 179974 180000\n"]}], "source": ["def calcul(N):\n", " s = 0\n", " c = 0\n", " while N > 1 :\n", " for i in range(1, N):\n", " s += log(i)\n", " c += 1\n", " N //= 2\n", " return c\n", "for i in range(10000,100000, 10000) :\n", " print( i, calcul(i), i * 2 )"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Enonc\u00e9 2"]}, {"cell_type": "markdown", "metadata": {}, "source": ["#### Q1\n", "\n", "On consid\u00e8re un mot ``abcdef``, puis on construit un autre mot selon le sch\u00e9ma :\n", "\n", "* 1\u00e8re lettre, derni\u00e8re lettre, 2\u00e8me lettre, avant-derni\u00e8re lettre, 3\u00e8me lettre, ...\n", "* Exemple 1 : ``abcdef`` $\\rightarrow$ ``afbecd``\n", "* Exemple 2 : ``kayak`` $\\rightarrow$ ``kkaay``"]}, {"cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [{"data": {"text/plain": ["('afbecd', 'kkaay')"]}, "execution_count": 8, "metadata": {}, "output_type": "execute_result"}], "source": ["def strange(mot):\n", " s = \"\"\n", " for i in range(len(mot)//2) :\n", " s += mot[i] + mot[-i-1]\n", " if len(mot)%2 == 1 :\n", " s += mot[len(mot)//2]\n", " return s\n", "\n", "strange(\"abcdef\"), strange(\"kayak\")"]}, {"cell_type": "markdown", "metadata": {}, "source": ["#### Q2\n", "\n", "Retourner un dictionnaire : les cl\u00e9s deviennent les valeurs et les valeurs deviennent les cl\u00e9s (on suppose que les cl\u00e9s et valeurs sont uniques)."]}, {"cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [{"data": {"text/plain": ["{'valeur2': 'cle2', 'valeur1': 'cle1'}"]}, "execution_count": 9, "metadata": {}, "output_type": "execute_result"}], "source": ["dictionnaire_depart = { \"cle1\":\"valeur1\", \"cle2\":\"valeur2\" }\n", "dictionnaire_retourne = { } \n", "for k,v in dictionnaire_depart.items():\n", " dictionnaire_retourne[v] = k\n", " \n", "dictionnaire_retourne"]}, {"cell_type": "markdown", "metadata": {}, "source": ["La m\u00e9thode [items](https://docs.python.org/3.4/library/stdtypes.html#dict.items) retourne un [it\u00e9rateur](http://fr.wikipedia.org/wiki/It%C3%A9rateur) et non une liste. Un it\u00e9reur n'est pas un ensemble mais une fa\u00e7on de parcourir tous les \u00e9l\u00e9ments d'un ensemble."]}, {"cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["dict_items([('cle1', 'valeur1'), ('cle2', 'valeur2')])\n", "[('cle1', 'valeur1'), ('cle2', 'valeur2')]\n"]}], "source": ["dictionnaire_depart = { \"cle1\":\"valeur1\", \"cle2\":\"valeur2\" }\n", "\n", "print ( dictionnaire_depart.items() )\n", "print ( list ( dictionnaire_depart.items() ) )"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Le python est un langage paresseux car tr\u00e8s lent. Il faut lui demander de fa\u00e7on explicite de construire un ensemble ou de copier un ensemble. Par d\u00e9faut, il ne copie jamais un dictionnaire ou une liste et il pr\u00e9f\u00e8re retourner un it\u00e9rateur plut\u00f4t qu'une copie d'un ensemble. La plupart du temps, on ne s'en aper\u00e7oit pas \u00e0 moins de vouloir acc\u00e9der \u00e0 un \u00e9l\u00e9ment pr\u00e9cis de l'ensemble :"]}, {"cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [{"ename": "TypeError", "evalue": "'dict_items' object does not support indexing", "output_type": "error", "traceback": ["\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mTypeError\u001b[0m Traceback (most recent call last)", "\u001b[1;32m\u001b[0m in \u001b[0;36m\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mdictionnaire_depart\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mitems\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[1;31mTypeError\u001b[0m: 'dict_items' object does not support indexing"]}], "source": ["dictionnaire_depart.items() [0]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["La fonction ``ensemble`` suivante retourne une liste d'\u00e9l\u00e9ments, la fonction ``iterateur`` retourne une fa\u00e7on de parcourir un ensemble. On appelle ce type ce fonction un [g\u00e9n\u00e9rateur](https://docs.python.org/3/glossary.html#term-generator)."]}, {"cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["\n", "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n"]}], "source": ["def ensemble(a,b):\n", " res = [ ]\n", " while a < b :\n", " res.append ( a )\n", " a += 1\n", " return res\n", "\n", "def iterateur(a,b):\n", " while a < b :\n", " yield a\n", " a += 1\n", " \n", "print( iterateur(0,10) )\n", "print( ensemble(0,10) )"]}, {"cell_type": "markdown", "metadata": {}, "source": ["On ne peut acc\u00e9der aux \u00e9l\u00e9ments d'un g\u00e9n\u00e9rateur car cela n'a pas de sens :"]}, {"cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [{"ename": "TypeError", "evalue": "'generator' object is not subscriptable", "output_type": "error", "traceback": ["\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mTypeError\u001b[0m Traceback (most recent call last)", "\u001b[1;32m\u001b[0m in \u001b[0;36m\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0miterateur\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m10\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[1;31mTypeError\u001b[0m: 'generator' object is not subscriptable"]}], "source": ["iterateur(0,10) [0]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Mais on peut parcourir les \u00e9l\u00e9ments g\u00e9n\u00e9r\u00e9s :"]}, {"cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["0\n", "1\n", "2\n", "3\n", "4\n", "5\n", "6\n", "7\n", "8\n", "9\n"]}], "source": ["for x in iterateur(0,10):\n", " print(x)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["#### Q3\n", "\n", "Calculer $\\frac{1}{1000} \\sum_{i=1}^{1000} e^{ \\frac{i}{1000} }$."]}, {"cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [{"data": {"text/plain": ["1.7191411125634257"]}, "execution_count": 15, "metadata": {}, "output_type": "execute_result"}], "source": ["from math import exp\n", "1/1000 * sum ( exp ( i / 1000 ) for i in range(1,1001) )"]}, {"cell_type": "markdown", "metadata": {}, "source": ["#### Q4\n", "\n", "Quel le co\u00fbt du programme suivant en $O(N)$ ?"]}, {"cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["317.3177321667311\n"]}], "source": ["from math import log\n", "s = 0\n", "ii = 1\n", "N = 7\n", "for i in range(1,N):\n", " ii *= 2\n", " for k in range(1,ii):\n", " s += log(k)\n", "print(s)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["A chaque it\u00e9ration $i$, on calcule $2^i$ logarithmes. On fait $N$ it\u00e9rations soit $1 + 2 + 4 + ... + 2^N$ calculs, c'est-\u00e0-dire environ $O(1 + 2^1 + 2^2 + 2^3 + ... + 2^N) = O(2^{N+1}) = O(2^N)$ (c'est une somme g\u00e9om\u00e9trique)."]}, {"cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["1013 1024\n", "2036 2048\n", "4083 4096\n", "8178 8192\n", "16369 16384\n", "32752 32768\n", "65519 65536\n", "131054 131072\n", "262125 262144\n", "524268 524288\n"]}], "source": ["from math import log\n", "\n", "def calcul(N):\n", " s = 0\n", " ii = 1\n", " c = 0\n", " for i in range(1,N):\n", " ii *= 2\n", " for k in range(1,ii):\n", " s += log(k)\n", " c += 1\n", " return c\n", "\n", "for N in range(10,20):\n", " print(calcul(N), 2**N)"]}, {"cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [], "source": []}], "metadata": {"kernelspec": {"display_name": "Python 3", "language": "python", "name": "python3"}, "language_info": {"codemirror_mode": {"name": "ipython", "version": 3}, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.1"}}, "nbformat": 4, "nbformat_minor": 2}