{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# **L3 Algèbre effective — TP 1  du mardi 17 septembre 2019**\n",
    " \n",
    "## **Pgcd, algorithme d'Euclide et relations de Bezout**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## **I La suite de Fibonacci: récursif vs. itératif**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On rappelle que la suite de Fibonacci est la suite linéaire récurrente définie par \n",
    "$$ u_0=1 \\qquad u_1=1 \\qquad \\text{ et } \\qquad \\forall n \\geq 2,\\ u_{n}=u_{n-1}+u_{n-2}.$$\n",
    "Pour évaluer le 100ème terme de la suite, il est tentant d'implémenter la suite de manière récursive. \n",
    "\n",
    "Faîtes le. Que remarquez-vous? Pourquoi?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "fib(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comment faire pour calculer $u_{100}$?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## **II -Pgcd**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "a) Trouver dans l'aide la fonction Sage qui permet de calculer le pgcd de deux entiers.\n",
    "\n",
    "Faire quelques tests: \n",
    "pgcd(5,6)=?\n",
    "pgcd(0,6)=?\n",
    "pgcd(0,0)=?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un premier objectif de ce TP est de reprogrammer cette fonction vous même, en utilisant l'algorithme d'Euclide."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "b) Quelle fonction permet en Sage de calculer le reste dans une division euclidienne? Et le quotient?\n",
    "\n",
    "Quelle est la division euclidienne de 1234 par 7?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quelle relation y a-t-il entre la division euclidienne de m par n et celle de m+n par n?\n",
    "Pour $0\\leq m \\leq n$, quelle est la division euclidienne de m par n?\n",
    "\n",
    "En utilisant les remarques ci-dessus, écrivez un programme **récursif** qui calcule la division euclidienne du premier argument par le second (s'il est non nul).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def div(m,n):\n",
    "    return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "c) Compléter la fonction ci-dessous pour qu'elle calcule le pgcd des arguments.\n",
    "Plusieurs approches sont possibles, dont:\n",
    "1) Une boucle \n",
    "2) Une approche récursive"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pgcd(m,n):\n",
    "    return 0\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vérifier sur les exemples précédents."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**d-1.)** Pour évaluer la \"complexité\" du calcul du pgcd, on pourrait commencer par compter le nombre de divisions euclidiennes effectuées. Faîtes le.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "pgcd(fib(10),fib(9))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "pgcd(fib(10)-1,fib(9))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "pgcd(fib(10)-2,fib(9))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**d-2)** Une façon d'améliorer la complexité ci-dessus est de ne pas utiliser des divisions euclidiennes *stricto sensu*, mais des divisions avec restes possiblement négatifs.\n",
    "Remarquer que si *a*>*b*>0 sont des entiers, alors il existe une division avec reste:\n",
    "\n",
    "*a=bq+r*, **avec |r|≤ b/2**\n",
    "\n",
    "(Noter  qu'ici, *r* est potentiellement négatif!) et qu'alors, on a *pgcd(a,b)=pgcd(b,|r|)*.\n",
    "\n",
    "Utiliser cette remarque pour proposer un calcul du pgcd plus rapide que le précédent et comparer le nombre d'opérations.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pgcd2(m,n):\n",
    "    return 0;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "e) Implémenter une fonction *pgcdbin* utilisant l'algorithme binaire (faire une recherche si nécessaire)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pgcdbin(m,n):\n",
    "    return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "f) Quelle fonction en sage permet de trouver les coefficients d'une relation de Bézout?\n",
    "\n",
    "Donner une relation de Bézout entre 779 et 123."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compléter la fonction suivante pour qu'elle calcule une relation de Bézout entre les arguments.\n",
    "\n",
    "Plusieurs approches sont possibles, dont\n",
    "1) Calquer la méthode \"humaine\" qui consiste à remonter l'algorithme d'Euclide. Pour cela, il faut créer des listes en sage pour stocker les valeurs des quotients successifs dans l'algorithme d'Euclide\n",
    "2) Si r est le reste de la division euclidienne de m par n, trouver un lien entre Bezout(m,n) et Bezout(n,r).\n",
    "En déduire une variante récursive."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Bezout(m,n):\n",
    "    return 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Testez votre fonction."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "Bezout(779,123)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## III - Ecriture triadique (=en base 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ecrire une fonction *triad* qui renvoie (sous forme de liste) l'écriture d'un entier en base *3*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def triad(n):\n",
    "    return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.4",
   "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.9.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": false,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": false,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}