Actualité

[[{"text":"

Alice pose le problème suivant à Basile.

Elle dessine sur une feuille de papier une petite grille 2 x 3

et demande à Basile combien de chemins mènent du coin supérieur gauche (D) au coin inférieur droit (A), en se déplaçant uniquement le long de traits horizontaux vers la droite et le long de traits verticaux vers le bas.

Basile entame une énumération exhaustive mais perd rapidement le compte des chemins qu'il a ou non déjà construits.

Basile à alors l'idée de noter, à côté de chaque intersection, le nombre total de chemins qui mènent au coin inférieur droit.

Il commence naturellement par la fin et procède vers le haut et vers la gauche.

Ainsi, Basile n'a pas besoin de recompter à chaque fois le nombre de chemins pour les intersections qu'il à déjà traitées et il ne se perd plus dans ses caiculs.

Il parvient rapidement à ses fins avec la grille ainsi complétée qu'il montre fièrement à Alice en lui indiquant que la réponse est 10.

Alice remarque alors que chaque nombre est la somme du nombre situé à droite et du nombre situé en-dessous, ce que Basile confirme en expliquant qu'un chemin partira soit vers la droite, soit vers le bas.

Tout excités, Alice et Basile mettent à profit cette idée pour calculer en quelques instants qu'il y a 184756 chemins sur une grille 10 x 10.

Alice et Basile viennent d'inventer la programmation dynamique.

D'une manière générale, la programmation dynamique est une technique consistant à faire en sorte de ne pas calculer plusicurs fois la même chose, en stockant des résultats intermédiaires dans une structure de données.

Dans l'exemple ci-dessus, un tableau à deux dimensions permettrait de stocker les nombres de chemins déjà calculés.

Dans cette séquence, on illustre la programmation dynamique sur deux exemples

le rendu de monnaie
et l'alignement de séquences.

D'autres exemples sont proposés en exercices, dont le calcul des chemins donné en exemple ci-dessus.

","title":"Programmation dynamique","tagtitle":"h1"},{"edit":"

"}],[{"text":"

Considérons le problème du rendu de monnaie, déjà abordé dans le programme de première.

On suppose un système monétaire utilisant des pièces, avec un certain nombre de pièces de différentes sortes, chacune ayant une valeur entière différente.

Par exemple, on peut imaginer un système avec trois sortes de pièces, avec les valeurs 1, 2 et 5. $\"Pièces$

Source:https://123montessori.fr/monnaie-pieces-et-billets-en-euro-259

On se pose alors la question, pour un système donné, du nombre minimal de pièces qui est nécessaire pour réaliser une somme donnée.

Ainsi, il faut au minimum 3 pièces pour réaliser la somme 12 avec le système ci-dessus.

Mais il n'en faudrait que 2 dans un système qui proposerait des pièces de valeurs 1, 6 et 10.

Dans le programme de première, on a vu qu'un algorithme glouton, qui favorise toujours la pièce la plus grande possible, répond au problème du rendu de monnaie sous certaines conditions.

C'est le cas notamment pour un système monétaire comme les euros, c'est-à-dire

(1,2,5,10,20,50,100,200).

Dans le cas général, cependant, l'algorithme glouton ne donne pas toujours la réponse optimale.

Ainsi, pour faire la somme 12 avec le système (1,6, 10), l'algorithme glouton donne la réponse 3, correspondant à 10 + 1 + 1, au lieu de 2 (6 + 6).

Dans cette section, on étudie un autre algorithme de rendu de monnaie qui donne toujours la solution optimale quelque soit le système monétaire utilisé.

On cherche à écrire sous la forme d'une fonction :

rendu_monnaie(pieces, s)

où pieces est la liste des valeurs des pièces, telle que [1, 2, 5] par exemple, et s la somme que l'on souhaite obtenir.

La fonction doit renvoyer le nombre minimal de pièces pour obtenir s.

On suppose que la liste pieces contient toujours la valeur 1. Ainsi, toute somme peut être obtenue, dans le pire des cas, comme 1+1+ ... +1.

L'algorithme que nous proposons n'est pas vraiment subtil:

il va considérer toutes les façons possibles de parvenir à la somme s.

Pour cela, il procède récursivement. Le cas de base est la somme s = 0, pour laquelle il ne faut aucune pièce.

On renvoie donc 0.

Lorsque s > 0, on considère chaque valeur p dans la liste pieces et on calcule récursivement le nombre minimal de pièces pour faire la somme s—p.

À chacune des valeurs obtenues on ajoute 1 (la pièce de valeur p) et on prend le minimum de toutes ces réponses.

Le programme ci-dessous contient le code Python d'une fonction récursive rendu_monnaie qui réalise cet algorithme.

Programme — Rendu de monnaie, naïf

def rendu_monnaie(pieces, s):

\"\"\"renvoie le nombre minimal de pièces pour faire

la somme s avec le système pieces\"\"\"

if s == 0:

return 0

r = s # s = 1 + 1 + ... + 1 dans le pire des cas

for p in pieces:

if p <= s:

r = min(r, 1 + rendu_monnaie(pieces, s - p))

return r

On prendra le temps de bien lire et de bien comprendre ce programine.

Le programme fonctionne correctement mais il est assez peu performant.

","title":"Rendu de monnaie","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

On constate que le programme ne termine tout simplement pas pour la somme 100.

Essayons de comprendre ce qui se passe, en comptant le nombre d'appels à la fonction rendu_monnaie.

Lorsqu'on l'appelle avec 100 comme argument, elle se rappelle deux fois récursivement, une fois avec 99 comme argument et une fois avec 98 comme argument.

Puis l'appel sur 99 va provoquer deux appels récursifs, sur 98 et 97 respectivement.

On constate qu'on va donc faire deux fois un appel avec 98 comme argument, ce qui provoquerait au total trois appels avec 97 comme argument. Et ainsi de suite d'une façon rapidement dramatique.

Essayons d'être plus précis encore, en calculant pour chaque valeur de s le nombre exact d'appels à la fonction rendu_monnaie.

Pour s = 0, il n'y a qu'un seul appel, à savoir l'appel initial.

Pour s = 1, à y en a deux, à savoir l'appel initial et l'appel sur s = 0.

Dans le cas général, il faut compter l'appel initial et les nombres d'appel pour s — 1 ct s — 2, c'est-à-dire les deux nombres obtenus précédemment.

Pour les premières valeurs de s, en partant de 0, on obtient la suite suivante :

1,2,4,7,12,20,33,...

Si on ajoute un à ces valeurs, on reconnaît la célèbre suite de Fibonacci:

2,3,5,8,13,21,34,...

Dit autrement, le nombre d'appels à rendu_monnaie dans le calcul de

rendu_monnaie([1, 2], n)

est égal à F_n+3 — 1 où F_n désigne le n-ième terme de la suite de Fibonacei.

Or, c'est là une suite qui croît exponentiellement rapidement.

Ainsi, F₅₀ = 12 586 269 025, ce qui veut dire que le calcul de rendu_monnaie([1, 2], 47) demanderait plus de 12 milliards d'appels.

Il n'est pas étonnant que le calcul de rendu_monnaie([1, 2], 100) ne semblait pas terminer, quand on sait que F103 dépasse 1500 milliards de milliards.

Bien évidemment, dans le cas précis du système [1,2] la réponse est tellement simple qu'on peut la calculer de tête.

Mais cet exemple minimal montre à quel point notre solution récursive est rapidement trop coûteuse.

Mieux encore, il nous a permis d'identifier la source du problème :

on appelle la fonction rendu_monnaie de très nombreuses fois sur le même argument.

Ainsi, pendant le calcul de rendu_monnaie([1,2], 35), qui prend plus de 8 secondes, on appelle 1346 273 fois la fonction rendu_monnaie avec s = 5.

C'est là qu'intervient l'idée de la programmation dynamique :

faire en sorte de ne pas calculer plusieurs fois la même chose.

","title":""},{"edit":"

"}],[{"text":"

La mise en œuvre de cette idée n'est pas si difficile que cela. On va utiliser un tableau dans lequel on va stocker successivement la réponse de la fonction rendu monnaie pour toutes les valeurs de 0 jusqu'à s.

Ainsi, on ne recalculera jamais deux fois la même réponse pour une certaine somme:

on se contentera de lire sa valeur dans ce tableau.

Notre nouvelle fonction rendu_monnaie commence donc par allouer un tableau, appelé nb pour «nombre de pièces», dont les indices vont de 0 à s inclus.

def rendu_monnaie(pieces, s):

nb = [0] * (s+1)

Ce tableau est ici initialisé avec 0, ce qui est notamment la bonne valeur pour la somme 0.

Ainsi, la première case du tableau est correctement initialisée.

Il s'agit maintenant de remplir ce tableau pour toutes les sommes de 1 à s.

On le fait avec une boucle for. Pour chaque indice n, c'est-à-dire pour chaque

On le fait avec une boucle for. Pour chaque indice n, c'est-à-dire pour chaque somme n, on commence par initialiser nb[n] avec n car on sait que, dans le pire des cas, on peut faire la somme n avec n pièces, à savoir :

n = 1+1+ ... + 1.

for n in range(i, s + 1):

nb[n] = n

Il faut maintenant se poser la question de savoir si on peut faire mieux.

Comme dans le programme récursif rendu_monnaie, on considère successivement toutes les valeurs de la liste pieces.

Pour chaque valeur p, on a une solution

en 1 + nb[n - p] pièces, à savoir une pièce de valeur p et la meilleure solution possible pour la somme n - p, déjà calculée.

for p in pieces:

if p<=n:

nb[n] = min(nb[n], 1 + nb[n - p])

Avec cette boucle, on calcule donc le minimum de toutes les solutions possibles, ce qui donne bien la solution pour la somme n.

Une fois sorti de ces deux boucles, on à calculé la solution pour toutes les sommes jusqu'à s inclus.

Il n'y à donc plus qu'à renvoyer la valeur de nb[s].

return nb[s]

Le programme ci-dessous contient l'intégralité du code.

Programme — Rendu de monnaie par programmation dynamique

def rendu_monnaie1(pieces, s):

\"\"\"renvoie le nombre minimal de pièces pour faire

la somme s avec le système pieces\"\"\"

nb = [0] * (s + 1)

for n in range(1, s + 1):

nb[n] = n # n = 1 + 1 + ... + 1 dans le pire des cas

for p in pieces:

if p <= n:

nb[n] = min(nb[n], 1 + nb[n - p])

return nb[s]

On constate qu'il a la même structure que le programme précédent, si ce n'est que l'appel récursif est maintenant remplacé par la consultation du tableau nb.

Tester la fonction rendu_monaie1 avec les instructions suivantes :

r = rendu_monnaie1([1, 2], 10)

print(r)

et ensuite avec:

r = rendu_monnaie1([1, 2], 47)

print(r)

et enfin avec:

r = rendu_monnaie1([1, 2], 100)

print(r)

Conclure

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Efficacité

Notre version de rendu monnaie qui utilise la programmation dynamique est bien plus efficace que la version récursive initiale.

Ainsi, le calcul de rendu _monnaie([1,2], 47), qui demandait beaucoup de temps, est maintenant instantané.

En effet, on a maintenant l'allocation d'un tableau de taille 48, une boucle qui parcourt 47 valeurs possibles pour la variable n et, pour chacune, une boucle interne qui parcourt deux valeurs possibles pour la variable p.

Le nombre total d'opérations est donc de l'ordre de la centaine, ce qui est ridicule.

D'une manière générale, le coût est maintenant proportionnel à

len(pieces) x s

en temps et à s en espace (pour le tableau nb).

C'est potentiellement plus coûteux que l'algorithme glouton, mais cela fonctionne maintenant pour tous les systèmes monétaires.

","title":""},{"edit":"

"}],[{"text":"

Construire une solution

Notre programme renvoie le nombre minimal de pièces pour obtenir la somme s mais il ne donne pas la solution pour autant, c'est-à-dire la liste des pièces à utiliser pour atteindre ce minimum.

Il est cependant facile de le modifier pour construire une telle solution.

Il suffit d'ajouter ur second tableau qui contient, pour chaque somme entre 0 et s, une solution minimale pour cette somme.

On remplit ce tableau exactement au même moment où on remplit le tableau nb.

Le programme ci-dessous contient une version du programme rendu_monnaie modifié en suivant cette idée.

Programme — Rendu de monnaie, avec solution

def rendu_monnaie_solution(pieces, s):

\"\"\"renvoie une liste minimale de pièces pour faire

la somme s avec le système pieces\"\"\"

nb = [0] * (s + 1)

sol = [[]] * (s + 1)

for n in range(1, s + 1):

nb[n] = n

sol[n] = [1] * n

for p in pieces:

if p <= n and 1 + nb[n - p] < nb[n]:

nb[n] = 1 + nb[n - p]

sol[n] = sol[n - p].copy()

sol[n].append(p)

return sol[s]

Le second tableau s'appelle sol. Pour chaque indice n, l'élément sol[n] est un tableau d'entiers, de taille nb[n], qui donne une solution pour la somme n.

On initialise sol avec un tableau vide dans chaque case, ce qui est en particulier correct pour n = 0.

La structure du programme est la même qu'auparavant.

Pour chaque somme n, de 1 jusqu'à s, on commence par stocker un tableau contenant n fois la valeur 1 dans sol[n], ce qui correspond à la solution 1+1+...+1.

Puis on examine toutes les pièces possibles et, lorsqu'une pièce p permet d'améliorer la solution, la valeur des deux tableaux est mise à jour.

Pour mettre à jour la valeur de sol[n], on commence par faire une copie du tableau sol[n - op], avec la méthode copy, puis on y ajoute la valeur p, avec la méthode append.

Tester la fonction rendu_monaie_solution avec les instructions suivantes :

r = rendu_monnaie_solution([1, 2], 10)

print(r)

et ensuite avec:

r = rendu_monnaie([1, 2], 47)

print(r)

Conclure

Pour une somme donnée, il n'y à pas nécessairement une solution unique.

Ainsi, avec le système [1, 3, 6, 7, 10], il y a deux solutions minimales pour faire la somme 13, à savoir 3 + 10 ct 6 + 7.

Tester avec:

r = rendu_monnaie_solution([1, 3, 6, 7, 10], 13)

print(r)

Notre programme va renvoyer une seule de ces solutions.

En l'occurrence, ici, il va renvoyer le

tableau [10, 3] correspondant à la première solution.

En effet, lorsque le programme parvient à n = 13, il considère les pièces par ordre croissant.

Pour p = 1, il détermine qu'on obtient une solution à trois pièces en considérant la solution déjà calculée 12 = 6 + 6 à deux pièces.

Puis, pour p = 3, il détermine qu'on obtient de nouveau une meilleure solution, à deux pièces cette fois, en considérant la solution déjà calculée pour la somme 10, à une seule pièce, ce qui nous fait une solution à deux pièces 3 + 10.

Quand on considère ensuite p - 6, on obtient de nouveau une solution à deux pièces, qui n'est donc pas strictement meilleure et qui n'est donc pas considérée.

De même quand on considère p = 7 et p = 10. On est donc resté sur la solution 13=3+10, qui est celle renvoyée au final.

On pourrait encore modifier le programme ci-dessous pour qu'il renvoie toutes les solutions pour faire la somme s en minimisant le nombre de pièces.

Il suffirait pour cela que le tableau sol stocke, pour chaque somme, non pas une solution minimale mais toutes les solutions minimales.

Mais il faut être alors conscient que le temps et l'espace consacrés au stockage de toutes les solutions vont dégrader les performances de notre programme.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Dans le contexte de la bio-informatique, un problème algorithmique essentiel est celui de l'alignement de séquences, typiquement pour comparer des séquences d'ADN.

Source: https://en.wikipedia.org/wiki/DNA_sequencing

On peut le formaliser en ces termes:

étant données deux chaînes de caractères, il s'agit de mettre en correspondance «le plus possible» les caractères de la première chaîne avec ceux de la seconde, en conservant l'ordre des caractères mais en s'autorisant à insérer des trous dans l'une ou l'autre chaîne.

Si on considère par exemple les chaînes \"GENOME\" et \"ENORME\", on peut aligner leurs caractères de la façon suivante, où le caractère - est utilisé pour désigner un trou:

GENO-ME

ENORME

Bien entendu, il existe de nombreuses autres façons d'aligner ces deux chaînes.

En voici une:

G--ENOME

—ENOR--ME

La seule contrainte est que l'on doit utiliser tous les caractères de chaque chaîne, dans l'ordre, et que l'on n'aligne jamais deux trous (c'est-à-dire deux caractères - ).

Parmi tous les alignements possibles, on cherche celui qui donne le score maximal.

Le score est ainsi calculé:

l'alignement de deux caractères identiques donne un point;

en revanche, l'alignement de deux

caractères différents, ce qui inclut l'alignement avec le caractère -, enlève un point.

Ainsi, le premier alignement proposé ci-dessus donne le score 3, car on a 5 caractères correctement alignés et deux mauvais alignements.

Parmi tous les alignements possibles des chaînes \"GENOME\" et \"ENORME\", c'est celui

qui a le score maximal.

À noter que les deux chaînes n'ont pas forcément la même longueur.

Ainsi, l'alignement

ASTUCIEUX

-STUDIEUX

a le score 5, ce qui est là encore maximal.

Comme pour le problème du rendu de monnaie de la section précédente, nous allons commencer par chercher une solution récursive à notre problème (mais cette fois sans écrire le code Python), puis en améliorer l'efficacité grâce à la programmation dynamique.

Reprenons l'exemple des mots \"GENOME\" et \"ENORME\" et voyons ce qu'il en est de leur dernier caractère.

Ici, il s'agit du caractère E dans les deux cas.

Il y à trois cas de figure :

soit ces deux E sont alignés, on marque un point et on doit aligner les mots “GENOM\" et \"ENORM\";
soit le E final de \"GENOME\" est aligné avec -, on perd un point et on doit aligner le mot \"GENOM\" avec le mot \"ENORME\";
soit enfin le E final de \"ENORME\" est aligné avec -, on perd un point et on doit aligner le mot \"GENOME\" avec le mot \"ENORM\",

Comme il n'y a pas d'autre cas possible, le score maximal sera le maximum des trois scores ainsi obtenus. Et comme on s'est ramené à des mots plus petits, plus précisément à une longueur totale des deux mots strictement plus petite, on peut procéder récursivement.

Ainsi, dans le premier cas on calcule le score maximal de l'alignement de \"GENOM\" et \"ENORM\", dans le deuxième cas de \"GENOM\" et \"ENORME\", et dans le troisième cas de \"GENOME\" ct \"ENORM\",

À chaque fois, il y à de nouveau trois cas de figure, qui nous ramènent à des mots plus courts. Et ainsi de suite.

Le processus termine lorsque l'un des deux mots n'a plus de caractères.

Quand par exemple on parvient au calcul du score de l'alignement du mot vide \"\" et du mot \"GE\", la réponse est —2 car il n'y à pas d'autre choix que d'aligner les deux caractères de \"GE\" avec des caractères -.

On pourrait ainsi écrire une fonction récursive aligne qui applique l'algorithme ci-dessus.

Mais exactement comme pour le rendu de monnaie, elle serait très inefficace car elle passerait son temps à recalculer ia même chose.

En effet, si l'on examine les trois cas ci-dessus, on voit que dans le deuxième

cas, le calcul de l'alignement de \"GENOM\" et \"ENORME\" va nous ramener en particulier au calcul de l'alignement de \"GENOM\" et \"ENORM\", déjà fait dans le

premier cas. Et de même, dans le troisième cas, le calcul de l'alignement de \"GENOME\" et \"ENDRM\" va nous ramener une troisième fois au calcui de l'alignement de \"GENOM\" et \"ENORM\".

Ce phénomène de duplication des calculs

va se répéter à chaque étape, provoquant une explosion exponentielle des appels récursifs et donc du temps de calcul.

Ainsi, le calcul du meilleur alignement de deux mots de 10 caractères chacun prend plus de 3 secondes et celui de deux mots de 20 caractères chacun ne se termine pas en un temps raisonnable.

Mais comme pour le rendu de monnaie, on

peut améliorer notre programme en évitant les calculs redondants grâce à la programmation dynamique.

","title":"Alignement de séquences","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Dans le cas du rendu de monnaie, on à utilisé un tableau dans lequel on a stocké, pour chaque somme, la solution optimale.

Ici, on va utiliser un tableau à deux dimensions dans lequel on va stocker, pour chaque paire de mots, le score maximal.

Plus précisément, pour deux entiers i et j, on va stocker dans la case (i,j) de ce tableau le score maximal de l'alignement

des à premiers caractères du premier mot et des j premiers caractères du second mot.

Notre fonction aligne commence par calculer la longueur de chacun des deux mots et par allouer un tableau sc de la bonne taille.

def aligne(s1, s2):

\"\"\"le score du meilleur alignement de s1 et s2\"\"\"

n1, n2 = len(s1), len(s2)

sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]

Il y a plusieurs remarques importantes ici. D'une part, le premier indice va

de 0 à n1 inclus et le second de 0 à n2 inclus. C'est pourquoi on à écrit n1+1

(resp. n2+1). Le tableau à donc la taille (n1 +1) x (n2 + 1).

D'autre part, on a utilisé la construction par compréhension pour construire ce tableau à deux dimensions.

Écrire simplement [[0] * (n2+1)] * (n1+1) aurait été incorrect.

Enfin, on à initialisé les cases de ce tableau avec la valeur 0. En particulier, c'est la bonne valeur pour la case (0,0) c'est-à-dire l'alignement de deux mots vides.

Il faut maintenant remplir toutes les autres cases de ce tableau, en mettant dans sc[i][j] le score de l'alignement maximal des mots s1[0:i] et s2[0:j].

On va le faire en progressant dans le sens des indices croissants.

En effet. le calcul de sc[i][j] va utiliser les trois valeurs :

sc[i-1][j],sc[i][j-1] et sc[i-1][j-1].

Il faut donc les avoir calculées auparavant.

En particulier, on peut commencer par initialiser les valeurs sc[0][j], c'est-

à-dire la première ligne, et sc[i][0], c'est-à-dire la première colonne.

Dans les deux cas, il s'agit de l'alignement avec un mot vide, pour lequel la réponse est facile à calculer:

il faut supprimer tous les caractères, ce qui produit un score égal à l'opposé de la longueur du mot considéré.

for i in range(1, n1 + 1):

sc[i][0] = -i

for j in range(1, n2 + 1):

sc[0][j] = -j

On peut maintenant attaquer le remplissage du reste du tableau, avec une

double boucle pour parcourir toutes les cases restantes.

for i in range(1, n1 + 1):

for j in range(1, n2 + 1):

Pour chaque case sc[i][j], il s'agit de calculer le score maximal pour aligner les mots s1[0:i] et s2[0:j].

Comme expliqué plus haut, il y a trois cas de figure, selon l'alignement du dernier caractère de chacun de ces deux mots.

On commente par les deux cas où l'un de ces deux caractères est aligné avec -. Le score est alors obtenu avec un point de pénalité et l'alignement maximal, déjà calculé, pour un mot raccourci d'un caractère, c'est-à-dire soit sc[i-1][j], soit sc[i][j-1].

s = max(-1 + sc[i - 1][j], -1 + sc[i][j - 1])

1] reste alors le cas où les deux derniers caractères sont alignés.

Dans ce cas, on marque un point si les caractères coïncident et on perd un point sinon.

Dans les deux cas, on utilise l'alignement maximal déjà calculé pour les deux mots raccourcis chacun d'un caractère, c'est-à-dire sc[i-1][j-1].

if s1[i - 1] == s2[j - 1]:

sc[i][j] = max(s, 1 + sc[i - 1][j - 1])

else:

sc[i][j] = max(s, -1 + sc[i - 1][j - 1])

Une fois sorti de la double boucle, le tableau est correctement rempli. Il ne reste plus qu'à renvoyer la valeur située dans la toute dernière case, qui correspond au score d'alignement des deux mots complets.

return sc[n1][n2]

Le programme ci-dessous contient l'intégralité du code:

Programme — Alignement de séquences

def aligne(s1, s2):

\"\"\"le score du meilleur alignement de s1 et s2\"\"\"

n1, n2 = len(s1), len(s2)

sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]

# première ligne et première colonne

for i in range(1, n1 + 1):

sc[i][0] = -i

for j in range(1, n2 + 1):

sc[0][j] = -j

# le reste

for i in range(1, n1 + 1):

for j in range(1, n2 + 1):

s = max(-1 + sc[i - 1][j], -1 + sc[i][j - 1])

if s1[i - 1] == s2[j - 1]:

sc[i][j] = max(s, 1 + sc[i - 1][j - 1])

else:

sc[i][j] = max(s, -1 + sc[i - 1][j - 1])

return sc[n1][n2]

Tester la fonction aligne avec:

s2 = \"ENORME\"

s1 = \"GENOME\"

sc = aligne(s1,s2)

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Il est utile de visualiser et de bien comprendre le tableau sc que ce programme construit. Si on reprend l'exemple des mots \"GENOME\" et \"ENORME\", le tableau obtenu au final est celui-ci:

On peut examiner par exemple comment a été calculé le résultat final, c'est-

à-dire sc[6][6]. Puisque les caractères s1[5] et s2[5] coïncident, on a :

sc[6][6] = max(1+sc[5][5],—1+sc[5][6], —1 + sc[6][5])

= max(1+2,-1+1,-1+1)

= 3

Si on prend un autre cas de figure où les caractères ne coïncident pas, comme par exemple le cas de sc[4][5], on a:

sc[4][5] = max(1+sc[3][4],—1+sc[3][5], —1 + sc[4][4])

= max(-1+-1,-1+-2,-1+1)

= 0

Une autre façon de lire ce tableau est la suivante:

quand on monte, c'est qu'on aligne le caractère correspondant à la ligne avec -;

quand on va à gauche, c'est qu'on aligne le caractère correspondant à la colonne avec -;

enfin, quand on va en diagonale vers le haut et la gauche, c'est qu'on aligne

les deux caractères correspondant à la ligne et à la colonne.

En particulier, le score maximal obtenu au final correspond à un certain chemin de la case en bas à droite jusqu'à la case en haut à gauche qui, à chaque étape, choisit entre aller vers le haut, aller vers la gauche ou aller en diagonale vers le haut et la gauche.

Comme pour le rendu de monnaie, il est possible de modifier le programme pour qu'il renvoie la solution, c'est-à-dire l'alignement réalisant le score maximal. Vous aurez à le faire dans un des exercices.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Efficacité

L'efficacité de ce programme est facile à évaluer. Si les deux mots s1 at s2 ont une longueur respective N et M, on a alloué un tableau de taille N x M.

On l'a ensuite rempli avec quelques calculs élémentaires pour chaque case, ce qui prend un temps proportionnel à N x M.

En particulier, le calcul de l'alignement de deux mots de 20 caractères chacun, qui n'aurait jamais terminé en un temps raisonnable avec une simple fonction récursive, termine maintenant instantanément, avec quelques centaines d'opérations élémentaires seulement.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Mémoïsation

La programmation dynamique n'est pas la seule façon d'éviter les calculs redondants.

Une autre technique consiste à utiliser

un dictionnaire, dans lequel on stocke les calculs déjà effectués.

Plus précisément, pour effectuer le calcul de f(a), on commence par regarder

dans le dictionnaire, indexé par a, si la valeur de f(a) est déjà connue.

Le cas échéant, on la renvoie. Sinon, on calcule la valeur v de f(a), on remplit le dictionnaire avec a -> v, puis on renvoie v.

Ainsi, si on cherche plus tard à recalculer f pour la même valeur a, alors le calcul sera immédiat.

Voici par exemple le programme rendu_monnaie réécrit avec cette idée.

def rendu_monnaie2(pieces, s):

if s in memo:

return memo[s]

r=s

for p in pieces:

if p <= s:

r = min(r, 1 + rendu_monnaie(pieces, s - p))

memo[s] = r

return r

Tester le code avec:

from time import time

start = time()

r = rendu_monnaie2([1, 3, 6, 7, 10], 30)

print(\"appel fct 1ère fois\",time()-start,\"s\")

print(r)

start = time()

r = rendu_monnaie2([1, 3, 6, 7, 10], 30)

print(\"appel fct 2ème fois avec memo\",time()-start,\"s\")

print(r)

Conclure sur l'avantage de la mémoïsation.

IL a toujours la structure récursive du programme rendu_monnaie mais il est maintenant aussi efficace que le programme rendu_monnaie1 (modulo les limites de la récursion de Python).

La programmation dynamique et la mémoïsation sont deux techniques différentes pour atteindre le même objectif, à savoir améliorer la complexité en évitant de calculer deux fois la même chose.

Dans l'immense majorité des cas, elles sont interchangeables.

Il existe cependant quelques cas de figure où la programmation dynamique permet un contrôle plus fin de la mémoire utilisée (en «oubliant» des valeurs précédemment calculées dont on sait qu'elles ne seront plus utiles).

À l'inverse, la mémoïsation est bien plus simple à mettre en œuvre. Mais tout ceci dépasse le cadre du programme de terminale.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Lien avec la technique «diviser pour régner»

La programmation dynamique présentée dans cette séquence n'est pas sans rapport avec la technique «diviser pour régner» présentée dans la séquence précédente.

En effet, il n'est pas rare de commencer par concevoir une décomposition récursive d'un problème, comme dans la séquence précédente, pour se rendre compte ensuite que certains appels récursifs vont être effectués plusieurs fois avec les mêmes arguments.

On peut alors employer la programmation dynamique ou la mémoïsation pour y

remédier.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

La programmation dynamique est une technique pour améliorer l'efficacité d'un algorithme en évitant les calculs redondants.

Pour cela, on stocke dans un tableau les résultats intermédiaires du calcul, afin de les réutiliser au lieu de les recalculer.

Les problèmes du rendu de monnaie ou de l'alignement de séquences sont deux exemples où la programmation dynamique améliore grandement l'efficacité par rapport à une solution récursive.

","title":"Conclusion"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Expliciter (à la main) tous les appels récursifs à la fonction rendu_monnaie (version naïve) quand on lance rendu_monnaie([1, 2], 3).

Identifier les calculs redondants.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Il y a sept appels au total (en comptant le tout premier):

rendu_monnaie([1,2], 3)

rendu_monnaie([1,2], 2)

rendu_monnaie([1,2], 1)

rendu_monnaie([1,2], 0)

rendu_monnaie([1,2], 1)

rendu_monnaie([1,2], 0)

On constate qu’on a fait deux fois l’appel pour s = 1 et trois fois l’appel

pour s = 0.

"}],[{"text":"

Quel est le tableau construit par le programme rendu_monnaie2 quand on

calcule rendu_monnaie2([1, 6, 10], 12)? (Le calculer à la main.)

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

[0, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 2]

La réponse est dans la dernière case (donc 2 ici).

"}],[{"text":"

def rendu_monnaie1(pieces, s):

\"\"\"renvoie le nombre minimal de pièces pour faire

la somme s avec le système pieces\"\"\"

nb = [0] * (s + 1)

for n in range(1, s + 1):

nb[n] = n # n = 1 + 1 + ... + 1 dans le pire des cas

for p in pieces:

if p <= n:

nb[n] = min(nb[n], 1 + nb[n - p])

return nb[s]

Modifier le programme rendu_monnaie1 pour qu'il renvoie, plutôt que le nombre minimal de pièces nécessaires, la liste des pièces constituant la solution optimale.

Tester avec:

print(rendu_monnaie3([1,2,5],47))

Résultat:

[2, 5, 5, 5, 5, 5, 5, 5, 5, 5]

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

À côté du tableau nb qui contient le nombre minimal

de pièces nécessaires pour chaque entier, on ajoute un second tableau, sol,

qui contient la solution, sous la forme d’une liste de pièces.

def rendu_monnaie3(pieces, s):

\"\"\"renvoie le nombre minimal de pièces pour faire

la somme s avec le système pieces\"\"\"

nb = [0] * (s + 1)

sol = [[]] * (s + 1)

for n in range(1, s + 1):

nb[n] = n # n = 1 + 1 + ... + 1 dans le pire des cas

sol[n] = [1] * n

for p in pieces:

if p <= n:

nb[n] = min(nb[n], 1 + nb[n - p])

sol[n] = sol[n - p].copy()

sol[n].append(p)

return sol[s]

"}],[{"text":"

La suite de Fibonacci est la suite d'entiers (F_n) définie par

F₀ = 0,

F₁ = 1

et pour n>1, on a Fn = Fn-1 + Fn-2

Écrire une fonction fibonacci(n) qui calcule la valeur de Fn en utilisant la programmation dynamique.

Tester avec:

print(fib(1200))

Résultat:

373026809482509284562310031170172380127627214493597616743856443016039972205847405917634660750474914561879656763268658528092195715626073248224067794253809132219056382939163918400

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On se sert d’un tableau f dans lequel on calcule successivement toutes les valeurs F₀, F₁,...,F_n.

def fib(n):

f = [0] * (n+1)

f[1] = 1

for i in range(2, n + 1):

f[i] = f[i - 1] + f[i - 2]

return f[n]

"}],[{"text":"

Calculer à la main le tableau des scores d'alignement pour les deux mots \"CHAT\" et \"CAT\".

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

C A T

0 -1 -2 -3

C -1 1 0 -1

H -2 0 0 -1

A -3 -1 1 0

T -4 -2 0 2

Le score maximal est donc 2.

"}],[{"text":"

Quel est le score maximal de l'alignement des mots \"AAAAAAAAAA\" et \"BBBBBBBBBB\" (10 caractères chacun)?

Quelle est la forme du tableau calculé par le programme aligne(s1,s2) sur ces deux mots?

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Le score maximal est -10.

Le tableau a la forme suivante:

B B B B B B B B B B

0 -1 -2 -3 -4 -5 -6 -7 -8 -9-10

A -1 -1 -2 -3 -4 -5 -6 -7 -8 -9-10

A -2 -2 -2 -3 -4 -5 -6 -7 -8 -9-10

A -3 -3 -3 -3 -4 -5 -6 -7 -8 -9-10

A -4 -4 -4 -4 -4 -5 -6 -7 -8 -9-10

A -5 -5 -5 -5 -5 -5 -6 -7 -8 -9-10

A -6 -6 -6 -6 -6 -6 -6 -7 -8 -9-10

A -7 -7 -7 -7 -7 -7 -7 -7 -8 -9-10

A -8 -8 -8 -8 -8 -8 -8 -8 -8 -9-10

A -9 -9 -9 -9 -9 -9 -9 -9 -9 -9-10

A-10-10-10-10-10-10-10-10-10-10-10

"}],[{"text":"

Écrire une fonction affiche(s1, s2, sc) qui affiche la table des scores calculée par le programme aligne(s1, s2), sous la forme suivante:

E N O R M E

0 -1 -2 -3 -4 -5 -6

G -1 -1 -2 -3 -4 -5 -6

E -2 0 -1 -2 -3 -4 -4

N -3 -1 1 0 -1 -2 -3

O -4 -2 0 2 1 0 -1

M -5 -3 -1 1 1 2 1

E -6 -4 -2 0 0 1 3

Pour obtenir un tel alignement, on pourra utiliser la commande:

print('{:>3}'.format(n), end=\"\")

qui affiche la valeur n sur exactement trois caractères, qu'il s'agisse d'un entier ou d'un caractère.

Tester avec:

def aligne(s1, s2):

\"\"\"le score du meilleur alignement de s1 et s2\"\"\"

n1, n2 = len(s1), len(s2)

sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]

# première ligne et première colonne

for i in range(1, n1 + 1):

sc[i][0] = -i

for j in range(1, n2 + 1):

sc[0][j] = -j

# le reste

for i in range(1, n1 + 1):

for j in range(1, n2 + 1):

s = max(-1 + sc[i - 1][j], -1 + sc[i][j - 1])

if s1[i - 1] == s2[j - 1]:

sc[i][j] = max(s, 1 + sc[i - 1][j - 1])

else:

sc[i][j] = max(s, -1 + sc[i - 1][j - 1])

#return sc[n1][n2]

return sc

s2 = \"ENORME\"

s1 = \"GENOME\"

sc = aligne(s1,s2)

affiche(s1,s2,sc)

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def affiche(s1, s2, sc):

print (\" \", end=\"\")

for c in s2:

print ('{:>3}'.format(c), end=\"\")

print()

for i in range(len(sc)):

if i > 0:

print ('{:>3}'.format(s1[i - 1]), end=\"\")

else:

print(\" \", end=\"\")

for v in sc[i]:

print ('{:>3}'.format(v), end=\"\")

print()

"}],[{"text":"

Modifier le programme aligne(s1,s2) pour qu'il renvoie également la solution donnant le meilleur score, sous la forme d'un couple de chaînes de caractères de même longueur contenant d'éventuels caractères -.

Ainsi, sur les deux chaînées \"GENOME\" et \"ENORME\", le programme doit renvoyer:

(3, (\"GEND-ME\", \"-ENORME\"))

On pourra s'inspirer de ce qui à été fait

dans le programme rendue_monnaie_solution.

Tester avec:

s2 = \"ENORME\"

s1 = \"GENOME\"

print(aligne2(s1,s2))

Résultat:

(3, ('GENO-ME', '-ENORME'))

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Comme dans le programme rendu_monnaie_solution, on ajoute un second tableau, sol, à côté du tableau sc, l’idée étant que so1[i][j] contient une solution pour l'alignement des chaînes s1[0:i] et s2[0:j].

L’initialisation se fait avec des couples de chaînes vides:

sol = [[(\"\", \"\")] * (n2 + 1) for _ in range(n1 + 1)]

Pour initialiser les bords du tableau, on écrit respectivement

sol[i][0] = (s1[0:i], \"-\" * i)

sol[0][j] = (\"-\" * j, s2[0:j])

ce qui correspond à des alignements avec le caractère -. Enfin, il y a quatre

cas de figure pour déterminer so1[i] [j], selon la situation qui maximise le

score. On peut réécrire la double boucle ainsi:

# le reste

for i in range(1, n1 + 1):

for j in range(1, n2 + 1):

s = -1 + sc[i - 1][j]

x,y = sol[i - 1][j]

sol[i][j] = (x + s1[i - 1], y + \"-\")

if s < -1 + sc[i][j - 1]:

s = -1 + sc[i][j - 1]

x,y = sol[i][j - 1]

sol[i][j] = (x + \"-\", y + s2[j-1])

if s1[i-1] == s2[j-1] and s < 1 + sc[i-1][j-1]:

s = 1 + sc[i - 1][j - 1]

x,y = sol[i - 1][j - 1]

sol[i][j] = (x + s1[i - 1], y + s2[j - 1])

if s1[i-1] != s2[j-1] and s < -1 + sc[i-1][j-1]:

s = -1 + sc[i - 1][j - 1]

x,y = sol[i - 1][j - 1]

sol[i][j] = (x + s1[i - 1], y + s2[j - 1])

sc[i][j] = s

On constate qu’on ne se sert plus de la fonction max. En effet, le calcul de sol[i][j] est différent à chaaue fois.

Le programme complet est le suivant:

def aligne2(s1, s2):

\"\"\"le score du meilleur alignement de s1 et s2\"\"\"

n1, n2 = len(s1), len(s2)

sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]

sol = [[(\"\", \"\")] * (n2 + 1) for _ in range(n1 + 1)]

# première ligne et première colonne

for i in range(1, n1 + 1):

sc[i][0] = -i

sol[i][0] = (s1[0:i], \"-\" * i)

for j in range(1, n2 + 1):

sc[0][j] = -j

sol[0][j] = (\"-\" * j, s2[0:j])

# le reste

for i in range(1, n1 + 1):

for j in range(1, n2 + 1):

s = -1 + sc[i - 1][j]

x,y = sol[i - 1][j]

sol[i][j] = (x + s1[i - 1], y + \"-\")

if s < -1 + sc[i][j - 1]:

s = -1 + sc[i][j - 1]

x,y = sol[i][j - 1]

sol[i][j] = (x + \"-\", y + s2[j-1])

if s1[i-1] == s2[j-1] and s < 1 + sc[i-1][j-1]:

s = 1 + sc[i - 1][j - 1]

x,y = sol[i - 1][j - 1]

sol[i][j] = (x + s1[i - 1], y + s2[j - 1])

if s1[i-1] != s2[j-1] and s < -1 + sc[i-1][j-1]:

s = -1 + sc[i - 1][j - 1]

x,y = sol[i - 1][j - 1]

sol[i][j] = (x + s1[i - 1], y + s2[j - 1])

sc[i][j] = s

return (s , sol[n1][n2])

"}],[{"text":"

Dans le problème de l'alignement de séquences d'ADN, on utilise en pratique un calcul des scores plus subtil, qui dépend des caractères qui sont alignés (pour tenir compte du nombre d'acides aminés identiques ou similaires qui sont mis en correspondance).

Pour cela, on se donne une matrice de similarités.

Par exemple, pour des chaînes formées uniquement des caractères A, G, C et T, on peut se donner la matrice suivante:

Indiquer comment représenter une telle matrice en Python (dans une variable globale sim).

Par ailleurs, on se donne aussi une variable globale gap pour le score d'un alignement avec le caractère - (par exemple gap = -5).

Modifier le programme aligne(s1,s2) pour qu'il utilise ces deux variables dans le calcul du score.

Tester avec:

sim = {

'A':{'A':10, 'G':-1, 'C':-3, 'T':-4},

'G':{'A':-1, 'G':7 , 'C':-5, 'T':-3},

'C':{'A':-3, 'G':-6, 'C':9 , 'T':0 },

'T':{'A':-4, 'G':-3, 'C':0 , 'T':8 }

}

gap = 5

s1 = \"AGCT\"

s2 = \"AGCT\"

print(aligne3(s1,s2))

Résultat:

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On peut se donner la matrice de similarités sous la forme d’un dictionnaire de dictionnaires:

sim = {

'A':{'A':10, 'G':-1, 'C':-3, 'T':-4},

'G':{'A':-1, 'G':7 , 'C':-5, 'T':-3},

'C':{'A':-3, 'G':-6, 'C':9 , 'T':0 },

'T':{'A':-4, 'G':-3, 'C':0 , 'T':8 }

}

Le calcul du score est alors modifié ainsi. Pour les bords, on utilise respec-

tivement

sc[i][0] = i * gap

sc[0][j] = j * gap

Et dans la double boucle, on utilise maintenant :

s = max(gap + sc[i - 1][j], gap + sc[i][j - 1])

sc[i][j] = max(s, sim[s1[i - 1]][s2[j - 1]]

+ sc[i - 1][j - 1])

Le programme complet est le suivant:

global sim,gap

sim = {

'A':{'A':10, 'G':-1, 'C':-3, 'T':-4},

'G':{'A':-1, 'G':7 , 'C':-5, 'T':-3},

'C':{'A':-3, 'G':-6, 'C':9 , 'T':0 },

'T':{'A':-4, 'G':-3, 'C':0 , 'T':8 }

}

gap = 5

def aligne3(s1, s2):

\"\"\"le score du meilleur alignement de s1 et s2\"\"\"

global sim,gap

n1, n2 = len(s1), len(s2)

sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]

# première ligne et première colonne

for i in range(1, n1 + 1):

sc[i][0] = i * gap

for j in range(1, n2 + 1):

sc[0][j] = j * gap

# le reste

for i in range(1, n1 + 1):

for j in range(1, n2 + 1):

s = max(gap + sc[i - 1][j], gap + sc[i][j - 1])

sc[i][j] = max(s, sim[s1[i - 1]][s2[j - 1]]

+ sc[i - 1][j - 1])

return sc[n1][n2]

#return sc

"}],[{"text":"

Écrire une fonction chemins(n, m) qui calcule le nombre de chemins, sur une grille n x m, qui mènent du coin supérieur gauche au coin inférieur droit, en se déplaçant uniquement le long des traits horizontaux vers la droite et le long des traits verticaux vers le bas.

Vérifier les valeurs trouvées par Alice et Basile en introduction à cette séquence.

Tester avec:

print(chemins1(2,3))

Résultat:

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On crée un tableau de taille

(n+1) x (m+1),

comme pour le problème de l’alignement de séquences.

def chemins(n, m):

grille = [[1] * (m +1) for _ in range(n + 1)]

for i in range(1, n + 1):

for j in range(1, m + 1):

grille[i][j] = grille[i - 1][j] + grille[i][j - 1]

#print(grille[i][j])

return grille#[n][m]

ou avec for décroissant:

def chemins1(n, m):

grille = [[1] * (m +1) for _ in range(n + 1)]

for i in range(n-1, -1, -1):

for j in range(m-1,-1,-1):

grille[i][j] = grille[i + 1][j] + grille[i][j + 1]

#print(grille[i][j])

return grille#[n][m]

#return grille[0][]

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 18 Octobre 2020; Mis à jour : 30 Novembre 2020; Clics : 2271

[[{"text":"

Alice se décide à ranger ses bandes dessinées par ordre alphabétique de titre.

Le travail est fastidieux car elle en possède une bonne centaine.

Elle appelle son frère Basile à la rescousse. Ils se partagent les bandes dessinées et chacun d'eux trie sa moitié, sous la forme d'une pile de bande dessinées.

Ensuite, les bandes dessinées sont rangées dans la bibliothèque en fusionnant les deux piles, c'est-à-dire en prenant à chaque fois celle des deux bandes dessinées au sommet des deux piles qui vient avant l'autre dans l'ordre alphabétique.

Si la fratrie est plus grande, on peut même imaginer décomposer le travail plus encore.

Ainsi, la pile d'Alice ou de Basile pourrait être triée en étant elle-même décomposée.

Dans un contexte informatique, cette façon de procéder suggère que plusieurs ordinateurs ou plusieurs programmes pourraient collaborer pour effectuer une tâche telle qu'un tri.

C'est effectivement le cas. Mais d'une façon très surprenante, il s'avère que même un unique programme peut tirer avantage à ainsi décomposer un problème en sous-problèmes plus petits, ou plus

simples, qu'il va lui-même résoudre successivement.

Ainsi, même si Alice est seule pour trier ses bandes dessinées, elle peut tout à fait partager les bandes dessinées en deux tas égaux, les trier puis les fusionner.

Et pour trier chacun des deux tas, elle peut recommencer ainsi avec la même idée, jusqu'à ce que chaque tas soit suffisamment petit pour pouvoir être trié sans effort.

Alice vient ainsi d'inventer le tri fusion, une méthode extrêmement efficace pour trier.

C'est là une instance du principe «diviser pour régner».

D'une manière générale, ce principe consiste à décomposer un problème à résoudre en sous-problèmes, plus petits, puis à les résoudre, éventuellement en appliquant le même principe autant de fois que nécessaire, puis enfin à combiner les résultats des sous-problèmes pour en déduire le résultat du

problème initial.

L'idée de se ramener à la résolution de sous-problèmes plus petits a déjà été explorée dans la séquence consacré à la récursivité.

En effet, quand on calcule la factorielle de n récursivement, on se ramène au calcul de la factorielle de n — 1, un problème identique mais «plus petit».

De même, le principe «diviser pour régner» invite à penser la solution

d'un problème récursivement.

Cependant, les sous-problèmes «plus petits» traités récursivement seront généralement plus nombreux ou nettement plus petits.

Dans cette séquence, nous détaillons deux exemples d'application du principe «diviser pour régner».

La première application est la recherche dichotomique dans un tableau trié, déjà étudiée en classe de première, mais reformulée ici à l'aide de récursion.

La seconde application est celle du tri fusion, suggérée ci-dessus avec l'exemple des bandes dessinées.

Les exercices proposés contiennent d'autres applications, dont un algorithme pour effectuer la rotation d'une image de 90 degrés.

","title":"Diviser pour régner","tagtitle":"h1"},{"edit":"

"}],[{"text":"

On rappelle qu'il s'agit de déterminer si un entier v apparaît dans un tableau t, ce dernier étant supposé trié par ordre croissant.

Plus précisément, on cherche à écrire une fonction qui renvoie un indice où la valeur v apparaît dans t, en choisissant arbitrairement s'il y a plusieurs réponses possibles, et None si la valeur v n'apparaît pas dans t.

L'idée principale de la recherche dichotomique consiste à délimiter une portion du tableau dans laquelle la valeur v peut encore se trouver, avec deux indices g et d.

On peut illustrer ainsi la situation à chaque étape:

0 g. d

éléments < v

...

éléments > v

On compare alors la valeur au centre de cet intervalle avec la valeur v et, selon le cas, on signale qu'on a trouvé la valeur v ou on se déplace vers la moitié gauche ou la moitié droite.

Il s'agit bien là d'une instance de l'idée «diviser pour régner», car on réduit le problème de la recherche dans

l'intervalle g ... d à celui de la recherche dans un intervalle plus petit.

Dans le programme de première, nous avions écrit la recherche dichotomique sous la forme d'une boucle while, en modifiant la valeur de g ou de d à chaque étape.

Cette fois, nous allons l'écrire sous la forme d'une fonction récursive, ce qui illustre encore mieux le principe «diviser pour régner».

En effet, l'appel récursif va directement exprimer la résolution d'un problème identique mais nlus petit.

Nous écrivons done une fonction récursive qui prend quatre arguments:

le tableau,
la valeur recherchée
et les deux indices délimitant la portion dans laquelle se fait la recherche:

def recherche(t, v, g, d):

On commence par traiter le cas d'un intervalle qui ne contient aucune valeur, c'est-à-dire lorsque la borne gauche g est plus grande que la borne droite d.

Dans ce cas, on renvoie None pour signaler l'échec de la recherche.

if g > d:

return None

Si l'intervalle n'est pas vide, on calcule la position centrale de cet intervalle, en faisant la moyenne de g et d.

Ensuite, on compare la valeur v à la valeur t[m].

Si elle est plus grande, cela veut dire qu'il faut poursuivre la recherche dans la moitié droite, délimitée par les indices m+1 et d.

On rappelle donc récursivement la fonction recherche sur cet intervalle.

if tm] < v:

return recherche(t, v, m + 1, d)

Attention à ne pas oublier le return devant l'appel à recherche, car il s'agit de renvoyer le résultat de l'appel récursif.

C'est justement là qu'on exprime l'idée que la solution de notre problème est ramenée à la solution d'un problème plus petit.

D'une façon symétrique, on rappelle récursivement la fonction sur la moitié gauche de l'intervalle, délimitée par les indices g et m-1, si la valeur v est plus petite que la valeur t[m]:

elif t[ml > v:

return recherche(t, v, g, m - 1)

Enfin, il ne reste que le cas où la valeur v vient d'être trouvée à la position m que l'on renvoie alors.

else:

return m

Le programme complet de la recherche dichotomique s'en déduit en appelant la fonction recherche sur l'intégralité du tableau.

def recherche _dichotomique(t, v):

return recherche(t, v, 0, len(t) - 1)

Le code complet est le suivant:

Programme — Recherche dichotomique dans un tableau trié

def recherche(t, v, g, d):

\"\"\"renvoie une position de v dans t[g..d],

supposé trié, et None si elle ne s'y trouve pas\"\"\"

if g > d:

return None

m = (g + d) // 2

if t[m] < v:

return recherche(t, v, m + 1, d)

elif t[m] > v:

return recherche(t, v, g, m - 1)

else:

return m

def recherche_dichotomique(t, v):

\"\"\"renvoie une position de v dans le tableau t,

supposé trié, et None si elle ne s'y trouve pas\"\"\"

return recherche(t, v, 0, len(t) - 1)

Tester le cpde avec les instructions suivantes:

t1 = [randint(0,10000) for _ in range(10000)]

t1.sort()

v1 = randint(0,10000)

print(recherche_dichotomique(t1,v1))

","title":"Retour sur la recherche dichotomique","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Correction et efficacité

Il est important de se persuader que ce programme ce termine toujours.

L'argument n'est pas différent de celui utilisé en première avec la boucle while:

la quantité d - g est un variant de notre fonction récursive. En effet, il s'agit d'une quantité entière qui décroît strictement à chaque appel récursif, tout en restant positive ou nulle.

On peut également se persuader qu'il n'y a pas de risque d'obtenir l'erreur RecursionError à cause d'un trop grand nombre d'appels récursifs. En effet, la taille de l'intervalle étant divisée par deux à chaque étape, il faudrait un tableau de plus de 2¹⁰⁰⁰ éléments pour que la fonction recherche soit appelée récursivement plus de 1000 fois. Or, la mémoire d'un ordinateur n'autorise aujourd'hui que des tableaux de quelques

milliards d'éléments, c'est-à-dire de l'ordre de 2³⁰. Il n'y a donc aucun risque de provoquer l'erreur RecursionError.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Supposons que l'on veuille trier une liste chaînée contenant des entiers par ordre croissant. Plus précisément, on cherche à écrire une fonction qui reçoit en argument une liste chaînée et renvoie une nouvelle liste contenant les mêmes éléments mais triés par ordre croissant.

On pourrait tout à fait utiliser le tri par sélection ou le tri par insertion vus

au programme de première.

Cependant, le principe «diviser pour régner» peut être avantageusement utilisé pour concevoir un algorithme de tri plus efficace encore, appelé tri fusion.

L'idée a été évoquée dans l'introduction.

Elle consiste à séparer les éléments de la liste en deux listes de même taille, à un élément près.

Ensuite, on trie chacune des deux listes avec le tri fusion, récursivement.

Enfin, on fusionne les deux listes triées, ce qui est facile car il suffit d'examiner uniquement le premier élément de chaque liste.

Il s'agit bien là d'une application du principe «diviser pour régner» car on ramène le problème du tri d'une liste aux sous-problèmes du tri de deux listes plus petites, jusqu'à parvenir à des listes d'au plus un élément, pour lesquelles il n'y a rien à faire.

Le code Python qui traduit cette idée est le suivant:

def tri_fusion(lst):

if 1st is None or lst.suivante is None:

return lst

l1, l2 = coupe(lst)

return fusion(tri_fusion(l1), tri_fusion(l2))

Bien entendu, il reste à réaliser les fonctions coupe et fusion mais le principe «diviser pour régner» est capturé entièrement par la fonction tri fusion et c'est pour cela que nous la donnons tout de suite.

Écrivons maintenant la fonction coupe qui sépare les éléments d'une liste donnée dans deux listes de même taille, à un près, qui sont renvoyées sous la forme d'un couple de listes.

Il y a plusieurs façons de procéder. On pourrait par exemple commencer par calculer la longueur n de la liste, puis mettre les n/2 premiers éléments dans la première liste et le reste dans la seconde.

Üne autre solution consiste à considérer les éléments deux par deux, en en mettant un dans chaque liste.

Pour éviter de faire un cas particulier pour un éventuel dernier élément, dans le cas d'un nombre impair d'éléments, on peut adopter une troisième approche:

on considère les éléments un par un, en les mettant alternativement dans la première et dans la seconde liste,

Une façon élégante de réaliser cela consiste à échanger à chaque étape le rôle des deux listes. C'est cette dernière approche que nous adoptons.

Le code de la fonction coupe est donné dans le programme ci-dessous.

Enfin, il nous reste à écrire la fonction fusion qui reçoit deux listes triées en arguments et renvoie une liste triée contenant les éléments de ces deux listes.

Nous allons l'écrire comme une fonction récursive, car c'est là le plus simple.

La fonction fusion reçoit en argument deux listes l1 et l2, supposées triées par ordre croissant.

def fusion(l1, l2):

Elle doit renvoyer une liste contenant les mêmes éléments que l1 et l2, triée par ordre croissant.

On commence par le cas où l'une des deux listes est vide => il suffit alors de renvoyer l'autre.

if l1 is None:

return l2

if l2 is None:

return l1

Sinon, cela veut dire que les deux listes sont non vides.

On peut donc sans risque examiner maintenant le premier élément de chaque liste.

Le plus petit des deux sera le premier élément du résultat, car les deux listes sont triées.

On compare donc les deux éléments l1.valeur et l2.valeur.

Si le plus petit provient de la première liste, on le place en tête du résultat et le reste de la liste est construit en fusionnant récursivement le reste de l1 avec l2.

if l1.valeur <= l2.valeur:

return Cellule(l1.valeur, fusion(l1.suivante, l2))

Dans le cas contraire, c'est l'inverse:

le premier élément de l2 est placé en tête du résultat et le reste de la liste est construit en fusionnant l1 avec le reste de l2.

else:

return Cellule(l2.valeur, fusion(l1, l2.suivante))

Ceci achève le code de la fonction fusion.

Le code complet du tri fusion est le suivant:

Programme — Tri fusion d'une liste chaînée

def coupe(lst):

\"\"\"sépare une liste en deux listes ayant le même nombre

d'éléménts, à un près\"\"\"

l1, l2 = None, None

while lst is not None:

l1, l2 = Cellule(lst.valeur, l2), l1

lst = lst.suivante

return l1, l2

def fusion(l1, l2):

\"\"\"fusionne deux listes triées\"\"\"

if l1 is None:

return l2

if l2 is None:

return l1

if l1.valeur <= l2.valeur:

return Cellule(l1.valeur, fusion(l1.suivante, l2))

else:

return Cellule(l2.valeur, fusion(l1, l2.suivante))

def tri_fusion(lst):

\"\"\"trie une liste avec le tri fusion\"\"\"

if lst is None or lst.suivante is None:

return lst

l1, l2 = coupe(lst)

return fusion(tri_fusion(l1), tri_fusion(l2))

Tester avec:

def creer_lst_hasard(n,maxhasard):

\"\"\"Creer une liste chainée de nombres aux hasards\"\"\"

lst = None

while n>0 :

lst = Cellule(randint(0,maxhasard),lst)

n -= 1

return lst

def affiche_lst(lst):

\"\"\"affiche le contenue d'une liste chainée\"\"\"

print(lst.valeur,end=\" \")

c = lst.suivante

while c.suivante is not None:

print(c.valeur,end=\" \")

c = c.suivante

print()

#Création de la liste chainée

lst1 = creer_lst_hasard(500,5000)

affiche_lst(lst1)

#Tri de la liste

lst2 = tri_fusion(lst1)

affiche_lst(lst2)

Tester avec 1000 éléments dans la liste lst1 et conclure.

","title":"Tri fusion","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Limites de la récursion

Si on cherche à trier une liste de plus de mille éléments avec notre fonction

tri_fusion, on obtient l'erreur RecursionError, qui signifie qu'on a fait un trop grand nombre d'appels récursifs imbriqués.

Plus précisément, c'est la fonction fusion qui est responsable de cette erreur.

Une solution consiste à augmenter le nombre maximal d'appels, avec setrecursionlimit. Une autre solution consiste À réécrire la fonc-

tion fusion avec une boucle while, ce que propose lexercice 112. C'est

cependant un peu plus délicat à écrire que la version récursive.

La fonction tri_fusion, bien que récursive, ne conduira en revanche

jamais à l'erreur RecursionError. En effet, la taille de la liste étant divisée par deux à chaque fois, il faudrait une liste de plus de 21000 éléments pour conduire à une erreur.

La mémoire de notre machine ne nous permet pas de construire une liste aussi grande.

Et quand bien même nous le pourrions, le tout premier appel à la fonction coupe ne termincrait pas avant très longtemps.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Efficacité

Il est intéressant de se demander si le tri fusion constitue une bonne méthode de tri. En particulier, on peut chercher à le comparer aux tris par sélection et par insertion du programme de première.

Par exemple. nous avions observé que le tri par sélection nous permettait de trier 16 000 valeurs en un peu moins de 7 secondes (sur notre machine).

Avec notre tri fusion, il ne faut que 0,28 secondes pour trier autant de valeurs.

Plus généralement, voici un tableau comparatif, à gauche, et un tracé des performances du tri fusion, à droite.

taille	sélection	fusion
1000	0,06s	0,01s
2000
4000
8000
16000
32000
64000

Comme on le constate, la courbe n'est pas tout à fait linéaire.

Néanmoins, les performances sont bien meilleures qu'avec le tri par sélection et il en serait de même si l'on comparait avec le tri par insertion.

Pour être précis, rappelons que, dans le pire des cas, les tris par sélection

et par insertion peuvent prendre un temps quadratique, c'est-à-dire proportionnel à N² où N désigne le nombre d'éléments à trier.

Ainsi, chaque fois que le nombre d'éléments à trier double, le temps est multiplié par quatre.

Le tri fusion, en revanche, demande un temps qui est proportionnel à N.log₂N, où

log2 désigne la fonction logarithme.

Le logarithme est une fonction qui croît

relativement lentement.

Ainsi, log2(10³⁰) < 30.

Ccla veut dire que lorsque le nombre d'éléments à trier double, le coût du tri fusion fait un peu plus que doubler, mais pas beaucoup plus.

On peut l'observer empiriquement dans le tableau ci-dessus.

Pour être complet, mentionnons qu'une telle complexité en N.log2N est optimale pour le problème du tri par comparaison.

En effet, la théorie nous dit que, dès lors qu'on ne connaît rien quant aux valeurs à trier, notamment leur distribution, et qu'on peut seulement les comparer deux à deux, alors il faut au moins N.log2N comparaisons, dans le pire des cas, pour trier N valeurs, et donc un temps au moins proportionnel à N.log2N.

Le tri fusion est donc optimal.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Remarque : Trier un tableau

Il est possible d'utiliser le tri fusion pour trier un tableau.

Cependant, c'est assez délicat à mettre en œuvre, car réaliser la fusion en place dans le tableau est extrêmement difficile.

Du coup, on utilise un second tableau comme espace de travail temporaire pour

réaliser la fusion et le code s'en trouve tout de suite un peu compliqué.

Il existe un autre algorithme de tri mettant en œuvre le principe «diviser

pour régner» qui s'adapte mieux au cas d'un tableau.

Il s'agit du tri rapide. H consiste à choisir une valeur arbitraire apparaissant dans le tableau et s'en servir comme “pivot”, c'est-à-dire déplacer les éléments dans le tableau pour mettre à gauche les éléments plus petits que le pivot et à droite les éléments plus grands que le pivot, et enfin à trier récursivement les deux moitiés.

Il reste cependant difficile à mettre en

œuvre efficacement. Le tri rapide n'est pas au programme de terminale.

","title":""},{"edit":"

"}],[{"text":"

Le principe «diviser pour régner» consiste à décomposer un problème en un ou plusieurs sous-problèmes de même nature, mais plus petits:

résoudre ces sous-problèmes, éventuellement en les décomposant à leur tour récursivement en problèmes plus petits encore;
déduire des solutions des sous-problèmes la solution du problème initial.

Le tri fusion est un algorithme de tri efficace qui met en œuvre la technique «diviser pour régner».

","title":"Conclusion","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Donner la séquence des appels à la fonction recherche pendant l'évaluation des deux appels suivants :

recherche_dichotomique([0,1,1,2,3,5,8,13,21], 13)

recherche_dichotomique([0,1,1,2,8,5,8,13,21], 12)

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

recherche(t, 13, O0, 8)

recherche(t, 13, 5, 8)

recherche(t, 13, 7, 8)

À ce moment-là, on obtient m = 7, position à laquelle on trouve la valeur 13.

recherche(t, 12, O0, 8)

recherche(t, 12, 5, 8)

recherche(t, 12, 7, 8)

recherche(t, 12, 7, 6)

À ce moment-là, on a g > d et la recherche termine avec le résultat None.

"}],[{"text":"

Quelles sont les deux listes renvoyées par la fonction coupe() lorsqu'on lui passe la liste 8 1 3 0 1 2 5?

L'ordre relatif des éléments est-il préservé?

Est-ce important?

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

La première liste est 5 1 3 8

et la seconde 2 0 1.

On constate que l’ordre relatif est inversé, car les premiers éléments de la

liste l sont ajoutés en premier dans les deux listes l1 et l2.

Ce n’est pas important, car les deux listes vont être triées avant d’être fusionnées.

"}],[{"text":"

Réécrire La fonction fusion à l'aide d'une boucle while plutôt que comme une fonction récursive.

Indication : Construire le résultat en

ordre décroissant, puis le renverser avec une seconde boucle while.

Tester avec:

def creer_lst_hasard(n,maxhasard):

\"\"\"Creer une liste chainée de nombres aux hasards\"\"\"

lst = None

while n>0 :

lst = Cellule(randint(0,maxhasard),lst)

n -= 1

return lst

def affiche_lst(lst):

\"\"\"affiche le contenue d'une liste chainée\"\"\"

print(lst.valeur,end=\" \")

c = lst.suivante

while c.suivante is not None:

print(c.valeur,end=\" \")

c = c.suivante

print()

#Création de la liste chainée

lst1 = lsthasard(1000,5000)

affiche_lst(lst1)

#Tri de la liste

lst2 = tri_fusion(lst1)

affiche_lst(lst2)

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def coupe(lst):

\"\"\"sépare une liste en deux listes ayant le même nombre

d'éléménts, à un près\"\"\"

l1, l2 = None, None

while lst is not None:

l1, l2 = Cellule(lst.valeur, l2), l1

lst = lst.suivante

return l1, l2

def fusion(l1, l2):

lst = None

while l1 is not None or l2 is not None:

if l1 is not None and \\

(l2 is None or l1.valeur <= l2.valeur):

lst, l1 = Cellule(l1.valeur, lst), l1.suivante

else:

lst, l2 = Cellule(l2.valeur, lst), l2.suivante

# puis on renverse lst

r = None

while lst is not None:

r, lst = Cellule(lst.valeur, r), lst.suivante

return r

def tri_fusion(lst):

\"\"\"trie une liste avec le tri fusion\"\"\"

if lst is None or lst.suivante is None:

return lst

l1, l2 = coupe(lst)

return fusion(tri_fusion(l1), tri_fusion(l2))

"}],[{"text":"

Le problème des tours de Hanoï est un jeu célèbre constitué de trois tiges verticales sur lesquelles sont empilés des disques de diamètres différents.

Il s'agit de déplacer tous les disques de la première tige (dessin de gauche) vers la dernière tige (dessin de droite) en respectant deux contraintes:

d'une part, on ne peut déplacer qu'un seul disque à la fois;
d'autre part, on ne peut pas poser un disque sur un disque de diamètre plus petit.

Sur l'exemple ci-dessus, avec quatre disques, il ne faut pas moins de 15 déplacements pour y parvenir.

Écrire une fonction hanoiï(n) qui affiche la solution du problème des tours de Hanoï pour n disques, sous la forme de déplacements élémentaires désignant les trois tiges par les entiers 1, 2 et 3, de la manière suivante:

déplace de 1 vers 3

déplace de 1 vers 2

Indication: Commencer par une fonction récursive deplace(a, b, c, k) qui résout le problème plus général du déplacement de k disques de la tige a vers la tige b en se servant de la tige c comme stockage intermédiaire.

Tester avec:

hanoi(4)

Résultat:

déplace de 1 vers 2

déplace de 1 vers 3

déplace de 2 vers 3

déplace de 1 vers 2

déplace de 3 vers 1

déplace de 3 vers 2

déplace de 1 vers 2

déplace de 1 vers 3

déplace de 2 vers 3

déplace de 2 vers 1

déplace de 3 vers 1

déplace de 2 vers 3

déplace de 1 vers 2

déplace de 1 vers 3

déplace de 2 vers 3

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On suit l'indication. Il n’est pas nécessaire de faire un cas particulier pour k = 1, c’est-à-dire un seul disque.

Il suffit de ne rien faire lorsque k = 0.

def deplace(a, b, c, k):

\"\"\"déplace k disques de La tour a vers la tour b,

en se servant de la tour c comme intermédiaire\"\"\"

if k > 0:

deplace(a, c, b, k - 1)

print(\"déplace de\", a, \"vers\", b)

deplace(c, b, a, k - 1)

#La solution s’en déduit facilement :

def hanoi(n):

deplace(1, 3, 2, n)

"}],[{"text":"

Dans le problème des tours de Hanoï (exercice précédent), combien faut-il de déplacements élémentaires au total pour déplacer les N disques de la tour de départ à la tour d'arrivée?

Indication : Regarder les 3 vidéos pour vous aider.

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Pour déplacer 1 disque, il suffit d’un seul mouvement.

Pour déplacer 2 disques, il faut 1 + 1 + 1 = 3 déplacements.

Pour déplacer 3 disques, il faut 3 + 1 + 3 = 7 déplacements (on en déplace deux,

puis le grand, puis on en déplace deux de nouveau).

En continuant ainsi, on trouve ensuite les valeurs 15, 31, 63, ...,

c’est-à-dire les nombres de la forme :

2^N - 1.

On peut le prouver à l’aide d’une récurrence.

En effet, c’est bien le cas pour N = 1, car 2¹ - 1 = 1 et s’il faut 2^N-1 - 1 déplacements pour N — 1 tours, alors on aura au total (2N-1 -1)+ 1 +(2N-1 -1) = 2N - 1 déplacements pour N tours.

"}],[{"text":"

Reprendre l'exercice sur les tours de Hanoï en utilisant trois piles, chacune contenant des entiers qui représentent les tailles des disques que cette pile contient.

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Les trois arguments a, b, c ne sont plus des entiers mais des piles. Dans le code de la fonction deplace, il suffit de remplacer la ligne

print (\"déplace de\", a, \"vers\", b)

par la ligne

b.empiler(a.depiler())

Dans le code de la fonction hanoi, il faut construire les trois piles, la première contenant les n disques.

def deplace2(a, b, c, k, posi):

\"\"\"déplace k disques de La tour a vers la tour b,

en se servant de la tour c comme intermédiaire\"\"\"

if k > 0:

deplace2(a, c, b, k - 1,[posi[0],posi[2],posi[1]])

b.empiler(a.depiler())

#affichage contenu pile

for i in range(3):

if posi[i] == 0 :

tab = afficher_pile(a)

print(tab)

elif posi[i] == 1 :

tab = afficher_pile(b)

print(tab)

else :

tab = afficher_pile(c)

print(tab)

print()

deplace2(c, b, a, k - 1,[posi[2],posi[1],posi[0]])

def hanoi2(n):

a = Pile()

for i in range(1,n+1):

a.empiler(i)

print(afficher_pile(a))

deplace2(a, Pile(), Pile(), n,[0,1,2])

def afficher_pile(pile:Pile):

if pile.contenu is None:

return []

tab = [pile.contenu.valeur]

c = pile.contenu.suivante

while c is not None:

tab.append(c.valeur)

c = c.suivante

return tab

On a pris soin d’empiler les diamètres en partant du plus grand. Suggestion :

ajouter un affichage du contenu des trois piles après chaque déplacement.

"}],[{"text":"

Dans cet exercice, on cherche à écrire une fonction qui effectue la rotation d'une image de 90 degrés en utilisant le principe «diviser pour régner».

Pour manipuler une image en Python, on peut utiliser par exemple la bibliothèque PIL (Python Image Library) et plus précisément son module Image.

Avec les quatre lignes suivantes:

from PIL import Image

im = Jmage.open(\"image.png\")

largeur, hauteur = im.size

px = im.load()

on charge l'image contenue dans le fichier image.png, on obtient ses dimensions dans les variables largeur et hauteur, et la variable px est la matrice

des pixels constituant l'image.

Pour 0 < x < largeur et 0 < y < hauteur, la couleur du pixel (x, y) est donnée par px[x, y].

Une couleur est un triplet donnant les composantes rouge, vert et bleu, sous la forme d'entiers entre 0 et 255.

On peut modifier la couleur d'un pixel avec une affectation de la forme px[x,y]=c où c est une couleur.

Dans cet exercice, on suppose que l'image est carrée et que sa dimension est une puissance de deux, par exemple 256 x 256.

Notre idée consiste à découper l'image en quatre, à effectuer la rotation de 90 degrés de chacun des quatre morceaux, puis à les déplacer vers leur position finale.

On peut illustrer les deux étapes ainsi:

Afin de pouvoir procéder récursivement, on va définir une fonction rotation_aux(px, x, y, t) qui effectue la rotation de la portion carrée

de l'image comprise entre les pixels (x,y) et (x+t,y+t).

Cette fonction ne renvoie rien. Elle modifie le tableau px pour effectuer la rotation de cette portion de l'image, au même endroit.

On suppose que t est une puissance de 2.

Écrire le code de la fonction rotation_aux.

En déduire une fonction rotation(px, taille) qui effectue une rotation de l'image toute entière, sa dimension étant donnée par le paramètre taille.

Une fois la rotation effectuée, on pourra sauvegarder le résultat dans un autre fichier avec la commande im.save(\"rotation.png\").

Tester avec:

from PIL import Image

im = Image.open(\"image1.png\")

largeur, hauteur = im.size

px = im.load()

rotation(px, largeur)

im.save(\"rotation.png\")

et l'image suivante (Clique droit enregistrer sous):

Résultat en ouvrant rotation.png:

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On commence par traiter le cas d’une région réduite

à un unique pixel. Dans ce cas, il n’y a strictement rien à faire :

def rotation_aux(px, x0, y0, t):

if t == 1:

return

#Sinon, on peut découper la région en quatre sous-régions, de dimension deux

#fois plus petite, dont on effectue la rotation récursivement :

t //=2

rotation_aux(px, x0 , y0 , t)

rotation_aux(px, x0+t , y0 , t)

rotation_aux(px, x0 , y0+t , t)

rotation_aux(px, x0+t , y0+t , t)

#Il faut ensuite déplacer chacune des quatre régions, ce que l’on peut faire

#élégamment avec une double boucle et une affectation simultanée des quatre

#pixels qui échangent leur position :

for x in range(x0, x0+t):

for y in range(y0, y0+t):

px[x,y+t],px[x+t,y+t],px[x+t,y],px[x,y] \\

= px[x,y], px[x,y+t], px[x+t,y+t], px[x+t,y]

La rotation de l’image toute entière est obtenue avec une région qui couvre

toute l’image:

def rotation(px, taille):

rotation_aux(px, 0, 0, taille)

"}],[{"text":"

Dans cet exercice, on se propose d'appliquer le principe «diviser pour régner» pour multiplier deux entiers, avec la méthode de Karatsuba.

Le principe est le suivant. Supposons deux entiers x et y ayant chacun 2ⁿchiffres en base 2.

On peut les écrire sous la forme

x = a2ⁿ+b

y = c2n+d

avec 0 < a,b,c,d < 2ⁿ, c'est-à-dire avec quatre entiers a, b, c, d qui s'écrivent

chacun sur n chiffres en base 2.

Dès lors, on peut calculer le produit de x et y de la façon suivante:

xy = (a2n + b)(c2n + d)

= ac22n + (ad + bc)2n + bd

= ac2n + (ac + bd — (a — b)(c — d))2n + bd

Cette dernière forme, d'apparence inutilement compliquée, fait apparaître

seulement trois produits, à savoir ac, bd et (a — b}(c — d).

Ainsi, on a ramené la multiplication de deux entiers de 2n chiffres à trois multiplications d'entiers de n chiffres.

Pour faire chacune de ces trois multiplications, on peut appliquer le même principe, et ainsi de suite jusqu'à obtenir de petits entiers dont la multiplication est immédiate.

Au final, cela permet d'effectuer la multiplication en un temps proportionnel à n1,58 (environ) au lieu de n2, ce qui est un gain significatif lorsque le nombre de chiffres n est grand.

1. Écrire une fonction taille(x) qui renvoie le nombre de chiffres de l'entier x lorsqu'il est écrit en base 2.

2. Écrire une fonction karatsuba(x, y, n) qui calcule le produit de x et y par la méthode de Karatsuba, en supposant que x et y s'écrivent sur n chiffres en base 2.

Indication : On peut calculer 2n en Python avec l'expression 1 << n.

On peut décomposer x sous la forme a2n+b

avec a, b = x>>n, x % (1 << n).

3. En déduire une fonction mult(x, y) qui calcule le produit de x et y.

Remarque : Il n'est pas nécessaire d'utiliser la base 2. On pourrait tout aussi bien utiliser la base 10 par exemple. Mais les opérations liées à la base deux (multiplication, division ou reste par une puissance de deux sont faciles à réaliser pour la machine).

Tester avec:

print(mult(31478987896658567686786785446,2311675667575656756575765757554))

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Pour la fonction taille, il suffit de diviser x par deux jusqu’à obtenir zéro.

def taille(x):

n=1

while x > 0:

x //= 2

n += 1

return n

Pour la fonction karatsuba, on suit l’algorithme proposé, en s’arrêtant lorsqu'il ne reste qu’un seul chiffre.

def karatsuba(x, y, n):

\"\"\"multiplie x et y par La méthode de Karatsuba\"\"\"

if n <= 1:

return x * y

n //=2

m = 1<<n

a , b = x >> n , x % m

c , d = y >> n , y % m

ac = karatsuba(a, c, n)

bd = karatsuba(b, d, n)

abcd = karatsuba(a - b, c - d, n)

return (ac << ( 2 * n ) ) + ((ac + bd - abcd) << n ) + bd

Enfin, la fonction mult calcule la valeur de n comme le maximum des deux tailles (l'algorithme reste correct si l’un des deux entiers a moins que n chiffres).

def mult(x, y):

n = max(taille(abs(x)), taille(abs(y)))

return karatsuba(x, y, n)

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 18 Octobre 2020; Mis à jour : 29 Novembre 2020; Clics : 2453

[[{"text":"

On a coutume de dire que pour sortir d'un labyrinthe il suffit de toujours suivre le mur situé sur notre droite.

En particulier, on emprunte ainsi toujours la première porte que l'on rencontre sur notre droite et, si on arrive à un cul de sac, cela a pour effet de nous faire faire un demi-tour.

Ceux qui ont un peu réfléchi à cette idée, voire qui ont essayé de la mettre

en pratique, savent plusieurs choses.

D'une part, cette méthode peut échouer

dans certains cas, où on se retrouve à « tourner en rond » autour d'un bloc.

Pour y remédier, ü suffit de marquer au sol les endroits par lesquels on est déjà passé.

Dès lors, quand on revient sur un embranchement qui est marqué, on procède comme s'il s'agissait d'un cul de sac.

D'autre part, on peut tout aussi bien suivre le mur sur la gauche plutôt que sur la droite.

On peut même changer d'avis à chaque nouvelle salle et emprunter à sa guise

n'importe laquelle des portes qui la quittent.

Ces deux idées combinées, à savoir emprunter les embranchernents de façon arbitraire et marquer les endroits par lesquels on est déjà passé, constituent un algorithme fondamental appelé parcours en profondeur. Il s'applique à n'importe quel graphe et permet de déterminer tous les sommets

$\"graphe10.png$

sommet
visité

action

..C

...E

....B

...E

..C

...F

..C

..E

marquer A, emprunter arc A—>B

marquer B, emprunter arc B—>C

marquer C, emprunter arc C—>E

marquer E, emprunter arc E—>B

déjà vu, terminé

pas d'autre arc, terminé

emprunter arc C—>F

marquer F, aucun arc, terminé

pas d'autre arc, terminé

emprunter arc A—>D

marquer D, emprunter arc D—>E

déjà vu, terminé

pas d'autre arc, terminé

Figure 1 — Parcours en profondeur, à partir du sommet A.

","title":"S.D. : Parcours en profondeur et en largeur un graphe","tagtitle":"h1"},{"edit":"

"}],[{"text":"

Avant de programmer le parcours en profondeur en Python, illustrons

son fonctionnement en détail sur un exemple. La figure 1 détaille les

différentes étapes du parcours en profondeur du graphe à partir du sommet A.

$\"graphe10.png$

La première chose que l'on fait est de marquer le sommet A comme déjà vu. En effet, il pourrait y avoir un cycle qui nous ramènerait sur le sommet A (ce n'est pas le cas ici, mais on ne peut pas le

savoir a priori) et avoir marqué le sommet A nous permettra d'interrompre

le parcours et de revenir en arrière.

On considère ensuite les arcs sortants du

sommet A. Il y en a deux, à savoir A—>B et A—>D. Comme on l'a expliqué dans l'introduction, on choisit de façon arbitraire un arc à considérer en premier.

Choisissons par exemple d'emprunter l'arc A—>B. On se retrouve donc maintenant à visiter le sommet B. On commence par le marquer puis on examine ses arcs.

Ici, il n'y en a qu'un seul, à savoir B—>C. On l'emprunte donc et on se retrouve à visiter le sommet C, que l'on commence par marquer.

Il y a 2 arcs sortants du sommet C et là encore on choisit arbitrairement celui qui est considéré en premier.

Ici, on choisit l'arc C—>E, ce qui nous

conduit à marquer E puis à considérer l'unique arc E—>B issu de E.

On se retrouve alors dans une situation nouvelle, où pour la première fois on retombe sur un sommet déjà marqué, à savoir B. On revient donc en arrière, pour se retrouver sur le sommet E.

Comme il n'y avait pas d'autre arc issu

de E, on revient une fois de plus en arrière, pour se retrouver sur le sommet C.

Là, on avait considéré l'arc C—>E mais il y a également l'arc C—>F, que l'on emprunte donc maintenant.

On visite donc le sommet F, que l'on marque.

Comme il n'y a aucun arc sortant du sommet F, on a terminé et on revient

au sommet C.

Cette fois, tous les arcs issus de C ont été examinés, et on a donc terminé la visite de C.

On revient donc au sommet B, donc la visite est également terminée.

On revient donc au sommet A.

Là, il y avait encore l'arc A->D à considérer.

On visite donc le sommet D, que l'on marque avant de considérer l'arc D—>E.

On retombe alors sur le sommet E, déjà visité.

On revient donc en arrière, sur le sommet D, puis encore en arrière, sur le sommet A.

Là, il n'y a plus d'arc à considérer et la visite de A est terminée, ce qui achève notre parcours en profondeur.

Une fois le parcours terminé, tous les sommets atteignables à partir de A

ont été marqués, à savoir A, B, C, D,E et F.

Inversement, le sommet G, qui n'est pas atteignable à partir de A, n'a pas été marqué. C'est là une propriété fondamentale du parcours en profondeur.

Venons-en à la programmation du parcours en profondeur. Le code, ci-dessous repose sur deux ingrédients. Le premier est l'utilisation d'un ensemble pour le marquage des sommets, que l'on appelle vus. Le second ingrédient est l'utilisation d'une fonction récursive pour réaliser le parcours proprement dit.

Cette fonction appelée parcours reçoit en arguments le graphe g, l'ensemble vus et un sommet s à partir duquel réaliser le parcours.

En quatre lignes seulement, elle s'écrit comme elle s'énonce :

«si le sommet s n'est pas dans vus, l'y ajouter et parcourir récursivement tous ses voisins».

Programme — Parcours en profondeur

def parcours(g, vus, s):

\"\"\"parcours en profondeur depuis le sommet s\"\"\"

if s not in vus:

vus.add(s)

for v in g.voisins(s):

parcours(g, vus, v)

def existe_chemin(g, u, v):

\"\"\"existe-t-il un chemin de u à v?\"\"\"

vus = set()

parcours(g, vus, u)

return v in vus

Tester le programme existe_chemin sur le graphe suivant:

$\"graphe10.png$

#réalisation du graphe

g2 = Graphe2()

g2.ajouter_arc(\"A\",\"B\")

g2.ajouter_arc(\"B\",\"C\")

g2.ajouter_arc(\"A\",\"D\")

g2.ajouter_arc(\"D\",\"E\")

g2.ajouter_arc(\"E\",\"B\")

g2.ajouter_arc(\"C\",\"E\")

g2.ajouter_arc(\"C\",\"F\")

g2.ajouter_arc(\"G\",\"C\")

g2.afficher()

#Test si il existe un chemin

print(\"A->F?\",existe_chemin(g2,\"A\",\"F\"))

print(\"A->G?\",existe_chemin(g2,\"A\",\"G\"))

print(\"D->F?\",existe_chemin(g2,\"D\",\"F\"))

","title":"Parcours en profondeur","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Déterminer l'existence d'un chemin entre deux sommets

Une application immédiate du parcours en profondeur consiste à déterminer s'il existe un chemin entre deux sommets u et v. En effet, il suffit de lancer un parcours en profondeur à partir du sommet u puis, une fois qu'il est terminé, de regarder si le sommet v fait partie de l'ensemble des sommets marqués.

Le progrannne contient une fonction existe_chemin qui réalise cette idée.

Elle crée un nouvel ensemble vus, appelle la fonction parcours à partir du sommet u puis vérifie enfin si le sommet v à été visité pendant le parcours.

Bien entendu, on pourrait interrompre le parcours en profondeur dès que le sommet v est atteint. Mais il faudrait modifier pour cela la fonction parcours.

","title":""},{"edit":"

"}],[{"text":"

Construire le chemin

Si on veut construire le chemin, il faut se fatiguer un peu plus.

Au lieu d'un ensemble vus, on prend un dictionnaire, qui associe à chaque sommet le sommet qui à permis de l'atteindre (la

première fois) pendant le parcours en profondeur.

Pour le sommet de départ u, on lui associe None dans ce dictionnaire.

Une fois le parcours en profondeur terminé, on ne se contente pas de regarder si le sommet d'arrivée v est dans vus, mais on «remonte» le dictionnaire, en partant de v, jusqu'à arriver à u.

Vous réaliserez ce programme dans les exercices.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Utilisation

Illustrons l'utilisation de notre parcours en profondeur sur le graphe des régions de la figure ci-dessous:

On a la variable regions qui contient une représentation de ce graphe.

******

On peut tester la présence de chemins, par exemple comme ceci :

assert existe_chemin(regions, \"Bretagne\", \"Occitanie\")

assert not existe_chemin(regions, \"Bretagne\", \"Mayotte\")

Ici, où vérifie l'existence d'un chemin entre la région Bretagne et la région

Occitanie et l'absence d'un chemin entre la région Bretagne et la région Mayotte.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Efficacité

Le parcours en profondeur est un algorithme très efficace, dont

******

pendant ce parcours.

En effet, l'arc u—>v est examiné au plus une fois, à savoir la première fois que la fonction parcours est appelée sur le sommet u.

En effet, si la fonction parcours est rappelée plus tard sur ce même sommet u, alors il sera trouvé dans l'ensemble vus et la fonction se terminera immédiatement, sans rien faire.

Dans le pire des cas, tous les sommets sont atteignables et tout le graphe est donc parcouru.

Le coût est moindre lorsque certains sommets ne sont pas atteignables depuis le sommet de départ.

Le coût en mémoire est celui de l'ensemble vus, qui contient au final tous les sommets atteignables.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Limites de la récursion

La fonction parcours étant récursive, il y a un risque de provoquer RecursionError si le graphe contient beaucoup de sommets.

Ainsi, un parcours en profondeur à partir du sommet 1 sur le graphe

1 -> 2 ... <> 2000

va provoquer cette erreur, car on va dépasser le nombre maximal d'appels récursifs imbriqués (1000 par défaut).

Comme expliqué dans la séquence sur les fonctions récursives, on peut modifier cette limite avec la fonction setrecursionlimit.

Une autre solution consiste à réécrire la fonction parcours avec une boucle while.

Pour cela, on utilise une pile dans laquelle on stocke les sommets qu'il faut parcourir.

Le programme ci-dessous donne le code de cette nouvelle fonction parcours.

On n'a pas besoin de savoir ici comment la pile est réalisée.

C'est un exemple de modularité. La fonction existe_chemin reste inchangée.

Programme — Parcours en profondeur avec une pile

from modPile import *

def parcours2(g, vus, s):

\"\"\"parcours en profondeur depuis le sommet s\"\"\"

pile = Pile()

pile.empiler(s)

while not pile.est_vide():

s = pile.depiler()

if s in vus:

continue

vus.add(s)

for v in g.voisins(s):

pile.empiler(v)

def existe_chemin2(g, u, v):

\"\"\"existe-t-il un chemin de u à v?\"\"\"

vus = set()

parcours2(g, vus, u)

return v in vus

Tester avec :

g2 = Graphe2()

g2.ajouter_arc(\"A\",\"B\")

g2.ajouter_arc(\"B\",\"C\")

g2.ajouter_arc(\"A\",\"D\")

g2.ajouter_arc(\"D\",\"E\")

g2.ajouter_arc(\"E\",\"B\")

g2.ajouter_arc(\"C\",\"E\")

g2.ajouter_arc(\"C\",\"F\")

g2.ajouter_arc(\"G\",\"C\")

g2.afficher()

print(\"A->F?\",existe_chemin2(g2,\"A\",\"F\"))

print(\"A->G?\",existe_chemin2(g2,\"A\",\"G\"))

print(\"D->F?\",existe_chemin2(g2,\"D\",\"F\"))

Conclure sur k'avantage de l'utilisation d'une pile par rapport à une fonction récursive.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Le parcours en profondeur permet également de détecter la présence d'un

cycle dans un graphe orienté.

En effet, puisque l'on marque les sommets

avant de considérer leurs voisins, pour justement éviter de tourner en rond dans un cycle, alors on doit pouvoir être à même de détecter la présence d'un cycle.

Il y a cependant une petite subtilité, car lorsqu'on retombe sur un sommet déjà marqué, on ne sait pas pour autant si on vient de découvrir un cycle.

Considérons par exemple le parcours en profondeur des deux graphes suivants, à partir du sommet A à chaque fois:

Dans le graphe de gauche, on retombe sur le sommet C.

Il n'y a pas de cycle pour autant, mais seulement un chemin parallèle.

Dans le graphe de droite, on retombe sur le sommet B, cette fois à cause d'un cycle.

Tel qu'il est écrit, notre parcours en profondeur ne nous permet pas de distinguer ces deux situations.

Dans les deux cas, on constate que le sommet est déjà dans l'ensemble vus, sans pouvoir en tirer de conclusion quant à l'existence d'un cycle.

Pour y remédier, on va distinguer dans l'ensemble vus deux sortes de sommets:

ceux pour lesquels le parcours en profondeur n'est pas encore terminé et ceux pour lesquels il est au contraire terminé.

On pourrait utiliser pour cela deux ensembles, ou encore un dictionnaire qui associe à chaque sommet déjà rencontré un booléen indiquant si son parcours en profondeur est terminé.

Mais traditionnellement on utilise un marquage à trois couleurs:

- on marque en blane les sommets non encore atteints par le parcours en profondeur,

- en gris les sommets déjà atteints dont le parcours en profondeur est en cours

- et enfin en noir les sommets atteints dont le parcours est terminé.

Dans l'exemple de gauche ci-dessus, le sommet C sera colorié en noir quand on retombera dessus la deuxième fois.

Dans l'exemple de droite, en revanche, il sera encore gris quand on retombera dessus et on en déduira la présence d'un cycle.

Nous adoptons ici cette solution utilisant trois couleurs.

Le parcours en profondeur est modifié de la façon suivante.

Lorsque l'on visite un sommet s, on procède ainsi :

s'il est gris, c'est qu'on vient de découvrir un cycle;
s'il est noir, on ne fait rien;
sinon, c'est qu'il est blanc, et on procède ainsi:

on colore le sommet s en gris;
on visite tous ses voisins, récursivement;
enfin, on colore le sommet s en noir.

Comme on le voit, les voisins du sommet s sont examinés après le moment où s est colorié en gris et avant le moment où s est colorié en noir.

Ainsi, s'il existe un cycle nous ramenant sur s, on le trouvera comme étant gris et

le cycle sera signalé.

Le programme ci-dessous contient une fonction cycle qui réalise cette détection de cycle. Il s'agit 1à d'une modification du parcours en profondeur où un dictionnaire couleur remplace l'ensemble vus.

Programme — Détecter la présence d'un cycle dans un graphe

BLANC, GRIS, NOIR = 1, 2, 3

def parcours_cy(g, couleur, s):

\"\"\"parcours en profondeur depuis le sommet s\"\"\"

if couleur[s] == GRIS:

return True

if couleur[s] == NOIR:

return False

couleur[s] = GRIS

for v in g.voisins(s):

if parcours_cy(g, couleur, v):

return True

couleur[s] = NOIR

return False

def cycle(g):

couleur = {}

for s in g.sommets():

couleur[s] = BLANC

for s in g.sommets():

if parcours_cy(g, couleur, s):

return True

return False

La fonction parcours est toujours une fonction récursive, mais elle renvoie désormais un résultat, à savoir un booléen indiquant la présence d'un cycle.

Enfin, la fonction cycle colorie tous les sommets en blanc puis lance un parcours en profondeur à partir de tous les sommets du graphe.

Si l'un de ces parcours renvoie True, on transmet re résultat. Sinon. on renvoie False.

Dans cette version, on cherche à détecter la présence d'un cycle n'importe où dans le graphe. C'est pourquoi on lance un parcours en profondeur à partir de tous les sommets du graphe,

Pour beauconp de ces sommets, le parcours est passé par là, car ils étaient accessibles depuis des sommets déjà parcourus, et la fonction parcours se termine immédiatement sans rien faire.

Le temps total passé dans la détection de cycle reste proportionnel à la taille du graphe. Si on lance un parcours en profondeur à partir d'un seul sommet s, alors on détecte uniquement la présence d'un cycle atteignable à partir de s.

Tester avec les graphes suivants:

g1 = Graphe2()

g1.ajouter_arc(\"A\",\"B\")

g1.ajouter_arc(\"B\",\"C\")

g1.ajouter_arc(\"A\",\"D\")

g1.ajouter_arc(\"D\",\"C\")

g1.afficher()

print(cycle(g1))

g2 = Graphe2()

g2.ajouter_arc(\"A\",\"B\")

g2.ajouter_arc(\"B\",\"C\")

g2.ajouter_arc(\"D\",\"B\")

g2.ajouter_arc(\"C\",\"D\")

g2.afficher()

print(cycle(g2))

Conclure sur les résultats donnés par la fonction cycle.

","title":"Détecter la présence d'un cycle dans un graphe orienté"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Le parcours en profondeur nous permet de déterminer l'existence d'un chemin entre deux sommets, et même d'en construire un, mais il ne détermine pas pour autant la distance entre deux sommets, c'est-à-dire la longueur minimale d'un chemin entre ces deux sommets.

Si on considère par exemple le graphe des régions et que l'on cherche un chemin entre la région Bretagne et la région Grand Est avec notre parcours en profondeur, alors on trouve le chemin suivant :

Bretagne—>Normandie—>Hauts-de-France—>Île-de-France—>Bourgogne-Franche-Comté —> Grand Est

Ce chemin à la longueur 5, alors qu'il existe un chemin de longueur 3, à savoir

Bretagne—>Normandie—>Île-de-France—>Grand Est

Le fait est que le parcours en profondeur détermine un chemin arbitraire parmi tous les chemins possibles (sans répétitions), car il emprunte les arcs dans un ordre arbitraire.

Si on veut en revanche déterminer la distance entre deux sommets, c'est-à-dire un plus court chemin entre ces deux sommets, alors il faut utiliser un autre algorithme, à savoir le parcours en largeur.

Comme pour le parcours en profondeur, on se donne un sommet de départ, pour initier le parcours. On l'appelle la source.

Et comme pour le parcours en profondeur, on va déterminer peu à peu tous les sommets atteignables à partir de ce sommet de départ.

Ce qui diffère, c'est l'ordre dans lequel ces sommets vont être visités.

Dans le parcours en largeur, on explore le graphe «en cercles concentriques» à partir de la source, c'est-à-dire qu'on visite d'abord tous les sommets à distance 1 de la source, puis tous les sommets à distance 2 de la source, et ainsi de suite, jusqu'à ce que tous les sommets atteignables depuis la source aient été visités.

","title":"Parcours en largeur"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

$\"graphe10.png$

Si on reprend l'exemple du graphe ci-dessus et qu'on effectue un parcours en largeur à partir du sommet A,

alors on va examiner d'abord les sommets B et D, situés à distance 1 de A,
puis les sommets C et E, situés à distance 2,
puis enfin le sommet F, situé à distance 3.

Comme pour le parcours en profondeur, le sommet G n'est pas visité, car il n'est pas atteignable depuis A.

Pour mettre en œuvre le parcours en largeur, et l'idée de cercles concentriques, on peut se servir de deux ensembles.

Le premier, appelé courant, contient des sommets situés à distance d de la source.

C'est notamment dans cet ensemble qu'on pioche le prochain sommet à examiner.

Le second ensemble, appelé suivant, contient des sommets situés à distance d de la source, que l'on examinera après ceux de l'ensemble courant.

À côté de ces deux ensembles, on utilise également un dictionnaire, appelé dist, qui associe à chaque sommet déjà atteint sa distance à la source.

Le parcours en largeur procède ainsi :

initialement, la source est placée dans l'ensemble courant et sa distance est fixée à D:
tant que l'ensemble courant n'est pas vide,
(a) on en retire un sommets,

(b) pour chaque voisin v de s qui n'est pas encore dans dist

* on ajoute v à l'ensemble suivant,

* on fixe dist[v] à dist[s]+1

suivant.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

La figure 2 détaille les différentes étapes de cet algorithme sur l'exemple

du graphe

$\"graphe10.png$

en partant du sommet A. La figure illustre le contenu des deux ensembles, ainsi que les différentes affectations effectuées dans le dictionnaire dist.

courant	suivant	action
A		initialisation, dist[A]=0
	B,D	on retire le sommet A, dist\|B]=1. dist[D]=1
B,D		l'ensemble suivant est vide => échange
D	C	on retire le sommet B, dist\|C]=2
	C,E	on retire le sommet D, dist[E]=2
C,E		l'ensemble suivant est vide => échange
E		on retire le sommet C, dist[F]=3
F		on retire le sommet E
		on retire le sommet F terminé

Figure 2 — Parcours en largeur, à partir du sommet A.

On prendra le temps de bien comprendre cet algorithme.

Le programme ci-dessous réalise cet algorithme en Python. La fonction parcours_largeur réalise un parcours en largeur en partant du sommet

source, à l'aide d'une boucle while.

Programme — Parcours en largeur

def parcours_largeur(g, source):

\"\"\"parcours en largeur depuis le sommet source\"\"\"

dist = {source: 0}

courant = {source}

suivant = set()

while len(courant) > 0:

s = courant.pop()

for v in g.voisins(s):

if v not in dist:

suivant.add(v)

dist[v] = dist[s] + 1

if len(courant) == 0:

courant, suivant = suivant, set()

return dist

def distance(g, u, v):

\"\"\"distance de u à v (et None si pas de chemin)\"\"\"

dist = parcours_largeur(g, u)

return dist[v] if v in dist else None

Les deux ensembles courant et suivant sont des variables locales à la fonction parcours. Une fois le parcours terminé, la fonction parcours renvoie le dictionnaire dist.

Une seconde fonction distance renvoie la distance entre deux sommets u et v, en lançant un parcours en largeur à partir de u puis en consultant la valeur de dist[v].

Si v n'a pas été atteint, on renvoie None.

Tester le programme avec les instructions suivantes :

g2 = Graphe2()

g2.ajouter_arc(\"A\",\"B\")

g2.ajouter_arc(\"B\",\"C\")

g2.ajouter_arc(\"A\",\"D\")

g2.ajouter_arc(\"D\",\"E\")

g2.ajouter_arc(\"E\",\"B\")

g2.ajouter_arc(\"C\",\"E\")

g2.ajouter_arc(\"C\",\"F\")

g2.ajouter_arc(\"G\",\"C\")

g2.afficher()

print(\"distance A F\",distance(g2,\"A\",\"F\"))

print(\"distance A F\",distance(g2,\"A\",\"G\"))

justifier les résultats.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Une file, pour quoi faire une file?

$\"pile_file1.png$

Le parcours en largeur est traditionnellement réalisé avec une file, dans laquelle on ajoute à la fin les nouveaux sommets (ceux que notre code met dans l'ensemble suivant) et dans laquelle on retire au début le prochain sommet à examiner (celui que notre code retire de l'ensemble courant).

Dans cette file, des sommets à la distance d de la source précède des sommets à distance d + 1, ce que l'on peut visualiser ainsi :

L'ordre des sommets situés à une même distance de la source important peu, notre solution avec deux ensembles convient tout aussi bien. Mais surtout, elle explicite la raison pour laquelle notre parcours en largeur est correct, ce que ne montre absolument pas la file.

En terme d'efficacité, il n'y à absolument aucune différence.

","title":""},{"edit":"

"}],[{"text":"

Utilisation

Illustrons l'utilisation de notre parcours en largeur sur le graphe des régions.

Nous avons la variable regions qui contienne la représentation de ce graphe:

regions = Graphe3() #non orienté

regions.ajouter_sommet(\"Guadeloupe\")

regions.ajouter_sommet(\"Martinique\")

regions.ajouter_sommet(\"Guyane\")

regions.ajouter_sommet(\"Corse\")

regions.ajouter_sommet(\"Mayotte\")

regions.ajouter_sommet(\"La Reunion\")

regions.ajouter_arc(\"Hauts-de-France\",\"Normandie\")

regions.ajouter_arc(\"Hauts-de-France\",\"Ile-de-France\")

regions.ajouter_arc(\"Hauts-de-France\",\"Grand Est\")

regions.ajouter_arc(\"Ile-de-France\",\"Grand Est\")

regions.ajouter_arc(\"Ile-de-France\",\"Hauts-de-France\")

regions.ajouter_arc(\"Pays de la Loire\",\"Bretagne\")

regions.ajouter_arc(\"Normandie\",\"Bretagne\")

regions.ajouter_arc(\"Normandie\",\"Pays de la Loire\")

regions.ajouter_arc(\"Pays de la Loire\",\"Centre-Val de Loire\")

regions.ajouter_arc(\"Centre-Val de Loire\",\"Normandie\")

regions.ajouter_arc(\"Pays de la Loire\",\"Nouvelie-Aquitaine\")

regions.ajouter_arc(\"Nouvelie-Aquitaine\",\"Centre-Val de Loire\")

regions.ajouter_arc(\"Ile-de-France\",\"Centre-Val de Loire\")

regions.ajouter_arc(\"Bourgogne-Franche Comte\",\"Centre-Val de Loire\")

regions.ajouter_arc(\"Bourgogne-Franche Comte\",\"Grand Est\")

regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Centre-Val de Loire\")

regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Bourgogne-Franche Comte\")

regions.ajouter_arc(\"Ile-de-France\",\"Bourgogne-Franche Comte\")

regions.ajouter_arc(\"Ile-de-France\",\"Normandie\")

regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Occitanie\")

regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Provence-Alpes-Cote d'Azur\")

regions.ajouter_arc(\"Occitanie\",\"Provence-Alpes-Cote d'Azur\")

regions.ajouter_arc(\"Occitanie\",\"Nouvelie-Aquitaine\")

regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Nouvelie-Aquitaine\")

On peut vérifier la distance entre des régions:

assert distance(regions, \"Bretagne\", \"Occitanie\") == 3

assert distance(regions, \"Bretagne\", \"Bretagne\") == 0

assert distance(regions, \"Bretagne\", \"Mayotte\") == None

Ici, on vérifie que la distance d'une région a elle-même est bien 0 et que la fonction distance renvoie bien None pour deux régions entre lesquelles il n'existe pas de chemin.

Tester les codes et conclure sur les résultats.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Efficacité

Comme pour le parcours en profondeur, le parcours en largeur a un coût directement proportionnel à la taille de la partie du graphe qui a été explorée. En effet, chaque sommet est placé au plus une fois dans l'ensemble suivant, la première fois qu'il est rencontré, c'est-à-dire lorsqu'il n'est pas encore dans le dictionnaire dist.

À ce moment-là, on fixe sa distance, ce qui fait qu'il ne sera pas considéré de nouveau.

De même, chaque arc s —> v est examiné au plus une fois, lorsque le sommet s est retiré de l'ensemble courant.

Le coût en mémoire est celui des deux ensembles et du dictionnaire, au pire proportionnel au nombre total de sommets du graphe.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Étant donnés un graphe et un sommet dans ce graphe, le parcours eu profondeur et le parcours en largeur sont deux algorithimes fondamentaux pour explorer le graphe en partant de ce sommet.

Ces deux parcours déterminent l'ensemble des sommets accessibles depuis le sommet de départ.

Le parcours en profondeur permet de détecter la présence d'un cycle dans un graphe orienté.

Le parcours en largeur permet de déterminer la distance entre le sommet de départ et tout sommet accessible, c'est-à-dire le plus petit nombre d'arcs pour

relier ces deux sommets.

","title":"Conclusion","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Dérouler à la main le parcours en profondeur sur le graphe

pour différentes valeurs du sommet de départ.

Donner à chaque fois la valeur finale de l'ensemble vus, c'est-à-dire l'ensemble des sommets atteints par le parcours.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

sommet | valeur finale

de départ de vus

0 {0,1,3,2}

1 {1,2}

2 C2}

3 {3,1,2}

"}],[{"text":"

Dérouler à la main le parcours en largeur sur le graphe suivant

pour différentes valeurs du sommet de départ.

Donner à chaque fois la valeur finale du dictionnaire dist, c'est-à-dire la distance à la source de chaque sommet atteint par le parcours.

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

sommet valeur finale

de départ de dist

0 {0H0,1H1,38m1,2r 2}

1 {1H0,2H 1}

2 {25 0}

3 {3-0,1H1,2r 2}

"}],[{"text":"

On peut se servir d'un parcours en profondeur pour déterminer si un graphe non orienté est connexe, c'est-à-dire si tous ses sommets sont reliés entre eux par des chemins.

Pour cela, il suffit de faire un parcours en profondeur à partir d'un sommet quelconque, puis de vérifier que tous les sommets ont été atteints par ce parcours.

Écrire une fonction est_connexe() qui réalise cet algorithme.

On pourra se servir de la méthode sommets() de la classe Graphe et de la fonction parcours.

Tester avec les 2 graphes suivants :

g1 :

g2:

print(\"g1 connexe?\",est_connexe(g1))

print(\"g2 connexe?\",est_connexe(g2))

Résultat :

True

False

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

g1 = Graphe3()

g1.ajouter_arc(\"A\",\"B\")

g1.ajouter_arc(\"B\",\"C\")

g1.ajouter_arc(\"A\",\"D\")

g1.ajouter_arc(\"D\",\"C\")

g2 = Graphe3()

g3.ajouter_arc(\"A\",\"B\")

g3.ajouter_arc(\"B\",\"C\")

g3.ajouter_arc(\"A\",\"D\")

g3.ajouter_arc(\"D\",\"C\")

g2.ajouter_arc(\"E\",\"F\")

On suit l’algorithme proposé, en faisant uniquement attention au cas d’un graphe qui ne contiendrait aucun

sommet.

def est_connexe(g):

\"\"\"le graphe est-il connexe?

(uniquement pour un graphe non orienté)\"\"\"

ts = g.sommets()

if len(ts) == 0:

return True

s = ts.pop()

vus = set()

parcours(g, vus, s)

for s in ts:

if s not in vus:

return False

return True

"}],[{"text":"

Dans cet exercice, on se propose d'utiliser le parcours en profondeur pour construire un chemin entre deux sommets, lorsque c'est possible.

On le fait avec deux fonctions, comme dans le programme parcours en profobdeur.

def parcours_ch(g, vus, org, s):

\"\"\"parcours depuis Le sommet s, en venant de org\"\"\"

...

def chemin(g, u, v):

\"\"\"un chemin de u à v, Le cas échéant, None sinon\"\"\"

...

L'idée est que l'attribut vus n'est plus un ensemble mais un dictionnaire, qui associe à chaque sommet visité le sommet qui a permis de l'atteindre pendant le parcours en profondeur.

La fonction parcours_ch prend un argument supplémentaire, org (pour origine), qui est justement le sommet qui a permis d'atteindre s, en empruntant l'arc org —>s.

Écrire le code de la fonction parcours_ch.

Il est très semblable à celui de la fonction parcours du programme parcours en profondeur.

Écrire ensuite le code de la fonction chemin qui renvoie un chemin entre les sommets u et v, le cas échéant, None s'il n'existe pas de chemin entre ces deux sommets.

Pour cela, lancer un parcours en profondeur à partir du sommet u, en donnant à org la valeur None, puis, si

le sommet v a été atteint, construire le chemin dans un tableau en «remontant» le dictionnaire vus de v jusqu'à u.

Tester avec le graphe suivant:

$\"graphe10.png$

print(\"A->F?\",chemin(g2, \"A\", \"F\"))

print(\"A->G?\",chemin(g2, \"A\", \"G\"))

Résultat:

A->F? ['A', 'D', 'E', 'B', 'C', 'F']

A->G? None

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Pour parcours_ch, l'ajout dans un ensemble de-

vient un ajout dans un dictionnaire.

def parcours_ch(g, vus, org, s):

\"\"\"parcours depuis le sommet s, en venant de org\"\"\"

if s not in vus:

vus[s] = org

for v in g.voisins(s):

parcours_ch(g, vus, s, v)

Pour chemin, on prend soin de tester si v a été atteint par le parcours. Dans

le cas contraire, on renvoie None. Sinon, on construit le chemin avec une

boucle while.

def chemin(g, u, v):

\"\"\"chemin de u à v, le cas échéant, None sinon\"\"\"

vus = {}

parcours_ch(g, vus, None, u)

if v not in vus:

return None

ch = []

s=v

while s is not None:

ch.append(s)

s = vus[s]

ch.reverse()

return ch

De fait, le chemin est construit à l'envers. On prend soin de le renverser avec

la méthode reverse avant de le renvoyer.

"}],[{"text":"

Dans cet exercice, on se propose d'utiliser le parcours en largeur pour construire un chemin de longueur minimale entre deux sommets.

On le fait avec deux fonctions, comme dans le programme parcours en largeur.

def parcours_largeur_ch(g, source):

\"\"\"parcours depuis le sommet source\"\"\"

...

def chemin(g, u, v):

\"\"\"un chemin de u à v, le cas échéant, None sinon\"\"\"

L'idée est qu'un dictionnaire vus remplace le dictionnaire dist.

Ce dictionnaire vus associe à chaque sommet visité le sommet qui à permis de l'atteindre pendant le parcours en largeur.

Écrire le code de la fonction parcours_largeur_ch.

Il est très semblable à celui de la fonction parcours_largeur du programme parcours en largeur.

Pour le sommet source, on lui associe la valeur None dans le dictionnaire vus.

Écrire ensuite le code de la fonction chemin qui renvoie un chemin réalisant la distance entre les sommets u et v, le cas échéant, et None s'il n'existe pas de chemin entre ces deux sommets.

Pour cela, lancer un parcours en largeur à partir du sommet u puis, si le sommet v a été atteint, construire le chemin dans un tableau en «remontant» le dictionnaire vus de v jusqu'à u.

Tester avec le graphe suivant:

$\"graphe10.png$

print(\"A->F?\",chemin(g2, \"A\", \"F\"))

print(\"A->G?\",chemin(g2, \"A\", \"G\"))

Résultat:

A->F? ['A', 'B', 'C', 'F']

A->G? None

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On garde la structure du programme 42, le diction-

naire vus prenant la place du dictionnaire dist.

def parcours_largeur_ch(g, source):

\"\"\"parcours depuis Le sommet source\"\"\"

vus = {source: None}

courant = {source}

suivant = set()

while len(courant)>0:

s = courant.pop()

for v in g.voisins(s):

if v not in vus:

suivant.add(v)

vus[v] = s

if len(courant) == 0:

courant, suivant = suivant, set()

return vus

La seconde partie, à savoir la reconstruction du chemin, n’est pas différente

de celle effectuée dans l’exercice précédent pour un parcours en profondeur.

def chemin(g, u, v):

\"\"\"chemin de u à v, Le cas échéant, None sinon\"\"\"

vus = parcours_largeur_ch(g, u)

if v not in vus:

return None

ch = []

s=v

while s is not None:

ch.append(s)

s = vus[s]

ch.reverse()

return ch

"}],[{"text":"

Les nœuds d'un arbre binaire peuvent être vus comme les sommets d'un graphe non orienté.

En particulier, on peut donc parcourir les nœuds d'un arbre avec un parcours en profondeur ou en largeur.

Pour le parcours en profondeur, il s'agit d'un parcours que nous avons déjà présenté, à savoir le parcours préfixe.

Dans cet exercice, on se propose de parcourir les nœuds d'un arbre binaire avec un parcours en largeur.

Écrire une fonction largeur(a) qui reçoit un arbre binaire a en argument et imprime les valeurs de ses différents nœuds dans un ordre donné par un parcours en largeur, c'est-à-dire la valeur contenue dans la racine, puis les valeurs contenues dans les nœuds immédiatement en-dessous (niveau 1), puis celles contenues dans les nœuds encore en-dessous (niveau 2), etc.

Tester le programme avec l'arbre ci-dessus et le code suivant:

largeur(a1)

Résultat:

Indication : Il faut utiliser les classes suivantes pour construire l'arbre a1:

class Noeud:

\"\"\"un noeud d'un arbre binaire\"\"\"

def __init__(self, g, v, d):

self.gauche = g

self.valeur = v

self.droit = d

def __eq__(self, n):

return n is not None \\

and self.gauche == n.gauche \\

and self.valeur == n.valeur \\

and self.droit == n.droit

class ABR:

\"\"\"arbre binaire de recherche\"\"\"

def __init__(self):

self.racine = None

def ajouter(self, x):

if self.racine is None :

self.racine = Noeud(None,x,None)

else :

self.__ajoute__(x,self.racine)

def contient(self, x):

return self.__appartient__(x, self.racine)

def affiche(self):

self.__afficher__(self.racine)

print(\"\\n\")

def __afficher__(self,a):

if a is None:

return

print (\"(\", end=\"\")

self.__afficher__(a.gauche)

print(a.valeur, end=\"\")

self.__afficher__(a.droit)

print(\")\", end=\"\")

def __ajoute__(self,x,a):

if x < a.valeur:

if a.gauche is None:

a.gauche = Noeud(None, x, None)

else:

self.__ajoute__(x,a.gauche)

elif x > a.valeur:

if a.droit is None:

a.droit = Noeud(None, x, None)

else:

self.__ajoute__(x,a.droit)

def __appartient__(self,x, a):

\"\"\"détermine si x apparaît dans l'ABR\"\"\"

if a is None:

return False

if x < a.valeur:

return self.__appartient__(x, a.gauche)

elif x > a.valeur:

return self.__appartient__(x, a.droit)

else:

return True

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On crée l'arbre a1:

a1 = ABR()

a1.ajouter(8)

a1.ajouter(4)

a1.ajouter(12)

a1.ajouter(2)

a1.ajouter(6)

a1.ajouter(10)

a1.ajouter(14)

a1.ajouter(1)

a1.ajouter(3)

a1.ajouter(7)

a1.ajouter(9)

a1.ajouter(13)

a1.ajouter(15)

a1.affiche()

Le programme en largeur est le suivant:

def largeur(a):

h = hauteur(a.racine)

for i in range(1, h+1):

affiche_niveau(a.racine, i)

print()

def affiche_niveau(Noeud, niveau):

if Noeud is None:

return

if niveau == 1:

print(Noeud.valeur)

elif niveau > 1:

affiche_niveau(Noeud.gauche, niveau-1)

affiche_niveau(Noeud.droit, niveau-1)

def hauteur(Noeud):

if Noeud is None:

return 0

else:

lheight = hauteur(Noeud.gauche)

rheight = hauteur(Noeud.droit)

return 1+max(lheight, rheight)

"}],[{"text":"

Nous avons le labyrinthe suivant:

Il est représenté part un liste à 2 dimensions en Python

grid = [[1, 0, 1, 1, 1, 1, 1 ,1],

[1, 0, 0, 0, 0, 0, 1 ,1],

[1, 1, 1, 0, 0, 0, 1 ,1],

[1, 0, 0, 0, 1, 0, 0 ,1],

[1, 0, 1, 1, 0, 0, 1 ,1],

[1, 0, 1, 0, 0, 1, 0 ,1],

[1, 0, 1, 0, 0, 0, 0 ,1],

[1, 1, 1, 1, 1, 1, 0 ,1]]

Avec :

O pour un passage;
1 pour un mur;
l'entrée est en haut à gauche en (1,0);
la sortie est en bas à droite en (len(grid[0])-2,len(grid)-1).

En le modélisant par un graphe et en le parcourant en largeur à l'aide de la fonction chemin, on détermine le moyen pour en sortir:

Vous allez donc écrire une fonction generer_graphe qui a comme argument une grille de labyrinthe et qui retourne son graphe non orienté (Graphe3).

En effet, grace au graphe du labyrinthe et à la fonction chemin, vu précédemment, nous pourrons déterminer le chemin pour en sortir.

Indications : Pour déterminer le graphe, il faut parcourir le labyrinthe et pour chacune des cases ajouter ou non des arcs.

Par exemple :

on ajoute pour cette cellule l'arc correspondant :

glaby.ajouter_arc((x,y),(x+1,y))

et pas :

glaby.ajouter_arc((x,y),(x,y+1))

car il y a un mur.

Tester avec le code suivant :

graphe_laby = generer_graphe(grid)

itineraire = chemin(graphe_laby,(1,0),(len(grid[0])-2,len(grid)-1))

print(itineraire)

Pour notre grille le résultat est le suivant:

[(1, 0), (1, 1), (2, 1), (3, 1), (3, 2), (4, 2), (5, 2), (5, 3), (5, 4), (4, 4), (4, 5), (4, 6), (5, 6), (6, 6), (6, 7)]

Donc avec les fonctions generer_graphe et chemin, nous pouvons déterminer les parcours pour des labyrinthe plus complexes:

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def generer_graphe(grille):

glaby = Graphe3()

for i in range(0,len(grille)-1):

for j in range(0,len(grille[0])-1):

if grille[i][j] == 0 and grille[i][j+1]==0:

glaby.ajouter_arc((j,i),(j+1,i))

if grille[i][j] == 0 and grille[i+1][j]==0:

glaby.ajouter_arc((j,i),(j,i+1))

j+=1

if grille[i][j]==0 and grille[i+1][j]==0:

glaby.ajouter_arc((j,i),(j,i+1))

i+=1

for j in range(0,len(grille[0])-1):

if grille[i][j] == 0 and grille[i][j+1]==0:

glaby.ajouter_arc((j,i),(j+1,i))

return glaby

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 18 Octobre 2020; Mis à jour : 23 Novembre 2020; Clics : 1891

[[{"text":"

Alice est sur Wikipedia, en train de lire la page Algorithme du lièvre et de la tortue. Trois clics plus tard, elle se surprend à lire la page Cathédrale Saint-Étienne de Metz et se demande soudain comment elle en est arrivée là.

D'autres questions se précipitent alors dans sa tête.

Est-il possible de revenir à la page Algorithme du lièvre et de la tortue en suivant uniquement des liens entre articles de Wikipedia?

Combien de clics seraient nécessaires

pour cela?

Certains article de Wikipedia sont-ils tout simplement inatteignables à partir de cette page?

Immédiatement, Alice comprend qu'il lui faudra écrire un programme si elle veut répondre à de telles questions, car tenter d'y répondre par une exploration manuelle lui prendrait bien trop de temps.

Mais Alice sait également qu'il y a plus de deux millions de pages sur fr.wikipedia.org, et des dizaines de liens dans chaque page, alors elle se demande légitimement si un tel programme a simplement une chance de répondre dans un délai raisonnable.

En cherchant à écrire des programmes pour répondre à ces questions, Alice découvre la théorie des graphes, inventée il y a presque 300 ans par le mathématicien Leonhard Euler, et qu'elle peut effectivement déterminer s'il existe un chemin d'une page à une autre dans Wikipedia avec un algorithme qui s'écrit en seulement cinq lignes de code.

","title":"S.D. : Graphes","tagtitle":"h1","posi":0},{"edit":"

"}],[{"text":"

Nous allons commencer par fixer les notions et le vocabulaire de base de

la théorie des graphes.

Sommets, arcs, orientation

Un graphe est un ensemble de sommets reliés entre eux par des arcs.

Dans l'exemple de Wikipedia chaque page forme un sommet, et les liens permettant de naviguer d'une page à l'autre constituent les arcs.

Graphe orienté

Voici un exemple plus petit de graphe possédant quatre sommets, notés A, B, C et D, et six arcs, dessinés par des flèches.

$\"graphe1.png$

Dans ce graphe il y à un arc du sommet A vers le sommet B, ce que l'on note A—>B , mais pas du sommet B vers le sommet A.

On parle de graphe orienté lorsque l'on distingue ainsi un sens pour les arcs.

En particulier, il y a un arc du sommet B vers le sommet D et un autre du sommet D vers le sommet B.

","title":"Définitions"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Graphe non orienté

Lorsqu'en revanche le sens des arcs n'est pas significatif, c'est-à-dire que l'on s'intéresse uniquement à la présence d'un arc entre deux sommets, on parle de graphe non orienté.

On dessine alors les arcs non pas comme des flèches mais comme de simples traits reliant les sommets.

$\"graphe1.png$

Sur cet exemple, on a toujours quatre sommets mais seulement cinq arcs maintenant.

La figure ci-dessous représente un graphe où les sommets sont les dix-huit régions françaises et où on a relié entre elles les régions limitrophes (par la terre).

$\"graphe1.png$

Figure 1 : Le graphe des régions françaises.

C'est un autre exemple de graphe non orienté.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Voisinage

Lorsqu'il y a un arc d'un sommet s vers un sommet t, on dit que t est adjacent à s.

Les sommets adjacents à s sont également appelés les voisins de s.

Dans les exemples précédents, le voisinage de A est l'ensemble {B,D} et le voisinage de D est le singleton {B} dans le cas orienté et l'ensemble {A,B, C} dans le cas non orienté.

Dans tout cette séquence, on se limite à des graphes simples, dans lesquels il y a au plus un arc entre deux sommets (pas d'arcs multiples) et pas d'arc reliant un sommet à lui-même (pas de boucles).

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Dessins

Il est important de comprendre que c'est l'ensemble des sommets et la relation d'adjacence, c'est-à-dire l'ensemble des arcs, qui définissent le graphe, et non pas la façon dont on le dessine.

Ainsi, les trois graphes suivants sont identiques, bien que dessinés différemment.

$\"graphe1.png$

Notons qu'un graphe n'est pas nécessairement fini. Il peut contenir une

infinité de sommets et, dans ce cas, possiblement une infinité d'arcs. Ainsi, on peut considérer le graphe dont les sommets sont les entiers naturels et où il y a un arc n — m dès lors que m est un diviseur strict de n.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Chemin dans un graphe

Dans notre exemple de Wikipedia, Alice a visité plusieurs pages l'une après l'autre, navigant de l'une à la suivante à l'aide de liens.

On appelle ceci un chemin.

Chemin

Dans un graphe donné, un chemin reliant un sommet u à un sommet v est une séquence finie de sommets reliés deux à deux par des arcs et menant de u à v.

Ainsi, dans le graphe

$\"graphe1.png$

il existe un chemin reliant A à C, à savoir A —> B —> C. Mais il y en a d'autres, comme par exemple A —> D —> B —> C ou encore A —> B -> C —> D —> B ->C.

En fait, il y a ici une infinité de chemins reliant A à C, car on peut emprunter le chemin D —> B —> C —> D ou encore B —> D —> B autant de fois que l'on veut.

Pour un graphe non orienté, on à un chemin reliant u à v si et seulement

si on à un chemin reliant v à u. Mais pour un graphe orienté, on peut avoir

un chemin reliant u à v mais pas de chemin reliant v à u.

Ainsi, dans le graphe ci-dessus, il n'y a pas de chemin reliant C à A.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Cycle

Un chemin est dit simple s'il n'emprunte pas deux fois le même arc, et élémentaire s'il ne passe pas deux fois par le même sommet.

Ainsi, dans le graphe précédent il n'y a que trois chemins simples reliant A à C, et seulement deux chemins élémentaires.

Un chemin simple reliant un sommet à lui-même et contenant au moins un arc est appelé un cycle.

C'est le cas par exemple de D—>B->C->D ici.

Notez que, dans le cas d'un graphe non orienté, la restriction imposant aux cycles d'être des chemins simples empêche de revenir sur ses pas.

Ainsi dans le graphe

$\"graphe1.png$

le chemin A->B—>A n'est pas simple et n'est donc pas un cycle.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Distance

La longueur d'un chemin est définie comme le nombre d'arcs qui constituent ce chemin.

La distance entre deux sommets est la longueur du plus court chemin reliant ces deux sommets, le cas échéant.

Ainsi, dans l'exemple ci-dessus, le chemin A->D->B->C a pour longueur 3, mais la distance entre A et C est 2, obtenue pour le chemin plus court A->B->C.

La distance d'un sommet s à lui-même est 0, obtenue pour le chemin allant de s à s en n'empruntant aucun arc.

La distance entre deux sommets n'est pas définie s'il n'existe aucun chemin entre les deux sommets.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Connexité

On dit qu'un graphe non orienté est connexe si, pour toute paire u,v de sommets, il existe un chemin de u à v.

Pour un graphe orienté, on dit qu'il est connexe si le graphe non orienté obtenu en oubliant le sens des arcs est connexe.

On dit qu'un graphe orienté est fortement connexe lorsqu'il existe un chemin de u à v et un chemin de v à u pour toute paire u,v de sommets.

Ainsi, le graphe

$\"graphe1.png$

est connexe mais pas fortement connexe. En effet, il existe un chemin reliant A à B mais pas de chemin reliant B à A.

Le graphe

$\"graphe1.png$

n'est pas connexe, car il n'y a pas de chemin reliant C à E une fois qu'on

a oublié le sens des arcs.

On dit qu'il possède deux composantes conneres, l'une formée des sommets A, B, C et D et l'autre formée des sommets E et F.

De même, le graphe des régions de la figure 11.1 n'est pas connexe. Il contient sept composantes connexes, dont six sont réduites à un unique sommet.

Dans la séquence suivant, nous verrons des algorithmes pour déterminer si un graphe est connexe et plus généralement pour déterminer s'il existe un chemin entre deux sommets.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Vocabulaire

Le vocabulaire des graphes varie selon le contexte et notamment selon le caractère orienté ou non des graphes.

Ainsi, on parle parfois de nœuds et d'arêtes plutôt que de sommets et d'arcs pour les graphes non orientés.

De même, on parle parfois de chaîne plutôt que de chemins dans les graphes non orientés.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Autres caractérisations des chemins

Un chemin peut également être caractérisé par la succession des arcs qu'il emprunte.

C'est notamment pertinent lorsque l'on ne considère pas un graphe simple, et que plusieurs arcs peuvent aller d'un sommet s à un sommet t.

Cette caractérisation peut cependant également comporter une ambiguïté dans le cas des graphes non orientés.

Dans ce cas, on peut aller jusqu'à une description complète donnant la succession des sommets et des arcs.

","title":""},{"edit":"

"}],[{"text":"

Étiquetage

Il est fréquent d'associer une information à chaque sommet et/ou à chaque arc d'un graphe. On parle alors de graphe étiqueté.

Pour ce qui est des sommets, on peut confondre un sommet et son étiquette dès lors que celle-ci est unique.

Ainsi, dans nos exemples précédents, on

peut dire « le sommet «A» ou «le sommet étiqueté par A».

Pour ce qui est des arcs, on peut adopter la notation u -e-> v pour indiquer

que l'arc entre les sommets u et v porte l'étiquette e.

Si la nature de cette étiquette est numérique, alors on peut définir une notion de coût pour un chemin, comme la somme des étiquettes des arcs constituant ce chemin.

On peut alors parler de plus court chemin au sens de ce coût plutôt qu'au sens du nombre d'arcs.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Maintenant que nous savons ce qu'est un graphe, on peut en donner de nombreux exemples.

Sur tous ces exemples, on peut se poser des questions comme :

- le graphe est-il connexe?

- existe-t-il un chemin entre le

sommet A et le sommet B?

- ou encore : quelle est la distance entre les sommets A et B?

","title":"Exemples de graphes"},{"edit":"

"}],[{"text":"

Réseau

Un réseau routier est naturellement un graphe. Ce peut être par exemple un réseau routier à grande échelle, avec des sommets qui sont des villes, reliés par des arcs qui représentent des routes entre ces villes.

Si toutes les routes sont à double sens, le graphe sera naturellement non orienté.

Mais on peut également imaginer un réseau routier à l'intérieur d'une même ville, où les sommets sont plutôt les intersections entre les rues ct les

arcs des portions de rues reliant une intersection à une autre.

Dans ce cas, le graphe sera naturellement orienté dès lors que certaines rues sont à sens unique.

Un navigateur GPS implémente un algorithme de recherche de chemin dans un tel graphe. Il prend en compte des informations supplémentaires, telles que la longueur des routes, la vitesse maximale autorisée, la présence de péages, etc pour calculer des chemins qui minimisent la distance totale, le temps de trajet, etc. La recherche d'un tel chemin minimal n'est pas au programme de terminale.

Un réseau n'est pas nécessairement un réseau routier. On peut ainsi considérer un réseau informatique, où des machines sont reliées entre elles, ou encore un réseau social, où des personnes sont reliées entre elles, par exemple par leurs contacts respectifs.

Dans ce domaine, les mathématiciens ont défini le nombre d'Erdös d'un mathématicien X comme la distance entre le mathématicien Paul Erdös et le mathématicien X dans un graphe non orienté où les arcs relient entre eux les mathématiciens qui sont coauteurs d'un même article.

Toujours dans le domaine des réseaux sociaux, la propriété de «petit monde» énonce que la distance entre deux personnes est très petite (logarithmique, pour être précis) comparativement au nombre d'individus.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Carte

$\"graphe1.png$

Le graphe des régions françaises de la figure 1 est une façon de concevoir la carte des régions. On pourrait faire la même chose avec les départements, les pays du monde, etc.

Un très célèbre théorème de mathématiques, le théorème des quatre couleurs, énonce que les pays d'une carte

planaire peuvent toujours être coloriés avec quatre couleurs seulement sans que deux pays limitrophes aient la même couleur.

Ce théorème s'énonce en termes de graphes en disant que tout graphe qui peut être dessiné dans le plan (i.e., sans que deux arcs ne se croisent) peut voir ses sommets coloriés avec quatre couleurs au plus sans que deux sommets reliés par un are n'aient la même couleur.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Labyrinthe

$\"Labyrinthe\"$

Source : https://omnilogie.fr/O/Labyrinthe

Un labyrinthe constitué de salles reliées entre elles par des portes peut être vu comme un graphe non orienté.

Les sommets sont les salles du labyrinthe et deux sommets sont reliés par un arc s'il existe une porte entre ces deux salles.

Dans la séquence suivant, nous étudierons un algorithme efficace pour déterminer s'il existe un chemin entre deux sommets donnés d'un graphe et même le construire, le cas échéant.

On peut en particulier se servir d'un tel algorithme pour trouver un chemin qui mène de l'entrée à la sortie d'un labyrinthe.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Jeu

Source:https://www.lapouleapois.fr/jeux-traditionnels/8490-jeu-de-dames-pliant-jeujura-3225280813103.html?gclid=CjwKCAiAtK79BRAIEiwA4OskBo1Rmxf0xpVrd0RXq8lOrdTi5JBVE0xvO4Wh081AX_qOdZxG8NzBGxoCkG4QAvD_BwE

De nombreux jeux consistent à modifier une configuration donnée, typiquement en déplacement des pièces, jusqu'à obtenir une configuration particulière.

Dans cette catégorie, on peut citer des jeux à un joueur de type casse-tête, comme l'âne rouge, le solitaire où encore le taquin, mais aussi à plusieurs joueurs, comme les échecs ou les dames.

Pour un tel jeu, on peut concevoir un graphe où les sommets sont les configurations possibles du jeu et les arcs les coups valides qui permettent de passer d'une configuration à une autre.

Un tel graphe est typiquement gigantesque, voire infini, et de

multiples chemins peuvent mener d'une configuration à une autre. Nous verrons que cela n'empêche pas néanmoins de chercher des chemins et en particulier des chemins menant à une configuration gagnante.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Arbre

$\"graphe1.png$

Un arbre peut être naturellement vu comme un graphe où chaque nœud constitue un sommet et est relié aux racines de ses sons-arbres, le cas échéant. On peut le voir au choix comme un graphe non orienté ou comme un graphe orienté, deux solutions étant alors envisageables (arcs dirigés «vers le haut» ou «vers le bas»).

","title":""},{"edit":"

"}],[{"text":"

Il existe de multiples façons de représenter un graphe en machine, selon la nature du graphe mais aussi selon la nature des opérations et des algorithmes

à effectuer sur ce graphe.

Quelle que soit la représentation, on souhaite proposer des opérations de deux sortes :

- d'une part des opérations de construction de graphes, comme l'obtention d'un graphe vide, l'ajout de sommets ou d'arcs, etc. ;

- d'autre part des opérations de parcours d'un graphe, comme parcourir tous les sommets, tous les arcs, ou encore tous les arcs issus d'un

sommet donné.

À priori, on ne souhaite pas fixer le type des sommets d'un graphe.

Ce pourrait être des entiers, des chaînes de caractères ou encore des objets.

Cependant, nous allons commencer par une représentation où les sommets sont des entiers, avant de proposer une représentation plus souple où les sommets peuvent être d'un type quelconque.

On se focalise pour l'instant sur des graphes orientés et on expliquera, à la fin de cette section, comment représenter des graphes non orientés.

","title":"Représentation d'un graphe en Python"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Matrice d'adjacence

Dans cette première représentation, les sommets du graphe sont supposés être les entiers 0,1,...,N — 1 pour un certain entier N, qui se trouve donc être le nombre total de sommets.

On peut alors représenter le graphe par une matrice adj de booléens de taille NxN, c'est-à-dire un tableau de N tableaux de booléens de taille N, où le booléen adj[i][j] indique la présence d'un arc entre les sommets i et j.

On appelle cela une matrice d'adjacence.

Pour construire un certain graphe, on peut commencer par construire une telle matrice où tous les booléens sont initialisés à False, par exemple de la manière suivante :

adj = [[False] * N for _ in range(N)]

Ensuite, on peut ajouter des arcs au graphe, en donnant la valeur True à certains éléments de cette matrice.

Ainsi, on peut ajouter un arc entre les

sommets 2 et 7 avec une simple affectation :

adj[2][7] = True

Et ainsi de suite.

Une telle représentation à le mérite d'être relativement simple. En particulier, on peut parcourir tous les sommets du graphe avec une simple boucle:

for s in range(N):

Programme 36 — Graphe représenté par une matrice d'adjacence

class Graphe:

l'un graphe représenté par une matrice d''adjacence, où les sommets sont les entiers 0,1,...,n-1\"\"\"

def __init__(self, n):

self.n=n

self.adj = [(False] * n for _ in range(n)]

def ajouter arc(self, si, 82):

self.adj{sii[s?2] = True

def arc(self, s1, 52):

return self.adj[s1] [s2]

def voisins(self, s):

v =

for i in range(self.n):

if self.adjfs]lil:

v.append(i)

return v

De même, on peut parcourir tous les voisins du sommet s avec une boucle for et un test :

for v in range(N):

if adj[s][v]:

...

Le programme ci-dessous encapsule une telle matrice d'adjacence dans une classe Graphe.

class Graphe1:

\"\"\"un graphe représenté par une matrice d'adjacence,

où les sommets sont les entiers 0,1,...,n-1\"\"\"

def __init__(self, n):

self.n = n

self.adj = [[False] * n for _ in range(n)]

def ajouter_arc(self, s1, s2):

self.adj[s1][s2] = True

def arc(self, s1, s2):

return self.adj[s1][s2]

def voisins(self, s):

v = []

for i in range(self.n):

if self.adj[s][i]:

v.append(i)

return v

def afficher_matrice(self) :

for l in self.adj:

print(l)

Le constructeur de cette classe prend en argument le nombre de sommets et alloue la matrice.

Une méthode ajouter_arc permet d'ajouter un arc au graphe. Ainsi, on peut écrire

g1 = Graphe1(4)

g1.afficher_matrice()

print(\"Ajout des arcs:\")

g1.ajouter_arc(0,1)

g1.ajouter_arc(0,3)

g1.ajouter_arc(1,2)

g1.ajouter_arc(3,1)

print(g1.voisins(0))

print(g1.voisins(1))

g1.afficher_matrice()

pour construire le graphe représenté ci-dessous:

$\"graphe1.png$

Une méthode arc permet de tester la présence d'un arc entre deux sommets et une méthode voisins renvoie l'ensemble des voisins d'un sommet donné, sous forme d'un tableau.

Efficacité

La matrice d'adjacence est indéniablement simple à mettre en œuvre, mais elle a néanmoins quelques défauts.

D'une part, elle occupe un espace mémoire proportionnel à N x N. Ainsi, un graphe de mille sommets nécessite une matrice d'un million de booléens, ce qui représente déjà quelques mégaoctets, et ce, même si le graphe contient très peu d'arcs.

D'autre part, parcourir tous les voisins d'un sommet donné exige de parcourir toute une ligne de la matrice, c'est-à-dire N booléens, alors même qu'il peut y avoir très peu de voisins.

Enfin, elle limite les sommets à des entiers, qui plus est consécutifs et d'un nombre connu à l'avance. Dans la section suivante, nous présentons une autre façon de représenter un graphe, qui s'affranchit de tous ces défauts.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Dictionnaire d'adjacence

Dans cette nouvelle représentation, un graphe est un dictionnaire, qui associe à chaque sommet l'ensemble de ses voisins. On appelle cela un dictionnaire d'adjacence.

La première conséquence est que les sommets ne sont pas limités à des entiers et qu'il n'est pas nécessaire de les connaître tous a priori.

En effet, il suffit d'ajouter une nouvelle entrée dans le dictionnaire

pour ajouter uu nouveau sommet au graphe.

L'ensemble des sommets du graphe est exactement l'ensemble des clés du dictionnaire.

En particulier, on peut parcourir tous les sommets d'un graphe stocké dans la variable graphe avec la boucle suivante :

for s in graphe:

Les voisins du sommet s sont donnés par l'ensemble graphe[s]. On peut donc les parcourir avec la boucle suivante :

for v in graphe[s]:

La deuxième conséquence de cette nouvelle représentation est que ce parcours est maintenant d'une complexité directement proportionnelle au nombre de voisins de s, indépendamment du nombre total de sommets du graphe.

Le programme ci-dessous encapsule un tel dictionnaire d'adjacence dans une classe Graphe.

Programme — Graphe représenté par un dictionnaire d'adjacence

class Graphe2:

\"\"\"un graphe comme un dictionnaire d'adjacence\"\"\"

def __init__(self):

self.adj = {}

def ajouter_sommet(self, s):

if s not in self.adj:

self.adj[s] = set()

def ajouter_arc(self, s1, s2):

self.ajouter_sommet(s1)

self.ajouter_sommet(s2)

self.adj[s1].add(s2)

def arc(self, s1, s2):

return s2 in self.adj[s1]

def sommets(self):

return list (self.adj)

def voisins(self, s):

return self.adj[s]

Le constructeur de cette classe alloue un dictionnaire vide.

Une méthode ajouter_sommet permet d'ajouter un nouveau sommet et une

méthode ajouter_arc permet d'ajouter un arc.

Ainsi, on peut écrire

g2 = Graphe2()

g2.ajouter_arc(0,1)

g2.ajouter_arc(0,3)

g2.ajouter_arc(1,2)

g2.ajouter_arc(3,1)

print(g2.voisins(0))

print(g2.voisins(1))

pour construire le graphe représenté ci-dessous.

$\"graphe1.png$

On note que le constructeur ne prend pas d'argument (contrairement à la matrice d'adjacence, où on avait passé le nombre de sommet, 4, en argument).

On note également qu'on n'a pas pris la peine d'ajouter les quatre sommets au graphe, parce que la méthode ajouter_arc le fait déjà.

Mais si un sommet n'est relié à aucun autre, alors il faut le rajouter explicitement au graphe, avec la méthode

aïouter_sommet.

On n'est nas censé annuler la méthode arc aver un sam-met si qui ne serait pas dans le graphe, sans quoi l'accès au dictionnaire adj avec la clé s1 provoquerait l'exception KeyError.

Efficacité

En ce qui concerne le coût des opérations, le dictionnaire d'adjacence est optimal:

ajouter un sommet, ajouter un arc ou tester la présence d'un arc se fait en temps constant (les dictionnaires et les ensembles de Python étant réalisés par des tables de hachage) et parcourir les voisins d'un sommet donné sc fait en un temps proportionnel au nombre de ces voisins.

Le seul intérêt de la matrice d'adjacence peut résider dans l'espace mémoire qu'elle occupe, qui peut être inférieur à celui d'un dictionnaire d'adjacence dans certains cas.

Ainsi, un graphe de 400 sommets qui contient presque tous les arcs possibles occupe dix fois moins d'espace quand il est représenté par une matrice d'adjacence que lorsqu'il est représenté par un dictionnaire d'adjacence. Mais s'il contient au contraire très peu d'arcs, alors c'est le dictionnaire d'adjacence qui occupe moins de mémoire, jusqu'à 13 fois moins.

Ën pratique, on suggère de privilégier le dictionnaire d'adjacence, car il permet des sommets d'un type quelconque, et de ne retenir la matrice d'adjacence que dans le cas extrême d'un graphe dont le dictionnaire d'adjacence ne tiendrait pas en mémoire.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Autres représentations

Dans la littérature, on rencontre souvent une autre représentation des graphes, dite de liste d'adjacence, où chaque sommet est associé à une liste ordonnée de ses voisins.

En Python, une telle liste pourrait être réalisée par une liste chaînée ou

encore un tableau.

Cependant, une telle représentation n'offre aucun avantage sur la solution à base d'ensembles que nous avons proposée.

En effet, pour déterminer s'il existe un arc entre les sommets s1 et s2, il faudrait parcourir linéairement la liste des voisins de s1, là où l'ensemble

d'adjacence offre une réponse en temps constant.

De même, on rencontre souvent des représentations des graphes utilisant

non pas un dictionnaire mais un tableau. Cela impose cependant que les sommets soient les entiers 0,1...,N — 1.

Là encore, notre solution utilisant un dictionnaire est meilleure:

elle est plus souple quant à la nature des sommets et fournit des opérations tout aussi efficaces (un dictionnaire, comme un tableau, offre des opérations en temps constant).

On aura compris qu'il y a de multiples façons de représeuter un graphe. Ainsi, on peut imaginer d'autres combinaisons, comme un tableau d'ensembles ou encore un dictionnaire de listes. Dans tous les cas, la représentation est relativement secondaire, dès lors que lon peut accéder à tous les sommets du graphe et à tous les voisins d'un sommet donné d'une façon ou d'une autre.

","title":""},{"edit":"

"}],[{"text":"

Représenter un graphe non orienté

La façon la plus simple de représenter un graphe non orienté consiste à le représenter exactement comme un graphe orienté, avec l'une ou l'autre des deux solutions que nous venons de présenter, et d'assurer en permanence l'invariant suivant :

- il y a un arc reliant le sommet u au sommet v si et seulement si il y à un arc reliant le sommet v au sommet u.

Dit autrement, on a systématiquement un double arc, orienté dans les deux sens.

Pour maintenir cet invariant, il suffit que les opérations ajouter_arc et supprimer_arc ajoutent et enlèvent systématiquement la paire d'arcs.

Ainsi, pour une matrice d'adjacence, on modifie la méthode ajouter_arc comme ceci:

self.adj[s1][s2] = True

self.adj[s2][s1] = True

Et pour un dictionnaire d'adjacence, on la modifie comme ceci:

self.ajouter_sommet(si)

self.ajouter_sommet(s2)

self.adj[s1].add(s2)

self.adj[s2].add(s1)

Avec ce choix de représentation des graphes non orientés, les algorithmes de

parcours de graphe que nous étudions à la séquence suivante s'écrivent exactement de la même façon que les graphes soient ou non orientés.

La seule subtilité est éventuellement le décompte des arcs, où l'on peut vouloir diviser par deux le nombre d'arcs obtenu au total.

En modifiant la classe Graphe2 on obtient la classe suivante pour les graphes non orientés:

class Graphe3:

\"\"\"un graphe non orienté comme un dictionnaire d'adjacence\"\"\"

def __init__(self):

self.adj = {}

def ajouter_sommet(self, s):

if s not in self.adj:

self.adj[s] = set()

def ajouter_arc(self, s1, s2):

self.ajouter_sommet(s1)

self.ajouter_sommet(s2)

self.adj[s1].add(s2)

self.adj[s2].add(s1)

def arc(self, s1, s2):

return s2 in self.adj[s1]

def sommets(self):

return list (self.adj)

def voisins(self, s):

return self.adj[s]

Donc le graphe ci-dessous;

$\"graphe1.png$

est représenté de la manière suivante :

g3 = Graphe3()

g3.ajouter_arc(\"A\",\"B\")

g3.ajouter_arc(\"A\",\"D\")

g3.ajouter_arc(\"B\",\"C\")

g3.ajouter_arc(\"D\",\"C\")

g3.ajouter_arc(\"B\",\"D\")

print(g3.voisins(\"B\"))

Tester le code et conclure.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Représenter un graphe infini

Si un graphe est infini, il reste néanmoins possible de le représenter en machine. En effet, beaucoup d'algorithmes ont uniquement besoin d'une fonction voisins qui énumère les voisins d'un sommet donné (sous la forme d'un tableau, d'un ensemble, etc.).

C'est le cas notamment des algorithmes de recherche de chemin que nous détaillons dans la séquence suivante. Ainsi, même si le graphe est infini, il suffit que les voisins d'un sommet donné soient en nombre fini pour que la fonction voisins puisse être réalisée.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

L'algorithme étudié va colorie un graphe à l'aide d'un algorithme glouton.

Colorier un graphe veut dire associer

une couleur à chacun de ses sommets, de façon à ce que deux sommets reliés par un arc n'aient pas la même couleur.

Colorier un graphe avec un minimum de couleurs est un problème difficile, mais si on accepte l'idée d'utiliser éventuellement plus de couleurs que nécessaire, alors on peut colorier un graphe efficacement.

Le principe d'un coloriage glouton est simple. On parcourt les sommets dans un ordre arbitraire et, pour chaque sommet, on lui attribue la première couleur qui n'est pas utilisée par ses voisins.

Le programme ci-dessous réalise cet algorithme. Il est décomposé en deux fonctions.

La fonction principale, coloriage, reçoit un graphe g en argument et renvoie un couple constituée d'un coloriage et du nombre total de couleurs utilisées.

Le coloriage est représenté par un dictionnaire, couleur, qui associe à tout sommet une couleur.

Une couleur est ici un entier naturel.

La variable n maintient le nombre total de couleurs utilisées.

Pour attribuer une couleur à un sommet, on utilise une seconde fonction, appelée mex (pour minimum exclus), qui reçoit en arguments l'ensemble des voisins du sommet et le coloriage courant couleur.

Cette fonction cherche la plus petite couleur qui n'est pas encore utilisée par les voisins.

Pour cela, elle utilise un tableau dispo qui indique, pour chaque couleur, si elle est encore disponible.

La taille de ce tableau est n+1 où n est le nombre de voisins.

On sera en effet assuré de trouver au moins une couleur disponible parmi les n+1 premiers entiers.

Une première boucle commence par marquer

toutes les couleurs utilisées.

IL faut être soigneux ici, en ne considérant que les sommets déjà coloriés d'une part et uniquement ceux pour lesquels la couleur est inférieure ou égale à n d'autre part, sans quoi on accéderait au tableau dispo en dehors de ses bornes.

Ensuite, une seconde boucle parcourt le tableau dispo à la recherche d'une couleur disponible. Il y en a forcément une et par conséquent la toute dernière ligne de la fonction est inatteignable, ce que l'on manifeste avec l'instruction assert False.

On pourrait se contenter de ne rien faire, mais une programmation défensive est une bonne pratique.

Cet algorithme est efficace, car il parcourt chaque sommet une seule fois et, pour chaque sommet, il parcourt l'ensemble de ses voisins une seule fois.

Dit autrement, le temps de calcul de cet algorithme est directement proportionnel à la taille du graphe, c'est-à-dire à la somme du nombre de ses sommets et de ses arcs.

Programme — Coloriage glouton d'un graphe

def mex(voisins, couleur):

\"\"\"la plus petite couleur non utilisée par les voisins\"\"\"

n = len(voisins)

dispo = [True] * (n + 1)

for v in voisins:

if v in couleur and couleur[v] <= n:

dispo[couleur[v]] = False

for c in range(n + 1):

if dispo[c]:

return c

assert False # on n'arrivera jamais ici

def coloriage(g):

\"\"\"colorie graphe g avec un algorithme glouton\"\"\"

couleur = {}

n = 0

for s in g.sommets():

c = mex(g.voisins(s), couleur)

couleur[s] = c

n = max(n, c + 1)

return couleur, n

On ne peut pas faire mieux, car il faut examiner tout sommet pour lui donner une couleur et il faut examiner tout arc pour prendre en compte toutes les contraintes.

$\"graphe1.png$

Créons le graphe des régions: