{ "cells": [ { "cell_type": "markdown", "id": "eee005ad", "metadata": { "deletable": false, "editable": false, "run_control": { "frozen": true } }, "source": [ "# TP1 – Euclide et consorts" ] }, { "cell_type": "markdown", "id": "38e9168a", "metadata": { "deletable": false, "editable": false, "run_control": { "frozen": true } }, "source": [ "**Consigne :** lire le sujet dans l'ordre et **exécuter chaque cellule de code pré-remplie** pour observer le résultat avant de continuer.\n", "\n", "### Remarque générale.\n", "**_Toutes_** les fonctions écrites doivent être testées. Par exemple, vous pouvez écrire, pour chaque fonction `fct`,\n", "une fonction de test `test_fct()` qui ne prend pas de paramètre et effectue des tests. Ces tests peuvent\n", "utiliser des valeurs (pseudo-)aléatoires. Pour cela, la plupart des types de SageMath implantent une méthode\n", "`random_element`. Lire la documentation (par exemple `ZZ.random_element?`) pour l’utiliser.\n", "\n", "Ce TP est prévu pour deux séances. De manière générale, ils ne sont pas à rendre, et l'objectif est d'aller aussi loin que possible pendant les séances. Finir les TPs par vous même est encouragé, sans vérification de notre part. Note : le TP noté pourra faire appel à toutes les parties des TPs, mêmes les derniers exercices." ] }, { "cell_type": "markdown", "id": "667b7971", "metadata": { "deletable": false, "editable": false, "run_control": { "frozen": true } }, "source": [ "## 1. Découverte de SageMath" ] }, { "cell_type": "markdown", "id": "86aef50d", "metadata": { "deletable": false, "editable": false, "run_control": { "frozen": true } }, "source": [ "1. SageMath peut (presque) être vu comme une bibliothèque de Python : vérifier dans des cellules de calcul\n", "que vous pouvez taper le code Python que vous voulez. On exécute une cellule avec `+`." ] }, { "cell_type": "code", "execution_count": 0, "id": "f16111bb", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "4cd34df7", "metadata": { "deletable": false, "editable": false, "run_control": { "frozen": true } }, "source": [ "2. SageMath n’est pas qu’une bibliothèque, il introduit quelques différences de type ou de syntaxe. Par\n", "exemple, les entiers que vous entrez sont de type `ZZ` et non `int`. Définir une variable `n` avec une valeur\n", "entière dans la première cellule, puis écrire « `n.` » dans la seconde cellule et appuyer sur `` pour voir toutes les méthodes rattachées à un entier.\n", "Chercher celle qui vous semble calculer un PGCD, et vérifier avec quelques exemples." ] }, { "cell_type": "code", "execution_count": 0, "id": "e7ee0665", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "id": "1d21e944", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "f69e3460", "metadata": { "deletable": false, "editable": false, "run_control": { "frozen": true } }, "source": [ "3. Vérifier le type des entiers renvoyés par la fonction `range` (qui vient de Python). Comparer avec la fonction\n", "`srange` (fournie par SageMath)." ] }, { "cell_type": "code", "execution_count": 0, "id": "b34d660d", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "b91915eb", "metadata": { "deletable": false, "editable": false, "run_control": { "frozen": true } }, "source": [ "4. Pour accéder à l’aide d’une méthode (par exemple la méthode `xgcd` d’un entier `n`), on écrit `n.xgcd?` et\n", "on exécute la cellule. Que fait `n.xgcd(...)` ?" ] }, { "cell_type": "code", "execution_count": 0, "id": "89c4dc8a", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "4754c5ee", "metadata": { "deletable": false, "editable": false, "run_control": { "frozen": true } }, "source": [ "5. Chercher dans les menus comment créer une nouvelle cellule (au dessus et en dessous), comment supprimer une cellule, etc. ainsi que les raccourcis clavier." ] }, { "cell_type": "markdown", "id": "ed525512", "metadata": { "deletable": false, "editable": false, "run_control": { "frozen": true } }, "source": [ "## 2. Le modulo de SageMath" ] }, { "cell_type": "markdown", "id": "12a867d1", "metadata": { "deletable": false, "editable": false, "run_control": { "frozen": true } }, "source": [ "1. En testant tous les possibilités, déterminer le comportement de l’opérateur `%` sur des entrées positives et\n", "négatives. Définir mathématiquement le résultat renvoyé par `%`.\n", "2. Effectuer le même travail avec l’opérateur `//` de calcul de quotient.\n", "3. Écrire une fonction `DivEucl(a,b)` qui calcule la division euclidienne de `a` par `b`, avec un reste positif,\n", "compris entre `0` et `|b| - 1`. Faire appel aux opérateurs `%` et `//` !" ] }, { "cell_type": "code", "execution_count": 0, "id": "42ace01b", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "id": "9d8c2a9b", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "id": "4ddcdff6", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "749b2606", "metadata": { "deletable": false, "editable": false, "run_control": { "frozen": true } }, "source": [ "### 3. Algorithme d'Euclide\n", "\n", "1. Implanter l’algorithme d’Euclide en versions récursive et itérative.\n", "2. Comparer les temps de calcul pour des entiers aléatoires. L’une des deux fonctions est-elle plus rapide ?\n", " *Dans la console Ipython ou le notebook Jupyter, les « commandes magiques » `%time` et `%timeit` permettent de mesurer des temps de calculs de manières très simple. Par exemple, il suffit d’écrire `%time EuclideRec(a,b)` pour mesurer le temps d’exécution de l’appel. La commande `%timeit` exécute plusieurs fois l’appel et renvoie une moyenne des temps de calcul (qui est donc moins sujette aux aléas).\n", "3. Implanter l’algorithme d’Euclide étendu en version récursive." ] }, { "cell_type": "code", "execution_count": 0, "id": "e314bc99", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "id": "508b2df4", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "id": "9ee1f4a9", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "f42cfc87", "metadata": { "deletable": false, "editable": false, "run_control": { "frozen": true } }, "source": [ "## 4. Entiers de Fibonacci\n", "La célèbrissime suite de Fibonacci $(F_n)_{n≥0}$ est définie par $F_0 = 0$, $F_1 = 1$ et $F_{n+2} = F_n + F_{n+1}$ pour $n ≥ 0$. Elle a la propriété que les pires entrées pour l’algorithme d’Euclide sont lorsque les deux entiers sont deux éléments consécutifs de la suite de Fibonacci.\n", "1. Écrire une fonction `FiboNaive(n)` qui calcule naïvement l’entier $F_n$. Vérifier que cette fonction est bien\n", "naïve : quelle est la plus grande valeur de $n$ pour laquelle `FiboNaive` s’exécute en moins d’une seconde ?\n", "2. Écrire une version itérative efficace `Fibo(n)` qui calcule le couple $(F_n , F_{n+1})$. L’idée est de partir avec le couple $(F_0,F_1)$, et à chaque itération de remplacer le couple $(F_i, F_{i+1})$ par $(F_{i+1}, F_{i+2})$.\n", "3. Tester les trois algorithmes d’Euclide de l’exercice précédent sur des éléments consécutifs de la suite de\n", "Fibonacci. À partir de quelle valeur (approximative) de $n$ les algorithmes récursifs plantent-ils quand ils\n", "sont appelés avec $F_n$ et $F_{n+1}$ ?" ] }, { "cell_type": "code", "execution_count": 0, "id": "091bcce9", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "id": "45411ca4", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "id": "787c4457", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "id": "058f5fc9", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "5e2bf02c", "metadata": { "deletable": false, "editable": false, "run_control": { "frozen": true } }, "source": [ "## 5. Euclide étendu itératif\n", "\n", "$\\newcommand\\quo{\\operatorname{quo}}$\n", "Pour pouvoir calculer les coefficients de Bézout pour des grands entiers, il faut écrire une version itérative de l'algorithme d'Euclide étendu. Pour cela, on note $r_0 = a$, $r_1 = b$, et $r_{i+2} = r_i\\bmod r_{i+1}$ pour tout $i≥0$ la suite des restes calculés par l'algorithme d'Euclide (on a alors $!pgcd!(a,b) = r_k$ où $r_k$ est le dernier reste non nul). L'objectif est de calculer, pour tout $i$, des coefficients $u_i$ et $v_i$ tels que $r_i = u_i⋅a+v_i⋅b$. Les cas $i = 0$ et $i=1$ peuvent être caclulés directement. Ensuite, si on sait que $r_i = u_i⋅a+v_i⋅b$ et $r_{i+1} = u_{i+1}⋅a+v_{i+1}⋅b$, en écrivant $r_{i+2} = r_i-q r_{i+1}$ où $q = r_i\\quo r_{i+1}$, on en déduit des valeurs pour $u_{i+2}$ et $v_{i+2}$.\n", "\n", "1. Compléter la fonction `EuclideEtenduIt` qui implante cette stratégie (remplacer les « `…` »). *Attention, pour ne pas multiplier les variables $r_i$, $u_i$ et $v_i$, on en utilise uniquement six : $r^0$, $r^1$, $u^0$, $u^1$, $v^0$ et $v^1$. À tout instant, si $r^0$ contient $r_{i+1}$, alors $r^1$ contient $r_i$.*\n", "\n", " ```python\n", " def EuclideEtenduIt(a,b):\n", " r0, r1 = (a,b) if a >= b else …\n", " u0, v0 = …,… # on veut r0 = u0*a+v0*b\n", " u1, v1 = …,… # on veut r1 = u1*a+v1*b\n", " while r1 != 0:\n", " q = r0 // r1\n", " r0,r1 = r1, …\n", " u0,u1 = u1, …\n", " v0,v1 = v1, …\n", " return (r0,u0,v0) if a>=b else …\n", " ```\n", "\n", "1. La tester sur des (grands !) éléments consécutifs de la suite de Fibonacci.\n" ] }, { "cell_type": "code", "execution_count": 0, "id": "76eadab4", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "id": "9091cafc", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "2d45cb46", "metadata": { "deletable": false, "editable": false, "run_control": { "frozen": true } }, "source": [ "## 6. Factorisation\n", "\n", "Comme on l'a vu, tout entier $n$ peut se décomposer de manière unique en produit de facteurs premiers. On va écrire un algorithme pour calculer cette décomposition. Pour cela, on commence diviser $n$ par $2$ tant qu'il est pair, et on obtient ainsi la puissance de $2$ dans la décomposition de $n$. On continue ensuite avec tous les entiers par ordre croissant, jusqu'à avoir $n = 1$. \n", "\n", "1. Pourquoi peut-on ne considérer que les entiers impairs, après $2$, au lieu de les prendre tous ? \n", "\n", "1. Montrer que si $n$ n'est divisible par aucun entier $k ≤ \\sqrt n$, on peut s'arrêter car $n$ est premier.\n", "\n", "1. Écrire une fonction `Factorisation(n)` qui prend entrée $n$ et calcule une décomposition de $n$ en produit de facteurs premiers avec la statégie décrite. *Vous pouvez tester vos résultats avec la méthode `factor` des entiers.*\n" ] }, { "cell_type": "code", "execution_count": 0, "id": "3174c153", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "id": "34e0eb48", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "id": "990a7ae1", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 9.5", "language": "sage", "name": "sagemath" }, "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.10.12" } }, "nbformat": 4, "nbformat_minor": 5 }