4 Nouveaux Travaux Dirigés d'Informatique (Python)

Date de génération : 2025-10-27

TD 1 : Algorithmes Génétiques et le Problème du Voyageur de

Commerce

Objectifs

Comprendre les principes des algorithmes génétiques (population, fitness, sélection,

croisement, mutation).

Modéliser le Problème du Voyageur de Commerce (PVC).

Implémenter un algorithme génétique en Python pour trouver une solution approchée

au PVC.

Visualiser les résultats (trajets et convergence) avec la bibliothèque matplotlib .

Prérequis

Connaissances de base en Python (listes, fonctions, classes). Notions d'algorithmique.

Installation des bibliothèques numpy et matplotlib .

pip install numpy matplotlib

Introduction
Le Problème du Voyageur de Commerce (PVC) est un problème d'optimisation célèbre : étant
donné un ensemble de villes et les distances entre chaque paire de villes, quel est le plus
court chemin possible qui visite chaque ville exactement une fois et retourne à la ville de
départ ? Ce problème est NP-difficile, ce qui signifie qu'aucune méthode exacte n'est connue
pour le résoudre efficacement pour un grand nombre de villes. Nous allons explorer une
approche heuristique, les algorithmes génétiques, qui s'inspirent de la théorie de l'évolution
de Darwin pour trouver de très bonnes solutions approchées.

Partie 1 : Modélisation du problème

1. Représentation des villes et d'un trajet :

Un trajet peut être vu comme une permutation des villes. Nous représenterons un
ensemble de N villes par leurs coordonnées (x, y) dans un plan. Un trajet sera une liste
d'indices de villes, par exemple [0, 3, 1, 2] pour 4 villes.

Écrire une fonction generer_villes(N) qui retourne un tableau NumPy de taille (N, 2)
contenant les coordonnées aléatoires de N villes dans le carré [0, 100] x [0, 100].

2. Calcul de la distance :

Écrire une fonction calculer_distance_totale(trajet, villes) qui prend un

trajet (liste d'indices) et le tableau des coordonnées des villes, et retourne la distance
euclidienne totale du parcours, en n'oubliant pas le retour au point de départ.

La distance entre deux points (x1, y1) et (x2, y2) est sqrt((x1-x2)² + (y1-y2)²) .

Partie 2 : Les briques de l'algorithme génétique

3. Population initiale :

Un algorithme génétique travaille sur une "population" de solutions potentielles. Écrire une
fonction creer_population(taille_pop, N_villes) qui génère une liste de
taille_pop trajets aléatoires.

Pour chaque trajet, il s'agit de créer une permutation aléatoire des entiers de 0 à N-1.
Utilisez [Link] .

4. Fonction de fitness :

La "fitness" (ou aptitude) d'un individu (un trajet) mesure sa qualité. Dans notre cas, plus le
trajet est court, meilleure est la fitness. On peut définir fitness = 1 /
 distance_totale . Écrire une fonction evaluer_population(population,
villes) qui retourne une liste des scores de fitness pour chaque trajet de la population.

5. Sélection :

La sélection choisit les "parents" qui vont se reproduire. Une méthode courante est la
sélection par tournoi. Écrire une fonction selection_tournoi(population,
fitness, k) qui sélectionne un individu en :

a. Choisissant k individus au hasard dans la population.

b. Retournant le meilleur de ces k individus (celui avec la plus haute fitness).

6. Croisement (Crossover) :

Le croisement combine deux parents pour créer un ou deux enfants. Pour le PVC, un
simple croisement point à point casserait la validité du trajet (villes dupliquées ou
manquantes). Nous utiliserons le croisement ordonné (OX1).

Écrire une fonction croisement_ordonne(parent1, parent2) qui :

a. Choisit deux points de coupe aléatoires, start et end .

b. Copie le segment du parent1 entre start et end dans l'enfant.

c. Remplit le reste de l'enfant avec les villes du parent2 , dans l'ordre où elles
apparaissent, en ignorant celles déjà présentes.

7. Mutation :

La mutation introduit de la diversité. Écrire une fonction mutation_swap(trajet,

taux_mutation) qui, avec une probabilité taux_mutation , échange deux villes
choisies au hasard dans le trajet.

Partie 3 : Simulation et visualisation

8. Boucle principale de l'algorithme :

Écrire une fonction evoluer_population(population, villes, taux_mutation)

qui crée la génération suivante :

a. Initialiser une nouvelle population vide.

b. Tant que la nouvelle population n'est pas pleine :

Sélectionner deux parents (par tournoi).
 Créer un enfant par croisement.

Appliquer une mutation à l'enfant.

Ajouter l'enfant à la nouvelle population.

c. Retourner la nouvelle population.

9. Lancement de la simulation :

Écrire le script principal qui :

a. Définit les paramètres : N_VILLES = 30 , TAILLE_POP = 100 , N_GENERATIONS =

500 , TAUX_MUTATION = 0.02 .

b. Génère les villes et la population initiale.

c. Itère sur N_GENERATIONS , en faisant évoluer la population à chaque étape.

d. Conserve à chaque génération le meilleur trajet trouvé et sa distance.

10. Visualisation :

Utiliser [Link] pour :

a. Afficher le meilleur trajet initial et le meilleur trajet final.

b. Tracer un graphique montrant l'évolution de la meilleure distance au fil des générations.

Analysez la courbe de convergence.

TD 2 : Simulation de Systèmes Dynamiques - Modèle Proie-

Prédateur

Objectifs

Comprendre les équations de Lotka-Volterra qui modélisent la dynamique des

populations proie-prédateur.

Implémenter un solveur numérique simple pour un système d'équations différentielles

(méthode d'Euler).
 Simuler et visualiser l'évolution des populations.

Analyser les résultats, notamment le portrait de phase du système.

Prérequis

Bases de Python, numpy et matplotlib . Notions d'analyse (dérivées, équations

différentielles).

Introduction

Le modèle de Lotka-Volterra est un système de deux équations différentielles non-linéaires

qui décrit la dynamique de populations biologiques, par exemple des lapins (proies) et des
renards (prédateurs). Soit 𝑥(𝑡) le nombre de proies et 𝑦(𝑡) le nombre de prédateurs à l'instant 𝑡.
Les équations sont :

dx/dt = αx - βxy (Évolution des proies)

dy/dt = δxy - γy (Évolution des prédateurs)

α : Taux de reproduction des proies.

β : Taux de prédation (efficacité des prédateurs).

δ : Taux de reproduction des prédateurs (dépendant des proies mangées).

γ : Taux de mortalité des prédateurs.

Nous allons résoudre numériquement ce système pour observer les cycles caractéristiques
de ces populations.

Partie 1 : Discrétisation du modèle

1. Méthode d'Euler explicite :

Pour résoudre numériquement ce système, on peut discrétiser le temps avec un pas ℎ. La

dérivée 𝑑𝑥/𝑑𝑡 peut être approchée par (𝑥(𝑡+ℎ) - 𝑥(𝑡))/ℎ. En réarrangeant, on obtient la
méthode d'Euler :

𝑥(𝑡+ℎ) = 𝑥(𝑡) + ℎ * (α𝑥(𝑡) - β𝑥(𝑡)𝑦(𝑡))

 Donner l'expression similaire pour 𝑦(𝑡+ℎ).

2. Implémentation du pas de calcul :

Écrire une fonction pas_euler(x, y, alpha, beta, delta, gamma, h) qui prend
les populations actuelles x et y , les paramètres du modèle et le pas de temps h , et
retourne les nouvelles populations x_new et y_new après un pas de temps.

Partie 2 : Simulation temporelle

3. Mise en place de la simulation :

Écrire une fonction simuler(x0, y0, params, t_max, h) qui :

a. Prend en entrée les populations initiales ( x0 , y0 ), un dictionnaire params

contenant les valeurs de α, β, δ, γ, la durée totale t_max et le pas de temps h .

b. Initialise des listes ou tableaux NumPy pour stocker l'historique des populations
( x_hist , y_hist ) et du temps ( t_hist ).

c. Itère de 𝑡=0 à 𝑡= t_max en appliquant la fonction pas_euler à chaque étape et en

stockant les résultats.

d. Retourne les trois listes/tableaux ( t_hist , x_hist , y_hist ).

4. Lancement et visualisation :

Choisissez des valeurs pour les paramètres (par exemple : alpha=1.1, beta=0.4,
delta=0.1, gamma=0.4 ), des conditions initiales ( x0=10, y0=5 ), une durée
t_max=100 et un pas h=0.01 .

Lancez la simulation et utilisez matplotlib pour tracer 𝑥(𝑡) et 𝑦(𝑡) sur le même
graphique. Que remarquez-vous ? Décrivez le comportement cyclique et le déphasage
entre les deux populations.

Partie 3 : Analyse dans l'espace des phases

5. Portrait de phase :

Le comportement d'un système dynamique est souvent étudié dans "l'espace des phases",
où l'on trace une variable en fonction de l'autre (ici, 𝑦 en fonction de 𝑥). Chaque point de la
courbe représente l'état du système (nombre de proies, nombre de prédateurs) à un instant
𝑡.
 En utilisant les résultats de la simulation précédente, tracez le graphique de y_hist en
fonction de x_hist . Qu'observez-vous ? Comment interpréter cette trajectoire fermée ?

6. Points d'équilibre :

Les points d'équilibre (ou points fixes) du système sont les points (𝑥, 𝑦) pour lesquels les
populations ne varient plus, c'est-à-dire 𝑑𝑥/𝑑𝑡 = 0 et 𝑑𝑦/𝑑𝑡 = 0.

Calculez analytiquement les coordonnées des deux points d'équilibre de ce système. L'un
est trivial (extinction des deux espèces), l'autre est non-trivial. Affichez ces points sur votre
portrait de phase. Que représente le point d'équilibre non-trivial au centre de la trajectoire ?

7. Influence des conditions initiales :

Relancez la simulation avec différentes conditions initiales (par exemple, x0=20, y0=10 )
mais les mêmes paramètres. Superposez la nouvelle trajectoire de phase sur le graphique
précédent. Que constatez-vous ? Le système est-il stable ?

TD 3 : Traitement d'Image - Détection de Contours par

Convolution

Objectifs

Comprendre comment une image est représentée numériquement.

Implémenter l'opération de convolution 2D.

Appliquer des filtres (noyaux de convolution) spécifiques pour la détection de contours

(filtres de Sobel).

Visualiser les étapes du traitement d'image.

Prérequis
 Python, numpy , matplotlib et Pillow (ou scikit-image ).

pip install numpy matplotlib Pillow scikit-image

Introduction

La détection de contours est une étape fondamentale en vision par ordinateur. Elle vise à
identifier les points d'une image où l'intensité lumineuse change brusquement. Ces points
forment souvent les bords des objets. Une technique classique pour cela est l'utilisation de
filtres de convolution. Une convolution consiste à faire glisser un petit masque (appelé
"noyau" ou "kernel") sur l'image et à calculer une somme pondérée des pixels sous ce
masque.

Partie 1 : Manipulation d'images

1. Chargement et conversion :

Trouvez une image de votre choix sur internet. Écrire un script qui :

a. Charge l'image en utilisant Pillow ( from PIL import Image ).

b. La convertit en niveaux de gris ( [Link]('L') ).

c. La transforme en un tableau NumPy ( [Link](image_grayscale) ).

d. Affiche l'image en niveaux de gris avec [Link] en utilisant la

carte de couleurs cmap='gray' .

Quelle est la forme (shape) du tableau NumPy obtenu ? Que représentent les valeurs qu'il
contient ?

Partie 2 : Implémentation de la convolution 2D

2. Le principe de la convolution :

Pour un pixel donné, la valeur de sortie est la somme des produits des pixels du voisinage
par les coefficients correspondants du noyau. L'opération est répétée pour chaque pixel de
l'image.
 Écrire une fonction convolution2d(image, noyau) qui prend une image (tableau 2D
NumPy) et un noyau (tableau 2D NumPy, typiquement 3x3) et retourne l'image convoluée.
Attention : La gestion des bords peut être simplifiée en ne calculant pas la convolution sur
les pixels du bord (l'image de sortie sera légèrement plus petite) ou en utilisant un
"padding" (remplissage).

3. Application d'un filtre simple :

Testez votre fonction avec un filtre de moyenne (flou) :

noyau_flou = [Link]([[1, 1, 1], [1, 1, 1], [1, 1, 1]]) / 9.0

Appliquez ce filtre à votre image en niveaux de gris et affichez le résultat. L'image est-elle
plus nette ou plus floue ? Pourquoi ?

Partie 3 : Détection de contours avec les filtres de Sobel

Le filtre de Sobel utilise deux noyaux pour approximer le gradient de l'image dans les
directions horizontale (Gx) et verticale (Gy).

Kx = [Link]([[-1, 0, 1],
[-2, 0, 2],
[-1, 0, 1]])

Ky = [Link]([[-1, -2, -1],

[ 0, 0, 0],
[ 1, 2, 1]])

4. Calcul des gradients :

Appliquez les deux noyaux Kx et Ky à votre image en niveaux de gris en utilisant votre
fonction de convolution. Vous obtiendrez deux images, Gx et Gy , représentant les
gradients horizontaux et verticaux.

Affichez Gx et Gy . Quelles structures de l'image originale sont mises en évidence par

chaque filtre ?

5. Magnitude du gradient :
 L'intensité totale du contour en un point est donnée par la magnitude du gradient, calculée
par : G = sqrt(Gx² + Gy²).

Calculez l'image de la magnitude du gradient G à partir de Gx et Gy . Affichez cette

image. Vous devriez voir les contours de l'image apparaître clairement.

6. Seuillage :

L'image des contours obtenue est en niveaux de gris. Pour obtenir une image binaire (noir
et blanc), on applique un seuillage : les pixels dont la valeur est supérieure à un certain
seuil deviennent blancs (255), les autres deviennent noirs (0).

Choisissez un seuil (par exemple, 50 ou 100) et appliquez-le à votre image de magnitude

de gradient. Affichez le résultat final. Expérimentez avec différentes valeurs de seuil et
observez l'impact sur le résultat.

TD 4 : Cryptographie - Implémentation de l'algorithme RSA

Objectifs

Comprendre les principes mathématiques de la cryptographie à clé publique, en

particulier RSA.

Implémenter les étapes clés de RSA : génération de clés, chiffrement et

déchiffrement.

Utiliser des notions d'arithmétique modulaire (exponentiation modulaire, inverse

modulaire).

Mettre en œuvre un test de primalité probabiliste (Miller-Rabin).

Prérequis
 Python (fonctions, manipulation des entiers). Notions d'arithmétique (nombres premiers,
PGCD, modulo).

Introduction

L'algorithme RSA (du nom de ses inventeurs Rivest, Shamir et Adleman) est l'un des premiers
et des plus célèbres systèmes de cryptographie à clé publique. Sa sécurité repose sur la
difficulté pratique de factoriser de très grands nombres entiers. Il permet de chiffrer un
message avec une clé publique (que tout le monde peut connaître) de telle sorte que seul le
détenteur de la clé privée correspondante puisse le déchiffrer.

Partie 1 : Outils mathématiques

1. Exponentiation modulaire rapide :

Le calcul de (a^b) mod n pour de grands nombres b est infaisable directement. On utilise
l'algorithme d'exponentiation modulaire (ou exponentiation binaire). Le principe est de
calculer les puissances successives de a au carré (a², a⁴, a⁸, ...) et de les multiplier en
fonction de la représentation binaire de b .

Écrire une fonction exp_mod(a, b, n) qui calcule (a^b) mod n de manière efficace.

2. Test de primalité de Miller-Rabin :

Pour générer les clés RSA, nous avons besoin de grands nombres premiers. Le test de
Miller-Rabin est un test probabiliste efficace. Pour un entier n à tester :

a. On écrit n-1 sous la forme 2^s * d, avec d impair.

b. On choisit un témoin aléatoire a dans [2, n-2].

c. Si a^d ≡ 1 (mod n) OU s'il existe r dans [0, s-1] tel que a^(2^r * d) ≡ -1 (mod n), alors
n est probablement premier. Sinon, n est certainement composé.

Répéter ce test k fois (ex: k=20) réduit la probabilité d'erreur.

Écrire une fonction est_premier_miller_rabin(n, k) qui retourne True si n est

probablement premier, False sinon.

3. Génération de grands nombres premiers :

 Écrire une fonction generer_premier(bits) qui génère un nombre premier aléatoire
d'environ bits bits en tirant des nombres impairs au hasard et en les testant avec Miller-
Rabin jusqu'à en trouver un.

4. Inverse modulaire :

L'algorithme d'Euclide étendu permet de trouver l'inverse modulaire. Pour deux entiers a
et n , il trouve x tel que a*x ≡ 1 (mod n). Cet inverse n'existe que si a et n sont
premiers entre eux.

Écrire une fonction inverse_mod(a, n) qui retourne l'inverse de a modulo n . Vous

pouvez vous aider de l'algorithme d'Euclide étendu.

Partie 2 : L'algorithme RSA

5. Génération des clés :

La génération d'une paire de clés (publique, privée) se fait comme suit :

a. Choisir deux grands nombres premiers distincts, p et q (utiliser generer_premier

avec, par exemple, 512 bits).

b. Calculer n = p * q . C'est le module.

c. Calculer l'indicatrice d'Euler : phi(n) = (p-1) * (q-1) .

d. Choisir un entier e (l'exposant public) tel que 1 < e < phi(n) et PGCD(e, phi(n)) = 1.
Une valeur commune est e = 65537 .

e. Calculer d (l'exposant privé) comme l'inverse modulaire de e modulo phi(n) , i.e.,

d = inverse_mod(e, phi(n)) .

La clé publique est le couple (n, e). La clé privée est le couple (n, d).

Écrire une fonction generer_cles_rsa(bits) qui retourne (cle_publique,

cle_privee) .

6. Chiffrement et Déchiffrement :

Un message doit d'abord être converti en un ou plusieurs entiers m plus petits que n .

Chiffrement : c = m^e mod n

Déchiffrement : m = c^d mod n

Écrire deux fonctions : chiffrer(m, cle_publique) et dechiffrer(c,

cle_privee) . Utilisez votre fonction exp_mod .
7. Test complet :

Mettez tout ensemble :

a. Générez une paire de clés.

b. Choisissez un message (un entier, par exemple m = 42 ).

c. Chiffrez le message avec la clé publique.

d. Déchiffrez le message chiffré avec la clé privée.

e. Vérifiez que vous retrouvez bien le message original.

Pour chiffrer du texte, il faut d'abord le convertir en entier(s). Par exemple, en utilisant
l'encodage UTF-8 : int.from_bytes("secret".encode('utf-8'), 'big') . Et pour
le retour : m_dechiffre.to_bytes((m_dechiffre.bit_length() + 7) // 8,
'big').decode('utf-8') .