MP, PSI et la TSI

Exercices corrigés en python sur le paradigme diviser pour régner

Exercice 1 :

Etant donné un tableau X composé de N éléments entiers. On voudrait déterminer son maximum par un algorithme récursif basé sur le paradigme « diviser pour régner » :

  1. En considérant que le maximum est le plus grand entre le dernier terme et le maximum des (n-1) premiers termes. Estimer sa complexité.
  2. En considérant que le maximum est le plus grand entre les maximums des deux moitiés du tableau. Estimer sa complexité.
Exercice 2 :

Soit X un tableau composé de N entiers ordonnés par ordre croissant et Y un entier.

  1. Elaborer une fonction récursive permettant de trouver la position de Y dans X en opérant selon le paradigme « diviser pour régner ».
  2. Estimer sa complexité.
Exercice 3 :

Soit une fonction à une dimension définie par N échantillons équidistants se trouvant dans un tableau X. On suppose que la fonction est unimodale (croissante puis décroissante) (Voir figure). On voudrait déterminer l’échantillon qui donne sa valeur maximale. Ecrire un fonction récursive permettant de déterminer l’élément du tableau X contenant l’échantillon maximal selon le paradigme « diviser pour régner ». Estimer sa complexité.

Exercice 4 :

Soit une matrice entière carrée T d’ordre NxN avec N=2^k

  1. Ecrire une fonction récursive basée sur le paradigme «diviser pour régner» permettant de déterminer le maximum de la matrice T. L’algorithme doit procéder par la division de T en quatre sous matrices d’ordre (N/2 x N/2) chacune. L’algorithme doit procéder par la division de T en quatre sous-matrices d’ordre (N/2 x N/2) chacune. Pour cela adopter le prototype suivant pour l’algorithme : Maximum (T, a, b, N) avec : a : début de l’indice des lignes, b : début de l’indice des colonnes, N : le nombre de lignes et le nombre de colonnes. Et supposer que vous avez à votre disposition une fonction Sup(x1,x2,x3,x4) qui vous retourne le maximum des 4 paramètres.
  2. Quelle est la formule de récurrence donnant sa complexité. Expliquer.
  3. Estimer cette complexité ?
Exercice 5 :

Soient trois matrices réelles A, B et C carrées d’ordre NxN avec N=2^k

  1. Ecrire une fonction récursive basée sur le paradigme « diviser pour régner » pour multiplier A par B et mettre le résultat dans une matrice C. L’algorithme doit procéder par la division de T en quatre sous matrices d’ordre (N/2 x N/2) chacune. 

  2. Quelle est la formule de récurrence donnant sa complexité. Expliquer. 

  3. Estimer cette complexité ?
Exercice 6 :

Etant donné un tableau X composé de N entiers et numérotés de 0 à (N-1), on se propose d’écrire une fonction « Trier » permettant de trier le tableau X en opérant par « insertion binaire ». Pour cela, on vous propose de suivre les étapes suivantes :

  1. Etant donné un tableau Y composé de M entiers triés par ordre croissant, écrire une fonction « Position » permettant de chercher, selon le paradigme « diviser pour régner », la position que devrait occuper un entier Z dans Y de telle sorte que le tableau Y reste trié. La fonction « position » doit retourner la position recherchée.
  2. Etant donné un tableau Y composé de M entiers triés par ordre croissant, écrire une fonction « Décaler » permettant de décaler d’une position vers la droite tous les éléments d’un tableau Y[k] pour k allant de P à M (P étant un indice compris entre 0 et M). On suppose que la position Y[M] est libre.
  3. Ecrire une fonction « trier » permettant de trier par ordre croissant un tableau X composé de N entiers. La fonction trier doit bien sûr appeler les fonctions « Position » et « Décaler »
  4. Etablir une formule récurrente puis estimer la complexité T(n) en nombre de comparaisons pour trier un tableau X composé de N entiers.
Exercice 7 :

Soit une matrice de taille (2^N) x (2^N) représentant un échiquier (figure-2a). Toutes les cases sont de couleur blanche sauf une de couleur noire.
Soit un motif pouvant avoir 4 orientations possibles (Figure-1) notées A, B, C et D. Il est prouvé qu’on peut couvrir la totalité de l’échiquier avec ces formes. Le problème est comment le faire ? Pour cela, on vous propose l’idée suivante : 


  1. On divise l’échiquier en 4 parties égales P1, P2, P3 et P4
  2. On place une des formes du motif (A ou B ou C ou D) au centre de telle sorte que chaque partie contienne une case noire (Figure-2b).
  3. Comment appliquer le paradigme « diviser pour régner » pour couvrir la totalité de l’échiquier ?
  4. Elaborer une fonction basée sur le paradigme « diviser pour régner » pour couvrir l’échiquier. La valeur N est un paramètre de la fonction.
  5. Quelle est sa complexité (avec démonstration) ?

Exercice 8 :

Soit X un tableau d’entiers de taille N. Un élément de X est majoritaire si l’ensemble {i tel que X[i] = e} est de cardinalité strictement supérieure à n/2.

  1. Proposer une fonction simple qui recherche un élément majoritaire dans un tableau X. Analyser sa complexité.
  2. Proposer une 2ème fonction opérant selon le paradigme “diviser pour régner” qui recherche un élément majoritaire dans un tableau X. Analyser sa complexité.

Partager ce cours avec tes amis :
Rédigé par Mostafa Sedoki
Professeur d'Informatique dans les CPGE

Cours Similaires :