\chapter{Python en classe de Terminale}
\enlargethispage*{4em}

\newpage
\pagestyle{main}
\section*{Extrait du programme}

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.

\textit{Capacités attendues:}
\begin{itemize}
\item Générer une liste (en extension, par ajouts successifs ou en compréhension).
\item Manipuler des éléments d'une liste (ajouter, supprimer,...) et leurs indices.
\item Parcourir une liste.
\item Itérer sur les éléments d'une liste.
\end{itemize}

\bigskip


\begin{attention}
Certains aspects qui interviennent en classe de Seconde et de Première ne seront pas systématiquement repris dans ce chapitre.

Il est donc conseillé de regarder les chapitres précédents avant d'aborder celui-ci.
\end{attention}

\newpage

\section{Factorielle}
\index{Factorielle}

La notion de \textit{factorielle} apparaît dans les dénombrements.

\begin{defin}
On définit la \textit{factorielle} d'un entier $n$ par le produit:
\[
n!=1\times2\times3\times4\times5\times\cdots\times(n-2)\times(n-1)\times n.
\]
\end{defin}

\begin{exemple}
\begin{itemize}
\item $3! = 1\times2\times3 = 6$.
\item $5! = 1\times2\times3\times4\times5=120$.
\end{itemize}
\end{exemple}

Vous avez sans doute remarqué que j'ai laissé le facteur \og 1 \fg{} dans la définition de la factorielle, bien qu'inutile dans le produit. La raison est purement informatique: nous allons voir que pour implémenter une fonction Python retournant une factorielle, ce \og 1 \fg{} est très important.

\subsection{Première approche: boucle itérative}

La première façon d'écrire une fonction Python \texttt{factorielle(n)} renvoyant $n!$ est d'utiliser une boucle itérative de la manière suivante:

\bigskip


\begin{minipage}{0.45\linewidth}
\begin{python}
def factorielle(n):
    f = 1
    for k in range(1,n+1):
        f = f * k       
    return f
\end{python}
\end{minipage}
\hfill
\begin{minipage}{0.45\linewidth}
\begin{console}
>>> factorielle(5)
120
>>> factorielle(10)
3628800
\end{console}
\end{minipage}

\subsection{Deuxième approche: fonction récursive}

Une deuxième façon d'implémenter cette fonction est de manière récursive :

\begin{python}
def factorielle(n):
    if n == 1: return 1
    else: return n * factorielle(n-1)
\end{python}

L'implémentation récursive est basée sur le fait que:

\begin{itemize}
\item $2! = 2 \times 1 = 2\times 1!$
\item $3! = 3 \times (2 \times 1) = 3 \times 2!$
\item $4! = 4 \times (3 \times 2 \times 1) = 4 \times 3!$
\item $\vdots$
\item $n! = n \times (n-1)!$
\end{itemize}

\subsection{Troisième approche: boucle conditionnelle}

De la forme récursive, on peut aussi voir la fonction de la manière suivante :

\begin{python}
def factorielle(n):
    f = 1
    while n > 1:
        f = f * n
        n = n - 1
        
    return f
\end{python}

\subsection{Quatrième approche: le module math}

Nous l'avons vu précédemment, le module \og math \fg{} contient déjà une fonction factorielle (très performante puisqu'implémentée en C). 

\begin{console}
>>> from math import factorial
>>> factorial(435)
\end{console}

\section{Loi binomiale}
\index{Loi binomiale}

Le module \texttt{scipy.stats} contient des fonctions pour calculer plusieurs nombres en rapport avec la loi binomiale.

\subsection{L'objet \og binom \fg et sa méthode \og stats \fg{} }

On ne va parler de \textit{fonction} mais d'\textit{objet} ici.

\begin{console}
>>> from scipy.stats import binom
>>> moyenne, variance, sigma = binom.stats(50, 0.3, moments='mvs')
>>> moyenne
array(15.)
>>> variance
array(10.5)
>>> sigma
array(0.12344268)
\end{console}

La deuxième ligne définit respectivement la moyenne, la variance et l'écart-type de la variable aléatoire qui suit la loi binomiale de paramètres $n=50$ et $p=0,3$.

\begin{rem}
L'argument \og \texttt{moments = 'mvs'} \fg{} signifie que l'on souhaite avoir un triplet de la forme \texttt{(Mean, Variance, Skew)} (\textit{mean} pour \og moyenne \fg{} et \textit{skew} pour \og écart-type \fg).
\end{rem}

Remarquez aussi que les résultats sont sous forme de tableaux (\textit{array}).


\subsection{L'objet \og binom \fg{} du module personnel probastat}

N'étant pas satisfait des outils disponibles, je me suis fais mon propre module \texttt{probastat} pour obtenir ce que l'on demande le plus souvent au lycée:

\begin{console}
>>> from probastat import binom
>>> X = binom(50,0.3)
>>> X.esp(2), X.var(2) , X.ecart(2)
15.0, 10.5, 3.24
>>> X.proba(10 , 2)
0.04
>>> X.proba_cdf(15 , 2)
0.57
>>> X.proba_icdf(0.95)
20
>>> X.simul(1000,'yellow','red')
\end{console}

\begin{center}
\begin{tikzpicture}
\node[draw=black,line width=3pt,inner sep=0pt, outer sep=0pt] (img) {\includegraphics[scale=1]{Term-simul-binom.png}
};
\drawshadow{img}{black}
\end{tikzpicture}
\end{center}

Pour télécharger ce module, vous pouvez vous rendre sur cet article :

\begin{center}
\url{https://www.mathweb.fr/euclide/2021/04/09/probabilites-et-python-au-lycee-loi-binomiale-et-variables-aleatoires/}
\end{center}

\section{Dénombrement}

Le module \textit{itertools} comporte plusieurs fonctions intéressantes.

\subsection{Produit cartésien}
\index{Denombrement@Dénombrement!Produit cartesien@Produit cartésien}

\texttt{product(E,F)} donne le produit cartésien des deux itérables E et F.
\begin{exemple}
\begin{console}
>>> from itertools import product
>>> E, F = 'abc', 'mn'
>>> list( product(E,F) )
[('a', 'm'), ('a', 'n'), ('b', 'm'), ('b', 'n'), ('c', 'm'), ('c', 'n')]
\end{console}
\end{exemple}

\subsection{Combinaisons}
\index{Denombrement@Dénombrement!Combinaison}


\texttt{combinations(iterable,k)} nous donne la liste de toutes les combinaisons de l'itérable (liste ou chaîne de caractères par exemple) à $k$ éléments. 

\begin{exemple}
\begin{console}
>>> from itertools import combinations
>>> list( combinations('ABC',2) )
[('A', 'B'), ('A', 'C'), ('B', 'C')]
\end{console}

Si un jeu de cartes est constitué de seulement trois cartes, il n'y a que trois mains de deux cartes possibles.

\begin{rem}
N'oublions pas que l'ordre des éléments ne compte pas dans une combinaison. Ainsi, la main \og \texttt{('A','B')} \fg{} est identique à la main \og \texttt{('B','A')} \fg. 
\end{rem}
\end{exemple}

\subsection{Permutations}
\index{Denombrement@Dénombrement!Permutation}

\texttt{permutations(iterable)} nous donne la liste de toutes les permutations des éléments de l'itérable.

\begin{exemple}
\begin{console}
>>> from itertools import permutations
>>> E = 'ABC'
>>> list( permutations(E) )
[('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]
\end{console}
\end{exemple}

\newpage

\subsection{Arrangements}
\index{Denombrement@Dénombrement!Arrangement}

\texttt{permutations(iterable,k)} nous donne la liste de tous les arrangements à $k$ éléments de l'itérable.

\begin{exemple}
\begin{console}
>>> from itertools import permutations
>>> E = 'ABCDE'
>>> list( permutations(E,3) )
[('A', 'B', 'C'), ('A', 'B', 'D'), ('A', 'B', 'E'), ('A', 'C', 'B'), ('A', 'C', 'D'), ('A', 'C', 'E'), ('A', 'D', 'B'), ('A', 'D', 'C'), ('A', 'D', 'E'), ('A', 'E', 'B'), ('A', 'E', 'C'), ('A', 'E', 'D'), ('B', 'A', 'C'), ('B', 'A', 'D'), ('B', 'A', 'E'), ('B', 'C', 'A'), ('B', 'C', 'D'), ('B', 'C', 'E'), ('B', 'D', 'A'), ('B', 'D', 'C'), ('B', 'D', 'E'), ('B', 'E', 'A'), ('B', 'E', 'C'), ('B', 'E', 'D'), ('C', 'A', 'B'), ('C', 'A', 'D'), ('C', 'A', 'E'), ('C', 'B', 'A'), ('C', 'B', 'D'), ('C', 'B', 'E'), ('C', 'D', 'A'), ('C', 'D', 'B'), ('C', 'D', 'E'), ('C', 'E', 'A'), ('C', 'E', 'B'), ('C', 'E', 'D'), ('D', 'A', 'B'), ('D', 'A', 'C'), ('D', 'A', 'E'), ('D', 'B', 'A'), ('D', 'B', 'C'), ('D', 'B', 'E'), ('D', 'C', 'A'), ('D', 'C', 'B'), ('D', 'C', 'E'), ('D', 'E', 'A'), ('D', 'E', 'B'), ('D', 'E', 'C'), ('E', 'A', 'B'), ('E', 'A', 'C'), ('E', 'A', 'D'), ('E', 'B', 'A'), ('E', 'B', 'C'), ('E', 'B', 'D'), ('E', 'C', 'A'), ('E', 'C', 'B'), ('E', 'C', 'D'), ('E', 'D', 'A'), ('E', 'D', 'B'), ('E', 'D', 'C')]
\end{console}

Si l'on imagine une compétition à cinq participants, on obtient la liste de tous les podiums (trois gagnants) possibles.
\end{exemple}


\section{Valeur approchée d'un logarithme\\népérien: algorithme de Briggs}
\index{Briggs (algorithme de)}
\index{Algorithme de Briggs}

\subsection{Principe}

Pour une fonction $f$ définie en $x=a$, nous savons que l'équation réduite de la tangente en $x=a$ à sa courbe représentative est:
\[
y=f'(a)(x-a)+f(a)
\]
ce qui donne pour la fonction $x\mapsto\ln x$ et $a=1$:
\[
y = x - 1.
\]

Par définition, cette tangente est très proche de la courbe au voisinage de $x=1$, ce qui sous-entend que $\ln(x)$ et $x-1$ sont très proches pour $x$ très proche de 1:
\[
\text{pour $x$ très proche de 1,}\qquad \ln x \approx x-1.
\]

Considérons maintenant un nombre positif $a \neq1$.

On démontre que la suite \suite{u}{n}{} définie pour tout entier naturel $n$ par:
\[
\begin{cases}
u_0=a\\
u_{n+1}=\sqrt{u_n}
\end{cases}
\]
converge vers 1.

Autrement dit, il existe une valeur de $p$ telle que, pour tout $n\geqslant p$, $u_n\approx 1$. En particulier, $u_p \approx 1$.

Alors,
\[
\ln(u_{p})\approx u_p - 1.
\]
Or, $u_{p} = \sqrt{u_{p-1}}$ donc :
\[
\ln(u_p) = \ln\sqrt{u_{p-1}}=\dfrac{1}{2}\ln(u_{p-1}).
\]
De même, $u_{p-1}=\sqrt{u_{p-2}}$ donc:
\[
\ln(u_p) = \dfrac{1}{2}\times\dfrac{1}{2}\ln(u_{p-2})=\dfrac{1}{2^2}\ln(u_{p-2}).
\]
Par récurrence, on démontre alors que:
\[
\ln(u_p) = \dfrac{1}{2^p}\ln u_0.
\]
Ainsi, 
\[
\dfrac{1}{2^p}\ln u_0 \approx u_0 - 1
\]
soit:
\[
\ln u_0 = \ln a \approx 2^p(a - 1).
\]
L'algorithme de Briggs consiste à trouver la valeur de $p$ pour déterminer la valeur de $\ln(a)$.


\subsection{L'algorithme}

L'algorithme de Briggs consiste donc à trouver la première valeur $p$ pour laquelle 
$u_p$ est \textit{assez proche} de 1.

Tout dépend donc de ce que l'on appelle \og assez proche \fg: cela va être arbitraire. On peut considérer que $u_p\approx1$ si $|u_p-1|\leqslant10^{-3}$ tout comme on peut considérer que $u_p\approx1$ si $|u_p-1|\leqslant10^{-8}$... D'où l'idée de définir une fonction Python admettant en argument cette marge d'erreur acceptée.

\begin{python}
def briggs(a,e):
    n = 0 # indice du premier terme de la suite (u)
    while abs(a - 1) > e:
        a = a ** 0.5 # terme suivant dans la suite (u)
        n = n + 1    # rang de ce terme
        
    # à la sortie de la boucle, n vaut p
    
    return (a - 1) * (2**n)
\end{python}

\begin{console}
>>> briggs(45,10**(-7))
3.806662604212761
\end{console}
Si on compare cette valeur à $\ln45\approx3,8066624897703\ldots$, c'est pas mal du tout!


\section{Calcul de ln(2) par l'algorithme de\\Brouncker}
\index{Brouncker (algorithme de)}
\index{Algorithme de Brouncker}

\subsection{Principe}

L'idée de cette méthode est de considérer la fonction $x\mapsto\ln x$ comme une primitive de $x\mapsto\dfrac{1}{x}$ et, en conséquence, que :
\[
\int_1^2\dfrac{1}{x}\dx = \ln2 - \ln1 = \ln2.\]
Cette méthode consiste donc à approximer l'aire sous la courbe représentative de la fonction inverse sur \intervFF{1}{2} d'une certaine manière, dont voici les explications:


\itemclass{titrecolor}
\begin{enumerate}
\item \textbf{\'Etape 1:} on construit le rectangle de base \intervFF{1}{2} et de hauteur $\dfrac{1}{2}$.

\begin{center}
\includegraphics[scale=0.75]{Brouncker-01.png}
\end{center}

\newpage

\item \textbf{\'Etape 2:} on prend le milieu de \intervFF{1}{2} et on construit le rectangle \og coincé \fg{} entre le rectangle précédent et la courbe sur \intervFF{1}{\frac{3}{2}}:

\begin{center}
\includegraphics[scale=0.75]{Brouncker-02.png}
\end{center}

\item \textbf{\'Etape 3:} on prend le milieu des intervalles \intervFF{1}{\frac{3}{2}} et \intervFF{\frac{3}{2}}{2}, puis on construit un rectangle \og coincé \fg{} entre les rectangles précédents et la courbe sur \intervFF{1}{\frac{5}{4}} et \intervFF{\frac{3}{2}}{\frac{7}{4}}:

\begin{center}
\includegraphics[scale=0.75]{Brouncker-03.png}
\end{center}

\end{enumerate}

En continuant ainsi, on construit de plus en plus de rectangles dont la somme des aires se rapproche de plus en plus de $\dint_1^2\dfrac{1}{x}\dx$, donc de $\ln2$.

\newpage

\subsection{Une première approche}

On peut alors construire une fonction Python basée sur cette méthode, qui retourne la valeur de la somme trouvée :

\begin{python}
def brouncker(n):
    aire = 0.5 # aire du premier rectangle
    for k in range(1,n):
        base = 1 / 2**k
        X = [ 1 ]
        x = 1
        while x < 2:
            x = x + base
            X.append( x )
        
        for i in range( 1 , len(X) , 2):
            aire = aire + base * ( 1/X[i] - 1/X[i+1] )
            
    return aire
\end{python}

\texttt{n} représente ici le nombre d'étapes souhaitées, $n\geqslant1$, $n=1$ étant l'étape où le premier rectangle est construit.

Je crée une boucle itérative sur \texttt{k} (donc \texttt{k} représentera le numéro de l'étape).

Pour chaque étape, je détermine la \og base \fg{} des rectangles: c'est $\dfrac{1}{2^k}$.

Ensuite, je souhaite créer une liste \texttt{X} de toutes les subdivisions de \intervFF{1}{2} par pas de $\dfrac{1}{2^k}$: c'est l'objet des lignes 5 à 9. 

Une fois cette liste construite, je la parcours par pas de 2. En effet, chaque nouveau rectangle se construit sur une subdivision sur 2. Regardez à l'étape 3: les subdivisions sont \intervFF{1}{1+\frac{1}{4}}, \intervFF{1+\frac{1}{4}}{1+\frac{2}{4}}, \intervFF{1+\frac{2}{4}}{1+\frac{3}{4}} et \intervFF{1+\frac{3}{4}}{1+\frac{4}{4}} et les rectangles verts sont sur \intervFF{1}{1+\frac{1}{4}} et \intervFF{1+\frac{2}{4}}{1+\frac{3}{4}}.

L'expression \og \texttt{base * ( 1/X[i] - 1/X[i+1] )} \fg{} sur la ligne 12 correspond à l'aire du rectangle ajouté.

\medskip

On obtient alors par exemple:

\begin{console}
>>> brouncker(15)
0.6931319220037134
>>> brouncker(20)
0.6931467037230511
\end{console}

Mais si d'aventure vous souhaitez mettre en argument une valeur de $n$ supérieure à 23, le temps d'exécution sera assez long... J'ai en effet pris le parti de rendre le plus clair possible (à mes yeux) le programme, au détriment de sa complexité (qui a une incidence sur le temps d'exécution). En l'occurrence, il y a beaucoup de calculs (car beaucoup de puissances et de listes), d'où un temps d'exécution lent pour de grandes valeurs de $n$.

\subsection{Une autre approche}

Plutôt que de tenter de calculer la somme des aires des rectangles, penchons-nous sur la formule que l'on peut obtenir en observant le principe de la méthode.

\begin{itemize}
\item le premier rectangle a pour aire $1\times\dfrac{1}{2}$, que l'on peut écrire aussi sous la forme $\dfrac{1}{1\times2}$;
\item le deuxième rectangle (orange) a pour aire $\dfrac{1}{2}\times\dfrac{1}{6}$, que l'on peut écrire aussi $\dfrac{1}{3\times4}$;
\item le troisième rectangle (le premier vert) a pour aire $\dfrac{1}{4}\times\dfrac{2}{15}=\dfrac{1}{5\times6}$;
\item le quatrième (vert) a pour aire $\dfrac{1}{4}\times\dfrac{1}{14}=\dfrac{1}{7\times8}$;
\item $\ldots$
\end{itemize}

On peut conjecturer que l'aire totale (donc $\ln2$) vaut:
\[
\ln2 = \dfrac{1}{1\times2} + \dfrac{1}{3\times4} + \dfrac{1}{5\times6} + \dfrac{1}{7\times8} + \cdots = \lim\limits_{n\to+\infty}\sum_{k=0}^n\dfrac{1}{(2k+1)(2k+2)}.
\]
D'où la fonction Python suivante, qui nécessite toute de même une valeur de $n$ assez grande (supérieure à $10^5$), mais pas trop (inférieure à $10^9$) sinon le temps d'exécution est assez long.

\medskip

\begin{minipage}[t]{0.55\linewidth}
\begin{python}
def brouncker(n):
    somme = 0
    for k in range(1,n+1,2):
        somme += 1 / (k * (k+1) )
        
    return somme
\end{python}
\end{minipage}
\hfill
\begin{minipage}[t]{0.43\linewidth}
\begin{console}
>>> brouncker(10**8)
0.6931471754736988
\end{console}
\end{minipage}


\section{Maths complémentaires: simuler la loi géométrique}
\index{Loi geometrique@Loi géométrique}
\label{loi-geometrique}

On considère une variable aléatoire $X$ suivant la loi binomiale $\mathcal{B}\coord{n}{p}$.

Si $G$ représente le nombre de fois qu'il est nécessaire de répéter l'expérience de Bernoulli avant d'obtenir un succès, alors elle suit la loi géométrique de paramètre $p$.

\medskip

Pour simuler une loi géométrique, on va donc considérer l'expérience consistant à répéter un choix aléatoire entre 0 et 1 (échec et succès d'une expérience de Bernoulli) jusqu'à obtenir 1 (le succès); on note $n$ le nombre de fois que nous avons répéter l'expérience de Bernoulli. 

On répète ceci $N$ fois en mettant les valeurs de $n$ obtenues dans une liste $L$. Ensuite, on calcule la fréquence d'apparition de tous les nombres de $L$.

\begin{python}
from random import randint
from matplotlib.pyplot import plot, show

L = []
N = 10**5

for i in range(N):
    n = 1
    while randint(0,1) == 0:
        n += 1
    
    L.append(n)

X = []
Y = []

for k in range( 1 , max(L) + 1 ):
    X.append(k)
    Y.append( L.count(k) / N )
    
plot(X,Y)
show()
\end{python}

On obtient alors un graphique nous donnant la probabilité que $G=k$, pour $k$ entier supérieur ou égal à 1.

\begin{center}
\begin{tikzpicture}
\node[inner sep=0pt,outer sep=0pt] (img) {\includegraphics[scale=0.9]{terminale-simul-loi-geometrique.png}};
\drawshadow{img}{black}
\end{tikzpicture}
\end{center}

\section{Math complémentaires: droite de\\régression linéaire}
\index{Regression lineaire@Régression linéaire}

Considérons une expérience de physique: on relève la tension et l'intensité aux bornes d'un dipôle; on cherche à établir une équation de la droite de régression de cette série statistique.

Nous allons faire appel au module \texttt{numpy} :

\begin{python}
from numpy import polyfit, array
from matplotlib.pyplot import plot, show, scatter, legend, xlabel, ylabel

U = array( [0 , 1 , 2 , 3 , 4 , 5] )
I = array( [0, 0.011 , 0.019 , 0.033 , 0.041 , 0.049] )

modele = polyfit(I,U,1)
equation = ("U = {} x I + {}".format( format(modele[0],".2E") , format(modele[1],".2E")))

scatter(I,U,marker='+',s=100) # placement des points
plot(I , modele[0]*I+modele[1] , color='red' , label = equation)

xlabel("I (A)")
ylabel("U (V)")
legend()
show()
\end{python}
\enlargethispage*{4em}
\begin{center}
\begin{tikzpicture}
\node[inner sep=0pt,outer sep=0pt] (img) {\includegraphics[scale=0.9]{terminale-numpy-polyfit.png}};
\drawshadow{img}{black}
\end{tikzpicture}
\end{center}

\section{Maths expertes: calcul du PGCD avec l'algorithme d'Euclide}
\index{PGCD (calcul)}
\index{Euclide (algorithme)}

\subsection*{Un programme basique}

Vous trouverez sans doute beaucoup de propositions sur Internet de cet algorithme car c'est un exemple classique. En voici un :

\begin{python}
def pgcd(a,b) :  
   while a%b != 0 : 
      a, b = b, a%b 
   return b
\end{python}

On a par exemple:

\begin{console}
>>> pgcd(1023,52)
6
\end{console}

\subsection*{Une autre fonction avec affichage des étapes}

Je vous propose ici un algorithme permettant d'afficher les étapes :

\begin{python}
def euclide(a,b):
    if b > a:
        a,b = b,a
    
    r = -1
    while r !=0 :
        q = a // b
        r = a % b
        print('{:3} = {:2} x {:2} + {}' . format(a,q,b,r))
        a = b
        b = r
\end{python}

On a par exemple:

\begin{console}
>>> euclide(1023,52)

1023 = 19 x 52 + 35
 52 =  1 x 35 + 17
 35 =  2 x 17 + 1
 17 = 17 x  1 + 0
\end{console}

\section{Maths expertes: un couple de Bézout}
\index{Bezout@Bézout}

Il s'agit ici de trouver un couple solution de l'équation $ax+by=1$, avec $\pgcd{a}{b}=1$.

\subsection*{Forme récursive}

\begin{python}
def bezout(a,b):
    if b == 0:
        return 1,0
    else:
        u , v = bezout(b , a % b)
        return v , u - (a//b)*v
\end{python}

Par exemple, pour trouver une solution de l'équation $13x+5y=1$, on tape:
\begin{console}
>>> bezout(13,5)
(2, -5)
\end{console}

\subsection*{Forme plus naturelle}

\begin{python}
def bezout(a,b):
    u, v, x, y = 1, 0, 0, 1
    while b > 0:
        r = a % b
        q = a // b
        u1, v1 = u, v # variables temporaires
        u, v = x, y # u et v deviennent x et y
        x = u1 - q*x
        y = v1 - q*y
        a, b = b, r
    
    return u, v
\end{python}

Cette dernière fonction s'inspire de l'algorithme d'Euclide pris à l'envers.

\newpage

\section{Maths expertes: crible d'Eratosthène}
\index{Eratosthene@Eratosthène (crible)}

Le crible d'Eratosthène consiste à prendre la liste de tous les nombres entiers de 2 à $n$, $n$ étant un entier supérieur ou égal à 2, et à supprimer tous les nombres qui n'ont aucun diviseur.

On obtient ainsi la liste de tous les nombres premiers inférieurs ou égaux à $n$.


\begin{python}
def eratosthene(n):
    P = [ ]
    for i in range(2,n+1):
        if len(P) == 0:
            P.append(i)
        else:
            prem = True
            for k in P:
                if i % k == 0:
                    prem = False
            if prem == True:
                P.append(i)
    
    return P
\end{python}

On crée une liste \texttt{P} devant contenir les nombres premiers cherchés.

On parcourt tous les nombres entiers $i$ de 2 à $n$: si on est sur \og 2 \fg, on l'insère dans \texttt{P} sinon, on parcourt la liste \texttt{P} (qui ne contient que des nombres premiers) et si $i$ est divisible par l'un de ses nombres, c'est qu'il n'est pas premier donc on ne l'insère pas dans \texttt{L}.


\section{Maths expertes: décomposition en produit de facteurs premiers}
\index{Decomposition (produit de facteurs premiers)@Décomposition (produit de facteurs premiers)}

L'idée ici est de créer une fonction \texttt{decompose(n)}, où l'argument $n$ est un entier naturel, qui détermine la liste des facteurs premiers de $n$ ainsi que le nombre de fois que $n$ peut être divisé par ces facteurs (donc leur exposant dans la décomposition en produit de facteurs premiers de $n$).

\medskip

On commence donc par voir si $n$ est divisible par $i=2$: si tel est le cas, on divise $n$ autant de fois que possible par 2 pour déterminer l'exposant $k$ du facteur 2 dans la décomposition.

\medskip

Une fois terminé, $n$ vaut $\dfrac{n}{2^k}$, et on recommence avec $i=3$.

\medskip

On continue ainsi jusqu'à ce que $n=1$.

\medskip

On a alors la fonction page suivante.

\newpage

\begin{python}
def decompose (n):
    factors_list = []
    i = 2
    val = n
    while n > 1:
        exposant = 0
        while n % i == 0:
            exposant = exposant + 1
            n = n/i
            
        if exposant != 0:
            factors_list.append( (i,exposant) )
            
        i = i+1

    return factors_list
\end{python}
\begin{console}
>>> decompose(420)
[(2, 2), (3, 1), (5, 1), (7, 1)]
\end{console}

Cette fonction retourne la liste de tous les facteurs premiers du nombre $n$ avec leur exposant dans la décomposition en produit de facteurs premiers.

Sur l'exemple ci-dessus, on a donc:
\[
420 = 2^2 \times 3^1 \times 5^1 \times  7^1.
 \]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\exercices

\section*{Suites}

\begin{exocor}{relation de récurrence}[1]
On définit la suite \suite{u}{n}{} pour tout entier naturel $n$ non nul par:
\[
\begin{cases}
u_0=0\\
u_{n+1}=\left(1+\frac{1}{n+1}\right)u_n + 1
\end{cases}
\]
\'Ecrire un programme Python qui calcule et affiche les 100 premiers termes de cette suite après $u_0$.

\tcblower

Attention à la formule de récurrence: quand on souhaite écrire un programme Python pour calculer les termes consécutifs, comme ici, il vaut mieux voir la relation de récurrence comme ceci:
\[
\begin{cases}
u_0=0\\
u_{n+1}=\left(1+\frac{1}{n+1}\right)u_n + 1
\end{cases}
\iff
\begin{cases}
u_0=0\\
u_{n}=\left(1+\frac{1}{n}\right)u_{n-1} + 1
\end{cases}
\]
On s'aperçoit alors que c'est l'inverse de l'indice du terme courant qui intervient dans le calcul.

\medskip

On connaît le nombre de termes à calculer, donc on utilise une boucle itérative:
\begin{python}
u = 0 # terme initial

for n in range(1,101):
	# on calcule le terme d'indice n
    u = (1 + 1/n) * u + 1
    print(u)
\end{python}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{relation de récurrence}[1]
On définit la suite \suite{u}{n}{} pour tout entier naturel $n$ non nul par:
\[
\begin{cases}
u_0=1\\
u_{n+1}=nu_n^2 - \frac{u_n}{2n+3}
\end{cases}
\]
\'Ecrire un programme Python qui calcule et affiche les 100 premiers termes de cette suite après $u_0$.

\tcblower

Comme dans l'exercice \ref{exercice:\thechapter.1}, il est conseillé d'écrire la relation de récurrence de la suite d'une autre manière:
\begin{align*}
\begin{cases}
u_0=1\\
u_{n+1}=nu_n^2 + \dfrac{u_n}{2n+3},\qquad n\geqslant0
\end{cases}
&
\iff
\begin{cases}
u_0=1\\
u_{n}=(n-1)u_{n-1}^2 + \dfrac{u_{n-1}}{2(n-1)+3},\qquad n\geqslant1
\end{cases}\\[15pt]
&
\iff
\begin{cases}
u_0=1\\
u_{n}=(n-1)u_{n-1}^2 + \dfrac{u_{n-1}}{2n+1},\qquad n\geqslant1
\end{cases}
\end{align*}
On en déduit le programme suivant:
\begin{python}
u = 1

for n in range(1,101):
    u = (n-1)*u**2 + u/(2*n+1)
    print(u)
\end{python}
\begin{attention}
Il me semble réellement important de transformer la relation de récurrence initiale pour ne pas se tromper dans les valeurs de $n$.
\end{attention}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{suite de Fibonacci}[1]
La suite de Fibonacci est définie par ses premiers termes $F_0=F_1=1$ et par la relation de récurrence:
\[
\forall n \geqslant0,\qquad F_{n+2}=F_{n+1}+F_n.
\]
\begin{enumerate}
\item \'Ecrire un programme Python permettant d'afficher les 50 premiers termes de cette suite (donc de $F_0$ à $F_{49}$) sans utiliser de liste.

\item On souhaite observer le quotient $\dfrac{F_{n+1}}{F_n}$ pour $n\geqslant0$.

Modifier la réponse à la question précédente pour afficher ces quotients, pour $n$ variant de 0 à 49.
\end{enumerate}

\tcblower

\begin{enumerate}
\item Voici un programme possible qui permet d'afficher les 50 premiers termes de la suite de Fibonacci sans liste:
\begin{python}
a, b = 1, 1
print(a)
print(b)

for n in range(48):
    a , b = b, a+b
    print(b)
\end{python}

\item Afin d'afficher les quotients $\dfrac{F_{n+1}}{F_n}$ pour tout entier compris entre 0 et 49, on modifie la solution précédente ainsi:
\begin{python}
a, b = 1, 1
print(b,'/',a,'=',b/a)

for n in range(48):
    a , b = b, a+b
    print(b,'/',a,'=',b/a)
\end{python}
\end{enumerate}
En exécutant ce dernier programme, on s'aperçoit que les dernières lignes sont:
\begin{console}
24157817 / 14930352 = 1.618033988749897
39088169 / 24157817 = 1.618033988749894
63245986 / 39088169 = 1.6180339887498951
102334155 / 63245986 = 1.6180339887498947
165580141 / 102334155 = 1.618033988749895
267914296 / 165580141 = 1.618033988749895
433494437 / 267914296 = 1.618033988749895
701408733 / 433494437 = 1.618033988749895
1134903170 / 701408733 = 1.618033988749895
1836311903 / 1134903170 = 1.618033988749895
2971215073 / 1836311903 = 1.618033988749895
4807526976 / 2971215073 = 1.618033988749895
7778742049 / 4807526976 = 1.618033988749895
12586269025 / 7778742049 = 1.618033988749895
\end{console}
On peut alors constater que les quotients se rapprochent d'une valeur limite.

En effet, on peut démontrer mathématiquement que:
\[
\limite{n}{+\infty}{\frac{F_{n+1}}{F_n}}=\dfrac{1+\sqrt5}{2}=\varphi
\]
qui est le \textit{nombre d'or}.
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage

\begin{exocor}{les suites de Héron}[2]
Pour un réel $a$ strictement positif quelconque, on considère la suite $(u_n(a))_{n\geqslant0}$ définie pour tout entier naturel $n$ par :
\[
\begin{cases}
u_0(a) & > 0\\
u_{n+1}(a) & = \dfrac{1}{2}\left(u_n + \dfrac{a}{u_n}\right)
\end{cases}
\]
\begin{enumerate}
\item Compléter la fonction Python suivante afin que l'instruction :

\begin{console}
>>> heron(4,7,10)
\end{console}

retourne les $n+1$ premiers termes de la suite $(u_n(4))_{n\geqslant0}$  dans une liste.

\begin{python}
def heron(a,u,n):
    if u <=0:
        return "Le premier terme doit être strictement positif."
    elif a <= 0:
        return "La valeur de 'a' doit être strictement positive."
    else:
        L = [ ... ]
        k = 0
        while k < ...:
            u = ...
            L.append(...)
            k = ...
        return ...
\end{python}

\item L'instruction renvoie alors la liste suivante:
\begin{console}
[7, 3.7857142857142856, 2.4211590296495955, 2.0366301688743387, 2.0003294091613366, 2.0000000271231317, 2.0, 2.0, 2.0, 2.0, 2.0]
\end{console}

Faites deux conjectures à partir de ces valeurs.
\end{enumerate}

On se propose d'étudier mathématiquement la suite $\suite{u(a)}{n}{}$ pour une valeur de $a>0$.

Pour cela, on introduit la fonction $f$ définie pour tout réel $x$ strictement positif par :
\[ 
f(x)=\dfrac{1}{2}\left(x + \frac{a}{x}\right)
\]

\begin{enumerate}[start=3]
\item Calculer $f'(x)$, puis donner les variations de $f$ sur \intervOO{0}{+\infty} en fonction de $a$.
\item En déduire que $u_1 \geqslant \sqrt{a}$, quelle que soit la valeur de $u_0 > 0$.
\item Montrer que pour tout réel $x \geqslant \sqrt{a}$, $f(x) \leqslant x$.
\item Montrer alors par récurrence que pour tout entier naturel $n\geqslant1$, $\sqrt{a} \leqslant u_{n+1} \leqslant u_n$.
\item Déduire que $(u_n(a))_{n\geqslant0}$ converge. On note $\ell$ sa limite.
\item On admet que $\ell=f(\ell)$. Déterminer alors la limite de$(u_n(a))_{n\geqslant0}$.
\end{enumerate}

\tcblower

\begin{enumerate}
\item La fonction Python complétée est la suivante:
\begin{python}
def heron(a,u,n):
    if u <=0:
        return "Le premier terme doit être strictement positif."
    elif a <= 0:
        return "La valeur de 'a' doit être strictement positive."
    else:
        L = [ u ]
        k = 0
        while k < n:
            u = 0.5 * (u + a / u)
            L.append(u)
            k = k + 1
        return L
\end{python}

\item On peut constater:
\begin{itemize}
\item d'une part que la suite \suite{u(4)}{n}{} semble être décroissante;
\item d'autre part, que la suite \suite{u(4)}{n}{} semble converger vers 2.
\end{itemize}

\item\label{heronq3} On a : $f'(x)=\dfrac{1}{2}\left(1-\dfrac{a}{x^2}\right)=\dfrac{x^2-a}{2x^2}$.

$x^2-a$ est un polynôme du second degré dont les racines sont $\sqrt{a}$ et $-\sqrt{a}$, d'où le tableau suivant:

\begin{center}
\begin{tikzpicture}
\node[inner sep=0pt,outer sep=0pt] (tab) {
\begin{tikzpicture}
\tkzTabInit[color,colorL=numpagecorrige!10,colorC=numpagecorrige!10,colorV=numpagecorrige!10]{$x$/0.8,$f'(x)$/0.5,$f$/1}{0,$\sqrt{a}$,$+\infty$}
\tkzTabLine{d,-,z,+}
\tkzTabVar{D+/,-/{$\sqrt{a}$},+/}
\end{tikzpicture}
};
\drawshadow{tab}{black}
\end{tikzpicture}
\end{center}

\item D'après les variations de $f$, si $x\in\intervFO{0}{\sqrt{a}}$ alors $f(x)\geqslant\sqrt{a}$.

Or, $u_1=f(u_0)$ donc si $u_0\in\intervOF{0}{\sqrt{a}}$ alors $u_1\geqslant\sqrt{a}$.

De plus, si $u_0\geqslant\sqrt{a}$, d'après les variations de $f$, $f(u_0)\geqslant\sqrt{a}$.

\uline{Ainsi, quelle que soit la valeur de $u_0>0$, $u_1\geqslant\sqrt{a}$.}




\item Montrer que pour tout réel $x\geqslant\sqrt{a}$, $f(x)\leqslant x$.

Considérons alors la fonction $g(x)=f(x)-x$:
\[
g(x)=\frac{1}{2}\left(\frac{a}{x}-x\right).
\]
Sa dérivée est alors:
\[
g'(x)=\dfrac{1}{2}\left(-\frac{a}{x^2}-1\right)
\]
donc $g'(x)<0$ sur \intervFO{\sqrt{a}}{+\infty}, ce qui signifie que $g$ est strictement décroissante sur \intervFO{\sqrt{a}}{+\infty}.

De plus, $g(\sqrt{a})=0$ donc $g(x)\leqslant0 $ sur \intervFO{\sqrt{a}}{+\infty}. On a alors $f(x)-x \leqslant 0$, soit $f(x) \leqslant x$.







\item Démontrons par récurrence que pour tout entier naturel $n\geqslant1$, $\sqrt{a} \leqslant u_{n+1} \leqslant u_n$.

\begin{itemize}
\item \textbf{Initialisation.} 

$u_1>\sqrt{a}$ et $u_2=f(u_1) \leqslant u_1$ d'après la question précédente. 

On a donc bien $\sqrt{a} \leqslant u_2 \leqslant u_1$.

L'initialisation est alors réalisée.


\item \textbf{Hérédité.}

Supposons que pour un entier $k>1$ , $\sqrt{a} \leqslant u_{k+1} \leqslant u_k$.

D'après la question \ref{heronq3}, $f$ est strictement croissante sur $\intervOO{\sqrt{a}}{+\infty}$ donc :
\[
f(\sqrt{a}) \leqslant f(u_{k+1}) \leqslant f(u_k)
\]
soit:
\[
\sqrt{a} \leqslant u_{k+2} \leqslant u_{k+1}.
\]
L'hérédité est alors vérifiée.
\end{itemize}

\uline{Ainsi, d'après le principe de récurrence, pour tout entier naturel $n\geqslant1$, $\sqrt{a} \leqslant u_{n+1} \leqslant u_n$.}


\item La suite \suite{u(a)}{n}{} est, d'après la question précédente, décroissante et minorée. Donc d'après le théorème de convergence des suites monotones, elle converge.

\item On admet que $\ell = f(\ell)$, soit $f(\ell)-\ell=0$. Donc: \begin{align*}
g(\ell)=0 & \iff \dfrac{a}{\ell}-\ell=0\\
& \iff a-\ell^2=0\\
& \iff \ell = -\sqrt{a}\text{ ou }\ell=\sqrt{a}.
\end{align*}
Or, $\ell>0$ car $u(a)_n>0$. Donc $\ell=\sqrt{a}$.

\uline{Ainsi, la limite de \suite{u(a)}{n}{} est égale $ \sqrt{a}$.}
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{méthode de Newton avec le logarithme népérien}[2]
On considère la fonction $f$ définie sur \intervOO{-1}{+\infty} par:
\[
f(x)=3x-2+\ln(x+1).
\]
On considère la suite $(u_n)$ définie pour tout entier naturel $n$ par :
\[
\begin{cases}
u_0=1\\
u_{n+1}=u_n-\dfrac{f(u_n)}{f'(u_n)}
\end{cases}
\]
On admet que cette suite converge vers l'unique solution de l'équation $f(x)=0$.

\'Ecrire un programme en Python permettant d'afficher les premiers termes de cette suite jusqu'à ce que la différence entre deux termes consécutifs soit inférieure à $10^{-12}$.

\tcblower

Un programme possible est le suivant:

\begin{python}
from math import log

g = lambda x : x-(x+1)*(3*x-2+log(x+1))/(3*x+4)

u = 1
v = f(1)

while abs(u-v) > 10**(-12):
    u = v
    v = g(u)
    print(v)
\end{python}

Ici, la ligne \og \texttt{g = lambda x : x-(x+1)*(3*x-2+log(x+1))/(3*x+4)} \fg{} permet de définir une fonction $g$ telle que $g(x)=x-\dfrac{f(x)}{f'(x)}$ car $u_{n+1}=g(u_n)$. Mais on aurait pu aussi écrire :

\begin{python}
def g(x):
	return x-(x+1)*(3*x-2+log(x+1))/(3*x+4)
\end{python}

C'est d'ailleurs cette syntaxe que j'ai choisi d'adopter dans tous les autres programmes Python car elle est plus naturelle... Après tout, nous ne sommes pas en NSI !

On initialise ensuite deux termes consécutifs $u=u_0$ et $v=u_1$, puis on calcule les termes successifs tant que $|u-v|>10^{-12}$.

Le programme s'arrête assez vite (seulement 4 affichages !) et donne:

\begin{console}
0.5258167668648809
0.5258221966299376
0.5258221966316697
0.5258221966316697
\end{console}

Cela signifie que la convergence est très rapide (ce qui est d'ailleurs une caractéristique de la méthode de Newton).
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Continuité}

\begin{exocor}{dichotomie}[2]
On considère l'algorithme de dichotomie suivant:
\begin{center}
\fbox{
\begin{minipage}{0.6\linewidth}
\ttfamily
delta $\leftarrow$ 1\\
e $\leftarrow$ 0,00001\\
f est une fonction continue sur [a;b]\\
Tant que delta > e faire:\\
\hspace*{5mm}m = a + (b-a)/2\\
\hspace*{5mm}delta = |b-a|\\
\hspace*{5mm}Si f(m) = 0 alors:\\
\hspace*{10mm}Affiche m\\
\hspace*{5mm}Sinon:\\
\hspace*{10mm}Si f(a)$\times$f(m) > 0 alors:\\
\hspace*{15mm}a $\leftarrow$ m\\
\hspace*{10mm}Sinon:\\
\hspace*{15mm}b $\leftarrow$ m\\
\hspace*{10mm}Fin du Si\\
\hspace*{5mm}Fin du Si\\
Fin du Tant que\\
Afficher a, b
\end{minipage}
}
\end{center}

En s'aidant de cet algorithme, écrire une fonction Python \texttt{dichotomie(a,b,e)} qui permet de renvoyer un encadrement d'amplitude $e$ de la solution à l'équation $f(x)=0$ sur \intervFF{a}{b}, en prenant $f(x)=\sqrt{(\ln x)^2 + \e^x}-2x$, $e=10^{-7}$, $(a;b)=(0,5; 1)$ d'une part, $(a;b)=(4;5)$ d'autre part.

\tcblower

\medskip

Une fonction possible est la suivante:
\begin{python}
from math import exp, log, sqrt

def f(x):
	return sqrt( log(x)**2 + exp(x) ) - 2*x
    
def dichotomie(a,b,e):
    delta = 1
    while delta > e:
        m = a + (b - a) / 2
        delta = abs(b - a)
        if f(m) == 0:
            return m
        elif f(a) * f(m)  > 0:
            a = m
        else:
            b = m
            
    return a, b
\end{python}

Dans la fonction \texttt{dichotomie}, je n'ai fait que traduire l'algorithme donné dans l'énoncé en langage Python.

\newpage

On obtient alors :

\begin{console}
>>> dichotomie(0.5, 1, 10**(-7))
(0.7391805052757263, 0.7391805350780487)
>>> dichotomie(4, 5, 10**(-7))
(4.2513850927352905, 4.251385122537613)
\end{console}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Intégration}

\begin{exocor}{méthode des rectangles}[2]
On considère l'algorithme suivant, qui permet d'obtenir un encadrement de $\dint_a^bf(x)\dx$, où $f$ est une fonction continue sur \intervFF{a}{b}:
\begin{center}
\fbox{
\begin{minipage}{0.65\linewidth}
\ttfamily
longueur $\leftarrow$ (b - a)/n\\
inf $\leftarrow$ 0\\
sup $\leftarrow$ 0\\
Pour k prenant ses valeurs de 0 à n-1 faire:\\
\hspace*{5mm}inf $\leftarrow$ inf + longueur*f(a+k*(longueur))\\
\hspace*{5mm}sup $\leftarrow$ sup + longueur*f(a+(k+1)*(longueur))\\
Fin du Pour\\
Afficher inf et sup
\end{minipage}
}
\end{center}

En s'inspirant de cet algorithme, écrire une fonction Python \texttt{integrale(a,b,n)} qui renvoie un encadrement de $\dint_a^bf(x)\dx$, en divisant \intervFF{a}{b} en $n$ segments identiques.

On prendra pour exemple la fonction $f(x)=\sqrt{(\ln x)^2+\e^x}-2x$, $a=0.739180505$,\linebreak $b=4.251385$ et $n=100$.

\tcblower

Une fonction possible est la suivante:
\begin{python}
from math import exp, log, sqrt

def f(x):
    return sqrt( log(x)**2 + exp(x) ) - 2*x

def integrale(a,b,n):
    longueur = (b - a) / n
    aire_inf , aire_sup = 0 , 0
    
    for k in range (n):
        aire_inf = aire_inf + longueur * f(a + k * longueur )
        aire_sup = aire_sup + longueur * f(a + (k+1) * longueur )
        
    return aire_inf , aire_sup
\end{python}
\begin{console}
>>> a, b = 0.739180505, 4.251385
>>> integrale(a,b,100)
(-3.3417134238835544, -3.3417134345212043)
\end{console}
\end{exocor}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Dénombrement}

\begin{exocor}{fonction shuffle du module random}[1]
La fonction \texttt{shuffle} du module \texttt{random} de Python permet de mélanger les éléments d'une liste.

Par exemple :

\begin{console}
>>> from random import shuffle
>>> L = [1,2,3,4,5,6,7,8,9,10]
>>> shuffle(L)
>>> L
[5, 10, 4, 1, 9, 8, 7, 3, 2, 6]
\end{console}

Combien d'affichages distincts est-il possible d'obtenir sur cet exemple ?

\tcblower

Il s'agit ici de savoir combien de permutations il est possible d'obtenir sur une liste à 10 éléments.

\medskip

D'après le cours de mathématiques, il y en a $10!$.

\medskip

\underline{Il y a donc $10!$ affichages distincts possibles sur l'exemple donné.}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\begin{exocor}{listes des noms et prénoms des élèves}[1]
Un enseignant dispose de deux listes Python nommées \texttt{noms} et \texttt{prenoms} contenant respectivement tous les noms et prénoms distincts des élèves d'une classe.

Par exemple, le code suivant :

\begin{python}
from itertools import product

noms = [ 'DUPOND' , 'DUPONT' , 'DURAND' , 'DUMONT' ]
prenoms = [ 'Jean' , 'Anne' , 'Vincent' ]

print ( list(product( noms, prenoms) ) )
\end{python}

donne le résultat suivant :

\begin{console}
[('DUPOND', 'Jean'), ('DUPOND', 'Anne'), ('DUPOND', 'Vincent'), ('DUPONT', 'Jean'), ('DUPONT', 'Anne'), ('DUPONT', 'Vincent'), ('DURAND', 'Jean'), ('DURAND', 'Anne'), ('DURAND', 'Vincent'), ('DUMONT', 'Jean'), ('DUMONT', 'Anne'), ('DUMONT', 'Vincent')]
\end{console}

Si les listes \texttt{noms} et \texttt{prenoms} comportent respectivement 30 noms et 25 prénoms, combien d'éléments comporte le résultat affiché ?

\tcblower

Il s'agit ici d'un produit cartésien de deux ensembles (les deux listes Python). Si les deux listes contiennent $n$ et $p$ éléments, alors le résultat final donnera une liste à $n \times p$ éléments.

\medskip

\underline{Ainsi, pour notre exemple, le résultat contiendra $30\times25=750$ éléments.}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{compétition de danse}[1]
L'organisatrice d'une compétition de danse souhaite afficher tous les podiums possibles (3 compagnies de danse gagnantes). Elle possède la liste de toutes les compagnies de danses inscrites, qu'elle a nommé \texttt{compagnies}.

Elle utilise alors le code Python suivant :

\begin{console}
>>> from itertools import permutations
>>> len(compagnies)
25
>>> print( len( list(permutations(compagnies,3) ) ) )
\end{console}

Quel est le résultat affiché ?

On rappelle que \texttt{len(L)} désigne le nombre d'éléments contenus dans la liste \texttt{L}.

\tcblower

Il s'agit ici de savoir combien de podiums de 3 gagnantes on peut obtenir sur un ensemble à 25 éléments (en effet, la console Python nous affiche pour \texttt{len(compagnies)} le nombre \og 25 \fg, ce qui signifie qu'il y a 25 éléments dans la liste \texttt{compagnies}).

D'après le cours de mathématiques, il s'agit donc du nombre d'arrangements de 3 éléments parmi 25, qui est égal à:
\[
\dfrac{25!}{(25-3)!}=\numprint{13800}.
\]

\medskip

\underline{Le résultat affiché dans la console est alors \texttt{13800}.}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{grilles de Loto\copyright}[2]
Monsieur Laguigne en a marre de perdre au Loto\copyright. Il décide alors de faire un programme Python qui génère tous les résultats possibles.

Rappelons que le jeu du Loto\copyright{} consiste à choisir 5 numéros entre 1 et 49, puis un numéro \og chance \fg{} à mettre à la fin.
\newpage
Voici par exemple un résultat fourni par la Française des Jeux, société organisatrice du jeu:

\medskip

\begin{center}
\includegraphics[scale=0.75]{loto.jpg}
\end{center}

\medskip

Pour cela, il voudrait utiliser le code suivant :

\begin{python}
from itertools import combinations, product

grille = [ n for n in range(1,50) ]

resultats_finaux = list()

for resultat in list( combinations( grille , 5 ) ):
    grille_restante = [ n for n in range(1,50) if n not in resultat ]
    r = list( resultat )
    for num in grille_restante:
        resultats_finaux.append( r + [num] )
\end{python}

Il souhaite ainsi parcourir la liste de toutes les combinaisons possibles de 5 nombres parmi 49 (ligne 7) et pour chacune d'elles, il construit une grille des numéros non encore choisis (ligne 8). Il convertit ensuite la combinaison en liste (ligne 12) puis il parcourt la grille des nombres restants: pour chacun d'eux, il considère la liste des nombres choisis à laquelle il ajoute le nombre (le numéro chance).

Par exemple, les deux premiers résultats sont :
\begin{console}
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 7]
\end{console} 

\begin{enumerate}
\item Calculer le nombre d'éléments de la liste \texttt{list( combinations( grille , 5 ) )}.

\item En déduire le nombre d'éléments de la liste \texttt{resultats\_finaux}.

\item En lançant son programme, la console affiche le message suivant :
\begin{console}
resultats_finaux.append( r + [num] )
MemoryError
\end{console}

Avancez une explication.
\end{enumerate}

\tcblower

\begin{enumerate}
\item Il s'agit ici de trouver le nombre de combinaisons de 5 éléments parmi 49 que l'on peut obtenir, donc de calculer $\dbinom{49}{5}$; on trouve \numprint{1906884}.

\item La liste \texttt{resultats\_finaux} est le résultat du produit cartésien de la liste\linebreak \texttt{list( combinations( grille , 5 ) )} et de la liste \texttt{grille\_restante}, qui compte $49-5=44$ éléments. Son cardinal est donc le produit de \numprint{1906884} par 44. 

\underline{Il y a donc \numprint{83902896} éléments dans la liste \texttt{resultats\_finaux}.}

\item Chacun des éléments de \texttt{resultats\_finaux} est un tuple de 6 nombres. Il faut donc stocker en mémoire $\numprint{83902896}\times6=\numprint{503417376}$ nombres.

Chaque nombre est représenté sur 1 octet (8 bits). Ainsi, il nous faut disposer de $\numprint{503417376}\times8=\numprint{4027339008}$ bits, ce qui correspond à un peu moins de 4 Go.

En théorie, il n'y aurait donc pas de problème de mémoire sur un ordinateur personnel classique, doté en général de 8 Go de mémoire.

Mais le système d'exploitation ainsi que les logiciels tiers (comme par exemple Python) occupent de l'espace mémoire, rendant l'espace disponible moindre, comme le montre cette capture d'écran montrant la mémoire de mon ordinateur :

\begin{center}
\includegraphics[scale=0.45]{ram.jpg}
\end{center}

Il n'est donc pas anormal que le programme de monsieur Laguigne ne fonctionne pas.
\end{enumerate}
\end{exocor}

\section*{Probabilités}

\begin{exocor}{}[2]
L'expérience $\mathcal{E}$ consiste à choisir un nombre au hasard sur l'intervalle \intervFO{0}{1}.

On note $X$ la variable aléatoire représentant le nombre de fois que l'on répète $\mathcal{E}$ pour que la somme des nombres choisis soit strictement supérieure à 1.

\medskip

\'Ecrire une fonction Python \texttt{moyenne(n)} permettant de simuler $n$ variables aléatoires $X$ et renvoyant leur moyenne, puis tester cette fonction pour des valeurs de $n$ de la forme $n=10^k$ pour $k$ entier de 2 à 7.

\medskip

\textit{Aide:} la fonction \texttt{random()} du module \texttt{random} donne un nombre aléatoire dans l'intervalle \intervFO{0}{1}.

\tcblower

Une fonction possible est la suivante:

\begin{python}
from random import random

def moyenne(n):
    T = 0
    for k in range(n):
        s = 0
        i = 0
        while s < 1:
            s += random()
            i += 1
            
        T += i
    
    return T / n
\end{python}

Pour des valeurs de $n$ de la forme $n=10^k$ pour $k$ entier de 2 à 7, on a alors :

\begin{console}
>>> for n in [ 10**k for k in range(2,8) ]:
    	print( moyenne(n) )
    	
2.83
2.719
2.7393
2.71931
2.718344
2.7186881
\end{console}

\begin{rem}
Il semblerait que cette moyenne converge vers un nombre bien particulier. D'après la loi des grands nombres, ce nombre correspond à $E(X)$, c'est-à-dire le nombre moyen de fois que l'on doit répéter l'expérience $\mathcal{E}$ pour que la somme des nombres choisis au hasard soit strictement supérieure à 1.

Avec du temps, en prenant $n=10^8$, puis $n=10^9$, on trouve :
\begin{console}
2.71829368
2.718286834
\end{console}

Or, $\e\approx2,71828182846$. Alors... Coïncidence ?

\medskip

Pour le savoir, il faudrait pouvoir calculer mathématiquement cette moyenne... Mais en terminale, les outils dont nous disposons ne sont pas assez puissants pour le faire. En effet, obtenir la loi de probabilité de $X$ n'est pas chose aisée... mais on peut le\linebreak démontrer à l'aide d'intégrales multiples (ça, c'est pour les profs!).
\end{rem}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{simulation de lancers de dés}[2]
\begin{enumerate}
\item Compléter la fonction Python suivante afin qu'elle affiche une estimation de la probabilité d'obtenir deux fois de suite le \og 6 \fg{} sur $n$ lancers d'un dé cubique.

\begin{python}
from random import randint

def lancer(n):
    L = []
    c = 0

    for k in range(n):
    	# on insère dans la liste L un nombre entier aléatoire entre 1 et 6
        L.append( randint(1,6) )
        
	...
\end{python} 

\item Exécuter cette fonction pour $n=10^k$, $k$ étant un entier de 2 à 7.

\item Calculer mathématiquement cette probabilité.
\end{enumerate}

\tcblower

\begin{enumerate}
\item Voici une proposition :

\begin{python}
from random import randint
def lancer(n):
    L = []
    c = 0
    for k in range(n):
        L.append( randint(1,6) )
        
    for i in range( len(L)-1 ):
        if L[i] == 6 and L[i+1] == 6:
            c += 1
        
    return c/n
\end{python}

Une autre possibilité (sans liste) est la suivante :

\begin{python}
def lancer(n):
    c = 0
    for k in range(n):
        d = randint(1,6)
        if k > 0:
            if d == 6 and precedent == 6:
                c += 1
        precedent = d
        
    return c/n
\end{python}

Si $k=0$, c'est-à-dire si c'est le premier lancer de dé qui est simulé, on ne fait rien et on affecte à la variable \texttt{precedent} le nombre choisi; il servira de précédent pour le tirage suivant. 

\item Pour $n=10^k$, $k$ étant un entier de 2 à 7, on a:

\begin{console}
>>> for n in [10**k for k in range(2,8)]:
    	print( lancer(n) )
    	
0.04
0.034
0.0281
0.02832
0.02791
0.0277122
\end{console}

\newpage

\item La probabilité d'avoir un 6 suivi d'un 6 est :
\[
\dfrac{1}{6}\times\dfrac{1}{6}\approx0,02777\ldots
\]
Le résultat trouvé à la question précédente est donc cohérent par rapport à cette probabilité.
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{inégalité de concentration}[2]
On considère l'expérience $\mathcal{E}$ consistant à choisir un nombre entier compris entre 1 et 10.

On répète 10 fois de façon indépendante l'expérience $\mathcal{E}$ et on note $X$ la variable aléatoire représentant le nombre de multiples de 3 obtenus lors de ces 10 expériences.

\begin{enumerate}
\item Quelle est la loi suivie par $X$ ?
\item Donner alors $E(X)$ et $\sigma(X)$.

\newpage

\item On répète $n$ fois l'expérience $\mathcal{E}$, $n\in\N*$.
Compléter la fonction Python suivante qui simule ces $n$ expériences et retourne le nombre moyen de multiples de 3 obtenus.


\begin{python}
from random import randint

def simul(n):
    total = 0
    for i in range(n):
        c = 0
        for k in range(10):
            a = randint(1,10)
            if ...:
                c = c + 1
                
        total = ...
            
    return ...
\end{python}

\item À partir de quelle valeur de $n$ peut-on être certain·e·s que la valeur retournée par cette fonction est une approximation de $E(X)$ à $10^{-3}$ près ?
\end{enumerate}

\tcblower

\begin{enumerate}
\item On répète 10 fois de façon indépendante l'expérience $\mathcal{E}$ donc $X$ suit la loi binomiale de paramètres $n=10$ et $p=\dfrac{3}{10}=0,3$ (probabilité d'obtenir un multiple de 3 entre 1 et 10, donc obtenir \og 3 \fg, \og 6 \fg{} ou \og 9 \fg{} sur 10 nombres).

\item D'après le cours, $E(X) = np = 3$ et $\sigma(X)=\sqrt{np(1-p)}\approx1,45$.

\item La fonction dûment complétée est la suivante :

\begin{python}
from random import randint

def simul(n):
    total = 0
    for i in range(n):
        c = 0
        for k in range(10):
            a = randint(1,10)
            if a % 3 == 0:
                c = c + 1
                
        total = total + c
            
    return total / n
\end{python}

\item Notons $X_k$ la variable aléatoire représentant le nombre de multiples de 3 obtenus lors de la simulation $k$, pour $1\leqslant k\leqslant n$.

D'après l'inégalité de concentration,
\[
P\left(\left|\frac{X_1+\cdots+X_n}{n}-\mu\right| \geqslant \delta\right) \leqslant \dfrac{\sigma^2}{n\delta^2}
\]
En prenant $\delta=10^{-3}$, $\mu=3$ et $\sigma=1,45$, cela donne:
\[
P\left(\left|\frac{X_1+\cdots+X_n}{n}-3\right| \geqslant 10^{-3}\right) \leqslant \dfrac{1,45^2}{10^{-6}n}
\]
ou encore:
\[
P\left(\left|\frac{X_1+\cdots+X_n}{n}-3\right| \geqslant 10^{-3}\right) \leqslant \dfrac{1,45^2\times10^{6}}{n}.
\]
Ainsi, choisir $n$ tel que $\dfrac{1,45^2\times10^{6}}{n} \leqslant 10^{-2}$ (par exemple... le seuil $10^{-2}$ est à notre convenance) suffirait, soit $n \geqslant 1,45^2\times10^{8}$.
\end{enumerate}
%\begin{rem}
%L'inégalité de concentration nous donne une condition suffisante sur $n$, mais pas nécessaire. En effet, si on teste le programme pour $n=10^6$, on trouve une valeur de \texttt{2.999021}, qui convient parfaitement à ce que l'on souhaitait.
%
%\medskip
%
%C'est d'ailleurs très souvent le cas: l'inégalité de concentration donne fréquemment une valeur très grande par rapport à la plus petite valeur de $n$ satisfaisant nos conditions. 
%\end{rem}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{inégalité de concentration}[2]
Une expérience $\mathcal{E}_n$ consiste à lancer un dé cubique (six faces) $n$ fois, les lancers étant indépendants les uns des autres.

On note $X$ la variable aléatoire représentant le nombre de chiffres pairs obtenus.

\begin{enumerate}
\item Quelle est la loi de probabilité de $X$ ?
\item Quelle en est alors son espérance et son écart-type?
\item Compléter la fonction Python suivante afin qu'elle simule l'expérience $\mathcal{E}_n$ et renvoie le nombre de chiffres pairs obtenus.
\begin{python}
from random import randint
def simul(n):
    total = ...
    for k in range(...):
        D = ...
        if D ... :
            total = ...  
    return total
\end{python}

\newpage

\item \'Ecrire une fonction Python \texttt{diff(n)} qui retourne la différence entre le nombre de chiffres pairs obtenus et l'espérance de $X$.

Par exemple, si la simulation trouve 512 chiffres pairs sur \numprint{1000} lancers, on devra avoir:
\begin{console}
>>> diff(1000)
12
\end{console}

\item \'Ecrire une fonction Python \texttt{echant(N,n)} qui calcule la moyenne des  résultats renvoyés si on fait appel $N$ fois à la fonction \texttt{diff(n)}.

\item \'Ecrire une fonction Python \texttt{proportion(N)} qui simule $N$ expériences $\mathcal{E}_{\numprint{1000}}$ et qui renvoie la proportion des cas où l'écart entre $m$ et $E(X)$ est inférieur ou égal à $\dfrac{2\sigma(X)}{\sqrt{\numprint{1000}}}$, où $m$ est le nombre moyen de chiffres pairs obtenus lors d'une simulation de \numprint{1000} lancers de dé.
\end{enumerate}  

\tcblower

\begin{enumerate}
\item $X$ suit la loi binomiale de paramètres $n$ (on répète la même expérience $n$ fois de manière indépendante) et $p=\dfrac{3}{6}=\dfrac{1}{2}$ (la probabilité d'obtenir un multiple de 2 à chaque lancer).

\item D'après le cours, 
\[
E(X)=np = \dfrac{1}{2}n
\]
et
\[
\sigma(X)=\sqrt{np(1-p)}=\dfrac{1}{2}\sqrt{n}.
\]

\item La fonction dûment complétée est la suivante:
\begin{python}
from random import randint

def simul(n):
    total = 0
    for k in range(n):
        D = randint(1,6)
        if D % 2 == 0:
            total = total + 1
    
    return total
\end{python}

\item Pour la fonction \texttt{diff(n)} on fait appel à la fonction \texttt{simul(n)}:
\begin{python*}
def diff(n):
    return abs( simul(n) - n/2 )
\end{python*}

\item On peut considérer la fonction suivante:
\begin{python}
def echant(N,n):
    somme = 0
    for k in range(N):
        somme = somme + diff(n)
        
    return somme / N
\end{python}
On obtient par exemple:
\begin{console}
>>> echant(10000,1000)
12.5797
\end{console}

\item Il s'agit ici de faire appel $N$ fois à la fonction \texttt{simul(1000)}, qui retourne une valeur $m$, et à chaque fois, de vérifier si $|E(X)-m|\leqslant\dfrac{2\sigma(X)}{\sqrt{\numprint{1000}}}$, auquel cas on devra incrémenter un compteur (que l'on va nommer \texttt{somme}).

À l'issue de ces $N$ simulations, on calculera $\dfrac{\texttt{compteur}}{N}\times100$ qui sera le pourcentage de cas où l'on a obtenu une différence plus petite que la borne supérieure $\dfrac{2\sigma(X)}{\sqrt{\numprint{1000}}}$.

On obtient alors la fonction suivante:

\begin{python}
def proportion(N):
    n = 1000
    mu = 500
    sigma = 250
    borne_sup = 2*sigma/(n**0.5)
    
    compteur = 0
    for k in range(N):
        if abs( mu - simul(n) ) <= borne_sup:
            compteur = compteur + 1
        
    return compteur * 100 / N
\end{python} 

Cela donne par exemple:
\begin{console}
>>> proportion(1000)
65.8
>>> proportion(1000)
67.5
>>> proportion(1000)
68.5
>>> proportion(1000)
67.9
\end{console}
\end{enumerate}
\end{exocor}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\corriges
