Cours 6 : Correction de l'exercice du précédent cours (disponible ici)

Question 1

Écrivez une fonction generer_sommets(n) qui prend en paramètre la taille $n$ (ici, $n = 12$) et retourne une liste de tous les sommets sous forme de tuples $(i, j)$ avec $0 \leq i, j < n$.

Exemple d'appel :

sommets = generer_sommets(12)
print(len(sommets))  # Devrait afficher 144

def generer_sommets(n):
    L=[]
    for i in range (n):
        for j in range(n):
            L.append((i,j))
    return L

def generer_sommets2(n):
    return [(i,j) for i in range (n) for j in range (n)]

>>> a = [(i,j) for i in range (10) for j in range (10)]
>>> b = [(i,j) for j in range (10) for i in range (10)]
>>> c = [[(i,j) for i in range (10)] for j in range (10)]
>>> d = [[(i,j) for j in range (10)] for i in range (10)]

>>> a[15]
(1, 5)
>>> b[15]
(5, 1)
>>> c[4][5]
(5, 4)
>>> d[4][5]
(4, 5)

Question 2

Écrivez une fonction voisins_potentiels(sommet, n) qui prend un sommet $(i, j)$ et la taille $n$, et retourne une liste des voisins potentiels valides (dans la grille), sans considérer s'ils sont conducteurs.

• Utilisez les règles du pavage hexagonal décrites ci-dessus.
• Vérifiez que chaque voisin potentiel est dans les bornes $[0, n-1] \times [0, n-1]$.

Exemple :

print(voisins_potentiels((0, 0), 15))  # Devrait retourner [(1, 0), (0, 1)]
print(voisins_potentiels((6, 6), 12))  # Devrait retourner 6 voisins pour un sommet intérieur

Pas de prob;ème pour cette question.

def voisins_potentiels(sommet,n):
    L=[]
    (i,j)= sommet
    if j%2==0:
        L.append((i-1,j+1))
        L.append((i,j+1))
        L.append((i-1,j-1))
        L.append((i,j-1))
    else:
        L.append((i,j+1))
        L.append((i+1,j-1))
        L.append((i,j-1))
        L.append((i+1,j-1))
    L.append((i-1,j))
    L.append((i+1,j))
    V=[]
    for voisins in L:
        if voisins[0]>=0 and voisins[0]<n and voisins[1]>=0 and voisins[1]<n:
            V.append(voisins)
    return V

       
print(voisins_potentiels((0, 0), 15))  # Devrait retourner [(1, 0), (0, 1)]
print(voisins_potentiels((6, 6), 12))  # Devrait retourner 6 voisins pour un sommet intérieur

Question 3

Écrivez une fonction generer_conducteurs(sommets, p) qui prend la liste des sommets et une probabilité $p$ (entre 0 et 1), et retourne un ensemble (set) des sommets conducteurs. Chaque sommet est choisi indépendamment comme conducteur avec probabilité $p$, en utilisant random.random().

Exemple :

import random
conducteurs = generer_conducteurs(generer_sommets(12), 0.5)
print(len(conducteurs))  # Environ 72 (aléatoire)

Pas de problème pour cette question non plus, bonne utilisation de la bibliothèque random.

import random      
       
def generer_conducteurs(sommets,p):
    L= set([])
    for i in sommets:
        aleatoire = random.random()
        if p >= aleatoire :
            L.add(i)
    return L

conducteurs = generer_conducteurs(generer_sommets(12), 0.5)
print((0,0) in conducteurs)

Question 4

Écrivez une fonction construire_graphe(conducteurs, n) qui prend l'ensemble des conducteurs et la taille $n$, et retourne un dictionnaire d'adjacence où :

• Les clés sont les sommets conducteurs.
• Les valeurs sont des listes de voisins conducteurs (utilisez voisins_potentiels pour filtrer).

Exemple :

graphe = construire_graphe(conducteurs, 12)
print(graphe.get((0, 0), []))  # Liste des voisins conducteurs >de (0, 0), si (0, 0) est conducteur

Pareil, pas de soucis.

def construire_graphe(conducteurs,n):
    dico={}
    for i in conducteurs:
        L=[]
        voisins=voisins_potentiels(i, n)
        for j in voisins:
            if j in conducteurs:
                L.append(j)
        dico[i]= L
    return dico
   
graphe = construire_graphe(conducteurs, 12)
print(graphe.get((0, 0), []))  # Liste des voisins conducteurs de (0, 0)

Question 5

Écrivez une fonction percolation_bas_haut(graphe, n) qui vérifie s'il existe un chemin connecté du bas (ligne $j = 0$) vers le haut (ligne $j = n-1$) dans le graphe.

• Utilisez une recherche en largeur (BFS) ou en profondeur (DFS) pour explorer à partir de tous les sommets conducteurs en bas ($j = 0$).
• Retournez True si au moins un sommet en haut ($j = n-1$) est atteignable, sinon False.
• Utilisez une file (queue) pour BFS, et un ensemble pour les visités.

Bon, malheureusement, c'est à l'avant dernière question que les problèmes ont commencé.

On a essayé beaucoup de choses en récursif mais rien n'a marché.

Pour la correction je propose de faire ça en deux temps:

1. Premièrement, contruire la fonction de parcours de graphe (facile, on enregistre les sommets visités, et les sommets à visiter dans une pile (profondeur) ou dans une file (largeur))
2. On répond à la question (facile aussi !)

def parcourir(graphe, sommet, profondeur = True):
    a_visiter = [sommet]
    deja_visite = []
    while a_visiter != []:

        s = a_visiter.pop() if profondeur else a_visiter.pop(0)

        if s[1]==n-1:
            return True
        voisins = graphe[s]
        for voisin in voisins:
            if voisin not in deja_visite:
                a_visiter.append(voisin)
    return False

def percolation_bas_haut(graphe,n):
    for i in range(n):
        if parcourir(graphe,(i,0)):
            return True
    return False

Question 6 (bonus)

Écrivez un script principal qui simule 100 fois le processus pour différentes valeurs de $p$ (par exemple, de 0.4 à 0.7 par pas de 0.05), et calcule la proportion de simulations où la percolation ocurre. Affichez les résultats pour estimer le seuil (sur un réseau hexagonal, il est théoriquement autour de 0.5 pour la percolation de sites, mais varie avec la taille).

Cette question nous a permis d'utiliser plt.plot(X, Y) suivi de plt.show() (hyper simple à utiliser):

import matplotlib.pyplot as plt
import numpy as np
E=np.linspace(0, 1, 100)
S=[]


n = 12
simulations = 100
for p in E:
    succes = 0
    for _ in range(simulations):
        sommets = generer_sommets(n)
        conducteurs = generer_conducteurs(sommets, p)
        graphe = construire_graphe(conducteurs, n)
        if percolation_bas_haut(graphe, n):
            succes += 1
    # print(f"Pour p={p}, proportion de percolation : {succes / simulations}")
    S.append(succes/simulations)    

plt.plot(E, S)
plt.show()

Résultats

Voici les résultats de tout ce qui précède:

Q1:
144
Q2:
[(0, 1), (1, 0)]
[(5, 7), (6, 7), (5, 5), (6, 5), (5, 6), (7, 6)]
Q3:
True
Q4:
[(1, 0)]