Portail Descartes

Introduction à la science info : TP 7

Exercice 1 Une image peut être codée à l’aide d’un tableau de tableau, où chaque pixel est alors codé comme
une case : dans le cas d’une image en couleur, on utilise un tableau de longueur 3 représentant les valeurs (entre
0 et 255) de rouge, vert et bleu, dans le cas d’une image en niveaux de gris, on utilise un entier (entre 0 et 255).
On peut visualiser une image en Python à l’aide de la bibliothèque matplotlib :
from matplotlib import pyplot as plt

def show_image(I):
if isinstance(I[0][0], list):
plt.imshow(I)
else:
plt.imshow(I, cmap='gray', vmin=0, vmax=255)
plt.show()

Un appel à la fonction show_image permet alors de visualiser une image, qu’elle soit en couleur ou en niveaux
de gris, et quels que soient ses nombres de lignes et de colonnes. Dans le fichier Python, on joint l’image avec 5
lignes et 4 colonnes vu en cours, en couleurs et en niveaux de gris.
1. Écrire une fonction cross qui prend en paramètre un entier n supposé impair et renvoie l’image avec n
lignes et n colonnes et contenant le dessin d’une croix (de type ×) remplissant l’image.
2. Écrire une fonction flip_left_right qui prend en paramètre une image (en couleurs ou en niveaux de
gris) et renvoie l’image obtenue en réalisant une symétrie axiale verticale (c’est-à-dire dans laquelle on
inverse la gauche et la droite).
3. Écrire une fonction blur qui prend en paramètres une image en niveaux de gris ainsi qu’un entier qu’on
appelle niveau de flou et renvoie l’image obtenue en floutant l’image de départ avec ce niveau de flou.
Plus précisément, un flou de niveau k est obtenu en associant à un pixel p donné la moyenne des niveaux
de gris dans l’image de départ des pixels compris dans un carré de côté 2k + 1 centré sur le pixel p. Cela
force à tronquer l’image puisque sinon il manque des pixels sur les côtés : si l’image de départ à n lignes
par exemple, celle renvoyée n’en aura plus que n − 2k. Pour simplifier, on pourra commencer par écrire
une fonction blur_pixel qui prend en paramètres une image en niveaux de gris, le niveau de flou, et
deux entiers i et j représentant un pixel de l’image de départ, et renvoie la valeur du pixel correspondant
dans l’image floutée.
Exercice 2 On a vu en cours le parcours en largeur, permettant de calculer des plus courts chemins dans des
graphes orientés, en utilisant une file pour stocker les sommets à traiter. On donne le code de ce parcours dans
le fichier Python, ainsi que du code permettant de visualiser un graphe, ainsi que son parcours.
On obtient d’autres parcours de graphe en remplaçant la file par d’autres façon de traiter les sommets à
traiter. Par exemple, si on prend une file de priorité, on peut calculer des plus courts chemins dans un graphe
où les arcs portent des poids (qui peuvent représenter le fait que certains arcs sont plus longs que d’autres), et
on obtient alors l’algorithme de Dijkstra.
Un autre exemple consiste à considérer un parcours en profondeur (depth first search ou dfs en anglais) d’un
graphe. On l’obtient en remplaçant la file par une pile, dans laquelle l’élément qu’on extrait de la pile est le
dernier élément qu’on y a inséré (et non pas le premier comme pour une file). En anglais, on parle de last in
first out, et une pile est donc appelée lifo.
L’algorithme de parcours en profondeur nécessite cependant un peu plus de soin pour obtenir le sous-graphe
obtenu en ne conservant que les arcs utiles pour le parcours (ce que renvoie la fonction bfs). Cela demande
donc l’ajout d’un nouveau tableau predecessor pour stocker une information de prédécesseur, mais aussi cela
demande de modifier le moment où l’on colore en rouge un sommet : plutôt que de le colorer lorsqu’on le voit
pour la première fois, on le colore au moment où on traite ses voisins. Illustrons cela sur un exemple de graphe
orienté :

1
 On cherche le parcours en profondeur issu du sommet 0. On insère 0 dans la pile initialement. Le tableau
predecessor est initialisé (arbitrairement) avec [0, 0, 0]. On entre dans la boucle while et on extrait le
sommet 0 de la pile (qui se retrouve temporairement vide). Le sommet 0 n’étant pas coloré en rouge, on traite
ses deux voisins, dans l’ordre 1 puis 2. Aucun de ces deux voisins n’est marqué en rouge, et on les insère donc
successivement dans la pile, en indiquant 0 comme leur prédécesseur. On arrive donc dans la situation suivante
(où 2 est le dernier sommet empilé, la tête de la pile se trouve donc à droite dans le tableau) :

1
pile : [1, 2]
0
predecessor = [0, 0, 0]
2

On extrait alors le sommet 2 de la pile. Il n’est pas rouge, donc on le marque en rouge, et on ajoute dans le
graphe que la fonction renverra à la fin l’arc menant du prédécesseur de 2 à 2, c’est-à-dire l’arc (0, 2). On traite
ensuite ses voisins non colorés, en l’occurrence 1 qu’on ajoute donc une seconde fois dans la pile. On modifie au
passage le prédécesseur de 1 en lui attribuant le sommet 2. On arrive donc dans la situation suivante :

1
pile : [1, 1]
0
predecessor = [0, 2, 0]
2

On extrait alors le sommet 1 de la pile. Il n’est pas rouge, donc on le marque en rouge, et on ajoute dans
le graphe que la fonction renverra à la fin l’arc menant du prédécesseur de 1 à 1, c’est-à-dire l’arc (2, 1). Le
sommet 1 n’ayant plus de voisins non colorés, l’itération se finit là. On arrive donc dans la situation suivante :

1
pile : [1]
0
predecessor = [0, 2, 0]
2

On extrait le sommet 1 de la pile à nouveau, mais on ne fait rien puisque ce sommet est déjà rouge. On
obtient alors une pile vide et la fonction renvoie donc le graphe rouge obtenu. Notons que dans ce sous-graphe,
même si 1 a été découvert pour la première fois lors de l’exploration du sommet 0, c’est bien l’arc (2, 1) qui est
dans le graphe retourné et pas l’arc (0, 1). On a donc exploré en profondeur le graphe, en s’entêtant à suivre un
chemin jusqu’à ce qu’on ne puisse plus continuer.
1. Écrire des fonctions permettant de manipuler une pile :
— new_lifo qui ne prend pas de paramètre et renvoie une pile vide (c’est-à-dire un tableau vide) ;
— is_empty_lifo qui prend en paramètre une pile et teste si elle est vide (en renvoyant un booléen
True ou False) ;
— insert_lifo qui prend en paramètre une pile et un sommet, et renvoie la pile obtenue en y insérant
le sommet ;
— next_lifo qui prend en paramètre une pile supposée non vide et renvoie le sommet en tête de pile
(sans modifier la pile) ;
— extract_lifo qui prend en paramètre une pile supposée non vide et renvoie la pile d’où on a supprimé
l’élément en tête.
2. Copier puis modifier le code du parcours en largeur pour obtenir une fonction dfs de parcours en
profondeur. Attention, il faudra penser à modifier le moment où est coloré chaque sommet dans le code,
et il faudra ajouter un tableau predecessor.
3. Tester vos fonctions sur les graphes suivants (avec plusieurs valeurs de n) en analysant les ordres de
parcours en largeur et en profondeur :
— un graphe de n sommets formant un unique chemin de longueur n ;
— un graphe de n sommets formant un chemin cyclique bidirectionnel de longueur n ;
— un graphe de p2 sommets formant une grille carrée bidirectionnelle de côté p (la visualisation ne
ressemblera a priori pas à une grille, mais ce qui compte c’est que les arcs soient les mêmes...).
On représente chaque type de graphe ci-dessous avec n = 4 et p = 3 :

2
 0 1 0 1 0 1 2

3 4 5
3 2 3 2
6 7 8

4. En expérimentant, trouver un graphe ayant au moins 5 sommets tels que le sous-graphe obtenu à partir
du parcours en largeur est de la forme du graphe de gauche, et le sous-graphe obtenu à partir du parcours
en profondeur est de la forme sur graphe de droite :

0 0 1 2 3 4

1 2 3 4

Généraliser ensuite votre graphe à une famille de graphe possédant n sommets qui produit des sous-
graphes de parcours respectifs de la forme de ceux ci-dessus.