{ "cells": [ { "cell_type": "markdown", "metadata": { "toc": "true" }, "source": [ "# Table of Contents\n", "

1  Texte d'oral de modélisation - Agrégation Option Informatique
1.1  Préparation à l'agrégation - ENS de Rennes, 2016-17
1.2  À propos de ce document
1.3  Question de programmation
1.4  Réponse à l'exercice requis
1.4.1  Structure de données
1.4.2  Exemples
1.4.3  Fonctions intermédiaires
1.4.4  Résolution
1.5  Bonus ?
1.6  Conclusion
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Texte d'oral de modélisation - Agrégation Option Informatique" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Préparation à l'agrégation - ENS de Rennes, 2016-17" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- *Date* : 29 mai 2017\n", "- *Auteur* : [Lilian Besson](https://GitHub.com/Naereen/notebooks/)\n", "- *Texte*: [Circuits (public2010-D1)](http://agreg.org/Textes/public2010-D1.pdf)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## À propos de ce document" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- 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": 1, "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The OCaml toplevel, version 4.04.2\n" ] }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 1, "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": [ "----" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question de programmation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La question de programmation pour ce texte était donnée en page 6, et était assez courte :\n", "\n", "> \"Écrire un programme prenant en entrée deux nombres $a$, $b$, représentés par des écritures en base $B$ avec des chiffres signés entre $-\\beta$ et $\\beta$, et retournant un résultat ternaire indiquant si $a < b$, si $a = b$ ou si $a > b$. On supposera que $\\beta < B < 2 \\beta$, et que les écritures de $a$ et $b$ ont même longueur.\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Réponse à l'exercice requis" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Structure de données\n", "\n", "Pour représenter ces entiers, on stocke leur base et le tableau de leur coefficients." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "type entier = { base : int; t : int array; }\n" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type entier = {\n", " base : int;\n", " t : int array\n", "}\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exemples" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val quatre : entier = {base = 10; t = [|4|]}\n" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let quatre = {\n", " base = 10;\n", " t = [| 4 |]\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le \"bit\" de poids faible est, par convention du texte, à gauche au début du tableau :" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val quarantedeux : entier = {base = 10; t = [|2; 4|]}\n" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let quarantedeux = {\n", " base = 10;\n", " t = [| 2; 4 |]\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Avec l'exemple du texte :" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val n2006 : entier = {base = 10; t = [|6; 0; 0; 2|]}\n" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let n2006 = {\n", " base = 10;\n", " t = [| 6; 0; 0; 2 |]\n", "}" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val n2006 : entier = {base = 10; t = [|6; 0; 0; 2|]}\n" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let n2006 = {\n", " base = 10;\n", " t = [| 6; 0; 0; 2 |]\n", "}" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val n2006_2 : entier = {base = 10; t = [|-4; 1; 0; 2|]}\n" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let n2006_2 = {\n", " base = 10;\n", " t = [| -4; 1; 0; 2 |]\n", "}" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val n2006_3 : entier = {base = 10; t = [|6; 0; 0; -8; 1|]}\n" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let n2006_3 = {\n", " base = 10;\n", " t = [| 6; 0; 0; -8; 1 |]\n", "}" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val n2006_4 : entier = {base = 10; t = [|-4; 1; 0; -8; 1|]}\n" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let n2006_4 = {\n", " base = 10;\n", " t = [| -4; 1; 0; -8; 1 |]\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Fonctions intermédiaires" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "Caml, dans sa toute beauté, ne permet pas de calculer $x^k$ facilement si $x$ est entier..." ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val puissance : int -> int -> int = \n" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let rec puissance x k = \n", " match k with\n", " | 0 -> 1\n", " | 1 -> x\n", " | k when k mod 2 = 0 ->\n", " (* x^k = x^(k/2 * 2) = (x^2)^(k/2) *)\n", " puissance (x * x) (k / 2)\n", " | k ->\n", " (* x^k = x^((k-1)/2 * 2 + 1) = x * (x^2)^((k-1)/2) *)\n", " x * (puissance (x * x) ((k - 1) / 2))\n", ";;" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int = 1\n" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : int = 10\n" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : int = 100\n" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : int = 1000\n" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : int = 10000\n" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "puissance 10 0;;\n", "puissance 10 1;;\n", "puissance 10 2;;\n", "puissance 10 3;;\n", "puissance 10 4;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On va convertir un entier représenté sous cette forme en un entier machine de Caml :" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val valeur : entier -> int = \n" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let valeur {base=b; t=t} =\n", " let v = ref 0 in\n", " let n = Array.length t in\n", " for k = 0 to n - 1 do\n", " v := !v + (t.(k) * (puissance b k))\n", " done;\n", " !v\n", ";;" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int = 4\n" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "valeur quatre;;" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int = 42\n" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "valeur quarantedeux;;" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int = 2006\n" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : int = 2006\n" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : int = 2006\n" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : int = 2006\n" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "valeur n2006;;\n", "valeur n2006_2;;\n", "valeur n2006_3;;\n", "valeur n2006_4;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Résolution" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le texte ne demandait *pas* une approche particulièrement maligne, donc on va naïvement répondre à la question : on convertit les deux entiers en leur valeur, on les compare et VOILÀ." ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val compare_entiers : entier -> entier -> int = \n" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let compare_entiers (a : entier) (b : entier) : int =\n", " let va = valeur a in\n", " let vb = valeur b in\n", " compare va vb\n", ";;" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int = -1\n" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : int = 1\n" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "compare_entiers quatre quarantedeux;;\n", "compare_entiers quarantedeux quatre;;\n", "compare_entiers quatre quatre;;\n", "compare_entiers quarantedeux quarantedeux;;" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int = 1\n" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "compare_entiers n2006 quarantedeux;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Bonus ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
FLEMME
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Conclusion" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Voilà pour la question obligatoire de programmation :\n", "\n", "- c'était facile.\n", "- on a pas essayé d'en faire plus.\n", "\n", "> Bien-sûr, ce petit notebook ne se prétend pas être une solution optimale, ni exhaustive." ] } ], "metadata": { "kernelspec": { "display_name": "OCaml 4.04.2", "language": "OCaml", "name": "ocaml-jupyter" }, "language_info": { "codemirror_mode": "text/x-ocaml", "file_extension": ".ml", "mimetype": "text/x-ocaml", "name": "OCaml", "nbconverter_exporter": null, "pygments_lexer": "OCaml", "version": "4.04.2" }, "toc": { "colors": { "hover_highlight": "#DAA520", "running_highlight": "#FF0000", "selected_highlight": "#FFD700" }, "moveMenuLeft": true, "nav_menu": { "height": "289px", "width": "252px" }, "navigate_menu": true, "number_sections": true, "sideBar": true, "threshold": 4, "toc_cell": true, "toc_position": { "height": "475px", "left": "0px", "right": "1015px", "top": "116px", "width": "201px" }, "toc_section_display": "block", "toc_window_display": true } }, "nbformat": 4, "nbformat_minor": 2 }