Diviser pour régner

Description

Diviser pour régner est une technique algorithmique qui se déroule en trois étapes :

• diviser : découper le problème en sous-problèmes ;
• régner : résoudre les sous-problèmes (en utilisant éventuellement diviser pour régner) ;
• combiner : trouver une solution au problème initial à partir des solutions des sous-problèmes.

Exemple du tri fusion

Le tri fusion est encore un algorithme de tri. Celui-ci est récursif et utilise, bien sur, la méthode diviser pour régner. Voici un algorithme décrivant le tri fusion :

triFusion(liste):
    si la liste contient un élément ou moins:
		retourner liste
    sinon:
		listegauche = demi-liste gauche de liste
		listedroite = demi-liste droite de liste
		retourner combinaison(triFusion(listegauche), triFusion(listedroite))

combinaison(listegauche, listedroite):
	# listegauche et listedroite sont des listes ordonées
	listeretour = liste vide
	indicelistegauche = 1
	indicelistedroite = 1
	tant que indicelistegauche ≤ taille(listegauche) et indicelistedroite ≤ taille(listedroite):
		si listegauche[indicelistegauche] < listedroite[indicelistedroite]:
			on ajoute listegauche[indicelistegauche] à listeretour
			indicelistegauche = indicelistegauche + 1
		sinon:
			on ajoute listedroite[indicelistedroite] à listeretour
			indicelistedroite = indicelistedroite + 1
	renvoyer listeretour + la fin de la liste non totalement explorée

Voici un schéma montrant le déroulement de cet algorithme sur la liste [4, 3, 8, 2, 7, 1, 5] :

1) Quelle ligne de l'algorithme fait qu'il est récursif ?

2) Expliquer en une phrase ce que fait la fonction combinaison.

3) Proposez une implémentation en Python de la fonction combinaison.

4) Proposez enfin une implémentation en Python du tri fusion.

Application : rotation d'image

Il est possible d'appliquer la méthode diviser pour régner à la rotation d'une image carrée. Nous ferons tourner l'image de 90° dans le sens trigonométrique. La méthode est illustrée sur le schéma ci-dessous :

• on coupe l'image en quatre quadrants ;
• on effectue une rotation récursive de chacun des quadrants ;
• on applique une permutation circulaire des quadrants.

Nous utiliserons le module PIL déjà utilisé l'année dernière. L'image à faire tourner sera la joconde. Elle est carrée avec une taille égale à une puissance de 2. Voici la structure que vous pourrez utiliser :

from PIL import Image

img = Image.open("joconde.png")
# Affiche l'image originale
img.show()

def echangePixels(image,pixel_a,pixel_b):
	"""
	Échange la couleur des deux pixels pixel_a et pixel_b.
	pixel_a : tuple de coordonnées
	pixel_b : tuple de coordonnées

	À compléter !
	"""
	…

def tourne(image):
	"""
	Lance la fonction récursive sur l'image originale.

	Fonction complète.
	"""
    tourneRecursif(image,(0,0),image.size[0])

def echangeQuadrant(image,coinHautGauche_a,coinHautGauche_b,n):
	"""
	Échange les pixels entre les deux quadrants de taille n
	définis par leur coin haut gauche.

	coinHautGauche_a : tuple des coordonnées du coin supérieur gauche du quadrant a
	coinHautGauche_b : tuple des coordonnées du coin supérieur gauche du quadrant b
	n : taille des deux quadrants

	À compléter !
	"""
	…

def tourneRecursif(image,coinHautGauche,taille):
	"""
	Applique une rotation du quadrant de l'image défini par
	son coin supérieur gauche et sa taille.

	coinHautGauche : tuple des coordonnées du coin supérieur gauche du quadrant
	taille : taille du quadrant à faire tourner

	À compléter !
	"""
	…

# Lance le programme
tourne(img)
# Affiche l'image
img.show()

Vous chercherez vous-même sur la documentation de PIL les méthodes à utiliser pour accéder aux pixels de l'image.

Application : minimum et maximum d'un tableau

L'objectif est d'écrire une fonction récursive min_et_max(T, a, b) renvoyant le couple (minimum, maximum) du tableau T[a:b].

Un algorithme du type « diviser pour régner » permet de déterminer ce couple en exploitant le fait qu’une seule comparaison suffit pour obtenir à la fois le minimum et le maximum d'un tableau de taille 2. Voici cet algorithme :

VARIABLES
T : tableau

DEBUT
si T ne contient qu'un élément:
	retourner (T[0], T[0])
sinon si T contient deux éléments:
	retourner le couple (minimum, maximum)
sinon:
	tableaugauche = demi-tableau gauche de T
	tableaudroit = demi-tableau droit de T
	calculer récursivement le couple (min, max) des deux tableaux
	fusionner les résultats précédents
	retourner le couple (minimum, maximum)
FIN

5) Écrire la fonction min_et_max(T) en Python.

6) La tester sur le tableau T = [1, 6, -5, 8, 14, -2, -7, 21] en lancant la commande min_et_max(T)

7) Combien cette fonction utilise de comparaisons pour un tableau de 4 éléments ?

8) Combien un algorithme classique utilise de comparaisons pour un tableau de 4 éléments ?

9) Répondez aux deux questions précédentes pour des tableaux de 8, 16 et 32 éléments. Que pouvez-vous conclure sur la complexité de cet algorithme ?