Algo - Calculs de surface et autres calculs#

Links: notebook, html, python, slides, GitHub

C’est l’histoire d’une boucle, puis d’une autre, puis enfin d’un couple de boucles, voire d’un triplé.

from jyquickhelper import add_notebook_menu
add_notebook_menu()

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.

def surface_cerle(r):
    # ...
    return 0.

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#

from math import pi


def surface_cercle(r):
    return r ** 2 * pi

surface_cercle(5)
78.53981633974483

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 \mathbf{1\!\!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$.

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
3.112
def surface_cercle_pi(r, pi):
    return r ** 2 * pi

surface_cercle_pi(5, pi)
77.8

2. tri aléatoire#

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)
[0, 1, 2, 3, 3, 4, 5, 7, 8, 9, 10, 11]

Et si i > j, on ne fait rien et c’est bien dommage.

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)
[0, 1, 2, 3, 3, 4, 5, 7, 8, 9, 10, 11]

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.

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)
[0, 1, 2, 3, 3, 4, 5, 7, 8, 9, 10, 11]

3. petits calculs parfaits pour une machine#

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)
0.81
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:]
100%|██████████| 10/10 [00:01<00:00,  5.77it/s]
[0.89, 0.91, 0.98, 0.96, 0.98]
%matplotlib inline
import matplotlib.pyplot as plt
plt.plot(cs, ecs)
plt.plot([0, max(cs)], [0.9, 0.9], '--');
../_images/2020_surface_29_0.png

La réponse se situe aux alentours de 150, on ne peut pas dire précisément car tout est aléatoire, on peut seulement estimer la distribution de ce résultat qui est aussi une variable aléatoire. Cette réponse dépend de la taille du tableau à tirer.