{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "___\n", "\n", "\n", "# Arithmétique - L2 Informatique - 2022-2023\n", "\n", "___\n", "\n", "\n", "### Enseignants: San Vũ Ngọc & Pierre Houedry & Fabien Narbonne\n", "\n", "___\n", "(IRMAR, Université de Rennes 1)\n", "___\n", "\n", "___\n", "\n", " \n", "### Références \n", "\n", "* Page Web:\n", " https://perso.univ-rennes1.fr/san.vu-ngoc/blog/arithmetique/\n", "\n", "* Cours de base:\n", " http://exo7.emath.fr/cours/livre-algebre-1.pdf\n", "\n", "* Cours avancé:\n", " https://perso.univ-rennes1.fr/christophe.mourougane/enseignements/2014-15/AR1/poly-test.pdf\n", " \n", " \n", " \n", "___\n", "\n", "___\n", "\n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Python\n", "\n", "Langage très facile à apprendre, beaucoup d'aide en ligne. Attention aux **indentations**." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0\n", "1\n", "2\n", "3\n", "4\n", "Hello\n", "4\n" ] } ], "source": [ "for i in range(5):\n", " print (i)\n", "print (\"Hello\")\n", "print (i) # Horreur" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# I. Introduction\n", "\n", "N'hésitez pas à fouiller sur internet. Par exemple, \n", "\n", "* La Chaîne Youtube [\"Science4all\"](https://www.youtube.com/channel/UC0NCbj8CxzeCGIF6sODJ-7A) de Lê Nguyên Hoang\n", "\n", "* La Chaîne [\"Micmaths\"](https://www.youtube.com/micmaths) de Mickaël Launay\n", "\n", "* Les [\"5 minutes Lebesgue\"](https://www.youtube.com/playlist?list=PLZ5ZEffH1cUAkodxGDs0SNif_wScXNTU0) de l'Institut de Recherche Mathématiques de Rennes !\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# II. Entiers naturels et relatifs\n", "\n", "## 1. construction des entiers naturels" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", " \n", " " ], "text/plain": [ "" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from IPython.display import IFrame\n", "\n", "IFrame(\"https://www.youtube.com/embed/oKprCgIKWxo?rel=0&&showinfo=0\",560,315)\n" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "frozenset()" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "zero = frozenset()\n", "zero" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "frozenset({frozenset()})" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "un = frozenset([zero])\n", "un" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "frozenset({frozenset(), frozenset({frozenset()})})" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "deux = frozenset([zero,un])\n", "deux" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(), frozenset({frozenset()})})})" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "trois = frozenset([zero,un,deux])\n", "trois" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(zero)" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(un)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(trois)" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "trois == deux.union([deux])" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": [ "def successeur(chiffre):\n", " return chiffre.union([chiffre])\n", " " ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "un == successeur(zero)" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "deux == successeur(trois)" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "frozenset()\n", "frozenset({frozenset()})\n", "frozenset({frozenset(), frozenset({frozenset()})})\n" ] } ], "source": [ "for n in trois:\n", " print(n)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "L'addition étant définie par récurrence, on peut chercher à la programmer par une fonction **récursive**. Mais, attention, une fonction récursive est en fait une récurrence *inversée*: étant donné $n$, on doit appeler la fonction avec $n-1$. Le problème est qu'ici on n'a pas (encore, voir plus bas !) défini la soustraction (ou même la fonction \"prédecesseur\" ou \"-1\").\n", "\n", "On s'en sort en examinant ce que fait la définition par récurrence de $n+k$: c'est `succ(succ(...(succ(n+0))..))`\n", "où l'opération `succ` est effectuée $k$ fois. On peut donc programmer:" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "def addition(n,k):\n", " r = n\n", " for _i in k: # on parcourt l'ensemble \"k\", qui contient \"k éléments\"\n", " r = successeur(r)\n", " return r" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(), frozenset({frozenset()})})})" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "addition(deux,un)" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "_ == trois" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Évidemment, ce n'est pas une **représentation** efficace des entiers !" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [], "source": [ "def of_int(n):\n", " assert (n >= 0)\n", " if n == 0:\n", " return (zero)\n", " else:\n", " return successeur(of_int(n - 1))" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "frozenset()" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "of_int(0)" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "of_int(2) == deux" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [], "source": [ "dix = of_int(10)" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "10" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len (dix)" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "scrolled": false }, "outputs": [ { "data": { "text/plain": [ "frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(), frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(), frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(), frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(), frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(), frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(), frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(), frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})})})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(), frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})})})})})})})})" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dix" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [], "source": [ "cinq = of_int(5)" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "addition(cinq, cinq) == dix" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2. L'ensemble de \"tous\" les entiers naturels\n", "\n", "Python 3 utilise par défaut des entiers \"longs\" de taille arbitraire (ou presque...)" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4611686018427387904" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "2**62" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "295811224608098629060044695716103590786339687135372992239556207050657350796238924261053837248378050186443647759070955993120820899330381760937027212482840944941362110665443775183495726811929203861182015218323892077355983393191208928867652655993602487903113708549402668624521100611794270340232766099317098048887493809023127398253860618772619035009883272941129544640111837184" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "n=2**1234\n", "n" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "int" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type(n)" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", " \n", " " ], "text/plain": [ "" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "IFrame(\"https://www.youtube.com/embed/oqMYAVV-hsA?rel=0&&showinfo=0\",560,315)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Langages informatiques: Attention aux implémentations des entiers!\n", "\n", "Le danger vient souvent des langages non strictement typés, ou de l'utilisation d'un type mal compris (`int` au lieu de `bigint`). Dans la plupart des langages informatiques, le type \"int\" est en fait cyclique: par exemple pour des entiers codés sur 64bit, on aura:\n", "\n", "``` 4611686018427387903 + 1 = -4611686018427387904\n", "```\n", "\n", "Mais il y a pire. Par exemple javascript est buggué: https://jsconsole.com/ (ou même la console de votre navigateur, si vous n'y croyez pas).\n", "Essayez `2**55`.\n", "\n", "(Pourquoi la réponse donnée 36028797018963970 ne peut pas être correcte ?) Imaginez si un ingénieur utilise ça pour contrôler la trajectoire d'une fusée dans l'espace...\n", "\n", "Essayez `2**55 == 2**55 - 1`\n", "\n", "Exemple de langage fortement typé: **[ocaml](https://ocaml.org/)**.\n", "\n", "En **python 3**, le passage aux entiers \"longs\" est automatique (et invisible à l'utilisateur), c'est très pratique pour nous. (Mais pas forcément très performant.) Attention, ce n'est pas le cas en **python 2**." ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(36028797018963968, 4611686018427387903)" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "2**55, 2**62-1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3. Ordre" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 2, 3, 5, 8, 10]" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sorted([5,1,3,8,10,2])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Python utilise `<=` pour tester l'inclusion des frozenset, donc c'est tout bon pour nous !" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "deux <= trois" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Comment trouver le **prédécesseur** d'un entier $n$ ? (c'est-à-dire $n-1$). Astuce: c'est le *plus grand élement* du `frozenset` $n$:" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "frozenset({frozenset(), frozenset({frozenset()})})" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "max(trois)" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "max(trois) == deux" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [], "source": [ "def pred (n):\n", " return max(n)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut re-définir l'addition avec une fonction récursive plus naturelle:" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [], "source": [ "def addition_rec (n,k):\n", " if k == zero:\n", " return n\n", " else:\n", " return successeur(addition(n,pred(k)))" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(), frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(), frozenset({frozenset()})})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(), frozenset({frozenset()})}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()}),\n", " frozenset({frozenset(),\n", " frozenset({frozenset()})})})})})" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "s = addition_rec (deux, trois)\n", "s" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(s)" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "s == addition(deux, trois)" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "s == addition_rec(trois, deux)" ] } ], "metadata": { "@webio": { "lastCommId": null, "lastKernelId": null }, "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "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.6" } }, "nbformat": 4, "nbformat_minor": 2 }