TP11.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d7fb961c",
   "metadata": {},
   "source": [
    "# ITC - MPSI\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f2dfd49",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "c6310d5ac2a01276a13e4cea555b98c7",
     "grade": false,
     "grade_id": "cell-23cdac2da4976f2f",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "# TP11 : Algorithmes gloutons\n",
    "Dans ce TP, nous allons explorer une stratégie algorithmique connue sous le nom d'_algorithme glouton_ (_greedy algorithms_ en anglais).\n",
    "\n",
    "Le principe d'un algorithme glouton est de construire une solution au problème par étapes successives, en prenant à chaque étape la solution qui semble la meilleure, et en espérant que cette optimisation locale mènera à une solution globalement optimale. On parie donc sur les maxima locaux, en supposant que l'élément qui semble le meilleur aboutira au meilleur résultat final.\n",
    "\n",
    "La qualité effective du résultat final dépendra en grande partie du choix de ce _meilleur_ élément. (En partie car tous les problèmes ne peuvent pas être résolus avec un algorithme glouton.)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "edb7156d",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "fde25d6ba5c1258af974398e3f23ed0e",
     "grade": false,
     "grade_id": "cell-3e95a71c847c5b28",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Petit complément concernant les compréhensions de listes avant : on peut filtrer les données d'une collection en écrivant\n",
    "```python\n",
    "[ e(x) for x in L if f(x) ]\n",
    "```\n",
    "Par exemple si `L` est une liste d'entiers et qu'on veut prendre les moitiés des entiers paires de la liste, on peut écrire :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dca0c74b",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "7212a75ac96f11ee9d4acf2d6deba0f9",
     "grade": false,
     "grade_id": "cell-0be5289057bbb85b",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "L = [1, 2, 3, 4, 5, 9, 8, 7, -3, -2]  # pour l'exemple\n",
    "[ x//2 for x in L if x%2==0 ]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c567c4b7",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "44c90318b9eca22f9d7d478f56999afd",
     "grade": false,
     "grade_id": "cell-bdff09183e9bb1a0",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Le problème de l'emploi du temps\n",
    "\n",
    "Considérons le problème d'attribution d'une salle pour un ensemble de cours :\n",
    "* entrée : un ensemble de cours à placer, chaque cours possédant une heure de début et une heure de fin\n",
    "* sortie : un ensemble maximal de cours qu'on peut placer sans chevauchement (par _maximal_ on entend qu'il n'existe pas d'ensemble de cours plaçables avec un cardinal strictement supérieur)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f3736e7",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "eb05c2b10f73e7a3c5a42103aa05c1d4",
     "grade": false,
     "grade_id": "cell-42f8a341dad2181b",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Le schéma général de résolution que nous allons adopter est le suivant :\n",
    "* $S\\leftarrow \\emptyset$\n",
    "* $P\\leftarrow$ tous les cours avec accès rapide au meilleur choix\n",
    "* tant que c'est possible\n",
    "  * $e\\leftarrow$ meilleur choix dans $P$\n",
    "  * $S\\leftarrow S\\cup \\{e\\}$\n",
    "  * mise à jour de $P$ (si besoin)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "79ee0621",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "60ae5f9454ce9d7b1e51a708b7eafa8a",
     "grade": false,
     "grade_id": "cell-c637cdc14ca01e90",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Pour simplifier le propos, on va supposer que chaque cours commence et termine à une heure entière. Un cours sera représenté par une liste de longueur 3 composée d'une chaîne de caractères donnant son nom, suivie de deux entiers positifs ou nuls représentant l'heure de début et l'heure de fin du cours.\n",
    "\n",
    "exemples : `[\"math\", 8, 12]` ou `[\"info\", 14, 16]`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6c07032f",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "e0f612e68588095ed83ef3c01d34c679",
     "grade": false,
     "grade_id": "cell-de8a8de607113a09",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exo 1 : première tentative, au plus court\n",
    "On peut penser que le mieux est de placer les cours qui durent le moins longtemps pour maximiser le nombre de cours qu'on place.\n",
    "\n",
    "On connaît l'heure de début et l'heure de fin de chaque cours, il est donc très simple de placer les cours en fonction de leur durée."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ef29a3c8",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "e376840ce9e9509dfc780245c26ea9f2",
     "grade": false,
     "grade_id": "cell-3b00b0317c550a34",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "1. Écrire et documenter une fonction `duree` qui prend en argument un triplet supposé représenter un cours et renvoie la durée de ce cours."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0007b45d",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "4477bfc78a88b3ed13006a1cd5e4e904",
     "grade": false,
     "grade_id": "cell-9854f500ad8e8ccc",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "080014d0",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "51483552d9e7b2e7d44b36aafbb09e0e",
     "grade": true,
     "grade_id": "cell-b2a715c96a2cf411",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "assert(duree([\"math\", 8, 12]) == 4)\n",
    "assert(duree([\"hg\", 0, 0]) == 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a6a937a3",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "053b61437ca4852bdf8d2630d6dc727a",
     "grade": false,
     "grade_id": "cell-db0d9845dfa87085",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Je vous donne la fonction suivante (vous n'avez pas besoin de comprendre son code, mais elle ne fonctionnera correctement que si votre fonction `duree` est correcte):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "09c7e7d6",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "a2120d266c43674fce256bc85a28c932",
     "grade": false,
     "grade_id": "cell-93e74222c64000bc",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def tri_selon_critere(liste, critere):\n",
    "    \"\"\"entree : liste de cours, critere de tri\n",
    "    sortie : la liste est triée selon le critere\"\"\"\n",
    "    liste.sort(key = critere, reverse = True)\n",
    "\n",
    "\n",
    "## exemple d'utilisation\n",
    "L = [[\"math\", 8, 12],  [\"hg\", 0, 0], [\"info\", 14, 16]]\n",
    "tri_selon_critere(L, duree)\n",
    "L"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf063ea5",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "716905ca04873d4cac8da6b6389d6056",
     "grade": false,
     "grade_id": "cell-5358a1f0788f6c2b",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "2. Écrire et documenter une fonction `mise_a_jour1` qui prend en argument une liste de cours, une heure de début `d` et une heure de fin `f`, et renvoie une nouvelle liste ne contenant que les cours de la liste fournie en paramètre qui terminent au plus tard à l'heure `d` ou commencent au plus tôt à l'heure `f`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5e621b3b",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "adc1afa0202dcaab52916dab6feae844",
     "grade": false,
     "grade_id": "cell-879e5e6c524fbb19",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5325b359",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "4ec8da9999c951efff62c329e0d0eaa2",
     "grade": false,
     "grade_id": "cell-d3b91221f86c433f",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "3. Écrire et documenter une fonction `emploi_du_temps1` qui prend en argument une liste de cours dans le format décrit précédemment, et renvoie une liste de cours qui ne se chevauchent pas, en suivant l'algorithme glouton, avec le choix du plus court comme étant le meilleur choix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "94d97ac1",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ed66c09f4bd4ec23b5a75a388609f65c",
     "grade": false,
     "grade_id": "cell-617c7f2ce25e08cd",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "635a7b9a",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "6481c1affa07d867628b7872abd00a13",
     "grade": true,
     "grade_id": "cell-eb71a23d72f4e94a",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "L = [[\"math\", 8, 12],  [\"hg\", 0, 0], [\"info\", 14, 16]]\n",
    "assert(sorted(emploi_du_temps1(L), key = lambda x : x[2]-x[1]) ==\n",
    "      [['hg', 0, 0], ['info', 14, 16], ['math', 8, 12]])\n",
    "\n",
    "L = [[\"math\", 8, 12],  [\"hg\", 13, 14], [\"info\", 14, 16]]\n",
    "assert(sorted(emploi_du_temps1(L), key = lambda x : x[2]-x[1]) ==\n",
    "       [['hg', 13, 14], ['info', 14, 16], ['math', 8, 12]])\n",
    "\n",
    "L = [[\"math\", 8, 12],  [\"hg\", 13, 16], [\"info\", 14, 16]]\n",
    "assert(sorted(emploi_du_temps1(L), key = lambda x : x[2]-x[1]) ==\n",
    "       [['info', 14, 16], ['math', 8, 12]])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3cd4b026",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "a7acdbffa0d8c406211a1bb1f0e647da",
     "grade": false,
     "grade_id": "cell-1519c4939b968f27",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Le problème de cette solution en prenant d'abord le plus court, c'est qu'elle n'est pas optimale, voir par exemple l'entrée suivante qui place un seul cours, alors qu'elle pourrait en placer deux:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "272d24a5",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "5dcfa27d48c39f21e6dad2f998771098",
     "grade": false,
     "grade_id": "cell-831b58a6d01eb721",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "L = [[\"math\", 8, 12], [\"phys\", 12, 16], [\"SI\", 11, 13]]\n",
    "emploi_du_temps1(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a5d99cb0",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "fab7d32a005f90c43609b0ce0a167ff1",
     "grade": false,
     "grade_id": "cell-822d7c5248e9fc46",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exo 2 : deuxième tentative, départ au plus tôt\n",
    "On essaie maintenant une solution qui prend en priorité le cours qui commence le plus tôt parmi les cours encore compatibles avec ce qui a déjà été placé."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "342188d9",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "beaa429c045e459b8c27570eb9289f00",
     "grade": false,
     "grade_id": "cell-c0c9b31ecf6f54f4",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "1. Écrire et documenter une fonction `debut` qui prend en argument un triplet supposé représenter un cours et renvoie l'heure de début de ce cours. Vous pourrez ensuite vous servir de cette fonction comme deuxième argument dans un appel à `tri_selon_critere`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6f5f19f7",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "7831393829ef4621a2d1e735a51107b1",
     "grade": false,
     "grade_id": "cell-2ea929b53d0068c9",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6e2e1869",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "064f81de0c5915beb353d0fc71071028",
     "grade": true,
     "grade_id": "cell-d7775ce144f34a65",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "assert(debut(['math', 9, 11]) == 9)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "390668ad",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "4280ea11e15d85b3990ce0770cc6ce9c",
     "grade": false,
     "grade_id": "cell-8e711a6fd3b98ecc",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "2. Écrire et documenter une fonction `mise_a_jour2` qui prend en argument une liste de cours et un entier `h` représentant une certaine heure, et renvoie une nouvelle liste ne contenant que les cours dont l'heure de début est au moins `h` (sans modifier l'ordre des cours). Utiliser une compréhension de liste pour construire une telle liste."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1015434e",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "4429277baa23964efb7b0191c6050e3d",
     "grade": false,
     "grade_id": "cell-36700eb15ba9da77",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "51724e61",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "fc63187d1c6bf57d383c1ee2701257ce",
     "grade": true,
     "grade_id": "cell-0f759943bc8a2826",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "L = [[\"math\", 8, 12],  [\"hg\", 0, 0], [\"info\", 14, 16]]\n",
    "assert(mise_a_jour2(L, 4) == [['math', 8, 12], ['info', 14, 16]])\n",
    "\n",
    "L = [[\"math\", 8, 12],  [\"hg\", 0, 0], [\"info\", 14, 16]]\n",
    "assert(mise_a_jour2(L, 13) == [['info', 14, 16]])\n",
    "\n",
    "L = [[\"math\", 8, 12],  [\"hg\", 0, 0], [\"info\", 14, 16]]\n",
    "assert(mise_a_jour2(L, 15) == [])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99f08246",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "69c19d8d8a2c29016bfd28d708359bd2",
     "grade": false,
     "grade_id": "cell-d3b91221f86c433g",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "3. Écrire et documenter une fonction `emploi_du_temps2` qui prend en argument une liste de cours dans le format décrie précédemment, et renvoie une liste de cours qui ne se chevauchent pas, en suivant l'algorithme glouton, avec le chiox au plus tôt comme étant le meilleur choix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "90a243fb",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "372c9c997492755cb88af99ed537d839",
     "grade": false,
     "grade_id": "cell-617c7f2ce25e08ce",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6a0e366e",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "2a5b39f6c726de87cd2c75e68b5709c6",
     "grade": true,
     "grade_id": "cell-3db677f9c8a3ccc8",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "L = [[\"math\", 8, 12],  [\"hg\", 0, 0], [\"info\", 14, 16]]\n",
    "assert(sorted(emploi_du_temps2(L), key = lambda x : x[1]) ==\n",
    "       [['hg', 0, 0], ['math', 8, 12], ['info', 14, 16]])\n",
    "\n",
    "L = [[\"math\", 8, 12],  [\"hg\", 13, 14], [\"info\", 14, 16]]\n",
    "assert(sorted(emploi_du_temps2(L), key = lambda x : x[1]) ==\n",
    "       [['math', 8, 12], ['hg', 13, 14], ['info', 14, 16]])\n",
    "\n",
    "L = [[\"math\", 8, 12],  [\"hg\", 13, 16], [\"info\", 14, 16]]\n",
    "assert(sorted(emploi_du_temps2(L), key = lambda x : x[1]) ==\n",
    "       [['math', 8, 12], ['hg', 13, 16]])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "582d243f",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "955f4c5fa38db4690b757541d998c5a7",
     "grade": false,
     "grade_id": "cell-1e693cb58f2f9b33",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Le problème de cette solution en prenant d'abord le cours qui commence le plus tôt, c'est qu'elle n'est pas optimale, voir par exemple l'entrée suivante qui place un seul cours, alors qu'elle pourrait en placer deux:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "12cb173e",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "e84deae451830fd8bef57f68de6b2510",
     "grade": false,
     "grade_id": "cell-ed973af5d96185f0",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "L = [[\"math\", 9, 12], [\"phys\", 12, 16], [\"SI\", 8, 13]]\n",
    "emploi_du_temps2(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df36bd62",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "99d07abce7fbccdb94cc49694bfeab5a",
     "grade": false,
     "grade_id": "cell-963aabcc408c6133",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exo 3 : avec le moins d'incompatibilités\n",
    "On pourrait penser qu'il faut commencer par prendre les cours qui présentent le moins d'incompatibilités, c'est-à-dire le moins d'intersection avec les autres cours.\n",
    "\n",
    "1. Écrire et documenter une fonction `intersections` qui prend en argument une liste de cours `L` et un cours `C`, au format décrit précédemment, et renvoie le nombre d'intersections de `C` avec les cours de `L`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8514acd1",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "3bf8b8f1df928644a684cff08241e15f",
     "grade": false,
     "grade_id": "cell-5072298a13436b32",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f9f6d70a",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "be9b8b9a6c7a838e9397b8b21a11cc9e",
     "grade": true,
     "grade_id": "cell-81d3fd0ff299ccd9",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "L = [[\"math\", 8, 12],  [\"hg\", 13, 16], [\"info\", 14, 16]]\n",
    "\n",
    "assert(intersection(L, [\"francais\", 6, 7]) == 0)\n",
    "assert(intersection(L, [\"francais\", 6, 9]) == 1)\n",
    "assert(intersection(L, [\"francais\", 9, 10]) == 1)\n",
    "assert(intersection(L, [\"francais\", 9, 14]) == 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b5e0409",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "6b05af5c812aa111e310eecacf2b0a9c",
     "grade": false,
     "grade_id": "cell-d9a168149f428ecc",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "2. Écrire et documenter une fonction `emploi_du_temps3` qui prend en argument une liste de cours dans le format décrit précédemment, et renvoie une liste de cours qui ne se chevauchent pas, en suivant l'algorithme glouton, avec le moins d'intrsection comme étant le meilleur choix (vous pouvez utiliser `mise_a_jour1`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "027a236c",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "308682217a02e802caceebeda407c220",
     "grade": false,
     "grade_id": "cell-ba1cb8fbde828077",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "critere_intersection = lambda x: intersection(L, x)\n",
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "12216735",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "b3d83305029f7aca692d2a71ca4de00f",
     "grade": true,
     "grade_id": "cell-6f6d59653c2a4ae5",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "L = [[\"math\", 8, 12],  [\"hg\", 13, 16], [\"info\", 14, 16]]\n",
    "assert(emploi_du_temps3(L) == [['info', 14, 16], ['math', 8, 12]])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e71e82c9",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "70fe7f7185e7a52e6c48cd32694aeb50",
     "grade": false,
     "grade_id": "cell-5297b670929ad378",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "3. Trouver un exemple d'entrée pour laquelle cet algorithme n'est pas optimal."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8bc7e20",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "4ca19c576aa1aa695e85d4cb1c870747",
     "grade": false,
     "grade_id": "cell-e69f3737e719fb1a",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": true
    }
   },
   "source": [
    "Describe the task here!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ee87f915",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "71df90202a04402eac985b44c89a6916",
     "grade": false,
     "grade_id": "cell-d59631182b18f330",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exo 4 : troisième méthode, fin au plus tôt\n",
    "Montrer que si on choisit comme meilleur prochain choix, le cours qui se termine au plus tôt parmi les cours restants, alors on obtient un résultat optimal, c'est-à-dire qu'il n'existe pas d'ensemble de cours plaçables de cardinal supérieur à l'ensemble qu'on obtient par cette méthode."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a6b44c87",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "93c982de17b11481c7641af431b23763",
     "grade": false,
     "grade_id": "cell-ce8daf5cb95d87a8",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Écrivez votre preuve dans la cellule suivante :"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a0020a4d",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "fdf99ff3c5d3463728257b87f96235ae",
     "grade": true,
     "grade_id": "cell-aa844a58656b80f7",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2516921b",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "6b3f300e887f1e3dee812b4838c11620",
     "grade": false,
     "grade_id": "cell-9017bd0a5d62dda0",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "<div class=\"alert alert-success\">\n",
    "    <h2>Les points à retenir</h2>\n",
    "    \n",
    "* le principe d'un algorithme glouton\n",
    "* on ne trouve pas systématique une solution optimale avec un algorithme glouton\n",
    "* compréhension de liste avec conditionnelle\n",
    "* tri d'une liste avec `L.sort()` et `sorted(L)`, avec l'ordre naturel\n",
    "</div>"
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}