{
"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",
" <iframe\n",
" width=\"560\"\n",
" height=\"315\"\n",
" src=\"https://www.youtube.com/embed/oKprCgIKWxo?rel=0&&showinfo=0\"\n",
" frameborder=\"0\"\n",
" allowfullscreen\n",
" \n",
" ></iframe>\n",
" "
],
"text/plain": [
"<IPython.lib.display.IFrame at 0x7f6eed72b7c0>"
]
},
"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",
" <iframe\n",
" width=\"560\"\n",
" height=\"315\"\n",
" src=\"https://www.youtube.com/embed/oqMYAVV-hsA?rel=0&&showinfo=0\"\n",
" frameborder=\"0\"\n",
" allowfullscreen\n",
" \n",
" ></iframe>\n",
" "
],
"text/plain": [
"<IPython.lib.display.IFrame at 0x7f6eed729570>"
]
},
"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
}