{ "cells": [ { "cell_type": "markdown", "metadata": { "toc": "true" }, "source": [ "# Table of Contents\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Texte d'oral de modélisation - Agrégation Option Informatique\n", "## Préparation à l'agrégation - ENS de Rennes, 2016-17\n", "- *Date* : 7 avril 2017\n", "- *Auteur* : [Lilian Besson](https://GitHub.com/Naereen/notebooks/)\n", "- *Texte*: Annale 2009, \"Contraintes temporelles\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## À propos de ce document\n", "- Ceci est une *proposition* de correction, partielle et probablement non-optimale, pour la partie implémentation d'un [texte d'annale de l'agrégation de mathématiques, option informatique](http://Agreg.org/Textes/).\n", "- Ce document est un [notebook Jupyter](https://www.Jupyter.org/), et [est open-source sous Licence MIT sur GitHub](https://github.com/Naereen/notebooks/tree/master/agreg/), comme les autres solutions de textes de modélisation que [j](https://GitHub.com/Naereen)'ai écrite cette année.\n", "- L'implémentation sera faite en OCaml, version 4+ :" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "scrolled": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The OCaml toplevel, version 4.04.2\n" ] }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Sys.command \"ocaml -version\";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> Notez que certaines fonctions des modules usuels [`List`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html) et [`Array`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html) ne sont pas disponibles en OCaml 3.12.\n", "> J'essaie autant que possible de ne pas les utiliser, ou alors de les redéfinir si je m'en sers." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Question de programmation\n", "La question de programmation pour ce texte était donnée en question 1 en page 9 :\n", "\n", "> \"Programmer l'algorithme PC. Faites le tourner sur l'exemple de réseau non distributif.\"\n", "\n", "La consigne était très courte, mais avec aucune indication.\n", "Notez qu'il est rare que le texte exige un exemple particulier." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Réponse à l'exercice requis\n", "Ça va être assez long, en fait...\n", "\n", "1. D'abord, il faut définir les types de données avec lesquels on va travailler,\n", "2. Ensuite, implémenter les deux opérations $\\oplus$ et $\\otimes$ sur les ensembles d'intervalles,\n", "3. Puis implémenter l'algorithme PC (similaire à Floyd-Warshall),\n", "4. Et enfin, l'exécuter sur l'exemple de réseau non distributif donné en page 8.\n", "\n", "Si possible, on va essayer de faire des *tests* pour chaque fonction intermédiaire, et un exemple de plus à la fin.\n", "\n", "Un des problèmes que l'on va rencontrer est le fait que l'on doit manipuler $-\\infty$ et $+\\infty$, pour pouvoir gérer une contrainte qui n'est pas une contrainte, à savoir l'interavalle $(-\\infty, +\\infty)$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "### Structures de données\n", "\n", "On va travailler avec des valeurs entières ou $\\pm\\infty$. En écrivant nous même les opérations arithmétiques ($+,max$) sur les entiers \"étendus\" on obtiendra ce qu'on veut." ] }, { "cell_type": "code", "execution_count": 75, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "type entier_etendu = MInf | PInf | E of int\n" ] }, "execution_count": 75, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type entier_etendu = MInf | PInf | E of int;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On se restreint aux intervalles à coordonnées *entières*, et on considère des listes d'intervalles.\n", "Tous les intervalles sont fermés à gauche et à droite." ] }, { "cell_type": "code", "execution_count": 76, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "type intervalle = entier_etendu * entier_etendu\n" ] }, "execution_count": 76, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type intervalle = (entier_etendu * entier_etendu);; (* (a, b) représente l'intervalle [a, b] *)" ] }, { "cell_type": "code", "execution_count": 77, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "type intervalles = intervalle list\n" ] }, "execution_count": 77, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type intervalles = intervalle list;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On définit tout de suite deux exemples, $T_a$ et $S_a$ tirés de la Figure 2.a) et $T_b,S_b$ de la Figure 2.b).\n", "Cela permettra de vérifier les opérations $\\oplus$ et $\\otimes$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- $T_a = \\{ [1, 4], [6, 8] \\}$ et $S_a = \\{ [0, 1], [3, 5], [6, 7] \\}$." ] }, { "cell_type": "code", "execution_count": 78, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val t_a : intervalles = [(E 1, E 4); (E 6, E 8)]\n" ] }, "execution_count": 78, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val s_a : intervalles = [(E 0, E 1); (E 3, E 5); (E 6, E 7)]\n" ] }, "execution_count": 78, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let t_a : intervalles = [\n", " (E(1), E(4));\n", " (E(6), E(8))\n", "];;\n", "\n", "let s_a : intervalles = [\n", " (E(0), E(1));\n", " (E(3), E(5));\n", " (E(6), E(7))\n", "];;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- $T_b = \\{ [-1, 0], [2, 4] \\}$ et $S_b = \\{ [0, 1], [4, 4] \\}$." ] }, { "cell_type": "code", "execution_count": 80, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val t_b : intervalles = [(E (-1), E 0); (E 2, E 4)]\n" ] }, "execution_count": 80, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val s_b : intervalles = [(E 0, E 1); (E 4, E 4)]\n" ] }, "execution_count": 80, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let t_b : intervalles = [\n", " (E(-1), E(0));\n", " (E(2), E(4))\n", "];;\n", "\n", "let s_b : intervalles = [\n", " (E(0), E(1));\n", " (E(4), E(4)) (* Intervalle de longueur nulle *)\n", "];;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- Et la contrainte vide, $T = \\{[-\\infty, +\\infty\\}$ :" ] }, { "cell_type": "code", "execution_count": 79, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val t_vide : intervalles = [(MInf, PInf)]\n" ] }, "execution_count": 79, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let t_vide : intervalles = [\n", " (MInf, PInf)\n", "];;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "### Arithmétiques sur nos entiers étendus" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Max/min" ] }, { "cell_type": "code", "execution_count": 81, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val max_ee : entier_etendu -> entier_etendu -> entier_etendu =