TP noté n°3 : Percolation

In [1]:

import numpy as np
import matplotlib.pyplot as plt
import random as rd
from matplotlib.colors import ListedColormap

Exercice 1

Plusieurs versions sont possibles :

In [2]:

def creation_grille(p, n):
    M = [[0 for j in range(n)] for i in range(n)]
    for i in range(n):
        for j in range(n):
            if rd.random() < p:
                M[i][j] = 2
    return M

Dans la version précédente, il y a trop de parcours de boucles...

In [3]:

def creation_grille(p, n):
    M=[]
    for i in range(n):
        L=[]
        for j in range(n):
            if rd.random()<p:
                L.append(2)
            else:
                L.append(0)
        M.append(L)
    return M

Sinon, on peut également adapter ce que l'on avait fait avec les images :

In [4]:

def coeff(p):
    if rd.random()<p:
        return 2
    else:
        return 0

In [5]:

def creation_grille(p, n):
    return [[coeff(p) for j in range(n)] for i in range(n)]

Pendant qu'on y est, avec les listes par compréhension :

In [6]:

def creation_grille(p, n):
    return [[2 if rd.random()<p else 0 for j in range(n)] for i in range(n)]

Et ma petite préférée :

In [7]:

def creation_grille(p, n):
    assert 0 < p < 1
    return [[2 * int(rd.random() < p) for j in range(n)] for i in range(n)]

Exercice 2

In [8]:

echelle = ListedColormap(['black', 'aqua', 'white'])

In [9]:

def afficher(C):
    plt.imshow(C, cmap = echelle)
    plt.xticks([])
    plt.yticks([])
    plt.show()
    return None

In [10]:

C = creation_grille(0.5, 10)
afficher(C)

In [11]:

C = creation_grille(0.8, 10)
afficher(C)

Exercice 3

In [12]:

def first_line(C):
    return [(0, j) for j in range(len(C)) if C[0][j]]

In [13]:

C = creation_grille(0.8, 10)
afficher(C)

In [14]:

first_line(C)

Out[14]:

[(0, 0), (0, 1), (0, 2), (0, 4), (0, 5), (0, 6), (0, 9)]

Exercice 4

In [15]:

def remplir(C, L, i, j):
    if C[i][j] == 2:
        C[i][j] = 1
        L.append((i, j))
    return None

Exercice 5

In [16]:

def percolation(C):
    n = len(C)
    L = first_line(C)
    for case in L:
        C[0][case[1]] = 1
    while len(L) > 0:
        i, j = L.pop()
        if j > 0:
            remplir(C, L, i, j - 1)
        if j < n - 1:
            remplir(C, L, i, j + 1)
        if i > 0:
            remplir(C, L, i - 1, j)
        if i < n - 1:
            remplir(C, L, i + 1, j)
    return None

Exercice 6

In [17]:

C = creation_grille(0.6, 64)
afficher(C)

In [18]:

percolation(C)
afficher(C)

Exercice 7

In [19]:

def reussite(C):
    n = len(C)
    for j in range(n):
        if C[-1][j] == 1:
            return True
    return False

In [20]:

C = creation_grille(0.6, 10)
percolation(C)
reussite(C)

Out[20]:

False

Exercice 8

In [21]:

def P(p):
    cpt = 0
    for k in range(100):
        C = creation_grille(p, 64)
        percolation(C)
        if reussite(C):
            cpt += 1
    return cpt / 100

In [22]:

P(0.8)

Out[22]:

1.0

Exercice 9

In [23]:

X = np.linspace(1e-3, 1 - 1e-3, 100)
Y = [P(p) for p in X]
plt.plot(X, Y)
plt.show()

Exercice 10

In [24]:

def seuil(a, b):
    mil = (a + b) / 2
    proba = P(mil)
    if proba < 0.4:
        return seuil(mil, b)
    elif proba > 0.6:
        return seuil(a, mil)
    else:
        return mil

Exercice 11

In [25]:

seuil(0,1)

Out[25]:

0.59375

Exercice 12

In [26]:

def seuil2():
    a, b, mil = 0, 1, 0.5
    proba = P(mil)
    while abs(proba - 0.5) >= 0.1:
        if proba < 0.4:
            a = mil
        elif proba > 0.6:
            b = mil
        mil = (a + b) / 2
        proba = P(mil)
    return mil

In [27]:

seuil2()

Out[27]:

0.59375

Remarque :

L'existence et l'unicité de $q_0 \in [0,1]$ est assurée par le théorème de la bijection.

Montrons que «$q_0\in [a,b]$» est un invariant de boucle.

Avant la boucle, on a $[a,b]=[0,1]$, donc $q_0\in [a,b]$ est bien vérifié.
Supposons que l'on ait $q_0\in [a,b]$ au début d'une itération. On note $a'$ et $b'$ les valeurs de $a$ et $b$ à la fin de l'itération.
Si $P(mil)<0.4$, alors $a'=mil = \frac{a+b}{2}$ et $b'=b$. Dans ce cas, $P(mil)<0.4<0.5 = P(q_0)$ donc (puisque $P$ est strictement croissante) $mil \leqslant q_0$, donc on a bien $q_0 \in [a',b']$.
Le second cas est similaire.

On a donc bien démontré que «$q_0\in [a,b]$» est un invariant de la boucle while.