Diviser pour régner - Applications

Il y a de nombreuses applications du principe "Diviser pour régner" : dès que l'on peut résoudre un gros problème en le scindant en plus petits problèmes indépendants, il faut songer à l'utiliser !

Voila des exemples pour lesquelles vous combinerez l'utilisation de la méthode "diviser pour régner" et la récursivité, les deux étant très souvent liées !

Pour comparer la vitesse d'exécution d'algorithme Diviser pour Régner avec d'autres, vous pourrez utiliser le module timeit.

Chaîne multiple

Voila une première "mise en bouche" 😋 assez simple à comprendre qui va bien vous faire saisir l’intérêt de l'approche Diviser pour Régner.

Vous connaissez la syntaxe qui permet d'obtenir une chaîne de caractères contenant n fois le même caractère/la même suite de caractères :


>>> 'Ha'*8
'HaHaHaHaHaHaHaHaHaHa'

La manière naïve de construire une telle chaîne est de concaténer n fois le motif à la suite :

def chaine_multiple(motif: str, n: int)->str: ch = '' for i in range(n): ch += motif return ch print(chaine_multiple('Ha', 8))

Une manière plus efficace serait de procéder plutôt ainsi :

chaîne('Ha', 8) = 'HaHaHaHaHaHaHaHa' = 'HaHaHaHa' + 'HaHaHaHa' = chaîne('Ha', 4) + chaîne('Ha', 4)
chaîne('Ha', 4) = 'HaHaHaHa' = 'HaHa' + ''HaHa' = chaîne('Ha', 2) + chaîne('Ha', 2)
chaîne('Ha', 2) = 'HaHa' = 'Ha' + 'Ha' = chaîne('Ha', 1) + chaîne('Ha', 1)
chaîne('Ha', 1) = 'Ha' : cas de base !
donc, au final : chaîne(motif, n) = chaîne(motif, n//2) + chaine(motif, n//2)

On a donc remplacé n concaténations du motif par log₂(n) concaténations de sous-chaînes.

En quoi diminuer le nombre de concaténations accélère-t-il les choses ? C'est lié à la manière dont Python ( entre autres langages ) gère les chaînes de caractères : ce sont des objets immuables, ce qui signifie qu'à chaque concaténation, Python crée en réalité un nouvel objet en recopiant les caractères de l'ancienne chaîne dans la nouvelle, ce qui prend évidemment du temps...Diminuer le nombre de concaténations améliore donc la vitesse d’exécution.

Diviser : on divise la chaîne par 2 jusqu'à arriver à un simple motif
Régner : on concatène un motif à lui-même, puis une sous-chaîne avec elle-même, etc...
Combiner : la chaîne finale est la concaténation des sous-chaînes obtenues à chaque étape précédente

Il faut cependant prendre garde à la parité de n : si à un appel récursif donné n est impair ( ce qui arrivera forcément si la valeur de n lors de l'appel initial de la fonction n'est pas une puissance de 2 ), il faut rajouter alors un motif supplémentaire à la concaténation des deux sous-chaînes; on distinguera donc deux cas généraux dans la récursion, l'un pour n pair, l'autre pour n impair.

Écrire une fonction chaine_multiple() qui prend en paramètre un motif motif et un entier n, et renvoie la chaîne motif*n, en utilisant l'approche Diviser pour Régner.

def chaine_multiple(motif: str, n: int)->str: pass

SOLUTION

L'exponentiation rapide

Ou comment calculer efficacement la puissance d'un nombre ( xⁿ ) ?

Algorithme naïf

La puissance n d'un nombre x est définie par : xⁿ = x . x . x ........ . x ( n fois )

Après avoir établi le cas général de la récursivité et son cas de base, écrire une fonction récursive puissance_naive(x, n) qui calcule la puissance n d'un nombre x.

def puissance_naive(x: int, n: int)->int: pass
Si on considère comme critère le nombre de multiplications réalisées, quelle est la complexité de l'algorithme utilisé ?

SOLUTION

Approche diviser pour régner

On peut faire mieux en adoptant une approche diviser pour régner.

Dans un premier temps, supposons pour simplifier que la puissance n est une puissance de 2 (1, 2, 4, 8, 16, ...).
Par exemple :

x¹⁶ = (x²)⁸ = (x²)²)⁴ = (x²)²)²)² ( soit 4 = log₂16 élévations au carré de x )
x⁸ = (x²)⁴ = (x²)²)² ( soit 3 = log₂8 élévations au carré de x )
etc.....
donc : xⁿ = (x²)²)²)²)..... ( log₂ n élévations au carré )

→ autrement dit, on remplace n multiplications de x par lui-même par log₂n élévations au carré de de x, d'où l'énorme gain en complexité quand n devient grand !

Diviser : on réduit le calcul de n fois x par lui-même au calcul de log₂ n fois x²
Régner : on calcule récursivement (x²)^n/2.
Combiner : la valeur de xⁿ est le résultat des log₂n élévations au carré de x

Cependant, si n n'est pas une puissance de 2, la division par 2 de n donnera un nombre impair à certains niveaux de la récursion; il faudra donc considérer 2 situations pour le cas général :

si n est pair : xⁿ = (x²)^n//2
si n est impair : xⁿ = x * (x²)^n//2

Écrire une fonction récursive expo_rapide(x, n) qui calcule la valeur de xⁿ avec l'approche diviser pour régner.
Bien réfléchir au cas de base de la récursion...

def expo_rapide(x: int, n: int)->int: pass

SOLUTION

Le tri rapide

Le tri rapide (en Anglais : quicksort ) d'un tableau ou d'une liste est peut-être l'algorithme de tri le plus utilisé. Il est relativement simple à comprendre et à implémenter, et, comme son nom l'indique, très rapide.

L'idée de l'algorithme, qui utilise l'approche divise pour régner, est très simple :

choisir un élément arbitraire du tableau ou de la liste, que l'on appelle pivot.
réorganiser les éléments du tableau ou de la liste de sorte que tous les éléments inférieurs au pivot soient à gauche du pivot et les éléments supérieurs au pivot à droite du pivot.
trier récursivement la partie gauche et la partie droite du tableau ou de la liste.

Si l'étape numéro 2 ci-dessus peut se faire avec une complexité O(n) et si le nombre d'éléments de la partie gauche et le nombre d'éléments de la partie droite ainsi obtenues ne sont pas trop différents, alors, la complexité de l'algorithme est O(n.log n).

Pour que les deux parties "gauche" et "droite" soient de tailles similaires, le pivot doit être proche de l'élément médian du tableau ou de la liste. Malheureusement, un algorithme optimal pour calculer l'élément médian est assez coûteux en temps...On choisira donc le pivot soit comme un élément donné du tableau ( le premier ou le dernier ), ou alors de manière complètement aléatoire.

Diviser : on découpe le tableau ou la liste à trier en deux parties "gauche" et "droite" selon la valeur des éléments par rapport à celle du pivot
Régner : on trie récursivement chaque partie "gauche" et "droite".
Combiner : on concatène les parties gauche et droite triées

Faire la trace de l'algorithme avec la liste suivante : [4, 7, 3, 6, 2, 1, 5] en prenant à chaque fois le premier élément comme pivot

SOLUTION


fonction tri-rapide(L: liste):
	si L n'a plus qu'1 ou 0 élément
		renvoyer L
	sinon :
		choisir le pivot
		gauche <- liste des éléments de L plus petits ou égaux au pivot, le pivot exclus
		droite <- liste des éléments de L plus grands que le pivot ( idem )
		
		gauche <- tri_rapide(gauche)
		droite <- tri_rapide(droite)
		
		renvoyer gauche + pivot + droite
	fin si

On notera qu'il n'y pas besoin de "fusionner" deux listes comme dans le tri-fusion, simplement d'une concaténation des parties "gauche" et "droite" ( sans oublier d'intercaler au milieu le pivot pour ne pas "perdre" cet élément ).

Écrire une fonction récursive implémentant le tri rapide d'une liste, en choisissant le pivot :

dans un premier temps comme premier élément de la liste
dans un deuxième temps, comme élément choisi aléatoirement dans la liste

A la place des "tranches" de liste hors programme, penser à utiliser plutôt des listes par compréhension.

L = [86, 2, 3, 44, 91, 34, 50, 61, 67, 76, 20, 10, 19, 4, 42, 54, 4, 1, 88, 70, 94, 86, 11, 63, 60, 11, 62, 41, 8, 29, 73, 93, 12, 62, 2, 29, 52, 20, 84, 36, 33, 32, 17, 33, 63, 84, 82, 32, 42, 12] def tri_rapide(L: list)->list: pass

SOLUTION

Contre-exemples !

L'approche "diviser pour régner" est-elle toujours judicieuse à utiliser ? Faut-il penser qu'elle améliore toujours la complexité des algorithmes ?

Les deux exemples suivants vont vous montrer que la réponse est à nuancer...

Recherche du maximum et du minimum dans une liste

Le problème est de déterminer la valeur du maximum ou du minimum d'une liste de nombres.

Approche naïve, mais avec diviser pour régner quand même...

En adoptant le paradigme "diviser pour régner", l'idée pour résoudre cette question est de calculer récursivement le maximum de la première moitié de la liste et celui de la seconde, puis de les comparer. Le plus grand des deux sera le maximum de toute la liste.
La condition d'arrêt à la récursivité sera l'obtention d'une liste à un seul élément, son maximum étant bien sûr la valeur de cet élément.


si la liste est réduite à un seul élément:	# Régner
	renvoyer cet élément

sinon:
	max_gauche ← rechercher le maximum dans la partie gauche du tableau	# Diviser
	max_droit ← rechercher le maximum dans la partie droite du tableau
	
renvoyer le plus grand entre max_gauche et max_droit	# Combiner

Écrire une fonction maximum() qui renvoie le maximum d'une liste ou d'un tableau en utilisant le principe Diviser pour Régner.
On pourra là aussi utiliser deux variables g et d pour "délimiter" la partie de la liste à traiter à chaque appel récursif.
Faire de même pour une fonction minimum().
Que pensez-vous de la complexité de l'un ou l'autre de ces deux algorithmes par rapport à la recherche séquentielle du maximum et du minimum ?
Si on exprime la complexité en fonction du nombre de comparaisons à faire lors de la recherche des valeurs du maximum et du minimum de la liste l'une après l'autre, quelle est la complexité de cette recherche ?

L = [17, 57, 88, 47, 4, 8, 33, 9, 99, 10, 84, 93, 62, 65, 56, 65, 92, 62, 95, 65, 16, 55, 85, 80, 55, 45, 18, 55, 48, 63, 69, 3, 15, 30, 58, 16, 54, 90, 55, 28, 39, 71, 52, 68, 89, 21, 86, 43, 37, 55] def maximum(L: list, g: int, d: int)->int: pass def minimum(L: list, g: int, d: int)->int: pass

SOLUTION

Une solution : recherche du maximum et du minimum...en même temps !

En réalité, l'approche Diviser pour Régner devient pertinente dans le cas de la recherche simultanée du maximum et du minimum dans la liste, car cela revient à faire beaucoup moins de comparaisons que si on recherchait ces deux valeurs l'une après l'autre.

écrire, en adaptant les fonctions précédentes, une seule fonction min_et_max qui renvoie simultanément le maximum et le minimum d'une liste ( par exemple sous forme d'un tuple (minimum, maximum) ) en utilisant l'approche diviser pour régner.
Sur l'exemple de la liste : [1, 3, 5, 2, 9], montrer que l'on fait effectivement moins de comparaisons en recherchant le maximum et le minimum en même temps en utilisant une approche Diviser pour Régner.
utiliser le module timeit pour comparer la durée des recherches successive et simultanée du maximum et du minimum d'une liste.

SOLUTION

Recherche d’un élément dans une liste non triée.

La recherche dichotomique d'une seule valeur dans une liste triée n'est pas intéressante, car il faut ( forcément...) avoir trié au préalable la liste; or, un théorème énonce qu'il n'y a aucun algorithme de tri de complexité meilleure que O(n.lg n), complexité qui se "rajoute" donc à celle de la fonction de recherche dichotomique même.
N'est-il alors pas possible de s'affranchir de cette étape de tri et faire la recherche dans une liste non-triée ?

En adoptant le paradigme "diviser pour régner", l'idée serait alors de rechercher récursivement l'élément dans la première moitié de la liste et dans la seconde, puis de combiner les résultats avec l'opérateur logique OU.

La condition d'arrêt ( cas de base ) de la récursivité sera l'obtention d'une liste à un seul élément, car il est alors immédiat de conclure si l'élément recherché appartient à une telle liste ou non.

La fonction récursive implémentant cette relation de récurrence réalisera donc deux appels à elle-même :


fonction recherche(liste, valeur)
	si liste n'a qu'un seul élément : # Régner
		si il est égal à valeur:
			renvoyer Vrai
		sinon :
			renvoyer Faux
		fin si
	fin si
	
	gauche = moitié gauche de liste  # Diviser
	droite = moitié droite de liste
	
	renvoyer recherche(gauche, valeur) OU recherche(droite, valeur) # Combiner

Écrire une fonction recherche() récursive qui :
- prend en paramètres une liste L non triée et une valeur n ( ainsi que les deux indices maintenant "habituels" g et d qui servent à "délimiter" les parties de la liste à traiter )
- retourne True si n est dans L, False sinon.
Que pensez-vous de la complexité de cet algorithme ? Est-ce une utilisation pertinente du principe "diviser pour régner" par rapport à une simple recherche séquentielle ?
Connaissez-vous une situation où la recherche d'une valeur dans un ensemble non ordonné est de meilleure complexité ?

L = [17, 57, 88, 47, 4, 8, 33, 9, 99, 10, 84, 93, 62, 65, 56, 65, 92, 62, 95, 65, 16, 55, 85, 80, 55, 45, 18, 55, 48, 63, 69, 3, 15, 30, 58, 16, 54, 90, 55, 28, 39, 71, 52, 68, 89, 21, 86, 43, 37, 55] def recherche(L: int, n: int, g: int, d: int)->bool: pass

SOLUTION