(IRMAR, Université de Rennes 1)
Page Web: https://perso.univ-rennes1.fr/san.vu-ngoc/blog/arithmetique/
Cours de base: http://exo7.emath.fr/cours/livre-algebre-1.pdf
Cours avancé: https://perso.univ-rennes1.fr/christophe.mourougane/enseignements/2014-15/AR1/poly-test.pdf
Langage très facile à apprendre, beaucoup d'aide en ligne. Attention aux indentations.
for i in range(5):
print (i)
print ("Hello")
print (i) # Horreur
0 1 2 3 4 Hello 4
N'hésitez pas à fouiller sur internet. Par exemple,
La Chaîne Youtube "Science4all" de Lê Nguyên Hoang
La Chaîne "Micmaths" de Mickaël Launay
Les "5 minutes Lebesgue" de l'Institut de Recherche Mathématiques de Rennes !
from IPython.display import IFrame
IFrame("https://www.youtube.com/embed/oKprCgIKWxo?rel=0&&showinfo=0",560,315)
zero = frozenset()
zero
frozenset()
un = frozenset([zero])
un
frozenset({frozenset()})
deux = frozenset([zero,un])
deux
frozenset({frozenset(), frozenset({frozenset()})})
trois = frozenset([zero,un,deux])
trois
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(), frozenset({frozenset()})})})
len(zero)
0
len(un)
1
len(trois)
3
trois == deux.union([deux])
True
def successeur(chiffre):
return chiffre.union([chiffre])
un == successeur(zero)
True
deux == successeur(trois)
False
for n in trois:
print(n)
frozenset()
frozenset({frozenset()})
frozenset({frozenset(), frozenset({frozenset()})})
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").
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))..))
où l'opération succ est effectuée $k$ fois. On peut donc programmer:
def addition(n,k):
r = n
for _i in k: # on parcourt l'ensemble "k", qui contient "k éléments"
r = successeur(r)
return r
addition(deux,un)
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(), frozenset({frozenset()})})})
_ == trois
True
Évidemment, ce n'est pas une représentation efficace des entiers !
def of_int(n):
assert (n >= 0)
if n == 0:
return (zero)
else:
return successeur(of_int(n - 1))
of_int(0)
frozenset()
of_int(2) == deux
True
dix = of_int(10)
len (dix)
10
dix
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(), frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(), frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(), frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(), frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(), frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(), frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(), frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})})})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(), frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})})})})})})})})
cinq = of_int(5)
addition(cinq, cinq) == dix
True
Python 3 utilise par défaut des entiers "longs" de taille arbitraire (ou presque...)
2**62
4611686018427387904
n=2**1234
n
295811224608098629060044695716103590786339687135372992239556207050657350796238924261053837248378050186443647759070955993120820899330381760937027212482840944941362110665443775183495726811929203861182015218323892077355983393191208928867652655993602487903113708549402668624521100611794270340232766099317098048887493809023127398253860618772619035009883272941129544640111837184
type(n)
int
IFrame("https://www.youtube.com/embed/oqMYAVV-hsA?rel=0&&showinfo=0",560,315)
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:
4611686018427387903 + 1 = -4611686018427387904
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).
Essayez 2**55.
(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...
Essayez 2**55 == 2**55 - 1
Exemple de langage fortement typé: ocaml.
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.
2**55, 2**62-1
(36028797018963968, 4611686018427387903)
sorted([5,1,3,8,10,2])
[1, 2, 3, 5, 8, 10]
Python utilise <= pour tester l'inclusion des frozenset, donc c'est tout bon pour nous !
deux <= trois
True
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$:
max(trois)
frozenset({frozenset(), frozenset({frozenset()})})
max(trois) == deux
True
def pred (n):
return max(n)
On peut re-définir l'addition avec une fonction récursive plus naturelle:
def addition_rec (n,k):
if k == zero:
return n
else:
return successeur(addition(n,pred(k)))
s = addition_rec (deux, trois)
s
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(), frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(), frozenset({frozenset()})})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(), frozenset({frozenset()})}),
frozenset({frozenset(),
frozenset({frozenset()}),
frozenset({frozenset(),
frozenset({frozenset()})})})})})
len(s)
5
s == addition(deux, trois)
True
s == addition_rec(trois, deux)
True