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.

def combinaison(l1, l2):
    """
    Permet de combiner deux listes ordonnées pour créer une liste ordonnée
    """
    l = []
    i1 = 0
    i2 = 0
    while i1 < len(l1) and i2 < len(l2):
        if l1[i1] < l2[i2]:
            l.append(l1[i1])
            i1 = i1 + 1
        else:
            l.append(l2[i2])
            i2 = i2 + 1
    return l + l1[i1:] + l2[i2:] # L'une des deux est vide

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

def triFusion(l):
    """
    Fonction implémentant l'algorithme de tri-fusion
    """
    if len(l) == 1:
        return l
    else:
        m = len(l) // 2
        return combinaison(triFusion(l[:m]),triFusion(l[m:]))

def combinaison(l1, l2):
    """
    Permet de combiner deux listes ordonnées pour créer une liste ordonnée
    """
    l = []
    i1 = 0
    i2 = 0
    while i1 < len(l1) and i2 < len(l2):
        if l1[i1] < l2[i2]:
            l.append(l1[i1])
            i1 = i1 + 1
        else:
            l.append(l2[i2])
            i2 = i2 + 1
    return l + l1[i1:] + l2[i2:] # L'une des deux est vide

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.

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 !
	"""
	couleur_a, couleur_b = image.getpixel(pixel_a),image.getpixel(pixel_b)
    image.putpixel(pixel_a,couleur_b)
    image.putpixel(pixel_b,couleur_a)

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 !
	"""
	xa, ya = coinHautGauche_a
    xb, yb = coinHautGauche_b
    for i in range(n):
        for j in range(n):
            echangePixels(image,(xa+i,ya+j),(xb+i,yb+j))

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 !
	"""

	if taille < 2: return
    x,y = coinHautGauche
    n = taille // 2
    tourneRecursif(image,(x,y),n)
    tourneRecursif(image,(x+n,y),n)
    tourneRecursif(image,(x+n,y+n),n)
    tourneRecursif(image,(x,y+n),n)
    echangeQuadrant(image,(x,y),(x+n,y),n)
    echangeQuadrant(image,(x+n,y),(x+n,y+n),n)
    echangeQuadrant(image,(x+n,y+n),(x,y+n),n)

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

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 ?