Exercices corrigés Algorithme Diviser pour régner

Les exercices corrigés suivants concernent la création d’algorithme selon la structure du diviser pour régner (divide&conquer).

divide y vencerás

Ejercicio 1

On va jouer au jeu du “plus petit, plus grand”. Le but est de deviner un nombre compris entre 1 et n (entier). On considère que l’algorithme prend en entrée la valeur de n et du nombre x à deviner, et qu’il retourne le nombre de coup pour trouver ce nombre.

a – Réexprimez le problème de façon plus formel.

b – Ecrire l’algorithme itératif résolvant ce problème.

c – Ecrire l’algorithme récursif résolvant ce problème.

d – Comparer les complexités.

a – Le problème pourrait se réécrire comme suit : Etant donné un tableau trié par ordre croissant d’entiers, comment déterminer si un élément appartient ou pas à ce tableau ? Le principe est bien connu : on compare l’élément recherché à l’élément médian, et le cas échéant on répète la recherche dans la partie gauche ou droite du tableau.

algorithme recherche dichotomique

b – L’algorithme itératif est le suivant :

algorithme recherche dichotomique

Puisque le tableau est coupé à chaque fois en deux, on parcourera au plus log n élément avant de trouver le bon ou de savoir qu’il n’existe pas. La complexité est donc O(log n)

c – Par défaut la réponse de l’algorithme est faux, sauf s’il y a un vrai qui est retournée ce qui donnera dans le main puis la méthode :

algorithme recherche dichotomique

Puisque le fonctionnement est exactement le même que l’algorithme itératif, on se doute que la complexité est la même.

Ejercicio 2

On cherche la somme d’un tableau B de n éléments entiers.

1 – Écrivez un algorithme de type diviser-pour-régner qui résout ce problème.

2 – Analysez sa complexité et faire l’arbre d’appels pour le tableau [3,4,2,3,4].

3 – Comparez-la avec un algorithme itératif que vous décrirez

On définit la fonction Sum(B,i,j) qui est la somme des éléments de B entre les positions i et j. Ainsi la valeur recherchée est Sum(B,1,n). On va calculer Sum(B,i,j) en découpant le tableau B[i..j] en deux moitiés ; calculant les sommes pour chaque moitié ; et additionnant ces deux sommes. Ceci donne le code suivant :

algorithme récursif somme tableau

Pour la complexité, vu qu’on n’a pas encore vu le Master Theorem on va se servir de l’arbre d’appels :

algorithme récursif somme tableau

On comprend que l’on coupe en deux à chaque fois le tableau. Le calcul est simple, donc la complexité ne dépend que de la profondeur de l’arbre p tel que 2^pag > n (taille du tableau) d’où p > log n et une complexité en O(log n).

L’algorithme itératif est le suivant :

algorithme récursif somme tableau

Ici la complexité est de O(n).

Ejercicio 3

On dit qu’un tableau a un élément majoritaire si une valeur du tableau est présent au moins n/2 fois sur n éléments.

1 – Proposer un algorithme itératif pour résoudre ce problème.

2 – Proposer une méthode pour résoudre ce problème en diviser pour régner.

3 – Ecrire la méthode décrite par un algorithme.

1 – On compte le nombre d’occurrence de chaque élément (pas besoin de compter vers la gauche car s’il existe alors il a déjà été compté auparavant). Pour la première boucle, on aurait pu s’arrêter à n/2 + 1 car même si tous les éléments suivant étaient identique il ne serait tout de même pas majoritaire.

algorithme récursif majoritaire

2 – On va partir du principe de diviser pour régner :

algorithme récursif majoritaire

S’il existe un élément majoritaire x dans E, alors x est majoritaire dans au moins une des deux listes E1 et E2 (en effet si x non majoritaire dans E1, ni dans E2, alors dans E, nombre de x ≤ n/4 + n/4 = n/2).

Le principe de la récursion est alors le suivant : calculer les éléments majoritaires de E1 et de E2 (s’ils existent) avec le nombre total d’occurrences de chacun et en déduire si l’un des deux est majoritaire dans E.

L’algorithme suivant Majoritaire(i, j) renvoie un couple qui vaut (x, cx) si x est majoritaire dans le sous-tableau E[i..j] avec cx occurrences et qui vaut (−, 0) s’il n’y a pas de majoritaire dans E[i..j], l’appel initial étant Majoritaire(1, n). La fonction Occurence(x, i, j) calcule le nombre d’occurrences de x dans le sous-tableau E[i..j].

algorithme récursif majoritaire

Il n’est pas si facile à comprendre, prenons un exemple d’un tableau de 8 éléments avec 5 éléments identiques pour bien comprendre son fonctionnement.

algorithme récursif majoritaire

Ejercicio 4

1 – Proposer un algorithme en diviser pour régner cherchant le minimum d’un tableau.

2 – De même avec le maximum.

3 – De même en recherchant à la fois le minimum et le maximum.

Je vais donner directement la réponse à la question 3 puisqu’elle contient la réponse aux deux précédentes. Dans cette méthode, il faut retenir les positions dans le tableau ainsi que la valeur de min et max. On va considérer deux conditions terminales, un tableau d’une case et un tableau de deux cases. Cela ne change pas grand chose mais cela peut faire gagner un cycle de récursion ce qui n’est pas négligeable.

algorithme diviser pour régner minimum maximum

Ejercicio 5

Voici la formule du produit matricielle :

produit matriciel

1 – Proposer un algorithme itératif et en donner la complexité.

2 – Pour décomposer une matrice en dichotomie, il faut le faire à la fois sur les lignes et sur les colonnes, donc en 4 parties comme le schéma suivant :

produit matricielle

Chaque élément est une matrice carrée. Développez les équations pour le calcul de r, s, t et u.

3 – Strassen a trouvé une méthode pour encore réduire le nombre de calcul. Il propose de calculer r, s, t, u en utilisant une combinaison linéaire (addition ou soustraction) des matrices suivantes :

algorithme de Strassen

Exprimer r, s, t, u en fonction des pi.

4 – Proposer un algorithme récursif basé sur les calculs de Strassen pour le produit matricielle.

1 – On remarque dans la formule qu’il va falloir faire trois boucles en fonction de i, j et k. 

algorithme produit matricielle

Au plus profond des structures à itérations, il y a trois boucles de 1 à n imbriquées, donc une complexité en O(n^3)

2 – En développant l’équation nous obtenons le résultat suivant :

algorithme de strassen

3 – Cela donne les relations linéaires suivantes :

algorithme de strassen

4 – L’algorithme en diviser pour régner est le suivant :

algorithme de strassen

Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: