NSI Bac: Correction complète d'un exercice graphes et virus en Python
💻 Bac NSI 2024 - Correction de l'exercice sur les graphes et les virus : comprendre, coder et réviser intelligemment !
Ce sujet de spécialité NSI (Numérique et Sciences Informatiques) du bac 2024 pour les centres étrangers proposait un exercice fascinant : lutter contre un virus informatique via des parcours aléatoires sur un réseau modélisé en graphe.
Cet post vous propose une correction détaillée, commentée, et enrichie de rappels de cours pour réviser efficacement les notions essentielles de terminale NSI : graphes, programmation récursive, simulations, et propagation sur réseau. 🧠💡
🎯 Objectif : Protéger le réseau avec des moyens limités
On modélise un réseau de 6 ordinateurs numérotés de 0 à 5. Le virus se déplace au hasard d’un ordinateur à un autre, en suivant les connexions définies dans un graphe.
Le but est de comprendre le comportement probabiliste du virus pour protéger les nœuds les plus vulnérables.
✅ Étape 1 : Représenter le réseau (graphe)
Représentation en liste de voisins :
voisins = [
[1, 2, 3, 4, 5], # ordinateur 0
[0, 2, 3], # ordinateur 1
[0, 1, 5], # ordinateur 2
[0, 1], # ordinateur 3
[0], # ordinateur 4
[0, 2] # ordinateur 5
]
👉 Compétence révisée : représentation des graphes par liste d’adjacence (programme NSI Terminale, thème "Structures de données").
🎲 Étape 2 : Choisir un voisin au hasard
Complétons la fonction :
import random
def voisin_alea(voisins, s):
return random.choice(voisins[s])
👉 Utilisation de random.choice, plus lisible que randrange.
🔁 Étape 3 : Comprendre la récursivité avec marche_alea
def marche_alea(voisins, i, n):
if n == 0:
return i
return marche_alea(voisins, voisin_alea(voisins, i), n - 1)
📌 Cette fonction est récursive car elle s'appelle elle-même jusqu'à atteindre le cas de base n == 0.
📌 Elle modélise le déplacement aléatoire du virus d’un nœud à un autre, pendant n étapes.
👉 Compétence révisée : récursivité, modélisation d’un phénomène stochastique (programme NSI Terminale, thème "Langages et programmation").
🧪 Étape 4 : Simuler les déplacements
Complétons la fonction simule :
def simule(voisins, i, n_tests, n_pas):
results = [0] * len(voisins)
for _ in range(n_tests):
final_node = marche_alea(voisins, i, n_pas)
results[final_node] += 1
return [x / n_tests for x in results]
📊 Interprétation de la sortie [0.328, 0.195, 0.18, 0.12, 0.059, 0.118] : l’ordinateur 0 est le plus fréquemment atteint à la fin → à protéger en priorité !
👉 Compétence révisée : simulation probabiliste, analyse statistique de résultats.
🦠 Étape 5 : Propagation d’un virus (modèle de diffusion)
On simule la propagation du virus : à chaque étape, il contamine tous les voisins non contaminés.
def temps_propagation(voisins, s):
visites = set([s])
a_traiter = [s]
temps = 0
while len(visites) < len(voisins):
suivants = []
for noeud in a_traiter:
for voisin in voisins[noeud]:
if voisin not in visites:
visites.add(voisin)
suivants.append(voisin)
a_traiter = suivants
temps += 1
return temps
💡 Cette fonction implémente un parcours en largeur pour simuler la contamination complète du réseau.
👉 Compétence révisée : algorithmes sur les graphes, BFS (Breadth-First Search).
📚 Notions clés révisées dans cet exercice
| Notion | Description |
|---|---|
| Graphe | Modélisation d’un réseau par liste de voisins |
| Récursivité | Fonction qui s'appelle elle-même pour modéliser un processus |
| Parcours aléatoire | Déplacement stochastique sur un graphe |
| Simulation | Expérience répétée pour estimer des probabilités |
| Propagation | Utilisation de parcours en largeur |
| Python | Structures : listes, fonctions, modules (random), boucles |
🧠 Ce que tu dois retenir pour le bac NSI
-
Savoir modéliser un réseau avec des graphes (listes d’adjacence).
-
Savoir coder une fonction récursive simple.
-
Savoir utiliser des bibliothèques Python comme
random. -
Savoir simuler un processus et analyser des résultats statistiques.
-
Savoir implémenter un algorithme de propagation (BFS).
✍️ Entraînement conseillé
👉 Refais cet exercice avec d’autres graphes que tu inventes.
👉 Modifie les probabilités, change les règles du virus (par ex. propagation partielle), observe les changements.
👉 Code une version avec visualisation (module matplotlib ou networkx).
Commentaires