<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Algo - Calculs de surface et autres calculs
C'est l'histoire d'une boucle, puis d'une autre, puis enfin d'un couple de boucles, voire d'un triplé.
Step1:  Enoncé
Exercice 1 
Step2:  1.1 En utilisant la constante pi
1.2 Sans utiliser pi ni aucune autre fonction
Donc juste des additions, des multiplications, des divisions. On a le droit aux boucles aussi.
Exercice 2 
Step3:  1.2. calcul de la surface d'un cercle sans pi ou autre fonction
Une approche possible est probabiliste 
Step4:  2. tri aléatoire
Step5:  Et si i > j, on ne fait rien et c'est bien dommage.
Step6:  Le résultat n'est pas forcément meilleur mais il est plus rapide à obtenir puisqu'on fait un test en moins.
Et si on s'arrête quand cinq permutations aléatoires de suite ne mènen à aucune permutations dans le tableau.
Step7:  3. petits calculs parfaits pour une machine
<ASSISTANT_TASK:>
Python Code:
from jyquickhelper import add_notebook_menu
add_notebook_menu()
Explanation: Algo - Calculs de surface et autres calculs
C'est l'histoire d'une boucle, puis d'une autre, puis enfin d'un couple de boucles, voire d'un triplé.
End of explanation
def surface_cerle(r):
    # ...
    return 0.
Explanation: Enoncé
Exercice 1 : calcul de la surface d'un cercle
On cherche à écrire une fonction qui calcule la surface d'un cercle de rayon r.
End of explanation
from math import pi
def surface_cercle(r):
    return r ** 2 * pi
surface_cercle(5)
Explanation: 1.1 En utilisant la constante pi
1.2 Sans utiliser pi ni aucune autre fonction
Donc juste des additions, des multiplications, des divisions. On a le droit aux boucles aussi.
Exercice 2 : tri aléatoire
On implémente le tri suivant (est-ce vraiment un tri d'ailleurs ?) :
Dans un tableau T, on tire deux élements aléatoires i < j, si T[i] > T[j], on les permute.
On s'arrête après n tirages sans permutations.
Exercice 3 : petits calculs parfaits pour une machine
On suppose que le tableau précédent est de taille n=10, l'algorithme précédent s'arrête après n tirages sans permutations. Comment choisir n de telle sorte que le tableau finisse trié dans 90% des cas...
Réponses
1.1. calcul de la surface d'un cercle avec pi
End of explanation
import numpy
def estimation_pi(n=10000):
    rnd = numpy.random.rand(1000, 2)
    norme = rnd[:, 0] ** 2 + rnd[:, 1] ** 2
    dedans = norme <= 1
    dedans_entier = dedans.astype(numpy.int64)
    return dedans_entier.sum() / dedans.shape[0] * 4
pi = estimation_pi()
pi
def surface_cercle_pi(r, pi):
    return r ** 2 * pi
surface_cercle_pi(5, pi)
Explanation: 1.2. calcul de la surface d'un cercle sans pi ou autre fonction
Une approche possible est probabiliste : on construit un estimateur de $\pi$ en tirant aléatoirement des points dans un carré de côté 1. Si le point $P_i$ tombe dans le quart de cercle inscrit dans le carré, on compte 1, sinon on compte 0. Donc:
$$\frac{1}{n} \sum_{i=1}^n \mathbb{1}_{\Vert P_i \Vert^2 \leqslant 1} \rightarrow \frac{\pi}{4}$$
Ce ratio converge vers la probabilité pour le point $P_i$ de tomber dans le quart de cercle, qui est égale au ratio des deux aires : $\frac{\pi r^2}{r^2}$ avec $ r=1$.
End of explanation
def tri_alea(T, n=1000):
    T = T.copy()
    for i in range(0, n):
        i, j = numpy.random.randint(0, len(T), 2)
        if i < j and T[i] > T[j]:
            T[i], T[j] = T[j], T[i]
    return T
tableau = [1, 3, 4, 5, 3, 2, 7, 11, 10, 9, 8, 0]
tri_alea(tableau)
Explanation: 2. tri aléatoire
End of explanation
def tri_alea2(T, n=1000):
    T = T.copy()
    for i in range(0, n):
        i = numpy.random.randint(0, len(T) - 1)
        j = numpy.random.randint(i + 1, len(T))
        if T[i] > T[j]:
            T[i], T[j] = T[j], T[i]
    return T
tableau = [1, 3, 4, 5, 3, 2, 7, 11, 10, 9, 8, 0]
tri_alea2(tableau)
Explanation: Et si i > j, on ne fait rien et c'est bien dommage.
End of explanation
def tri_alea3(T, c=100):
    T = T.copy()
    compteur = 0
    while compteur < c:
        i = numpy.random.randint(0, len(T) - 1)
        j = numpy.random.randint(i + 1, len(T))
        if T[i] > T[j]:
            T[i], T[j] = T[j], T[i]
            compteur = 0
        else:
            compteur += 1
    return T
tableau = [1, 3, 4, 5, 3, 2, 7, 11, 10, 9, 8, 0]
tri_alea3(tableau)
Explanation: Le résultat n'est pas forcément meilleur mais il est plus rapide à obtenir puisqu'on fait un test en moins.
Et si on s'arrête quand cinq permutations aléatoires de suite ne mènen à aucune permutations dans le tableau.
End of explanation
def est_trie(T):
    for i in range(1, len(T)):
        if T[i] < T[i-1]:
            return False
    return True
def eval_c(n, c, N=100):
    compteur = 0
    for i in range(N):
        T = numpy.random.randint(0, 20, n)
        T2 = tri_alea3(T, c=c)
        if est_trie(T2):
            compteur += 1
    return compteur * 1. / N
eval_c(10, 100)
from tqdm import tqdm  # pour afficher une barre de défilement
cs = []
ecs = []
for c in tqdm(range(1, 251, 25)):
    cs.append(c)
    ecs.append(eval_c(10, c=c))
    
ecs[-5:]
%matplotlib inline
import matplotlib.pyplot as plt
plt.plot(cs, ecs)
plt.plot([0, max(cs)], [0.9, 0.9], '--');
Explanation: 3. petits calculs parfaits pour une machine
End of explanation
<END_TASK>