Aller au contenu

TNSI : cours Diviser Pour Régner⚓︎

Introduction⚓︎

Une technique de programmation souvent efficace, lorsqu'elle est possible, consiste en :

  • Diviser un problème initial en plusieurs sous-problèmes indépendants,
  • Régner : Résoudre les sous-problèmes récursivement (ou directement s'ils sont assez petits), puis
  • Combiner ensemble les sous-problèmes, ce qui veut dire: Calculer une solution au problème initial à partir des solutions des sous-problèmes.

Principe Général⚓︎

Le paradigme de programmation Diviser pour Régner 🇫🇷 ou Divide and Conquer 🇺🇸 consiste à ramener la résolution d'un problème dépendant d'un entier \(n\) à la résolution de un ou plusieurs sous-problèmes indépendants, dont la taille des entrées passe de \(n\) à \(\dfrac n2\), ou plus généralement une fraction de \(n\) (\(\dfrac n3\), \(\dfrac n4\), \(\dfrac {2n}{3}\)...)

Les algorithmes ainsi conçus s'écrivent naturellement de manière récursive. Le procédé Diviser pour Régner est un cas particulier de la récursivité, où la taille du problème est divisée à chaque appel récursif plutôt que seulement décrémenté d'une unité.

Exemple de l'Exponentiation Rapide⚓︎

Principe⚓︎

Le calcul de la puissance d'un nombre définie par:

  • \(a^0=1\) et
  • Si \(n\) est pair, \(a^n=(a\times a)^{\dfrac n2}\)
  • Sinon, si \(n\) est impair, \(a^n=a\times (a\times a)^{\dfrac {n-1}{2}}\)

Ex

  1. Proposer un algorithme récursif dans le langage Python qui prend comme arguments un réel \(a\) et un entier \(n\), et qui calcule récursivement l'exponnentiation rapide \(a^n\).

def expo(a:float,n:int)->float:
  if n == 0:
    return 1
  elif n%2 == 0:
    return expo(a*a,int(n/2))
  else:
    return a*expo(a*a,int((n-1)/2))

Étudier la complexité temporelle de cet algorithme

A chaque appel récursif, la taille du problème est bien divisée par \(2\), et les sous-problèmes sont indépendants. En notant \(T(n)\) le nombre d'opérations à réaliser pour cet algorithme, alors \(T(n)\) vérifie \(T(n)\le T(\dfrac {n}{2})+1\) et \(T(1)=1\) donc dans le pire des cas \(T(n)= T(\dfrac {n}{2})+1\)

donc \(T(n)=O(log_2n)\) \(\,\) d'après le Master Theorem

Tri Fusion⚓︎

Le tri fusion permet de trier une liste \(A\) selon le principe Diviser pour Régner.

  • Pour reconstuire une liste à partir de deux listes \(A1\) et \(A2\) déjà triées, on peut les interclasser de la manière suivante:

    • On compare les plus petits éléments de chacune d'entre elles
    • On place le plus petit des deux dans une nouvelle liste \(Atemp\), et on poursuit cette opération jusqu'à épuisement d'une des deux listes
    • On complète alors \(Atemp\) en ajoutant à la fin de celle-ci, les éléments restants de la liste non vide.

  • Le Tri fusion est alors défini de la manière suivante:

    • Si la liste \(A\) a au plus un élément, Alors elle est déjà triée
    • Si la liste \(A\) a deux élément ou plus, Alors:
      • Diviser On partage \(A\) en deux sous-listes de même taille, à un élément près, puis
      • Régner On résoud récursivement chaque sous-problème : on appelle récursivement la fonction sur chacune des sous-listes, et
      • Combiner On interclasse / fusionne les sous-listes triées: À partir de deux sous-listes triées, on reconstruit une grande liste, combinaison entre les deux, encore triée.

Exp

G[4,3,8,2,7,1,5][4,3,8,2,7,1,5][4,3,8,2][4,3,8,2][4,3,8,2,7,1,5]--[4,3,8,2][7,1,5][7,1,5][4,3,8,2,7,1,5]--[7,1,5][4,3][4,3][4,3,8,2]--[4,3][8,2][8,2][4,3,8,2]--[8,2][4][4][4,3]--[4][3][3][4,3]--[3][3,4][3,4][4]--[3,4][3]--[3,4][2,3,4,8][2,3,4,8][3,4]--[2,3,4,8][8][8][8,2]--[8][2][2][8,2]--[2][2,8][2,8][8]--[2,8][2]--[2,8][2,8]--[2,3,4,8][1,2,3,4,5,7,8][1,2,3,4,5,7,8][2,3,4,8]--[1,2,3,4,5,7,8][7,1][7,1][7,1,5]--[7,1][5][5][7,1,5]--[5][7][7][7,1]--[7][1][1][7,1]--[1][1,7][1,7][7]--[1,7][1]--[1,7][1,5,7][1,5,7][5]--[1,5,7][1,7]--[1,5,7][1,5,7]--[1,2,3,4,5,7,8]

Ex

Proposer, en langage Python, une fonction interclasser(A1:list,A2:list)->list qui prend en arguments deux listes A1 et A2 déjà triées et qui renvoie la liste Ainter qui est l'interclassement de A1 et de A2

Version Récursive: 

def interclasser(A1:list,A2:list)->list :
    if A1 == []:
        return A2
    elif A2 == []:
        return A1
    elif A1[0] >= A2[0]:
        return [A2[0]] + interclasser(A1, A2[1:])
    else:
        return [A1[0]] + interclasser(A1[1:], A2)

Version Itérative (avec une boucle):

def interclasser(A1:list,A2:list)->list:
  Ainter = []
  n1, n2 = len(A1), len(A2)
  i1, i2 = 0,0 # indices resp. dans A1 et dans A2
  while i1 < n1 and i2 < n2:
    if A1[i1] < A2[i2]:
      Ainter.append(A1[i1])
      i1 += 1
    else:
      Ainter.append(A2[i2])
      i2 += 1
  return Ainter+A1[i1:]+A2[i2:]
  1. Déterminer la complexité (dans le pire des cas) de cette fonction interclasser(A1,A2) où A1 et A2 sont des sous-listes d'une liste A dont la taille est notée n

Notations: n=taille(A), n1=taille(A1), n2=taille(A2) donc \(n1+n2\le n\)

  • Commençons par la complexité temporelle de la fonction interclasser(A1,A2), dont la taille des données en entrées est n1+n2. Dans le pire des cas, on doit piocher alternativement (jusqu'à la fin) un élément de A1 suivi systématiquement d'un élément de A2 (puis un élément de A1, puis un de A2, etc..), la complexité dans ce cas est en \(O(n1+n2)\), avec \(n1+n2\le n\), donc dans le pire des cas la complexité de la fonction interclasser(A1,A2) est en \(O(n)\)

  • Remarques & Notations

    • Remarquons que \(n\) n'est pas forcément divisible par \(2\), donc qu'il faut comprendre \(\dfrac n2\) comme la division entière de \(n\) par \(2\), c'est-à-dire que : \(\dfrac n2 = n//2 = \left\{ \begin{array}{ll} \dfrac n2=\left \lfloor \dfrac n2 \right \rfloor \quad \text{si } n \text{ est pair}\\ \dfrac {n-1}{2}= \left \lfloor \dfrac n2 \right \rfloor \quad \text{si } n \text{ est impair}\\ \end{array} \right.\) Dans tous les cas, donc, on a \(\dfrac n2 = \left \lfloor \dfrac n2 \right \rfloor\)

  • Ensuite, notons \(p\) le plus grand entier tel que \(n\ge 2^p\), donc

    • en particulier \(2^p=O(n)\) \(\,\) et
    • \(p\) est le plus grand entier tel que \(\dfrac {n}{2^p}\ge 1\), donc
    • \(p\) est le plus grand entier tel que \(p\le log_2n\), plus précisément on a \(p=\lfloor log_2n\rfloor\)
  • On généralise la notation précédente, de sorte que : \(\dfrac {n}{2^p} = \left \lfloor \dfrac {n}{2^p} \right \rfloor\)
  1. Proposer, en langage Python, une fonction fusion(A:list)->list qui prend comme argument une liste \(A\) non triée, et qui renvoie en sortie la \(A\) triée récursivement grâce au tri fusion.
def fusion(A:list)->list:
  if len(A) <= 1:
    return A
  m = len(A) // 2
  return interclasser(fusion(A[:m]), fusion(A[m:]))
  1. Étudier la complexité temporelle de l'algorithme de Tri Fusion

Notations: n=taille(A), n1=taille(A1), n2=taille(A2) donc \(n1+n2\le n\)

  • Complexité temporelle T(n) de la fonction fusion(A) Dans le pire des casT(n) vérifie la relation \(T(n)=2\times T\left( \dfrac n2 \right) + O(n)\) \(\,\) et avec \(T(1)=1\) (une comparaison) En effet, d'après la Ligne 5 de la fonction fusion():
    • Au pire \(T\left( \dfrac n2 \right)\) pour fusion(A[:m])
    • Au pire \(T\left( \dfrac n2 \right)\) pour fusion(A[m:])
    • Au pire \(O(n)\) pour interclasser(A1,A2) avec n1=taille(A1), n2=taille(A2) et \(n1+n2=O(n)\)

donc \(T(n)=O(n)+2\times T\left( \dfrac n2 \right)\) \(T(n)=O(n)+2\times \left[ O\left( \dfrac n2 \right) + 2\times T\left( \dfrac {n}{2^2} \right) \right]\) \(T(n)=O(n)+2\times O\left( \dfrac n2 \right) + 2^2\times T\left( \dfrac {n}{2^2} \right)\) \(T(n)=O(n) + O(n) + 2^2\times T\left( \dfrac {n}{2^2} \right)\) \(T(n)=O(n) + O(n) + 2^2\times \left[ O\left( \dfrac {n}{2^2} \right) + 2\times T\left( \dfrac {n}{2^3} \right) \right]\) \(T(n)=O(n) + O(n) + 2^2\times O\left( \dfrac {n}{2^2} \right) + 2^3\times T\left( \dfrac {n}{2^3} \right)\) \(T(n)=O(n) + O(n) + O(n) + 2^3\times T\left( \dfrac {n}{2^3} \right)= etc...\) \(T(n)=\underbrace{O(n) + O(n) + O(n) + ...+ O(n)}_{p \text{ fois la quantité } O(n)} + 2^p\times T\left( \dfrac {n}{2^p} \right)\) Calcul de \(T\left( \dfrac {n}{2^p} \right)\) Remarquons ensuite que \(p\) est le plus grand entier tel que \(\dfrac {n}{2^p}\ge 1\), En particulier, on peut en déduire que \(2 \gt \dfrac {n}{2^p}\) (On peut raisonner par l'absurde: Si on avait \(2 \le \dfrac {n}{2^{p}}\) Alors on aurait \(\dfrac {n}{2^{p+1}}\ge 1\) ce qui contredirait la maximalité de \(p\). Donc c'est forcément le contraire qui est vrai: \(\dfrac {n}{2^{p+1}}\lt 1 \Leftrightarrow \dfrac {n}{2^p}\lt 2\) ) Conclusion : \(1 \le \dfrac {n}{2^p}\lt 2\) ce qui prouve que \(\left \lfloor \dfrac {n}{2^p} \right \rfloor = 1\) donc \(T\left( \dfrac {n}{2^p} \right) = T\left( \left \lfloor \dfrac {n}{2^p} \right \rfloor \right)=T(1)=1\)

On peut maintenant poursuivre le calcul de la Complexité temporelle \(T(n)\) : \(T(n)=p\times O(n)+O(n)\times 1\) avec \(p=\left \lfloor log_2 n \right \rfloor\) \(T(n)=log_2 n\times O(n)+O(n)\) \(T(n)=O(nlog_2 n)+O(n)\) \(T(n)=O(nlog_2 n)\) \(\,\) car \(n\) est négligeable par rapport à \(nlog_2n\)

  1. Étudier la complexité spatiale de l'algorithme de Tri Fusion

La fonction interclasser est la seule qui crée une nouvelle liste Ainter. Dans le pire des cas, c'est-à-dire lorsque on choisit de manière répétée, alternativement un élément de A1, puis un élément de A2, etc..., auquel cas la complexité en espace de la fonction interclasser est en \(O(n1+n2)=O(n)\) Dans le pire des cas, la complexité en espace est en \(O(n)\)

def interclasser(A1:list,A2:list)->list:
  Ainter = []
  n1, n2 = len(A1), len(A2)
  i1, i2 = 0,0 # indices resp. dans A1 et dans A2
  while i1 < n1 and i2 < n2:
    if A1[i1] < A2[i2]:
      Ainter.append(A1[i1])
      i1 += 1
    else:
      Ainter.append(A2[i2])
      i2 += 1
  return Ainter+A1[i1:]+A2[i2:]