Mathématice, intégration des Tice dans l'enseignement des mathématiques  
Sommaire > N°65 - Mai 2019 > Les algorithmes du programme de spécialité (...)

Les algorithmes du programme de spécialité mathématiques de Première (2019).
Moteur de recherche
Mis en ligne le 27 avril 2019, par Benjamin Clerc

Cet article peut être librement diffusé et son contenu réutilisé pour une utilisation non commerciale (contacter l’auteur pour une utilisation commerciale) suivant la licence CC-by-nc-sa

Dans le programme de mathématiques de première générale (spécialité Mathematiques) on trouve parmi la liste des compétences mathématiques travaillées :
- calculer, appliquer des techniques et mettre en œuvre des algorithmes ;
Ainsi, il y a dans ce programme des indications au sujet de ces algorithmes que l’on peut mettre en œuvre, nous allons ici les illustrer.

Algèbre

Calculer des termes d’une suite définie par un algorithme.

Les listes en compréhension sont des objets qui permettent de générer assez simplement des suites de nombres (voir Notion de liste en dernier paragraphe) :

  1. >>> [7*i for i in range(1,11)]
  2. [7, 14, 21, 28, 35, 42, 49, 56, 63, 70]
  3. >>> [2*i for i in range(20)]
  4. [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38]
  5. >>> [i**2 for i in range(16)]
  6. [0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225]
  7. >>> [i for i in range(100) if i%7==2]
  8. [2, 9, 16, 23, 30, 37, 44, 51, 58, 65, 72, 79, 86, 93]

Télécharger

Voyons maintenant, plus classiquement, le calcul de termes d’une suite définie de manière explicite, c’est-à-dire à l’aide d’une fonction de n.

  1. def u(n):
  2. return 3*n+1
  3. def suite_explicite(u,debut,fin):
  4. suite = []
  5. for i in range(debut,fin+1):
  6. suite.append(u(i))
  7. return suite

Télécharger

Après avoir défini la fonction u, on crée une liste vide appelée "suite" dans laquelle on ajoute (append) à l’aide d’une boucle les termes d’indice compris entre début et fin.
Si l’on veut simplement un terme de rang donné, il suffit d’utiliser la fonction u :

  1. >>> suite_explicite(u,0,10)
  2. [1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31]
  3. >>> u(5)
  4. 16

Télécharger

Regardons maintenant du côté des suites définies par récurrence :

  1. def f(u_n):
  2. return 3*u_n+1
  3. def suite_recurrente(f,debut,fin,u_0):
  4. suite = [u_0]
  5. for i in range(debut,fin):
  6. suite.append(f(suite[i-debut]))
  7. return suite

Télécharger

Après avoir défini la fonction f, qui calcule $u_{n+1}$ en fonction de $u_{n}$, on crée une liste appelée "suite" qui contient uniquement le premier terme de la liste, dans laquelle on ajoute (append) à l’aide d’une boucle les termes d’indice compris entre début+1 et fin.

  1. >>> suite_recurrente(f,0,10,0)
  2. [0, 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524]
  3. >>> suite_recurrente(f,5,10,12)
  4. [12, 37, 112, 337, 1012, 3037]

Télécharger

Si l’on veut simplement un terme de rang "fin", il suffit de renvoyer suite[fin-debut] à la place de suite.

  1. >>> suite_recurrente(f,0,10,0)
  2. 29524
  3. >>> suite_recurrente(f,5,10,12)
  4. 3037

Télécharger

Calcul de termes d’une suite, de sommes de termes, de seuil.

Étant donné que "Les suites arithmétiques et géométriques sont formalisées." d’après le programme, il semble légitime de s’y intéresser particulièrement. On peut bien sûr utiliser les fonctions suite_explicite() et suite_recurrente() précédentes, il suffit d’écrire le terme général ou la relation de récurrence adéquats. Sinon, il est possible aussi de créer un outil spécifique qui prendrait en paramètres les rangs de début et de fin ainsi que le terme initial et la raison.

  1. def suite_geometrique(debut,fin,u_0,raison):
  2. suite = [u_0]
  3. for i in range(debut,fin):
  4. suite.append(suite[i-debut]*raison)
  5. return suite
  6. def suite_arithmetique(debut,fin,u_0,raison):
  7. suite = [u_0]
  8. for i in range(debut,fin):
  9. suite.append(suite[i-debut]+raison)
  10. return suite

Télécharger

Utilisation :

  1. >>> suite_arithmetique(1,10,2000,30)
  2. [2000, 2030, 2060, 2090, 2120, 2150, 2180, 2210, 2240, 2270]
  3. >>> suite_geometrique(4,10,3,2)
  4. [3, 6, 12, 24, 48, 96, 192]

Télécharger

Un algorithme "de seuil" permet de déterminer une valeur pour laquelle une condition est respectée pour la première fois.
Ce type d’algorithme peut être utilisé pour répondre, par exemple, à ce genre de question : « déterminer la plus petite valeur de n pour laquelle $u_n>1000$ ».

Concrètement, on considère une suite $(u_n)$ et on cherche à écrire un algorithme "de seuil" sur cette suite.
Le modèle à utiliser est le suivant (où les termes de la suite sont représentés par la lettre U et les rangs par la lettre N) :

N ← valeur initiale (souvent 0 ou 1)
U  ← valeur initiale
TANT QUE condition
   N  ← N+1
   U  ← .... (le terme suivant qui dépend de l'exercice)
FIN TANT QUE

On en profite pour calculer la somme des termes de la suite entre les indices debut et fin.
Si la suite est définie de manière explicite :

  1. def u(n):
  2. return 3*n+1
  3. def seuil_explicite(n_0,N):
  4. n=n_0
  5. while u(n)<N:
  6. n=n+1
  7. return n
  8. def somme_explicite(debut,fin):
  9. s=0
  10. for i in range(debut,fin+1):
  11. s=s+u(i)
  12. return s

Télécharger

Utilisation :

  1. >>> seuil_explicite(5,1000)
  2. 333
  3. >>> somme_explicite(5,9)
  4. 110

Télécharger

Si la suite est définie de manière récurrente :

  1. def f(u_n):
  2. return 3*u_n+1
  3. def seuil_recurrent(n_0,u_0,N):
  4. n=n_0
  5. U=u_0
  6. while U<N:
  7. n=n+1
  8. U=f(U)
  9. return n
  10. def somme_recurrente(debut,fin,u_0):
  11. s=u_0
  12. u=u_0
  13. for i in range(debut,fin):
  14. u=f(u)
  15. s=s+u
  16. return s

Télécharger

Utilisation :

  1. >>> seuil_recurrent(5,1000,15000)
  2. 8
  3. >>> somme_recurrente(3,7,5)
  4. 663

Télécharger

On pourra facilement adapter ces scripts de seuil si la suite est décroissante et qu’il s’agit de déterminer à partir de quand son terme devient inférieur à une valeur donnée.

Calcul de factorielle.

Pour tout nombre entier $n > 1, n ! = n\times(n-1)\times ...\times 1$ (lisez : "factorielle n"). Et par convention : $1 ! = 1$.
On remarquera également que $(n+1) ! = (n + 1)n !$, ce qui nous permet d’écrire le programme récursif suivant :

  1. def factorielle(n):
  2. if n==1:
  3. return 1
  4. else:
  5. return n*factorielle(n-1)

Télécharger

Utilisation :

  1. >>> factorielle(5)
  2. 120

Télécharger

En utilisant un programme récursif tel que celui-ci, on peut rencontrer le problème suivant :

>>> factorielle(975)
>>> RecursionError: maximum recursion depth exceeded in comparison

Sinon, plus classiquement, avec une boucle Pour :

  1. def factorielle(n):
  2. fact=1
  3. for i in range(n):
  4. fact*=(i+1)
  5. return fact

Télécharger

Ou avec un Tant Que :

  1. def factorielle(n):
  2. fact = 1
  3. i = 1
  4. while i <= n:
  5. fact = fact*i
  6. i = i + 1
  7. return fact

Télécharger

Liste des premiers termes d’une suite : suite de Syracuse, suite de Fibonacci

La suite de Fibonacci est une suite d’entiers dans laquelle chaque terme est la somme des deux termes qui le précèdent. Elle commence généralement par les termes 0 et 1 (parfois 1 et 1) et ses premiers termes sont : 0, 1, 1, 2, 3, 5, 8, 13, 21, etc.
Une première version du calcul de ces termes peut consister à utiliser deux variables a et b, initiées à 1, et à chaque boucle on met le contenu de b dans a et a+b dans b, soit :

  1. def fibonacci1(n):
  2. a=1
  3. b=1
  4. for n in range(n):
  5. a,b=b,a+b
  6. return a

Télécharger

Utilisation :

  1. >>> fibonacci1(20)
  2. 10946

Télécharger

Une seconde version s’appuiera sur la récurrence double de la suite : $u_{n+1}=u_n + u_{n−1}$

  1. def fibonacci2(n):
  2. if (n==0) or (n==1):
  3. return 1
  4. else:
  5. return fibonacci2(n-1)+fibonacci2(n-2)

Télécharger

Comme fibonacci2(0)= fibonacci2(1)=1, le code ci-dessus peut calculer fibonacci2(2) et les suivants.
Utilisation :

  1. >>> fibonacci2(20)
  2. 10946

Télécharger

Nombre d’Or : Un problème numériquement intéressant (et c’était la motivation initiale de Fibonacci) est d’étudier le comportement du rapport entre deux termes successifs de la suite de Fibonacci, on pourra dans fibonacci1() renvoyer b/a et pour fibonacci2() créer une nouvelle fonction :

  1. def rapport(n):
  2. return fibonacci2(n+1)/fibonacci2(n)

Télécharger

On conjecture alors que la suite de Fibonacci tend vers le nombre d’or : $\varphi =\frac {1+\sqrt {5}}{2}$.

La suite de Syracuse ou suite de Collatz est une suite d’entiers naturels définie de la manière suivante : on part d’un nombre entier naturel non nul ; s’il est pair, on le divise par 2 ; s’il est impair, on le multiplie par 3 et on ajoute 1. En répétant l’opération, on obtient une suite d’entiers positifs dont chacun ne dépend que de son prédécesseur.
Par exemple, à partir de 28, on construit la suite des nombres : 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2… C’est ce qu’on appelle la suite de Syracuse du nombre 14.
Une fois que le nombre 1 est atteint, la suite des valeurs (1,4,2,1,4,2…) se répète indéfiniment en un cycle de longueur 3, appelé cycle trivial.
Si l’on était parti d’un autre entier, en lui appliquant les mêmes règles, on aurait obtenu une suite de nombres différente. A priori, il serait possible que la suite de Syracuse n’atteigne jamais la valeur 1, pour une valeur de départ bien choisie, soit qu’elle aboutisse à un cycle différent du cycle trivial, soit qu’elle diverge vers l’infini. Or, on n’a jamais trouvé d’exemple de suite obtenue suivant les règles données qui n’aboutisse pas à 1.
Voici le calcul des termes de la suite pour n entier naturel non nul :

  1. def syracuse(n):
  2. suite=[]
  3. u=n
  4. while(u>1):
  5. if u%2:
  6. u=3*u+1
  7. else:
  8. u//=2
  9. suite.append(u)
  10. return suite

Télécharger

Utilisation :

  1. >>> syracuse(65)
  2. [196, 98, 49, 148, 74, 37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Télécharger

L’observation graphique de la suite pour N = 15 et pour N = 127 montre que la suite peut s’élever assez haut avant de retomber. Les graphiques sont chaotiques. De cette observation est né tout un vocabulaire imagé : on parlera du vol de la suite.
On définit alors :
- le temps de vol : c’est le plus petit indice n tel que $u_n = 1$. Il est de 17 pour la suite de Syracuse 15 et de 46 pour la suite de Syracuse 127 ;
- le temps de vol en altitude : c’est le plus petit indice n tel que $u_{n+1} ≤ u_0$. Il est de 10 pour la suite de Syracuse 15 et de 23 pour la suite de Syracuse 127 ;
- l’altitude maximale : c’est la valeur maximale de la suite. Elle est de 160 pour la suite de Syracuse 15 et de 4 372 pour la suite de Syracuse 127.
Le code suivant calcule ces différentes valeurs et graphe la suite en utilisant la librairie Matplotlib.

  1. import matplotlib.pyplot as plt
  2. suite = []
  3. def syracuse(n):
  4. u=n
  5. suite.append(u)
  6. while(u>1):
  7. if u%2:
  8. u=3*u+1
  9. else:
  10. u//=2
  11. suite.append(u)
  12. return suite
  13. def graphique(n):
  14. ax=plt.axes()
  15. syracuse(n)
  16. temps_vol_altitude=0
  17. alt_max=max(suite)
  18. len_suite=len(suite)
  19. for i in range(1,len_suite-1):
  20. if suite[i]>=suite[0]:
  21. temps_vol_altitude+=1
  22. else:
  23. break
  24. plt.plot(list(range(len_suite)),suite,'b.', linestyle='solid')
  25. plt.grid()
  26. plt.text(len_suite/3, alt_max, "Temps de vol : "+str(len_suite))
  27. plt.text(len_suite/3, alt_max*0.95, "Altitude maximum : "+str(alt_max))
  28. plt.text(len_suite/3, alt_max*0.9, "Temps de vol en altitude : "+str(temps_vol_altitude))
  29. plt.title("Suite de Syracuse pour n ="+str(n))
  30. ax = ax.set(xlabel='Temps de vol', ylabel='Altitude')
  31. plt.show()

Télécharger

Utilisation :

  1. >>> graphique(15)

Voici ce que l’on obtient :

PNG - 37.7 ko
Syracuse pour n=15

Essayez avec 2019 ...

Analyse

Écrire la liste des coefficients directeurs des sécantes pour un pas donné.

Pour une fonction $f$ continue sur un intervalle $[a ; b]$, on coupe l’intervalle en $n$ morceaux et on obtient $(n+1)$ points de la courbe avec $A_0 (a ; f(a))$ et $A_n (b ; f(b))$, on calcule les coefficients directeurs des droites $(A_i A_{i+1})$ pour i allant de 0 à $n - 1$ :

  1. def f(x):
  2. return x**2-2*x+7
  3. def coeffs_secantes(f,a,b,n):
  4. liste_coeffs=[]
  5. h=(b-a)/n
  6. for i in range(n):
  7. liste_coeffs.append(round((f(a+h*(i+1))-f(a+i*h))/h,2))
  8. return liste_coeffs

Télécharger

Utilisation :

  1. >>> coeffs_secantes(f,-5,5,25)
  2. [-11.6, -10.8, -10.0, -9.2, -8.4, -7.6, -6.8, -6.0, -5.2, -4.4, -3.6,
  3. -2.8, -2.0, -1.2, -0.4, 0.4, 1.2, 2.0, 2.8, 3.6, 4.4, 5.2, 6.0, 6.8, 7.6]

Télécharger

PNG - 292 ko
Courbe avec ses sécantes

Méthode de Newton, en se limitant à des cas favorables

Soit $f$ une fonction dérivable sur un intervalle $I$.
L’équation $f (x) = 0$ admet une racine unique $\alpha$ sur cet intervalle $I$.
Soit $a \in I$ une valeur approchée de $\alpha$.
On va utiliser l’approximation affine $g$ de $f$ au point $a$.
On aura donc $g(x) = f (a) + (x − a)f ′(a)$ (tangente $T_a$).
La droite $T_a$ coupe l’axe des abscisses en $b = a −\frac{f(a)}{f’(a)}$.
Sous certaines conditions, le nombre $b$ peut représenter une meilleure approximation de $\alpha$ que $a$.
La méthode de Newton consiste à itérer le processus en repartant de $b$ et ainsi de suite.
On proposera deux solutions :
- si l’on sait dériver la fonction $f$.
  1. def f(x):
  2. return 7/(3*x)-1
  3. def derivee_f(x):
  4. return -7/(3*x**2)
  5. def newton(f,x0,e):
  6. x = x0
  7. while abs(f(x))>e:
  8. d=derivee_f(x) #on calcule f'(x)
  9. x = x-f(x)/d
  10. return x

Télécharger


Utilisation :

  1. >>> newton(f,2,1e-6)
  2. 2.3333329285781073

Télécharger

PNG - 235.3 ko

- si l’on doit se contenter d’un calcul approché de ce nombre dérivé en prenant comme approximation $f’(a) \approx \frac{f(a + h) - f(a)}{h}$ avec h suffisamment petit.

  1. def f(x):
  2. return 7/(3*x)-1
  3. def newton(f,x0,e,h):
  4. x = x0
  5. while abs(f(x))>e:
  6. d = (f(x+h)-f(x))/h #on calcule une approximation du nombre dérivé en x
  7. x = x-f(x)/d
  8. return x

Télécharger

Utilisation :

  1. >>> newton(f,2,1e-6,1e-5)
  2. 2.333332932960443

Télécharger

Construction de l’exponentielle par la méthode d’Euler.

Soit $f$ une fonction dérivable sur $\mathbf{R}$ et vérifiant $f(0) = 1$ et pour tout $x \in \mathbf{R}, f’(x) = f(x)$.
La méthode d’Euler consiste à construire une suite de points $(x_n ; y_n)$ telle que $y_n$ soit proche de $f(x_n)$. Ainsi le nuage de points $(x_n ; y_n)$ formera une approximation de la courbe représentative de la fonction $f$.
La suite $(x_n)$ est une suite arithmétique de raison $h>0$ et de premier terme 0, $h$ est appelé le pas. On a donc $x_n = nh$ et $x_{n+1}=x_n + h$.
La suite $(y_n)$ est définie par $y_0 = f(x_0) = f(0) = 1$ et pour tout $n \in \mathbf{N}, y_{n+1}=y_n+hf’(x_n)$. C’est-à-dire que l’on se sert de l’approximation affine de la fonction par ses tangentes successives.
$(y_n)$ est géométrique de premier terme 1 et de raison 1 + h, en effet $y_{n+1}=y_n+hf(x_n)=y_n+hy_n= (1 + h)y_n$.
D’où le script suivant :

  1. import matplotlib.pyplot as plt
  2. def Euler(x_f,n) :
  3. x=0
  4. y=1
  5. h=x_f/n
  6. abscisse=[0]
  7. ordonnee=[1]
  8. for i in range(n) :
  9. y=(1+h)*y
  10. x=x+h
  11. abscisse.append(x)
  12. ordonnee.append(y)
  13. plt.plot(abscisse,ordonnee,"r")
  14. plt.show()

Télécharger

Utilisation, pour un nuage de n=100 points pour x allant de 0 à x_f=5 :

  1. >>> Euler(5,100)

Ce qui donne le graphique suivant :

Et si l’on veut comparer avec le "vrai" graphe de la fonction exponentielle :

  1. import matplotlib.pyplot as plt
  2. from math import exp
  3. def Euler(x_f,n) :
  4. x=0
  5. y=1
  6. h=x_f/n
  7. abscisse=[0]
  8. ordonnee=[1]
  9. expo=[1]
  10. for i in range(n) :
  11. y=(1+h)*y
  12. x=x+h
  13. abscisse.append(x)
  14. ordonnee.append(y)
  15. expo.append(exp(x))
  16. plt.plot(abscisse,ordonnee,"r")
  17. plt.plot(abscisse,expo,"b")
  18. plt.show()

Télécharger

Détermination d’une valeur approchée de e à l’aide de la suite ((1+1/n)^n).

La fonction $f$ définie sur $\mathbf{R}$ par $f(x) = e^x - x - 1$ est dérivable sur $\mathbf{R}$ et $f’(x) = e^x - 1$, donc $f$ est décroissante sur l’ensemble des nombres négatifs et croissante sur l’ensemble des nombres positifs, elle admet donc un minimum qui est $f(0) = 0$, ce qui implique que $e^x - x - 1 \geqslant 0$ donc $e^x \geq x + 1$.
On en déduit deux choses :
- Si n est un entier non nul, $e^{\frac 1 n} \geq \frac 1 n + 1$, donc $\left(e^{\frac 1 n} \right)^n\geq \left(\frac 1 n + 1\right)^n$, d’où $e \geq \left(\frac 1 n + 1\right)^n$.
- $e^{-x} \geq 1 - x$, c’est-à-dire $\frac{1}{e^{x}} \geq 1 - x$, donc si $x < 1, 0 < 1 - x$, la fonction inverse étant décroissante sur l’ensemble des nombres positifs on obtient ${e^{x}} \leq \frac{1}{1 - x}$.
On déduit alors de ce qui précède, puisque $n \geq 1$ alors $\frac 1 {n+1} \leq \frac 1 2< 1$ :
${e^{\frac 1{n+1}}} \leq \frac{1}{1 - \frac 1{n+1}}$, d’où ${e^{\frac 1{n+1}}} \leq \frac{1}{\frac {n + 1 - 1}{n+1}}$, donc ${e^{\frac 1{n+1}}} \leq{\frac {n + 1}{n}}$, c-à-d ${e^{\frac 1{n+1}}} \leq{1 + \frac {1}{n}}$, et enfin ${e} \leq \left({1 + \frac {1}{n}}\right)^{n+1}$.
On a ainsi démontré que pour tout entier $n \geq 1$ :
$\left(\frac 1 n + 1\right)^n \leq {e} \leq \left({1 + \frac {1}{n}}\right)^{n+1}$.
On obtient pour n = 5, 2,48<e<2,99, donc e<3.
De plus $ {e} \leq \left({1 + \frac {1}{n}}\right)^{n}\left({1 + \frac {1}{n}}\right)$, donc $ {e} \leq \left({1 + \frac {1}{n}}\right)^{n} +\frac{\left({1 + \frac {1}{n}}\right)^{n} }{n}\leq \left({1 + \frac {1}{n}}\right)^{n} +\frac{e}{n}\leq \left({1 + \frac {1}{n}}\right)^{n} +\frac{3}{n}$, finalement $e - \frac 3 n \leq \left({1 + \frac {1}{n}}\right)^{n} \leq e$.
On en déduit que $\displaystyle{\lim_{n \to +\infty} \left({1 + \frac {1}{n}}\right)^{n} =e}$.
On va pouvoir implémenter un algorithme qui calcule les termes de cette suite afin d’approximer e :

  1. def approx_e(n):
  2. return (1+1/n)**n

Télécharger

Il faut n=74 pour obtenir la première décimale exacte, n=164 pour la deuxième, n=4822 pour la troisième ... :

  1. >>> approx_e(74)
  2. 2.7001396788468326
  3. >>> approx_e(164)
  4. 2.710040437932739
  5. >>> approx_e(4822)
  6. 2.718000019542224

Télécharger

Si l’on revient à l’encadrement démontré précédemment : $\left(\frac 1 n + 1\right)^n \leq {e} \leq \left({1 + \frac {1}{n}}\right)^{n+1}$, l’on peut s’intéresser au rang à partir duquel cet encadrement devient d’amplitude inférieure à $10^{-n}$.

  1. def approx_e(n):
  2. x=1
  3. ecart=1
  4. while ecart>1/10**n:
  5. x_n=(1+1/x)**x
  6. x_f=(1+1/x)**(x+1)
  7. ecart=x_f-x_n
  8. x+=1
  9. return x,x_n,x_f

Télécharger

  1. >>> approx_e(2)
  2. (273, 2.713301767821834, 2.723277141968238)
  3. >>> approx_e(3)
  4. (2719, 2.717781945201135, 2.7187818649749396)
  5. >>> approx_e(4)
  6. (27184, 2.718231830478112, 2.7183318279703124)
  7. >>> approx_e(5)
  8. (271829, 2.7182768284461742, 2.7182868284345063)
  9. >>> approx_e(6)
  10. (2718283, 2.7182813290770236, 2.718282329076777)

Télécharger

On conjecture alors que ce rang est environ égal à $10^{n}e$, en effet $écart = \left({1 + \frac {1}{x}}\right)^{x+1}- \left(\frac 1 x + 1\right)^x $, d’où $écart = \left({1 + \frac {1}{x}}\right)^{x}\left({1 + \frac {1}{x}}\right)- \left(\frac 1 x + 1\right)^x = \frac 1 x \left({1 + \frac {1}{x}}\right)^{x}\approx \frac e x$ ainsi $ \frac {e}{x} \leq 10^{-n} $, d’où $10^{n}{e} \leq {x} $.

Approximation de π par la méthode d’Archimède

Pour approcher π, on peut s’intéresser aux périmètres des polygones réguliers à n côtés inscrits et circonscrits au cercle de diamètre 1 :

Le principe de l’algorithme d’Archimède est le suivant :
Soit $p_n$ le périmètre d’un polygone régulier de n côtés inscrit dans un cercle de rayon $\frac 1 2$. Archimède observe que : $\displaystyle{\lim_{n \to +\infty} p_n = \pi}$ et il évalue la limite au moyen de la suite $p_6, p_{12}, p_{24}, p_{48} ...$ obtenue par doublements successifs du nombre de côtés. Soit $u_n = \frac 1 n p_n$ la longueur du côté d’un n-gone.
L’hexagone inscrit a pour côté $\frac 1 2$ et pour périmètre 3.
Si l’on appelle $u_n$ la longueur du côté du polygone à n côtés et $u_{2n}$ la longueur du côté du polygone à 2n côtés, nous obtenons ceci :

PNG - 1021.7 ko

Le triangle ACG est rectangle en G, et la somme des angles dans le triangle ACF, isocèle en A, conduit à l’égalité suivante :
$\widehat{CAF} + 2\times\widehat{ACF} = \pi$, d’où $\widehat{CAF} + 2(\frac{\pi}{2} - \widehat{CAF} + \widehat{GCF}) = \pi$, et finalement $2\widehat{GCF} = \widehat{CAF}$.
Dans le triangle GCF rectangle en G, on a $\cos\widehat{GCF} = \frac{\frac{u_n}{2}}{u_{2 n}}$ et dans le triangle GCA rectangle en G, on a $\sin\widehat{GAC} = \frac{\frac{u_n}{2}}{\frac 1 2}$, d’où $\sin\widehat{CAG} = u_n$. De plus $\cos\widehat{GCF} = \cos{\frac{\widehat{CAF}}{2}} = \sqrt{\frac{1+\cos{\widehat{CAF}}}{2}} = \sqrt{\frac{1+\sqrt{1 - \sin^2{\widehat{CAF}}}}{2}} = \sqrt{\frac{1+\sqrt{1 - {u_n}^2}}{2}}$, donc $\frac{\frac{u_n}{2}}{u_{2 n}} = \sqrt{\frac{1+\sqrt{1 - {u_n}^2}}{2}}$, ainsi ${u_{2 n}} = \frac{\frac{u_n}{2}}{\sqrt{\frac{1+\sqrt{1 - {u_n}^2}}{2}}}$, finalement $u_{2 n} = \sqrt{\frac 1 2 \left(1-\sqrt{1 - {u_n}^2}\right)}$.
On peut maintenant passer à la programmation :

  1. from math import sqrt
  2. def archimede(n):
  3. nb_cotes=6
  4. u=0.5
  5. p=3
  6. for i in range(n):
  7. u=sqrt(0.5*(1-sqrt(1-u**2)))
  8. nb_cotes=6*2**(i+1)
  9. p=nb_cotes*u
  10. return nb_cotes,p

Télécharger

Utilisation : La fonction renvoie le nombre de côtés du polygone et son périmètre. Elle prend en paramètre la valeur de n pour obtenir le polygone $p_{6\times 2^n}$. Archimède avait fait le calcul pour $n = 4$, c’est-à-dire pour 96 côtés.

  1. >>> archimede(4)
  2. (96, 3.14103195089053)
  3. >>> archimede(5)
  4. (192, 3.1414524722853443)
  5. >>> archimede(11)
  6. (12288, 3.1415926186407894)
  7. >>> archimede(12)
  8. (24576, 3.1415926453212157)
  9. >>> archimede(13)
  10. (49152, 3.1415926453212157)
  11. >>> archimede(14)
  12. (98304, 3.1415926453212157)
  13. >>> archimede(15)
  14. (196608, 3.1415926453212157)
  15. >>> archimede(16)
  16. (393216, 3.141593669849427)

Télécharger

Le programme rencontre un problème pour n>=12, le résultat est le même (à l’affichage) et ne donne pas les bonnes décimales de pi, au-delà de 16 la suite diverge, puis deviens nulle ...

Géométrie
Il n’y a pas d’algorithme explicitement indiqué dans le programme pour cette partie. Aussi nous nous permettons de vous proposer celui-ci :

Le triangle de Sierpinski

Le triangle de Sierpiński est une fractale.
Il est défini de la manière suivante : on part d’un triangle équilatéral "plein" que l’on partage en quatre triangles équilatéraux et dont on enlève le triangle central. On recommence l’opération pour les triangles restants et ainsi de suite. Pour des raisons liées à la programmation, nous allons juste inverser le "plein" et le "vide", ce qui devient : on part d’un triangle équilatéral "vide" que l’on partage en quatre triangles équilatéraux et dont on colore le triangle central. On recommence l’opération pour les triangles vides restants et ainsi de suite.
Les figures ci-dessous donnent le rang 0 et les deux premières étapes :

PNG - 11.6 ko
Sierpinski0
PNG - 14.1 ko
Sierpinski1
PNG - 17.5 ko
Sierpinski2

Nous allons nous intéresser à la programmation de l’algorithme qui produit ces figures. Il nous faut donc tracer un triangle équilatéral, et pour cela, il va nous falloir le faire à partir des coordonnées de ces sommets afin de réitérer l’opération :

  1. import matplotlib.pyplot as plt
  2. def triangle(A,B,C):
  3. sommet1=A
  4. sommet2=B
  5. sommet3=C
  6. x=[sommet1[0],sommet2[0],sommet3[0],sommet1[0]]
  7. y=[sommet1[1],sommet2[1],sommet3[1],sommet1[1]]
  8. plt.plot(x,y,"r")

Télécharger

Ce programme trace les segments [AB], [BC] et [CA] donc le triangle ABC.
Pour avoir la même chose mais coloriée :

  1. def triangle_plein(A,B,C):
  2. sommet1=A
  3. sommet2=B
  4. sommet3=C
  5. x=[sommet1[0],sommet2[0],sommet3[0],sommet1[0]]
  6. y=[sommet1[1],sommet2[1],sommet3[1],sommet1[1]]
  7. plt.fill(x,y,"r")

Télécharger

Nous avons également besoin du calcul des coordonnées du milieu d’un segment afin d’itérer le processus :

  1. def milieu(A,B):
  2. return [(A[0]+B[0])/2,(A[1]+B[1])/2]

Télécharger

Dans la suite, nous allons appliquer une démarche récursive : on part de l’étape n (inconnue) et on la décrit en fonction de l’étape n - 1, qui elle-même est décrite en fonction de l’étape n - 2 et ainsi de suite jusqu’à arriver à l’étape 1 connue. On parvient au résultat voulu en écrivant un algorithme qui s’appelle lui-même.

  1. def triangle_serpienski(A,B,C,n):
  2. if (n>0 and n<9):
  3. E = milieu(A,B)
  4. F = milieu(B,C)
  5. G = milieu(C,A)
  6. triangle_plein(E,F,G)
  7. triangle_serpienski(A,E,G,n-1)
  8. triangle_serpienski(E,B,F,n-1)
  9. triangle_serpienski(G,F,C,n-1)
  10. elif(n>=9):
  11. return "Le nombre de calculs est trop important, vous devez donner 1<n<9"

Télécharger

On prend soin d’éviter que le programme ne se bloque en raison d’un trop grand nombre de calculs.
Enfin, on gère l’ensemble du programme, en évitant l’affichage des axes et des graduations, non nécessaires :

  1. def resultat(A,B,C,n):
  2. fig,ax = plt.subplots()
  3. triangle(A,B,C)
  4. triangle_serpienski(A,B,C,n)
  5. ax.spines['right'].set_visible(False)
  6. ax.spines['left'].set_visible(False)
  7. ax.spines['top'].set_visible(False)
  8. ax.spines['bottom'].set_visible(False)
  9. ax.xaxis.set_visible(False)
  10. ax.yaxis.set_visible(False)
  11. plt.show()

Télécharger

Après avoir calculé les coordonnées des sommets du triangle initial, par exemple $A\left(-\frac 1 2 ; 0\right)$,$B\left(0 ; \frac{\sqrt{3}}{2}\right)$ et $C\left(\frac 1 2 ; 0\right)$.
Utilisation :

  1. >>> from math import sqrt
  2. >>> resultat([-1/2,0],[0,sqrt(3)/2],[1/2,0],7)

Télécharger

PNG - 49.5 ko
Sierpinski7

On pourra compléter l’activité avec une feuille de calcul pour conjecturer le comportement des suites $(p_n)$ le périmètre de la surface colorée à l’étape n et $(a_n)$ l’aire de la surface colorée (ou blanche) à l’étape n.

OpenDocument Spreadsheet - 23.7 ko
Triangles de Sierpinski

Et démontrer tout cela mathématiquement.

Probabilités et statistiques

Méthode de Monte-Carlo : estimation de l’aire sous la parabole, estimation du nombre π.

Cette méthode est proche de l’expérience de l’aiguille de Buffon.
Soit un point M de coordonnées $(x, y)$, où $0 < x < 1$ et $0 < y < 1$. On tire aléatoirement les valeurs de x et y entre 0 et 1 suivant une loi uniforme. Le point M appartient au disque de centre (0,0) de rayon R=1 si et seulement si $x^2 + y^2 ≤1$. La probabilité que le point M appartienne au disque est $\frac \pi 4$, puisque le quart de disque est de surface $\sigma=\frac{\pi R^2} 4=\frac \pi 4$, et le carré qui le contient est de surface $S = R^2 = 1$ : si la loi de probabilité du tirage de point est uniforme, la probabilité de tomber dans le quart de disque vaut $\frac \sigma S = \frac \pi 4$.
En faisant le rapport du nombre de points dans le disque au nombre de tirages, on obtient une approximation du nombre $\frac \pi 4$ si le nombre de tirages est grand.

  1. import matplotlib.pyplot as plt
  2. from matplotlib import patches
  3. from random import *
  4. from math import sqrt
  5. from math import pi
  6. def distance(x,y):
  7. return sqrt(x**2+y**2)
  8. def monte_carlo(n):
  9. #dessin du cercle
  10. fig=plt.figure()
  11. ax=fig.add_subplot(1,1,1)
  12. centreCircle = plt.Circle((0,0),1,color="red",fill=False) #
  13. ax.add_patch(centreCircle)
  14. #dessin des points
  15. c=0
  16. for i in range(n):
  17. a,b = random(),random()
  18. if distance(a,b)<=1:
  19. c+=1
  20. plt.plot(a,b,"r.")
  21. else:
  22. plt.plot(a,b,"b.")
  23. plt.axis("equal")
  24. plt.axhline(color='g') #l'axe (Ox)
  25. plt.axvline(color='g') #et (Oy)
  26. plt.title("Métode de Monte Carlo")
  27. texte1="Nombre de points dans le cercle/Nombre de points = ",c/n
  28. plt.text(-1.1,-0.3,texte1)
  29. texte2="Valeur approchée de pi/4 = ",round(pi/4,5)
  30. plt.text(-1.1,-0.5,texte2)
  31. plt.grid()
  32. plt.show()
  33. return c/n

Télécharger

Utilisation :

  1. >>> monte_carlo(5000)
  2. 0.7804

Télécharger

PNG - 45 ko

Pour calculer l’aire sous la parabole de la fonction carré entre 0 et 1, on adapte le script précédent :

  1. import matplotlib.pyplot as plt
  2. from random import *
  3. def monte_carlo_parabole(n):
  4. #dessin de la parabole
  5. x,y=[],[]
  6. for i in range(51):
  7. x.append(i/50)
  8. y.append(i**2/2500)
  9. plt.plot(x,y,"r-")
  10. #dessin des points
  11. c=0
  12. for i in range(n):
  13. a,b = random(),random()
  14. if b<a**2:
  15. c+=1
  16. plt.plot(a,b,"r.")
  17. else:
  18. plt.plot(a,b,"b.")
  19. plt.axis("equal")
  20. plt.axhline(color='g') #l'axe (Ox)
  21. plt.axvline(color='g') #et (Oy)
  22. plt.title("Métode de Monte Carlo")
  23. texte1="Nombre de points sous la parabole/Nombre de points = ",c/n
  24. plt.text(-0.2,0.7,texte1)
  25. plt.grid()
  26. plt.show()
  27. return c/n

Télécharger

Utilisation :

  1. >>> monte_carlo_parabole(3000)
  2. 0.334

Télécharger

PNG - 76.7 ko

Algorithme renvoyant l’espérance, la variance ou l‘écart type d’une variable aléatoire.

Illustrons cela à l’aide d’un jeu.
On lance un dé à 6 faces non truqué :
- Si c’est 1 qui sort, on gagne 1€.
- Si c’est 2, 3 ou 4 qui sort, on gagne 2€.
- Sinon, on gagne 4€.
On appelle X la variable aléatoire qui enregistre la somme gagnée.
X prend donc les valeurs 1, 2 ou 4 avec comme probabilité 1/6, 0.5 et 1/3.
L’algoritme suivant permet le calcul de l’espérance, la variance ou l‘écart type de cette variable aléatoire :

  1. from math import sqrt
  2. X=[1,2,4]
  3. p=[1/6,0.5,1/3]
  4. def esperance(valeurs,probabilites):
  5. E_X=0
  6. for i in range(len(valeurs)):
  7. E_X += probabilites[i]*valeurs[i]
  8. return E_X
  9. def variance(valeurs,probabilites):
  10. varX = 0
  11. E_X=esperance(valeurs,probabilites)
  12. for i in range(len(valeurs)):
  13. varX += probabilites[i]*(valeurs[i]-E_X)**2
  14. return varX
  15. def ecarttype(valeurs,probabilites):
  16. return sqrt(variance(valeurs,probabilites))

Télécharger

Utilisation :

  1. >>> esperance(X,p)
  2. 2.5
  3. >>> variance(X,p)
  4. 1.25
  5. >>> ecarttype(X,p)
  6. 1.118033988749895
  7. >>>

Télécharger

On peut alors rajouter une fonction qui simule le jeu de dé avec la loi de probabilité associée :

  1. def simulation(valeurs,probabilites):
  2. nb=random()
  3. pcumulee=0
  4. for i in range(len(valeurs)):
  5. if pcumulee<= nb < probabilites[i]+pcumulee:
  6. return valeurs[i]
  7. pcumulee+=probabilites[i]

Télécharger

Utilisation :

  1. >>> simulation(X,p)
  2. 2
  3. >>> simulation(X,p)
  4. 4
  5. >>> simulation(X,p)
  6. 1

Télécharger

Puis réaliser l’expérience à plusieurs reprises et obtenir un échantillon de taille n de ce jeu :

  1. def echantillon(valeurs,probabilites,taille):
  2. listeX=[]
  3. for i in range(taille):
  4. listeX.append(simulation(valeurs,probabilites))
  5. return listeX

Télécharger

Utilisation :

  1. >>> echantillon(X,p,20)
  2. [4, 2, 4, 2, 4, 4, 4, 2, 2, 2, 2, 2, 1, 2, 2, 1, 4, 1, 2, 2]

Télécharger

On peut alors comparer les fréquences obtenues à partir de l’échantillon aux probabilités :

  1. def frequences(valeurs,probabilites,taille):
  2. test=echantillon(valeurs,probabilites,taille)
  3. n=len(test)
  4. F=[]
  5. for x in valeurs:
  6. F.append(test.count(x)/n)
  7. return F,probabilites

Télécharger

Utilisation :

  1. >>> frequences(X,p,500)
  2. ([0.16, 0.526, 0.314], [0.16666666666666666, 0.5, 0.3333333333333333])

Télécharger

On pourra enfin écrire une fonction qui va simuler N échantillons de taille n de la variable aléatoire X, d’espérance E(X) et d’écart type $\sigma(X)$, qui renverra la proportion des cas où l’écart entre m, la moyenne de cet échantillon et E(X) est inférieur ou égal à $\frac{2\sigma(X)}{\sqrt n}$

  1. def moyenne(liste):
  2. return sum(liste)/len(liste)
  3. def proportion(valeurs,probabilites,taille,nbechantillons):
  4. m=0
  5. E_X=esperance(valeurs,probabilites)
  6. S_X=ecarttype(valeurs,probabilites)
  7. for i in range(nbechantillons):
  8. test=echantillon(valeurs,probabilites,taille)
  9. if abs(E_X-moyenne(test))<=2*S_X/sqrt(taille):
  10. m+=1
  11. return m/nbechantillons

Télécharger

Utilisation :

  1. >>> proportion(X,p,100,200)
  2. 0.955

Télécharger

Fréquence d’apparition des lettres d’un texte donné, en français, en anglais.

S’intéresser à la fréquence d’apparition des lettres dans un texte sert principalement à déchiffrer un texte codé par substitution. Cette technique n’est plus utilisée car elle ne résiste pas à l’analyse fréquentielle et à la puissance des ordinateurs. On arrive, après analyse fréquentielle et différents tests à retrouver le texte initial. Plusieurs options, pour le chiffrement comme pour le décodage, sont possibles :
- prise en compte ou pas de la ponctuation ;
- remplacement ou suppression des caractères accentués ; [1]
- prise en compte des chiffres ;
- remplacement ou suppression des ç, €, %, &, (),[], œ, ...
Le type de document analysé a aussi son importance, si c’est un texte technique, un roman, un texte narratif. Sa longueur est également un critère important, plus il est long, plus il est théoriquement sensé donner des fréquences correspondant au modèle, nous utiliserons le résultat suivant, pour un texte en langue française :
e:14,2% ; a:8,3% ; i:7,7% ; s:7,6% ; n:7,5% ; r:7,1% ; t:6,9% ; o:5,9% ; l:5,8% ; u:5,3% ; d:4,3% ; c:3,7% ; m:3,1% ; p:2,9% ; g:1,4% ; b:1,3% ; v:1,3% ; h:1,3% ; f:1,3% ; q:0,8% ; y:0,5% ; x:0,4% ; j:0,4% ; k:0,3% ; w:0,2% ; z:0,2%.
Nous nous intéresserons donc à des textes codés uniquement avec des lettres minuscules.
Soit le texte codé suivant :

Tous les caractères autres que ceux de l’alphabet classique ont été enlevés et les majuscules ont été remplacées par des minuscules à l’aide des deux fonctions suivantes :

  1. # encoding: utf-8
  2. import unicodedata
  3. #Ce module donne accès à la base de données des caractères Unicode
  4. #ce qui permet de convertir les caractères accentués
  5. def nettoyage(texte):
  6. if ".txt" in texte:
  7. fichier=open(texte,'r')
  8. texte=fichier.read()
  9. fichier.close()
  10. texte = unicodedata.normalize('NFKD', texte).encode('ascii','ignore').decode()
  11. alphabet="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
  12. nbcar=len(texte)
  13. texteformate=""
  14. for k in range(nbcar):
  15. j=0
  16. trouve=0
  17. while (j<len(alphabet)) and (trouve==0):
  18. if texte[k]==alphabet[j]:
  19. trouve=1
  20. if trouve==0:
  21. j+=1
  22. if trouve==1:
  23. texteformate+=texte[k]
  24. return(texteformate)
  25. def minuscules(texte):
  26. nbcar=len(texte)
  27. texteformate=""
  28. for k in range(nbcar):
  29. if ord(texte[k])<97:
  30. texteformate+=chr(ord(texte[k])+32)
  31. else:
  32. texteformate+=texte[k]
  33. return(texteformate)

Télécharger

Utilisation :

  1. >>> minuscules(nettoyage("Fréquence d’apparition des lettres d’un texte donné"))
  2. 'frequencedapparitiondeslettresduntextedonne'

Télécharger

Pour illustrer notre propos, nous avons utilisé un texte plus long, enregistré dans un fichier texte nommé "texte_analyse.txt" avec le code suivant :

  1. >>> minuscules(nettoyage("texte_analyse.txt"))

Le texte a ensuite été transformé (le résultat est dans le cadre ci-dessus) à l’aide d’un chiffrement affine qui peut ne pas être expliqué aux élèves, selon le script suivant :

  1. def codage_affine(texte,m,p):
  2. textecode=""
  3. nbcar=len(texte)
  4. for k in range(nbcar):
  5. u=ord(texte[k])-97
  6. v=m*u+p
  7. w=v%26
  8. t=chr(97+w)
  9. textecode+=t
  10. return(textecode)

Télécharger

Le code ci-dessus transforme le code ascii de chaque lettre en un nombre compris entre 0 et 25, ce nombre est transformé par la fonction affine $f(x) = mx + p$, puis ramené à un nombre compris entre 0 et 25, transformé en code ascii d’une lettre minuscule en ajoutant 97. Ce codage affine ne fonctionne pas si m et 26 ne sont pas premiers entre eux car plusieurs lettres sont alors codées par la même lettre. Si $m=1$, on retrouve le chiffrement de César qui consiste en un simple décalage des lettres (a -> e, b ->f, c ->g, ...).
Cette fonction sert aussi de fonction de décodage, en effet si $y \equiv mx + p [26]$ alors $y - p \equiv mx [26]$ et $x \equiv m^{-1}y - m^{-1}p [26]$ où $m^{-1}$ est tel que $mm^{-1} \equiv 1 [26]$, c’est-à-dire que $m^{-1}$ est l’inverse modulaire de $m$ modulo 26 (Par exemple : 9 est l’inverse modulaire de 3 car $9\times 3 = 27 \equiv 1 [26]$). On peut alors décoder le texte avec codage_affine(texte,$m^{-1},- m^{-1}p$).
Procédons maintenant au décryptage du texte codé, commençons par l’analyse fréquentielle d’apparition des lettres dans ce texte, à l’aide du script suivant :

  1. def analyse_frequence_lettre(texte,lettre):
  2. nbcar=len(texte)
  3. compteur=0.0
  4. for k in range(nbcar):
  5. if texte[k]==lettre:
  6. compteur+=1
  7. freq=round(compteur/nbcar,3)
  8. return(freq)
  9. def analyse_frequence_alphabet(texte):
  10. alphabet="abcdefghijklmnopqrstuvwxyz"
  11. frequences=[]
  12. for lettre in alphabet:
  13. frequences.append([lettre,analyse_frequence_lettre(texte,lettre)])
  14. return(frequences)

Télécharger

Utilisation :

  1. >>> analyse_frequence_alphabet("slylsfnxakxhtxyqjxssxbtlylsfnxuxakxhtxyrxnxnq...")
  2. [['a', 0.023], ['b', 0.04], ['c', 0.008], ['d', 0.009], ['e', 0.032], ['f', 0.012], ['g', 0.012],
  3. ['h', 0.017], ['i', 0.0], ['j', 0.064], ['k', 0.062], ['l', 0.069], ['m', 0.0], ['n', 0.082],
  4. ['o', 0.008], ['p', 0.001], ['q', 0.081], ['r', 0.035], ['s', 0.065], ['t', 0.053], ['u', 0.033],
  5. ['v', 0.024], ['w', 0.006], ['x', 0.202], ['y', 0.063], ['z', 0.001]]

Télécharger

Au vu des résultats ci-dessus, on conjecture que c’est la lettre "x" qui code la lettre "e", on procède alors au changement de la lettre "x" par la lettre "e" dans le texte codé, sauf que si on fait cela on ne va plus distinguer le "e" codé du "e" décodé, on va donc procéder au changement de la lettre "x" par la lettre "E" dans le texte codé afin de faire la distinction. Ceci à l’aide du code suivant :

  1. def change_lettre(texte,lettre1,lettre2):
  2. texte=texte.replace(lettre1,lettre2)
  3. return(texte)

Télécharger

Ce qui donne comme résultat :

  1. >>> change_lettre("slylsfnxakxhtxyqjxssxbtlylsfnxuxakxhtxyrxnxnq...","x","E")
  2. 'slylsfnEakEhtEyqjEssEbtlylsfnEuEakEhtEyrEnEnqtyEvEqgbuEuErkfeqlyl...'

Télécharger

Rien dans le résultat ne nous permet de dire si cette conjecture est vraie ou fausse, continuons en gardant cette permutation.
On conjecture alors que c’est la lettre "n" qui code la lettre "a", on procède au changement de lettre dans le texte et on obtient :

  1. >>> change_lettre("slylsfnEakhtEyqjEssEbtlylsfnEuEakhtEyrEnEnqtyEvqg...","n","A")
  2. 'slylsfAEakhtEyqjEssEbtlylsfAEuEakhtEyrEAEAqtyEvqgb...'

Télécharger

La suite de lettre "EAEA" nous laisse à penser que ce n’est pas la bonne solution.
On conjecture alors que c’est la lettre "q" qui code la lettre "a", on procède au changement de lettre dans le texte et on obtient :

  1. >>> change_lettre("slylsfnEakhtEyqjEssEbtlylsfnEuEakhtEyrEnEnqtyEvqg...","q","A")
  2. 'slylsfnEakEhtEyAjE...nulyntyvEnnldErgjaakErEAAEvEAgbu...'

Télécharger

La suite de lettre "EAAE" nous laisse à penser que ce n’est pas la bonne solution.
On conjecture alors que c’est la lettre "l" qui code la lettre "a", on procède au changement de lettre dans le texte et on obtient :

  1. >>> change_lettre("slylsfnEakhtEyqjEssEbtlylsfnEuEakhtEyrEnEnqtyEvqg...","l","A")
  2. 'sAyAsfnEakEhtEyqjEssEbtAyAsfnEuEakEhtEyrEnEnqtyEvEqgbuEuErkfeqA...'

Télécharger

Rien dans le résultat ne nous permet de dire si cette conjecture est vraie ou fausse, continuons en gardant cette permutation.
Et ainsi de suite, jusqu’au résultat final :

  1. >>> change_lettre("LANALYSEFREhUENTIELLEOUANALYSEDEFREhUENCE...","h","Q")
  2. "LANALYSEFREQUENTIELLEOUANALYSEDEFREQUENCESESTUNEMETHODEDE ..."

Télécharger

En rajoutant "à la main" les espaces et la ponctuation :
"L’ANALYSE FRÉQUENTIELLE OU ANALYSE DE FRÉQUENCES EST UNE METHODE DE ..."

Texte - 1.3 ko
Le fichier qui contient le texte initial en français.

Pour un texte en Anglais :
la procédure est exactement la même avec le tableau des fréquences d’apparition des lettres en Anglais :

A B C D E F G H I J K L M
8,08% 1,67% 3,18% 3,99% 12,56% 2,17% 1,80% 5,27% 7,24% 0,14% 0,63% 4,04 % 2,60%
N O P Q R S T U V W X Y Z
7,38% 7,47% 1,91% 0,09% 6,42% 6,59% 9,15% 2,79% 1,00% 1,89% 0,21% 1,65% 0,07%

Donc les lettres les plus fréquentes arrivent dans cet ordre : ETAONISRH ...
Soit le texte suivant à décoder :

On obtient alors :

  1. >>> analyse_frequence_alphabet('gafesxgdtxqhzgxmadjcfghzeshqrfadjcfgxmyf...')
  2. [['a', 0.064], ['b', 0.014], ['c', 0.04], ['d', 0.085], ['e', 0.017], ['f', 0.114], ['g', 0.093],
  3. ['h', 0.072], ['i', 0.002], ['j', 0.027], ['k', 0.01], ['l', 0.001], ['m', 0.023], ['n', 0.024],
  4. ['o', 0.001], ['p', 0.011], ['q', 0.078], ['r', 0.025], ['s', 0.073], ['t', 0.028], ['u', 0.009],
  5. ['v', 0.009], ['w', 0.0], ['x', 0.072], ['y', 0.036], ['z', 0.075]]

Télécharger

On procède alors au changement de lettres "f" -> "E", "g" -> "T" et "d" -> "A" qui ne montrent pas d’incohérences. En suivant l’ordre logique, le changement suivant est "q" -> "O" et, en cherchant des incohérences, je constate que si on remplace "a" par "H", on voit apparaitre de nombreux "THE" et "THAT", ce qui semble être une bonne chose, le texte "TAOAO" m’incite à procéder au changement "q" -> "N". Le texte présente de nombreux "zz" voire "zzz" ce qui conduit à procéder au changement "z" -> "S" puis "h" -> "I", "x" -> "O" et "s" -> "R". On a alors placé toutes les lettres aux fréquences les plus importantes. On intuite ensuite les changements "e" -> "P", "t" -> "G", "j" -> "M", "c" -> "L", "y" -> "D", "p" -> "Y", "v" -> "K", "b" -> "W", "n" -> "U", "l" -> "Q", "o" -> "J", "i" -> "X" en complétant des mots partiellement découverts.

Texte - 2.3 ko
Le fichier qui contient le texte initial en anglais.

Algorithmique et programmation

Histoire des mathématiques

De nombreux textes témoignent d’une préoccupation algorithmique au long de l’Histoire. Lorsqu’un texte historique a une visée algorithmique, transformer les méthodes qu’il présente en un algorithme, voire en un programme, ou inversement, est l’occasion de travailler des changements de registre qui donnent du sens au formalisme mathématique.
Vous consulterez l’article à venir d’Alain Busser à ce sujet.

Notion de liste

La génération des listes en compréhension et en extension est mise en lien avec la notion d’ensemble. Les conditions apparaissant dans les listes définies en compréhension permettent de travailler la logique.Afin d’éviter des confusions,on se limite aux listes sans présenter d’autres types de collections.
Capacités attendues :
- Générer une liste (en extension, par ajouts successifs ou en compréhension).
- Manipuler des éléments d’une liste (ajouter, supprimer...) et leurs indices.
- Parcourir une liste.
- Itérer sur les éléments d’une liste.

Une liste est une séquence modifiable. Un élément d’une liste peut être de n’importe quel type.

  1. >>> L=[6,1,69]
  2. >>> type(L)
  3. <class 'list'>
  4. >>> L[2]=1969
  5. >>> L
  6. [6, 1, 1969]
  7. >>> liste=[L,7,11,67,"Marie",18.2]
  8. >>> liste
  9. [[6, 1, 1969], 7, 11, 67, 'Marie', 18.2]
  10. >>> [a,b]=[0,1]
  11. >>> a
  12. 0
  13. >>> [a,b]
  14. [0, 1]

Télécharger

La liste vide :

  1. >>> L = []
  2. >>> L
  3. []

Télécharger

Longueur d’une liste : fonction len

  1. >>> a = [0,1,2,3]
  2. >>> len(a)
  3. 4

Télécharger

Le type list est itérable
On peut itérer une liste :

  1. >>> for k in [1,2,3]:
  2. print(k,end=" ")
  3. 1 2 3

Télécharger

Les listes supportent les tests x in list et x not in list.

  1. >>> solide_platon=["Tétraèdre","Hexaèdre","Octaèdre","Dodécaèdre","Icosaèdre"]
  2. >>> "polyèdre" in solide_platon
  3. False

Télécharger

Concaténation et multiplication
On concatène avec + :

  1. >>> a=[1,2,3]
  2. >>> b=a+[4,5]
  3. >>> b
  4. [1, 2, 3, 4, 5]
  5. >>> [0,1,2]+["Marie","Mylène"]+[67,72]
  6. [0, 1, 2, 'Marie', 'Mylène', 67, 72]

Télécharger

On peut utiliser la concaténation pour insérer un terme à la fin de la liste, mais on préfèrera utiliser la méthode append :

  1. >>> L = ["Benjamin","Alain"]
  2. >>> L.append("Yves")
  3. >>> L
  4. ['Benjamin', 'Alain', 'Yves']

Télécharger

On multiplie avec * :

  1. >>> [1,2,3]*3
  2. [1, 2, 3, 1, 2, 3, 1, 2, 3]
  3. >>> [1,2]*3
  4. [1, 2, 1, 2, 1, 2]
  5. >>> 2*["Pile","Face"]
  6. ['Pile', 'Face', 'Pile', 'Face']

Télécharger

Convertir avec la fonction list
On peut convertir n’importe quel itérable en liste :

  1. >>> list("abcdef")
  2. ['a', 'b', 'c', 'd', 'e', 'f']
  3. >>> list(b"abcdef")
  4. [97, 98, 99, 100, 101, 102]
  5. >>> list((0,1,2,3,4,5))
  6. [0, 1, 2, 3, 4, 5]
  7. >>> list(range(10))
  8. [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  9. >>> list(range(5,9))
  10. [5, 6, 7, 8]

Télécharger

Indexing et slicing
Les listes sont des séquences, elles sont donc indexables (les items sont repérés par un indice) et sliceables (on peut en extraire des tranches grâce à des plages d’indices). Comme d’habitude, l’indice du premier item est zéro :

  1. >>> a=[42, 43, 45, 47]
  2. >>> a[2]
  3. 45
  4. >>> a[2]=12
  5. >>> a
  6. [42, 43, 12, 47]

Télécharger

Indices négatifs : Python numérote le dernier item avec -1, l’avant-dernier avec -2, et ainsi de suite :

  1. >>> a=[42, 43, 45, 47]
  2. >>> a[-1]
  3. 47
  4. >>> a[-2]
  5. 45

Télécharger

Si on est obligé d’initialiser les termes dans le désordre, on commencera par créer une liste triviale.
Supposons par exemple qu’on veuille L de longueur 10, on écrira :

  1. >>> L=[None]*10
  2. >>> L[5]=12
  3. >>> L
  4. [None, None, None, None, None, 12, None, None, None, None]

Télécharger

sans déclencher d’erreur.
Un peu de slicing :

  1. >>> a=[0,1,2,3,4,5,6,7,8,9]
  2. >>> a[3:7]
  3. [3, 4, 5, 6]
  4. >>> a[3:3]
  5. []
  6. >>> a[5:]
  7. [5, 6, 7, 8, 9]
  8. >>> a[:5]
  9. [0, 1, 2, 3, 4]
  10. >>> a[-3:-1]
  11. [7, 8]
  12. >>> a[-5:]
  13. [5, 6, 7, 8, 9]
  14. >>> a[:]
  15. [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Télécharger

On peut faire du slicing avec un pas (positif ou négatif) :

  1. >>> a[2:20:3]
  2. [2, 5, 8]
  3. >>> a[::-1]
  4. [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
  5. >>> a[20:2:-2]
  6. [9, 7, 5, 3]

Télécharger

Remplacer une tranche par une autre
Dans une liste, on peut remplacer une tranche par une autre (il s’agit d’une mutation) :

  1. >>> L=list(range(15))
  2. >>> L[2:5]=5*[0]
  3. >>> L
  4. [0, 1, 0, 0, 0, 0, 0, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

Télécharger

On peut utiliser ce procédé pour changer un terme :

  1. >>> L=list(range(15))
  2. >>> L[3:4]=[7]
  3. >>> L
  4. [0, 1, 2, 7, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

Télécharger

On peut utiliser cette méthode pour supprimer une tranche :

  1. >>> L[2:5]=[]
  2. >>> L
  3. [0, 1, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

Télécharger

On peut utiliser ce procédé pour supprimer un terme d’indice connu :

  1. >>> L[3:4]=[]
  2. >>> L
  3. [0, 1, 5, 7, 8, 9, 10, 11, 12, 13, 14]

Télécharger

On peut utiliser ce procédé pour insérer un élément où on veut :

  1. >>> L[5:5]=[25]
  2. >>> L
  3. [0, 1, 5, 7, 8, 25, 9, 10, 11, 12, 13, 14]

Télécharger

On peut insérer une tranche :

  1. >>> L[5:5]=[1,1,1,1,1]
  2. >>> L
  3. [0, 1, 5, 7, 8, 1, 1, 1, 1, 1, 25, 9, 10, 11, 12, 13, 14]

Télécharger

Compréhension
En mathématiques (théorie des ensembles), l’axiome de compréhension est fondamental :
Axiome : Si E est un ensemble et P une propriété exprimée dans le langage de la théorie des ensembles, alors $\left\{x \in E | P\right\}$ est un ensemble.
Il est très courant en mathématiques de définir des ensembles en compréhension. L’ensemble des nombres pairs, par exemple est l’ensemble $\left\{n \in \mathbb{Z} | n\equiv 0 [2] \right\}$.
On peut avec Python définir des listes en compréhension (on dit aussi en intension avec un s) :

  1. >>> X=[1,5,7,12]
  2. >>> Y=[x**2 for x in X]
  3. >>> Y
  4. [1, 25, 49, 144]

Télécharger

Y est la liste des carrés des nombres appartenant à X. On peut même ajouter une condition :

  1. >>> Y=[x**2 for x in X if x**2<30]
  2. >>> Y
  3. [1, 25]
  4. >>> Y=[x**2 for x in X if x<10]
  5. >>> Y
  6. [1, 25, 49]

Télécharger

On peut redéfinir X à partir de X directement :

  1. >>> X=[1,5,7,12]
  2. >>> X=[x**2 for x in X]
  3. >>> X
  4. [1, 25, 49, 144]

Télécharger

On peut imbriquer des listes en compréhension :

  1. >>> L = [[k for k in range(m)] for m in range(6)]
  2. >>> L
  3. [[], [0], [0, 1], [0, 1, 2], [0, 1, 2, 3], [0, 1, 2, 3, 4]]

Télécharger

Fusionner
Soit L une liste de listes. On peut récupérer les items des listes de L en une seule instruction :

  1. >>> L = [[k for k in range(m)] for m in range(1,6)]
  2. >>> L
  3. [[0], [0, 1], [0, 1, 2], [0, 1, 2, 3], [0, 1, 2, 3, 4]]
  4. >>> fusion=[x for SL in L for x in SL]
  5. >>> fusion
  6. [0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4]

Télécharger

On peut utiliser cette technique pour effectuer des produits de listes :

  1. >>> valeur = [1,7,8,9,10,"Valet","Dame","Roi"]
  2. >>> couleur = ["Coeur","Carreau","Pique","Trèfle"]
  3. >>> jeu = [(n,c) for n in valeur for c in couleur]
  4. >>> jeu
  5. [(1, 'Coeur'), (1, 'Carreau'), (1, 'Pique'), (1, 'Trèfle'), (7, 'Coeur'), (7, 'Carreau'), (7, 'Pique'),
  6. (7, 'Trèfle'), (8, 'Coeur'), (8, 'Carreau'), (8, 'Pique'), (8, 'Trèfle'), (9, 'Coeur'), (9, 'Carreau'),
  7. (9, 'Pique'), (9, 'Trèfle'), (10, 'Coeur'), (10, 'Carreau'), (10, 'Pique'), (10, 'Trèfle'), ('Valet',
  8. 'Coeur'), ('Valet', 'Carreau'), ('Valet', 'Pique'), ('Valet', 'Trèfle'), ('Dame', 'Coeur'),
  9. ('Dame', 'Carreau'), ('Dame', 'Pique'), ('Dame', 'Trèfle'), ('Roi', 'Coeur'), ('Roi', 'Carreau'),
  10. ('Roi', 'Pique'), ('Roi', 'Trèfle')]
  11. >>> (10,"Trèfle") in jeu
  12. True

Télécharger

Trier avec sort ou sorted (arguments reverse, key)
La fonction sorted et la méthode sort font la même chose : elles trient les items dans l’ordre croissant (par défaut). La fonction sorted prend n’importe quel itérable et retourne les items dans l’ordre, sous forme de liste :

  1. >>> L=[7,12,3,2]
  2. >>> sorted(L)
  3. [2, 3, 7, 12]
  4. >>> L
  5. [7, 12, 3, 2]

Télécharger

La méthode sort s’applique à une liste et modi-e cette liste :

  1. >>> L.sort()
  2. >>> L
  3. [2, 3, 7, 12]

Télécharger

Les deux, sort et sorted, acceptent les arguments reverse et key. L’argument reverse permet de trier dans l’ordre décroissant :

  1. >>> sorted([7,12,3,2],reverse=True)
  2. [12, 7, 3, 2]

Télécharger

L’argument key permet de choisir la fonction avec laquelle on fera le tri. Si on veut trier selon la valeur absolue, on fera :

  1. >>> sorted([-13,15,-2,6,-6],key=abs)
  2. [-2, 6, -6, -13, 15]

Télécharger

Très pratique avec des données complexes :

  1. >>> def f(t):
  2. return t[1]
  3. >>> L=[["Marie",21],["Mylène",17],["Fred",24],["Denis",23]]
  4. >>> sorted(L,key=f)
  5. [['Mylène', 17], ['Marie', 21], ['Denis', 23], ['Fred', 24]]

Télécharger

Instruction del (mot réservé)
Pour effacer un item selon son rang, ou une plage d’items :

  1. >>> L=[7,12,3,2]
  2. >>> del L[2]
  3. >>> L
  4. [7, 12, 2]

Télécharger

Une autre syntaxe :

  1. >>> del(L[2])

On peut utiliser del sur une plage d’indices :

  1. >>> L=list(range(11))
  2. >>> del L[2:5]
  3. >>> L
  4. [0, 1, 5, 6, 7, 8, 9, 10]
  5. >>> L=list(range(21))
  6. >>> L
  7. [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
  8. >>> del L[::3]
  9. >>> L
  10. [1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20]

Télécharger

Méthode index
Pour trouver l’indice d’un terme :

  1. >>> L=[0, 1, 6, 7, 8, 9, 10, 11, 12, 5, 6, 7, 8, 9, 10]
  2. >>> L.index(6)
  3. 2

Télécharger

C’est l’index de la première ocurrence du terme qui est renvoyé, si l’on veut l’index de la seconde ocurrence, on peut démarrer la recherche plus loin :

  1. >>> L.index(6,3)
  2. 10

Télécharger

Méthode count
Pour compter les occurrences d’un item :

  1. >>> L = [1,2,1,1,1,1,2,1,2]
  2. >>> L.count(2)
  3. 3
  4. >>> L.count(3)
  5. 0

Télécharger

Méthode remove
Pour supprimer une occurrence (ne supprime que la première occurrence) :

  1. >>> L = [1,10,56,23,897,56,1000]
  2. >>> L.remove(56)
  3. >>> L
  4. [1, 10, 23, 897, 56, 1000]
  5. >>> L.remove(100000)
  6. Traceback (most recent call last):
  7. File "<pyshell#165>", line 1, in <module>
  8. L.remove(100000)
  9. ValueError: list.remove(x): x not in list

Télécharger

Méthode append
Pour insérer un terme à la fin :

  1. >>> L = [1,10,56,23,897,56,1000]
  2. >>> L.append(1945)
  3. >>> L
  4. [1, 10, 56, 23, 897, 56, 1000, 1945]

Télécharger

Méthode insert
Pour insérer un terme où on veut :

  1. >>> L.insert(3,666)
  2. >>> L
  3. [1, 10, 56, 666, 23, 897, 56, 1000, 1945]

Télécharger

Méthode extend
Pour étendre une liste par concaténation :

  1. >>> LL=[456,567]
  2. >>> L.extend(LL)
  3. >>> L
  4. [1, 10, 56, 666, 23, 897, 56, 1000, 1945, 456, 567]

Télécharger

Méthode pop
Supprime le dernier terme et le retourne :

  1. >>> L.pop()
  2. 567
  3. >>> L
  4. [1, 10, 56, 666, 23, 897, 56, 1000, 1945, 456]

Télécharger

Fonction max
Retourne le plus grand élément :

  1. >>> max(L)
  2. 1945

Télécharger

Fonction min
Retourne le plus petit élément :

  1. >>> min(L)
  2. 1

Télécharger

Méthode copy
Pour copier une liste dans une autre :

  1. >>> LL=L.copy()
  2. >>> LL
  3. [1, 10, 56, 666, 23, 897, 56, 1000, 1945, 456]
  4. >>> LL==L
  5. True
  6. >>> LL is L
  7. False

Télécharger

Méthode clear
Pour effacer le contenu d’une liste :

  1. >>> L.clear()
  2. >>> L
  3. []

Télécharger

Bibliographie


notes

[1Merci à Vincent-Xavier JUMEL qui m’a alerté sur la possibilité de transformer les caractères accentués en caractères non accentués grace au module unicodedata.

Réagir à cet article
Vous souhaitez compléter cet article pour un numéro futur, réagir à son contenu, demander des précisions à l'auteur ou au comité de rédaction...
À lire aussi ici
MathémaTICE est un projet
en collaboration avec
Suivre la vie du site Flux RSS 2.0  |  Espace de rédaction  |  Nous contacter  |  Site réalisé avec: SPIP  |  N° ISSN 2109-9197