{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 1A.e - TD not\u00e9, 5 d\u00e9cembre 2014\n", "\n", "Parcours de chemins dans un graphe acyclique (arbre)."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["<div id=\"my_id_menu_nb\">run previous cell, wait for 2 seconds</div>\n", "<script>\n", "function repeat_indent_string(n){\n", "    var a = \"\" ;\n", "    for ( ; n > 0 ; --n)\n", "        a += \"    \";\n", "    return a;\n", "}\n", "var update_menu_string = function(begin, lfirst, llast, sformat, send, keep_item, begin_format, end_format) {\n", "    var anchors = document.getElementsByClassName(\"section\");\n", "    if (anchors.length == 0) {\n", "        anchors = document.getElementsByClassName(\"text_cell_render rendered_html\");\n", "    }\n", "    var i,t;\n", "    var text_menu = begin;\n", "    var text_memo = \"<pre>\\nlength:\" + anchors.length + \"\\n\";\n", "    var ind = \"\";\n", "    var memo_level = 1;\n", "    var href;\n", "    var tags = [];\n", "    var main_item = 0;\n", "    var format_open = 0;\n", "    for (i = 0; i <= llast; i++)\n", "        tags.push(\"h\" + i);\n", "\n", "    for (i = 0; i < anchors.length; i++) {\n", "        text_memo += \"**\" + anchors[i].id + \"--\\n\";\n", "\n", "        var child = null;\n", "        for(t = 0; t < tags.length; t++) {\n", "            var r = anchors[i].getElementsByTagName(tags[t]);\n", "            if (r.length > 0) {\n", "child = r[0];\n", "break;\n", "            }\n", "        }\n", "        if (child == null) {\n", "            text_memo += \"null\\n\";\n", "            continue;\n", "        }\n", "        if (anchors[i].hasAttribute(\"id\")) {\n", "            // when converted in RST\n", "            href = anchors[i].id;\n", "            text_memo += \"#1-\" + href;\n", "            // passer \u00e0 child suivant (le chercher)\n", "        }\n", "        else if (child.hasAttribute(\"id\")) {\n", "            // in a notebook\n", "            href = child.id;\n", "            text_memo += \"#2-\" + href;\n", "        }\n", "        else {\n", "            text_memo += \"#3-\" + \"*\" + \"\\n\";\n", "            continue;\n", "        }\n", "        var title = child.textContent;\n", "        var level = parseInt(child.tagName.substring(1,2));\n", "\n", "        text_memo += \"--\" + level + \"?\" + lfirst + \"--\" + title + \"\\n\";\n", "\n", "        if ((level < lfirst) || (level > llast)) {\n", "            continue ;\n", "        }\n", "        if (title.endsWith('\u00b6')) {\n", "            title = title.substring(0,title.length-1).replace(\"<\", \"&lt;\")\n", "         .replace(\">\", \"&gt;\").replace(\"&\", \"&amp;\");\n", "        }\n", "        if (title.length == 0) {\n", "            continue;\n", "        }\n", "\n", "        while (level < memo_level) {\n", "            text_menu += end_format + \"</ul>\\n\";\n", "            format_open -= 1;\n", "            memo_level -= 1;\n", "        }\n", "        if (level == lfirst) {\n", "            main_item += 1;\n", "        }\n", "        if (keep_item != -1 && main_item != keep_item + 1) {\n", "            // alert(main_item + \" - \" + level + \" - \" + keep_item);\n", "            continue;\n", "        }\n", "        while (level > memo_level) {\n", "            text_menu += \"<ul>\\n\";\n", "            memo_level += 1;\n", "        }\n", "        text_menu += repeat_indent_string(level-2);\n", "        text_menu += begin_format + sformat.replace(\"__HREF__\", href).replace(\"__TITLE__\", title);\n", "        format_open += 1;\n", "    }\n", "    while (1 < memo_level) {\n", "        text_menu += end_format + \"</ul>\\n\";\n", "        memo_level -= 1;\n", "        format_open -= 1;\n", "    }\n", "    text_menu += send;\n", "    //text_menu += \"\\n\" + text_memo;\n", "\n", "    while (format_open > 0) {\n", "        text_menu += end_format;\n", "        format_open -= 1;\n", "    }\n", "    return text_menu;\n", "};\n", "var update_menu = function() {\n", "    var sbegin = \"\";\n", "    var sformat = '<a href=\"#__HREF__\">__TITLE__</a>';\n", "    var send = \"\";\n", "    var begin_format = '<li>';\n", "    var end_format = '</li>';\n", "    var keep_item = -1;\n", "    var text_menu = update_menu_string(sbegin, 2, 4, sformat, send, keep_item,\n", "       begin_format, end_format);\n", "    var menu = document.getElementById(\"my_id_menu_nb\");\n", "    menu.innerHTML=text_menu;\n", "};\n", "window.setTimeout(update_menu,2000);\n", "            </script>"], "text/plain": ["<IPython.core.display.HTML object>"]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Apr\u00e8s chaque question, on v\u00e9rifie sur un petit exemple que cela fonctionne comme attendu."]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Exercice 1\n", "\n", "Ce premier exercice aborde la probl\u00e8me d'un parcours de graphe non r\u00e9cursif.\n", "\n", "**Q1**"]}, {"cell_type": "code", "execution_count": 2, "metadata": {"collapsed": true}, "outputs": [], "source": ["def adjacence(N):\n", "    # on cr\u00e9e uen matrice vide\n", "    mat = [ [ 0 for j in range(N) ] for i in range(N) ]\n", "    for i in range(0,N-1):\n", "        mat[i][i+1] = 1\n", "    return mat"]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [{"data": {"text/plain": ["[[0, 1, 0, 0, 0, 0, 0],\n", " [0, 0, 1, 0, 0, 0, 0],\n", " [0, 0, 0, 1, 0, 0, 0],\n", " [0, 0, 0, 0, 1, 0, 0],\n", " [0, 0, 0, 0, 0, 1, 0],\n", " [0, 0, 0, 0, 0, 0, 1],\n", " [0, 0, 0, 0, 0, 0, 0]]"]}, "execution_count": 4, "metadata": {}, "output_type": "execute_result"}], "source": ["mat = adjacence(7)\n", "mat"]}, {"cell_type": "markdown", "metadata": {}, "source": ["**Q2**\n", "\n", "Il faut ajouter 5 arcs au hasard en \u00e9vitant d'ajouter deux fois le m\u00eame."]}, {"cell_type": "code", "execution_count": 4, "metadata": {"collapsed": true}, "outputs": [], "source": ["import random\n", "def ajoute_points(mat,nb=5):\n", "    ajout = { }\n", "    while len(ajout) < 5 :\n", "        i,j = random.randint(0,len(mat)-1),random.randint(0,len(mat)-1)\n", "        if i < j and (i,j) not in ajout:\n", "            mat[i][j] = 1\n", "            ajout[i,j] = 1"]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [{"data": {"text/plain": ["[[0, 1, 0, 0, 0, 0, 1],\n", " [0, 0, 1, 0, 0, 0, 1],\n", " [0, 0, 0, 1, 1, 0, 0],\n", " [0, 0, 0, 0, 1, 1, 0],\n", " [0, 0, 0, 0, 0, 1, 0],\n", " [0, 0, 0, 0, 0, 0, 1],\n", " [0, 0, 0, 0, 0, 0, 0]]"]}, "execution_count": 6, "metadata": {}, "output_type": "execute_result"}], "source": ["ajoute_points(mat)\n", "mat"]}, {"cell_type": "markdown", "metadata": {}, "source": ["**Q3**"]}, {"cell_type": "code", "execution_count": 6, "metadata": {"collapsed": true}, "outputs": [], "source": ["def successeurs(adj,i):\n", "    ligne = adj[i]\n", "    # dans l'expression suivante, \n", "    # s est la valeur de la matrice (0 ou 1)\n", "    # i l'indice\n", "    return [ i for i,s in enumerate(ligne) if s == 1  ]"]}, {"cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [{"data": {"text/plain": ["[2, 6]"]}, "execution_count": 8, "metadata": {}, "output_type": "execute_result"}], "source": ["successeurs(mat, 1)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["**Q4**"]}, {"cell_type": "code", "execution_count": 8, "metadata": {"collapsed": true}, "outputs": [], "source": ["def successeurs_dico(adj):\n", "    return { i:successeurs(adj, i) for  i in range(len(adj)) }"]}, {"cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [{"data": {"text/plain": ["{0: [1, 6], 1: [2, 6], 2: [3, 4], 3: [4, 5], 4: [5], 5: [6], 6: []}"]}, "execution_count": 10, "metadata": {}, "output_type": "execute_result"}], "source": ["dico = successeurs_dico(mat)\n", "dico"]}, {"cell_type": "markdown", "metadata": {}, "source": ["**Q5**"]}, {"cell_type": "code", "execution_count": 10, "metadata": {"collapsed": true}, "outputs": [], "source": ["def suites_chemin(chemin, dico):\n", "    dernier = chemin[-1]\n", "    res = [ ]\n", "    for s in dico[dernier]:\n", "        res.append ( chemin + [ s ] )\n", "    return res"]}, {"cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [{"data": {"text/plain": ["[[0, 1, 2], [0, 1, 6]]"]}, "execution_count": 12, "metadata": {}, "output_type": "execute_result"}], "source": ["suites_chemin( [ 0, 1 ], dico)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["**Q6**"]}, {"cell_type": "code", "execution_count": 12, "metadata": {"collapsed": true}, "outputs": [], "source": ["def parcours(adj):\n", "    dico = successeurs_dico(adj)\n", "    chemins = [ [ 0 ]]\n", "    resultat = [ ]\n", "    while len(chemins) > 0 :\n", "        chemins2 = []\n", "        for chemin in chemins :\n", "            res = suites_chemin(chemin, dico)\n", "            if len(res) == 0:\n", "                # chemin est un chemin qui ne peut \u00eatre continu\u00e9\n", "                resultat.append ( chemin )\n", "            else:\n", "                chemins2.extend ( res ) \n", "        chemins = chemins2\n", "    return resultat"]}, {"cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [{"data": {"text/plain": ["[[0, 6],\n", " [0, 1, 6],\n", " [0, 1, 2, 3, 5, 6],\n", " [0, 1, 2, 4, 5, 6],\n", " [0, 1, 2, 3, 4, 5, 6]]"]}, "execution_count": 14, "metadata": {}, "output_type": "execute_result"}], "source": ["parcours(mat)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["**Q7**"]}, {"cell_type": "markdown", "metadata": {}, "source": ["La diff\u00e9rence entre un parcours en profondeur et un parcours en largeur tient au fait qu'on pr\u00e9f\u00e8re d'abord explorer le successeur direct, puis le successeur direct plut\u00f4t que les voisins du successeurs directe. Dans le premier cas, on aboutit tr\u00e8s vite \u00e0 un chemin termin\u00e9. Dans le second cas, on obtient les chemins plut\u00f4t vers la fin de l'algorithme. Dans la version propos\u00e9e par l'algorithme, c'est un **parcours en largeur** qui est impl\u00e9ment\u00e9."]}, {"cell_type": "markdown", "metadata": {}, "source": ["**Q8**\n", "\n", "La matrice en question est la suivante (pour $N=7$) :"]}, {"cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [{"data": {"text/plain": ["[[0, 1, 1, 1, 1, 1, 1],\n", " [0, 0, 1, 1, 1, 1, 1],\n", " [0, 0, 0, 1, 1, 1, 1],\n", " [0, 0, 0, 0, 1, 1, 1],\n", " [0, 0, 0, 0, 0, 1, 1],\n", " [0, 0, 0, 0, 0, 0, 1],\n", " [0, 0, 0, 0, 0, 0, 0]]"]}, "execution_count": 15, "metadata": {}, "output_type": "execute_result"}], "source": ["def adjacence8(N):\n", "    # on cr\u00e9e uen matrice vide\n", "    mat = [ [ 0 for j in range(N) ] for i in range(N) ]\n", "    for i in range(0,N-1):\n", "        for j in range(i+1,N):\n", "            mat[i][j] = 1\n", "    return mat\n", "\n", "adj = adjacence8(7)\n", "adj"]}, {"cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["nombre 32\n"]}, {"data": {"text/plain": ["[[0, 6],\n", " [0, 1, 6],\n", " [0, 2, 6],\n", " [0, 3, 6],\n", " [0, 4, 6],\n", " [0, 5, 6],\n", " [0, 1, 2, 6],\n", " [0, 1, 3, 6],\n", " [0, 1, 4, 6],\n", " [0, 1, 5, 6],\n", " [0, 2, 3, 6],\n", " [0, 2, 4, 6],\n", " [0, 2, 5, 6],\n", " [0, 3, 4, 6],\n", " [0, 3, 5, 6],\n", " [0, 4, 5, 6],\n", " [0, 1, 2, 3, 6],\n", " [0, 1, 2, 4, 6],\n", " [0, 1, 2, 5, 6],\n", " [0, 1, 3, 4, 6],\n", " [0, 1, 3, 5, 6],\n", " [0, 1, 4, 5, 6],\n", " [0, 2, 3, 4, 6],\n", " [0, 2, 3, 5, 6],\n", " [0, 2, 4, 5, 6],\n", " [0, 3, 4, 5, 6],\n", " [0, 1, 2, 3, 4, 6],\n", " [0, 1, 2, 3, 5, 6],\n", " [0, 1, 2, 4, 5, 6],\n", " [0, 1, 3, 4, 5, 6],\n", " [0, 2, 3, 4, 5, 6],\n", " [0, 1, 2, 3, 4, 5, 6]]"]}, "execution_count": 16, "metadata": {}, "output_type": "execute_result"}], "source": ["che = parcours(adj)\n", "print(\"nombre\",len(che))\n", "che"]}, {"cell_type": "markdown", "metadata": {}, "source": ["On fait une petite boucle pour intuiter le r\u00e9sultat :"]}, {"cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["5 --> 8\n", "6 --> 16\n", "7 --> 32\n", "8 --> 64\n", "9 --> 128\n", "10 --> 256\n"]}], "source": ["for i in range(5,11):\n", "    adj = adjacence8(i)\n", "    che = parcours(adj)\n", "    print(i, \"-->\",len(che))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Cela ressemble beaucoup \u00e0 des puissances de deux. Cela sugg\u00e8re un raisonnement par r\u00e9currence. Chaque noeud $i$ est connect\u00e9 \u00e0 tous les suivantes $i+1$, $i+2$... On remarque que tous les chemins se termine par le dernier noeud $n$. Lorsqu'on ajoute le noeud $n+1$ au graphe, il sera le successeur de tous les autres. Pour un chemin donn\u00e9, on peut soit l'ajouter \u00e0 la fin, soit remplacer le dernier noeud $n$ par $n-1$. C'est ainsi qu'on multiplie par deux le nombre de chemins. S'il y a $n$ noeuds, on obtient $2^{n-2}$."]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Exercice 2\n", "\n", "On suppose qu'on dispose d'un tableau de nombres non tri\u00e9. Ecrire une fonction qui retourne les trois \u00e9l\u00e9ments minimaux.\n", "\n", "La premi\u00e8re option consiste \u00e0 utiliser la fonction [sort](https://docs.python.org/3.4/library/stdtypes.html?highlight=list#list.sort). Celle-ci a un co\u00fbt de $O(n \\ln n)$ le programme est tr\u00e8s simple."]}, {"cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [{"data": {"text/plain": ["[-1, 1, 4]"]}, "execution_count": 18, "metadata": {}, "output_type": "execute_result"}], "source": ["l = [ -1, 4, 6, 4, 1, 9, 5 ]\n", "l.sort()\n", "l[:3]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Le probl\u00e8me qu'on cherche \u00e0 r\u00e9soudre est plus simple puisqu'il s'agit de ne garder que les trois premiers \u00e9l\u00e9ments. On n'a pas besoin de trier la fin de la liste. L'id\u00e9e consiste \u00e0 parcourir le tableau et \u00e0 ne conserver que les trois premiers \u00e9l\u00e9ments. Si un \u00e9l\u00e9ment est plus grand que le troisi\u00e8me \u00e9l\u00e9ment, on ne s'en occupe pas."]}, {"cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [{"data": {"text/plain": ["[-1, 1, 4]"]}, "execution_count": 19, "metadata": {}, "output_type": "execute_result"}], "source": ["def garde_3_element(tab):\n", "    meilleur = [ ]\n", "    for t in tab:\n", "        if len(meilleur) < 3 :\n", "            meilleur.append(t)\n", "            meilleur.sort()\n", "        elif t < meilleur[2] :\n", "            meilleur[2] = t\n", "            meilleur.sort()\n", "    return meilleur\n", "\n", "garde_3_element(l)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["M\u00eame si on utilise un tri, le co\u00fbt est en en $O(n)$ car le tri op\u00e8re sur au plus trois \u00e9l\u00e9ments."]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Exercice 3\n", "\n", "**Q1**"]}, {"cell_type": "code", "execution_count": 19, "metadata": {"collapsed": true}, "outputs": [], "source": ["def word2dict(mot):\n", "    return { i: mot[:i] for i in range(len(mot)+1) }"]}, {"cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [{"data": {"text/plain": ["({0: '', 1: 'm', 2: 'mo', 3: 'mot'},\n", " {0: '', 1: 'p', 2: 'py', 3: 'pyt', 4: 'pyth', 5: 'pytho', 6: 'python'})"]}, "execution_count": 21, "metadata": {}, "output_type": "execute_result"}], "source": ["word2dict(\"mot\"), word2dict(\"python\")"]}, {"cell_type": "markdown", "metadata": {}, "source": ["**Q2**"]}, {"cell_type": "code", "execution_count": 21, "metadata": {"collapsed": true}, "outputs": [], "source": ["def two_words2dict(d1,d2):\n", "    return { (i,j): (d1[i],d2[j]) for i in d1 for j in d2 }"]}, {"cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [{"data": {"text/plain": ["{(1, 2): ('p', 'pi'),\n", " (3, 2): ('pyt', 'pi'),\n", " (0, 0): ('', ''),\n", " (5, 0): ('pytho', ''),\n", " (6, 4): ('python', 'pito'),\n", " (3, 0): ('pyt', ''),\n", " (0, 4): ('', 'pito'),\n", " (5, 4): ('pytho', 'pito'),\n", " (1, 4): ('p', 'pito'),\n", " (6, 0): ('python', ''),\n", " (5, 5): ('pytho', 'piton'),\n", " (1, 3): ('p', 'pit'),\n", " (0, 5): ('', 'piton'),\n", " (2, 1): ('py', 'p'),\n", " (5, 1): ('pytho', 'p'),\n", " (4, 2): ('pyth', 'pi'),\n", " (2, 5): ('py', 'piton'),\n", " (1, 0): ('p', ''),\n", " (6, 5): ('python', 'piton'),\n", " (3, 5): ('pyt', 'piton'),\n", " (0, 1): ('', 'p'),\n", " (5, 3): ('pytho', 'pit'),\n", " (4, 1): ('pyth', 'p'),\n", " (0, 2): ('', 'pi'),\n", " (3, 3): ('pyt', 'pit'),\n", " (1, 5): ('p', 'piton'),\n", " (3, 4): ('pyt', 'pito'),\n", " (6, 1): ('python', 'p'),\n", " (3, 1): ('pyt', 'p'),\n", " (5, 2): ('pytho', 'pi'),\n", " (4, 4): ('pyth', 'pito'),\n", " (1, 1): ('p', 'p'),\n", " (6, 3): ('python', 'pit'),\n", " (2, 0): ('py', ''),\n", " (6, 2): ('python', 'pi'),\n", " (4, 3): ('pyth', 'pit'),\n", " (2, 2): ('py', 'pi'),\n", " (4, 5): ('pyth', 'piton'),\n", " (2, 3): ('py', 'pit'),\n", " (4, 0): ('pyth', ''),\n", " (0, 3): ('', 'pit'),\n", " (2, 4): ('py', 'pito')}"]}, "execution_count": 23, "metadata": {}, "output_type": "execute_result"}], "source": ["mot1 = \"python\"\n", "mot2 = \"piton\"\n", "d1 = word2dict(mot1)\n", "d2 = word2dict(mot2)\n", "vertices = two_words2dict(d1,d2)\n", "vertices"]}, {"cell_type": "markdown", "metadata": {}, "source": ["**Q3**\n", "\n", "Il y a autant d'\u00e9l\u00e9ments que $(len(mot1) +1)*(len(mot2)+1)$ puisqu'on fait une double boucle sur toutes les positions + 1 pour 0. Donc $(p+1)(q+1)$ si $p$ et $q$ sont les tailles des deux mots."]}, {"cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [{"data": {"text/plain": ["(42, 42)"]}, "execution_count": 24, "metadata": {}, "output_type": "execute_result"}], "source": ["len(vertices),(len(mot1)+1)*(len(mot2)+1)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["**Q4**"]}, {"cell_type": "code", "execution_count": 24, "metadata": {"collapsed": true}, "outputs": [], "source": ["def add_edge_hv(vertices):\n", "    edges =  { }\n", "    for edge1 in vertices:\n", "        i1,j1 = edge1\n", "        for edge2 in vertices:\n", "            i2,j2 = edge2\n", "            if (i2-i1==1 and j1==j2) or (j2-j1==1 and i1==i2) :\n", "                edges[ edge1,edge2 ] = 1\n", "    return edges"]}, {"cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [{"data": {"text/plain": ["{((5, 5), (6, 5)): 1,\n", " ((2, 1), (3, 1)): 1,\n", " ((5, 0), (5, 1)): 1,\n", " ((1, 4), (2, 4)): 1,\n", " ((6, 2), (6, 3)): 1,\n", " ((0, 3), (1, 3)): 1,\n", " ((2, 1), (2, 2)): 1,\n", " ((5, 3), (6, 3)): 1,\n", " ((5, 4), (6, 4)): 1,\n", " ((1, 1), (2, 1)): 1,\n", " ((4, 0), (5, 0)): 1,\n", " ((1, 1), (1, 2)): 1,\n", " ((1, 0), (2, 0)): 1,\n", " ((2, 2), (2, 3)): 1,\n", " ((1, 5), (2, 5)): 1,\n", " ((4, 1), (5, 1)): 1,\n", " ((3, 3), (3, 4)): 1,\n", " ((1, 2), (2, 2)): 1,\n", " ((0, 4), (0, 5)): 1,\n", " ((1, 4), (1, 5)): 1,\n", " ((4, 5), (5, 5)): 1,\n", " ((3, 5), (4, 5)): 1,\n", " ((2, 4), (2, 5)): 1,\n", " ((4, 2), (4, 3)): 1,\n", " ((3, 0), (3, 1)): 1,\n", " ((4, 3), (5, 3)): 1,\n", " ((6, 1), (6, 2)): 1,\n", " ((5, 2), (6, 2)): 1,\n", " ((2, 5), (3, 5)): 1,\n", " ((0, 4), (1, 4)): 1,\n", " ((3, 3), (4, 3)): 1,\n", " ((1, 2), (1, 3)): 1,\n", " ((0, 1), (1, 1)): 1,\n", " ((4, 2), (5, 2)): 1,\n", " ((3, 1), (3, 2)): 1,\n", " ((2, 0), (2, 1)): 1,\n", " ((5, 1), (6, 1)): 1,\n", " ((2, 4), (3, 4)): 1,\n", " ((4, 0), (4, 1)): 1,\n", " ((3, 2), (4, 2)): 1,\n", " ((4, 4), (4, 5)): 1,\n", " ((1, 0), (1, 1)): 1,\n", " ((2, 3), (2, 4)): 1,\n", " ((3, 1), (4, 1)): 1,\n", " ((5, 2), (5, 3)): 1,\n", " ((6, 0), (6, 1)): 1,\n", " ((6, 3), (6, 4)): 1,\n", " ((2, 3), (3, 3)): 1,\n", " ((0, 2), (1, 2)): 1,\n", " ((4, 3), (4, 4)): 1,\n", " ((0, 0), (1, 0)): 1,\n", " ((4, 1), (4, 2)): 1,\n", " ((5, 4), (5, 5)): 1,\n", " ((1, 3), (1, 4)): 1,\n", " ((3, 4), (3, 5)): 1,\n", " ((3, 4), (4, 4)): 1,\n", " ((5, 0), (6, 0)): 1,\n", " ((0, 0), (0, 1)): 1,\n", " ((0, 1), (0, 2)): 1,\n", " ((4, 4), (5, 4)): 1,\n", " ((1, 3), (2, 3)): 1,\n", " ((2, 0), (3, 0)): 1,\n", " ((3, 0), (4, 0)): 1,\n", " ((0, 3), (0, 4)): 1,\n", " ((2, 2), (3, 2)): 1,\n", " ((3, 2), (3, 3)): 1,\n", " ((0, 5), (1, 5)): 1,\n", " ((5, 3), (5, 4)): 1,\n", " ((6, 4), (6, 5)): 1,\n", " ((0, 2), (0, 3)): 1,\n", " ((5, 1), (5, 2)): 1}"]}, "execution_count": 26, "metadata": {}, "output_type": "execute_result"}], "source": ["edges = add_edge_hv(vertices)\n", "edges"]}, {"cell_type": "markdown", "metadata": {}, "source": ["**Q5**\n", "\n", "Pour chaque noeud, on ajoute deux arcs except\u00e9 les noeuds qui correspond \u00e0 la fin des mots. Donc $2(p+1)(q+1)-(p+1)-(q+1)=2pq+p+q$."]}, {"cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [{"data": {"text/plain": ["(71, 71)"]}, "execution_count": 27, "metadata": {}, "output_type": "execute_result"}], "source": ["len(edges), 2*len(mot1)*len(mot2)+len(mot1)+len(mot2)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["**Q6**\n", "\n", "On s'inspire de la fonction pr\u00e9c\u00e9dente. Il serait plus efficace de les fusionner."]}, {"cell_type": "code", "execution_count": 27, "metadata": {"collapsed": true}, "outputs": [], "source": ["def cout(m1,m2):\n", "    c1 = m1[-1]\n", "    c2 = m2[-1]\n", "    if c1==c2 : return 0\n", "    else : return 1\n", "\n", "def ajoute_diagonale(edges, vertices):\n", "    # edges =  { } # on n'ajoute surtout pas cette ligne, sinon c'est comme si on effa\u00e7ait tout ce que contient\n", "    # edges\n", "    for edge1 in vertices:\n", "        i1,j1 = edge1\n", "        for edge2 in vertices:\n", "            i2,j2 = edge2\n", "            if i2-i1==1  and j2-j1==1 :\n", "                edges[ edge1,edge2 ] = cout (vertices [ edge2 ][0], vertices [ edge2 ][1] )"]}, {"cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [{"data": {"text/plain": ["{((2, 1), (3, 1)): 1,\n", " ((5, 0), (5, 1)): 1,\n", " ((5, 4), (6, 5)): 0,\n", " ((3, 3), (4, 4)): 1,\n", " ((6, 1), (6, 2)): 1,\n", " ((5, 4), (6, 4)): 1,\n", " ((2, 3), (3, 4)): 1,\n", " ((2, 0), (2, 1)): 1,\n", " ((0, 0), (1, 1)): 0,\n", " ((1, 1), (2, 1)): 1,\n", " ((3, 1), (4, 2)): 1,\n", " ((2, 4), (2, 5)): 1,\n", " ((0, 4), (0, 5)): 1,\n", " ((1, 4), (1, 5)): 1,\n", " ((3, 5), (4, 5)): 1,\n", " ((0, 4), (1, 5)): 1,\n", " ((0, 5), (1, 5)): 1,\n", " ((3, 0), (3, 1)): 1,\n", " ((5, 1), (6, 2)): 1,\n", " ((2, 2), (2, 3)): 1,\n", " ((0, 4), (1, 4)): 1,\n", " ((4, 0), (5, 1)): 1,\n", " ((3, 3), (4, 3)): 1,\n", " ((1, 2), (1, 3)): 1,\n", " ((1, 4), (2, 4)): 1,\n", " ((2, 4), (3, 4)): 1,\n", " ((0, 1), (1, 2)): 1,\n", " ((4, 4), (4, 5)): 1,\n", " ((2, 4), (3, 5)): 1,\n", " ((3, 1), (4, 1)): 1,\n", " ((3, 4), (3, 5)): 1,\n", " ((1, 1), (1, 2)): 1,\n", " ((2, 3), (3, 3)): 1,\n", " ((1, 4), (2, 5)): 1,\n", " ((0, 2), (1, 2)): 1,\n", " ((0, 0), (1, 0)): 1,\n", " ((5, 4), (5, 5)): 1,\n", " ((5, 2), (5, 3)): 1,\n", " ((2, 2), (3, 3)): 0,\n", " ((5, 0), (6, 0)): 1,\n", " ((3, 4), (4, 4)): 1,\n", " ((5, 1), (6, 1)): 1,\n", " ((0, 1), (1, 1)): 1,\n", " ((3, 0), (4, 0)): 1,\n", " ((0, 3), (0, 4)): 1,\n", " ((2, 2), (3, 2)): 1,\n", " ((3, 2), (4, 3)): 1,\n", " ((4, 2), (5, 2)): 1,\n", " ((5, 3), (5, 4)): 1,\n", " ((5, 0), (6, 1)): 1,\n", " ((6, 0), (6, 1)): 1,\n", " ((5, 2), (6, 2)): 1,\n", " ((5, 5), (6, 5)): 1,\n", " ((2, 0), (3, 1)): 1,\n", " ((4, 2), (5, 3)): 1,\n", " ((6, 2), (6, 3)): 1,\n", " ((4, 3), (5, 4)): 0,\n", " ((0, 2), (1, 3)): 1,\n", " ((5, 3), (6, 3)): 1,\n", " ((1, 5), (2, 5)): 1,\n", " ((4, 0), (5, 0)): 1,\n", " ((1, 0), (2, 1)): 1,\n", " ((1, 0), (2, 0)): 1,\n", " ((1, 3), (2, 4)): 1,\n", " ((2, 1), (3, 2)): 1,\n", " ((2, 1), (2, 2)): 1,\n", " ((1, 2), (2, 2)): 1,\n", " ((5, 3), (6, 4)): 1,\n", " ((4, 1), (5, 1)): 1,\n", " ((3, 1), (3, 2)): 1,\n", " ((0, 3), (1, 3)): 1,\n", " ((3, 4), (4, 5)): 1,\n", " ((2, 3), (2, 4)): 1,\n", " ((3, 0), (4, 1)): 1,\n", " ((4, 3), (5, 3)): 1,\n", " ((4, 0), (4, 1)): 1,\n", " ((6, 4), (6, 5)): 1,\n", " ((0, 3), (1, 4)): 1,\n", " ((5, 2), (6, 3)): 1,\n", " ((1, 0), (1, 1)): 1,\n", " ((6, 3), (6, 4)): 1,\n", " ((1, 1), (2, 2)): 1,\n", " ((4, 3), (4, 4)): 1,\n", " ((4, 4), (5, 5)): 1,\n", " ((3, 3), (3, 4)): 1,\n", " ((2, 5), (3, 5)): 1,\n", " ((4, 1), (4, 2)): 1,\n", " ((1, 3), (1, 4)): 1,\n", " ((4, 2), (4, 3)): 1,\n", " ((1, 2), (2, 3)): 1,\n", " ((0, 0), (0, 1)): 1,\n", " ((0, 1), (0, 2)): 1,\n", " ((4, 4), (5, 4)): 1,\n", " ((4, 1), (5, 2)): 1,\n", " ((1, 3), (2, 3)): 1,\n", " ((2, 0), (3, 0)): 1,\n", " ((3, 2), (3, 3)): 1,\n", " ((3, 2), (4, 2)): 1,\n", " ((4, 5), (5, 5)): 1,\n", " ((0, 2), (0, 3)): 1,\n", " ((5, 1), (5, 2)): 1}"]}, "execution_count": 29, "metadata": {}, "output_type": "execute_result"}], "source": ["ajoute_diagonale(edges, vertices)\n", "edges"]}, {"cell_type": "markdown", "metadata": {}, "source": ["**Q7**\n", "\n", "L'algorithme du plus court chemin."]}, {"cell_type": "code", "execution_count": 29, "metadata": {"collapsed": true}, "outputs": [], "source": ["def loop_on_edges(distance, edges):\n", "    for edge,cout in edges.items() :\n", "        v1,v2 = edge\n", "        if v1 in distance and (v2 not in distance or distance[v2] > distance[v1] + cout) :\n", "            distance[v2] = distance[v1] + cout"]}, {"cell_type": "markdown", "metadata": {}, "source": ["**Q8**\n", "\n", "La question \u00e9tait sans doute un peu mal pos\u00e9 car il est beaucoup plus facile pour la fonction ``loop_on_edges`` de savoir si le dictionnaire ``distance`` est modifi\u00e9 ou non. On la modifie pour qu'elle retourne le nombre de mises \u00e0 jour."]}, {"cell_type": "code", "execution_count": 30, "metadata": {"collapsed": true}, "outputs": [], "source": ["def loop_on_edges(distance, edges):\n", "    misejour = 0\n", "    for edge,cout in edges.items() :\n", "        v1,v2 = edge\n", "        if v1 in distance and (v2 not in distance or distance[v2] > distance[v1] + cout) :\n", "            distance[v2] = distance[v1] + cout\n", "            misejour += 1\n", "    return misejour"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Puis l'algorithme final :"]}, {"cell_type": "code", "execution_count": 31, "metadata": {"collapsed": true}, "outputs": [], "source": ["def plus_court_chemin(edges):\n", "    distance = { (0,0): 0 }\n", "    m = 1\n", "    while m > 0:\n", "        m = loop_on_edges(distance, edges)\n", "    return distance"]}, {"cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [{"data": {"text/plain": ["{(0, 1): 1,\n", " (3, 2): 2,\n", " (0, 0): 0,\n", " (5, 0): 5,\n", " (6, 4): 3,\n", " (3, 0): 3,\n", " (0, 4): 4,\n", " (5, 4): 2,\n", " (2, 1): 1,\n", " (6, 0): 6,\n", " (5, 5): 3,\n", " (2, 5): 4,\n", " (1, 3): 2,\n", " (2, 3): 2,\n", " (1, 4): 3,\n", " (2, 4): 3,\n", " (4, 2): 3,\n", " (1, 0): 1,\n", " (0, 3): 3,\n", " (6, 5): 2,\n", " (3, 5): 3,\n", " (1, 2): 1,\n", " (5, 1): 4,\n", " (5, 3): 3,\n", " (3, 3): 1,\n", " (1, 5): 4,\n", " (4, 1): 3,\n", " (6, 1): 5,\n", " (3, 1): 2,\n", " (5, 2): 4,\n", " (4, 4): 2,\n", " (1, 1): 0,\n", " (6, 3): 4,\n", " (2, 0): 2,\n", " (6, 2): 5,\n", " (4, 3): 2,\n", " (2, 2): 1,\n", " (4, 5): 3,\n", " (0, 5): 5,\n", " (4, 0): 4,\n", " (3, 4): 2,\n", " (0, 2): 2}"]}, "execution_count": 33, "metadata": {}, "output_type": "execute_result"}], "source": ["resultat = plus_court_chemin(edges)\n", "resultat"]}, {"cell_type": "markdown", "metadata": {}, "source": ["**Q9**"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Comme on a tout fait avec ces deux mots, il suffit de prendre la bonne valeur dans le tableau distance :"]}, {"cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["python piton\n"]}, {"data": {"text/plain": ["2"]}, "execution_count": 34, "metadata": {}, "output_type": "execute_result"}], "source": ["print(mot1,mot2)\n", "resultat [ len(mot1), len(mot2) ]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Exercice 4\n", "\n", "On a un tableau d'entiers ``l = [1, 8, 5, 7, 3, 6, 9]``. On veut placer les entiers pairs en premiers et les entiers impairs en derniers : ``8, 6, 1, 5, 7, 3, 9``. Ecrire une fonction qui fait cela.\n", "\n", "Le co\u00fbt d'un tri est de $O(n \\ln n)$. On construit d'abord le couple *(parit\u00e9, \u00e9l\u00e9ment)* pour chaque \u00e9l\u00e9ment puis on trie de table. C'est la solution la plus simple."]}, {"cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [{"data": {"text/plain": ["[6, 8, 1, 3, 5, 7, 9]"]}, "execution_count": 35, "metadata": {}, "output_type": "execute_result"}], "source": ["l = [1, 8, 5, 7, 3, 6, 9]\n", "l2 = [ (i%2, i) for i in l]\n", "l2.sort()\n", "res = [ b for a,b in l2 ]\n", "res"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Dans cas pr\u00e9cis, on ne souhaite pas trier sur les nombres mais sur leur parit\u00e9. En quelque sorte, on ne s'int\u00e9resse pas de savoir dans quel ordre deux nombres pairs seront tri\u00e9s. Cela r\u00e9duit le nombre d'op\u00e9rations \u00e0 effectuer. Une id\u00e9e consiste \u00e0 parcourir le tableau par les deux bouts et \u00e0 \u00e9changer deux nombres d\u00e8s que leur parit\u00e9 sont mal class\u00e9es."]}, {"cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [{"data": {"text/plain": ["[8, 6, 5, 3, 7, 9, 1]"]}, "execution_count": 36, "metadata": {}, "output_type": "execute_result"}], "source": ["def trie_parite(l):\n", "    i = 0\n", "    j = len(l)-1\n", "    while i < j :\n", "        while i < j and l[i]%2 == 0 : i += 1\n", "        while i < j and l[j]%2 == 1 : j -= 1\n", "        if i < j:\n", "            ech = l[i]\n", "            l[i] = l[j]\n", "            l[j] = ech\n", "            i += 1\n", "            j -= 1\n", "    \n", "l = l.copy()\n", "trie_parite(l)\n", "l"]}, {"cell_type": "code", "execution_count": 36, "metadata": {"collapsed": true}, "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}