{ "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, 2017-18
1.2  À propos de ce document
1.3  Question de programmation
1.3.1  Modélisation
1.4  Solution
1.4.1  Types et représentations
1.4.2  Algorithmes
1.5  Complexités
1.5.1  En espace
1.5.2  En temps
1.6  Conclusion
1.6.1  Qualités
1.6.2  Défauts
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Texte d'oral de modélisation - Agrégation Option Informatique\n", "## Préparation à l'agrégation - ENS de Rennes, 2017-18\n", "- *Date* : 6 décembre 2017\n", "- *Auteur* : [Lilian Besson](https://GitHub.com/Naereen/notebooks/)\n", "- *Texte*: Annale 2018, [\"Polynômes avec des nombres flottants\" (public2018-D2)](http://agreg.org/Textes/public2018-D2.pdf)" ] }, { "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": 1, "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": 1, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "4.04.2\n" ] }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Sys.command \"ocaml -version\";;\n", "print_endline Sys.ocaml_version;;" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val print : ('a, out_channel, unit) format -> 'a = \n" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let print f =\n", " let r = Printf.printf f in\n", " flush_all();\n", " r\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Question de programmation\n", "La question de programmation pour ce texte était donnée en page 6 :\n", "\n", "Cet exercice consiste à observer le comportement des nombres en virgule flottante de la\n", "machine.\n", "Toutes les variables utilisées seront de type `double` ou `float` selon le langage choisi.\n", "On écrit un programme qui évalue $$S = \\sum_{i=0}^{\\infty} \\left(1 - \\frac{1}{\\rho}\\right)^i$$\n", "où $\\rho$ est une puissance de $2$ suffisamment grande, par exemple $\\rho = 2^{20}$.\n", "\n", "Si on calcule naïvement $S_n = \\sum_{i=0}^{n} (1 - \\frac{1}{\\rho})^i$, en ajoutant les termes un par un dans l'ordre des puissances croissantes, on remarque quand $n$ est suffisamment grand, $S_{n+1} = S_n \\oplus (1 - \\frac{1}{\\rho})^{n+1}$\n", "lorsqu’on calcule en `double` (ou `float`).\n", "\n", "En évaluant $S$ sous la forme $$S = \\sum_{j=0}^{\\infty} \\sum_{k=0}^{K-1} \\left(1 - \\frac{1}{\\rho}\\right)^{jK + k}$$\n", "ce phénomène se produit pour des rangs plus grands que précedemment, l'approximation de $S$ calculée est donc meilleure. On pourra essayer plusieurs valeurs de $K$ ($1,10,100,1000,10000$) et comparer. $K = 1$ correspond au calcul naïf de $S$ ci-dessus.\n", "Optionnellement, le programme pourra également calculer une borne sur l’erreur com-\n", "mise sur $S$.\n", "\n", "### Modélisation\n", "On est libre de choisir l'approche, mais ici il n'y a pas tellement de choix, on va utiliser des `float` de OCaml." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Solution\n", "\n", "On va essayer d'être rapide et de faire simple." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Types et représentations\n", "\n", "Rien à faire ici, on va travailler avec des `float` de OCaml classiques." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Algorithmes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Première méthode de calcul. On remarque qu'on est déjà malin, on n'utilise aucune exponentiation mais simplement un accumulateur `terme` qui vaut $(1-1/\\rho)^j$ pour les valeurs successives de $j$, et qu'on met à jour par une simple multiplication." ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val premiercalcul : float -> int -> float = \n" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let premiercalcul (rho : float) (n : int) =\n", " let somme = ref 0. in\n", " let unmoinsunsurrho = 1. -. (1. /. rho) in\n", " let terme = ref 1. in\n", " for _ = 0 to n do (* terme = (1-1/rho)^j pour j = _ *)\n", " somme := !somme +. !terme; (* somme = sum_k=0^j terme_k *)\n", " terme := !terme *. unmoinsunsurrho; (* conserve l'invariant de boucle *)\n", " done;\n", " !somme\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Voyons un exemple :" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val rho : float = 1048576.\n" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let rho = 2. ** 20.;;" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : float = 0.999999046325683594\n" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1. -. 1. /. rho;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Cette valeur est proche de $1$, mais strictement plus petite que $1$, et donc $(1-1/\\rho)^i \\to 0$ géométriquement vite, ainsi $S_n$ converge bien vers $S$ pour $n \\to \\infty$." ] }, { "cell_type": "code", "execution_count": 40, "metadata": { "scrolled": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "S_10000 \t= 1.04847e+06\n", "S_100000 \t= 1.04847e+06\n", "S_0 \t= 1\n", "S_1 \t= 2\n", "S_2 \t= 3\n", "S_3 \t= 3.99999\n", "S_4 \t= 4.99999\n", "S_5 \t= 5.99999\n", "S_6 \t= 6.99998\n", "S_7 \t= 7.99997\n", "S_8 \t= 8.99997\n" ] }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "for n = 0 to 10 do\n", " print \"\\nS_%i \\t= %g\" n (premiercalcul rho n);\n", "done;" ] }, { "cell_type": "code", "execution_count": 42, "metadata": { "scrolled": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "S_1009 \t= 1009.51\n", "S_1010 \t= 1010.51\n", "S_1000 \t= 1000.52\n", "S_1001 \t= 1001.52\n", "S_1002 \t= 1002.52\n", "S_1003 \t= 1003.52\n", "S_1004 \t= 1004.52\n", "S_1005 \t= 1005.52\n", "S_1006 \t= 1006.52\n", "S_1007 \t= 1007.52\n", "S_1008 \t= 1008.52\n" ] }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "for n = 1000 to 1010 do\n", " print \"\\nS_%i \\t= %g\" n (premiercalcul rho n);\n", "done;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Deuxième méthode de calcul :" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val deuxiemecalcul : float -> int -> int -> float = \n" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let deuxiemecalcul (rho : float) (k : int) (n : int) =\n", " let somme = ref 0. in\n", " let unmoinsunsurrho = 1. -. (1. /. rho) in\n", " let terme = ref 1. in\n", " for _ = 0 to n do\n", " for _ = 0 to k-1 do\n", " somme := !somme +. !terme;\n", " terme := !terme *. unmoinsunsurrho;\n", " done;\n", " terme := !terme *. unmoinsunsurrho;\n", " done;\n", " !somme\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Voyons le même exemple :" ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "scrolled": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "S_9 \t= 95379.3\n", "S_10 \t= 104426\n", "\n", "For K = 1 ...\n", "S_0 \t= 1\n", "S_1 \t= 2\n", "S_2 \t= 2.99999\n", "S_3 \t= 3.99999\n", "S_4 \t= 4.99998\n", "S_5 \t= 5.99997\n", "S_6 \t= 6.99996\n", "S_7 \t= 7.99995\n", "S_8 \t= 8.99993\n", "S_9 \t= 9.99991\n", "S_10 \t= 10.9999\n", "\n", "For K = 10 ...\n", "S_0 \t= 9.99996\n", "S_1 \t= 19.9998\n", "S_2 \t= 29.9996\n", "S_3 \t= 39.9992\n", "S_4 \t= 49.9987\n", "S_5 \t= 59.9982\n", "S_6 \t= 69.9975\n", "S_7 \t= 79.9967\n", "S_8 \t= 89.9958\n", "S_9 \t= 99.9949\n", "S_10 \t= 109.994\n", "\n", "For K = 100 ...\n", "S_0 \t= 99.9953\n", "S_1 \t= 199.981\n", "S_2 \t= 299.957\n", "S_3 \t= 399.923\n", "S_4 \t= 499.88\n", "S_5 \t= 599.827\n", "S_6 \t= 699.765\n", "S_7 \t= 799.693\n", "S_8 \t= 899.611\n", "S_9 \t= 999.52\n", "S_10 \t= 1099.42\n", "\n", "For K = 1000 ...\n", "S_0 \t= 999.524\n", "S_1 \t= 1998.09\n", "S_2 \t= 2995.71\n", "S_3 \t= 3992.38\n", "S_4 \t= 4988.09\n", "S_5 \t= 5982.86\n", "S_6 \t= 6976.67\n", "S_7 \t= 7969.54\n", "S_8 \t= 8961.46\n", "S_9 \t= 9952.43\n", "S_10 \t= 10942.5\n", "\n", "For K = 10000 ...\n", "S_0 \t= 9952.47\n", "S_1 \t= 19810.5\n", "S_2 \t= 29574.9\n", "S_3 \t= 39246.6\n", "S_4 \t= 48826.6\n", "S_5 \t= 58315.6\n", "S_6 \t= 67714.5\n", "S_7 \t= 77024.2\n" ] }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "S_8 \t= 86245.5\n" ] } ], "source": [ "let valeurs_k = [|1; 10; 100; 1000; 10000|] in\n", "\n", "for i = 0 to (Array.length valeurs_k) - 1 do\n", " let k = valeurs_k.(i) in\n", " print \"\\n\\nFor K = %i ...\" k;\n", " for n = 0 to 10 do\n", " print \"\\nS_%i \\t= %g\" n (deuxiemecalcul rho k n);\n", " done;\n", "done;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Avec de grandes valeurs de $n$, on semble converger vers la limite $S$, d'autant plus vite que $K$ est grand." ] }, { "cell_type": "code", "execution_count": 38, "metadata": { "scrolled": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "S_10000 \t= 1.04847e+06\n", "S_100000 \t= 1.04847e+06\n", "\n", "For K = 1 ...\n", "S_100 \t= 100.99\n", "S_1000 \t= 1000.05\n", "S_10000 \t= 9906.23\n", "S_100000 \t= 91042.7\n", "\n", "For K = 10 ...\n", "S_100 \t= 1009.47\n", "S_1000 \t= 9957.64\n", "S_10000 \t= 94942.6\n", "S_100000 \t= 619357\n", "\n", "For K = 100 ...\n", "S_100 \t= 10051\n", "S_1000 \t= 95425.8\n", "S_10000 \t= 641990\n", "S_100000 \t= 1.03813e+06\n", "\n", "For K = 1000 ...\n", "S_100 \t= 96283.8\n", "S_1000 \t= 644662\n", "S_10000 \t= 1.04745e+06\n", "S_100000 \t= 1.04753e+06\n", "\n", "For K = 10000 ...\n", "S_100 \t= 648345\n", "S_1000 \t= 1.0484e+06\n" ] }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let valeurs_n = [|100; 1000; 10000; 100000|] in\n", "let valeurs_k = [|1; 10; 100; 1000; 10000|] in\n", "\n", "for i = 0 to (Array.length valeurs_k) - 1 do\n", " let k = valeurs_k.(i) in\n", " print \"\\n\\nFor K = %i ...\" k;\n", " for j = 0 to (Array.length valeurs_n) - 1 do\n", " let n = valeurs_n.(j) in\n", " print \"\\nS_%i \\t= %g\" n (deuxiemecalcul rho k n);\n", " done;\n", "done;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Complexités" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### En espace\n", "Ces calculs coûtent un espace constant en mémoire.\n", "\n", "(ou $\\log n$ si on considère que stocker des entiers bornés par $n$ coûtent un espace $\\log n$)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### En temps\n", "Ces calculs coûtent un temps linéaire en $n$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Conclusion\n", "\n", "Voilà pour la question obligatoire de programmation.\n", "\n", "### Qualités\n", "- On a fait des exemples et *on les garde* dans ce qu'on présente au jury,\n", "- On a testé la fonction exigée sur de petits exemples et sur un exemple de taille réelle (venant du texte).\n", "\n", "### Défauts\n", "- Par contre, on est un peu pauvre en visualisation et explication,\n", "- Et on a implémenté aucun autre développement. A suivre, j'en ajouterai quand je peux.\n", "\n", "\n", "> Bien-sûr, ce petit notebook ne se prétend pas être une solution optimale, ni exhaustive.\n", "\n", "> Vous auriez pu choisir de modéliser le problème avec une autre approche, mais je ne vois pas ce qu'on aurait pu faire différement." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> C'est tout pour aujourd'hui les amis, allez voir [ici pour d'autres corrections](https://github.com/Naereen/notebooks/tree/master/agreg), et que la force soit avec vous !" ] } ], "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" }, "notify_time": "10", "toc": { "colors": { "hover_highlight": "#DAA520", "running_highlight": "#FF0000", "selected_highlight": "#FFD700" }, "moveMenuLeft": true, "nav_menu": { "height": "429px", "width": "251px" }, "navigate_menu": true, "number_sections": true, "sideBar": true, "threshold": 4, "toc_cell": true, "toc_section_display": "block", "toc_window_display": false } }, "nbformat": 4, "nbformat_minor": 2 }