Université Hassan II
Année universitaire : 2018/2019
Faculté des Sciences Ain Chock
Casablanca
Algorithme II Session Normale
SMI3
Problème I : Récursivité & Complexité 8 pts
1. Donner la fonctionnalité de cet algorithme :
Déterminer la longueur d’une sous-séquence commune maximale entre deux tables A et B
Algorithme PLSSC-Recursif (A, i, B, j) : // A et B deux tableau de dimensions i et j
Si i = 0 ou j = 0
Alors renvoyer 0
Sinon
Si A[i] = B[j]
Alors renvoyer 1+ PLSSC-Recursif (A, i − 1, B, j − 1)
Sinon renvoyer max (PLSSC-Recursif (A, i − 1, B, j), PLSSC-Recursif(A, i, B, j − 1))
FSi
FSI
2. Donnez la complexité de la fonction PLSSC-Recursif (A, i, B, j) :
La table A a n élément et B a m éléments :
Max (T (n, m-1),T(n-1,m))= T(n,m-1)+T(n-1,m))
On peut dire que T(n,m) est borné avec la fonction 2min(n,m)
3. La fonction f est définie comme suite :
3
( )=3∗ ( )+1
2
( ) = ( − 1) + 1
(0) = 0
3.1. Donner la fonction récursive terminale :
Fonction f(n,S :Entier) :Entier
Début
Si n=0 Alors retourner S
Sinon
Si n est pair Alors retourner f(3*n/2,3*S+1)
Sinon Alors retourner f(n-1,S+1)
FSI
FSi
FFonction
1/2
Non terminale :
Fonction f(n:Entier) :Entier
Début
Si n=0 Alors retourner S
Sinon
Si n est pair Alors retourner 3*f(3*n/2)+1
Sinon Alors retourner f(n-1)+1)
FSi
FFonction
3.2. Calculer la complexité de la fonction récursive f
Dans le cas Non Terminale :
3
( )=3∗ ( )+1
2
( ) = ( − 1) + 1
(0) = 0
L’équation de complexité est :
( )= ( )+ ( )
( )= ( − )+ ( )
( )=
(1). Le théorème de Master n’est pas applicable dans le premier cas pair car b =2/3 <1. Ainsi, à
chaque fois la fonction est divergente ( le n est multiplié et pas divisé) dans le calcul si le
nombre est impair, et par conséquent la complexité est infinie ( la fonction n’est pas une
primitive récursive) .
(2). Dans le cas pair, par substitution, on obtient une relation linéaire
( ) = ( − 1) + 1 = ( − 2) + 1 + 1 = ( − 2) + 1 + 1 + 1 = (0) + ⋯ 1 + 1 =
3.3. Calculer la complexité de la fonction récursive f si on remplace la fonction dans le cas impair
avec ( ) = 2 ∗ + +
Dans ce cas L’équation de complexité est : ( )= ∗ ( )+
Théorème de Master a=2, b=3, d=0 donc >d donc T(n) ( ) ∈ ( )
3.4. Si Possible, écrire la version itérative avec une pile (vous pouvez utiliser les fonctions d’une
pile sans définition) :
La fonction est fonction non primitive récursive donc ce n’est pas nécessaire d’écrire la
solution itérative ou récursive.
3
( )=3∗ ( )+1
2
( ) = ( − 1) + 1
(0) = 0
2/2
Rappels :
Problème II : Algorithme de Tri 12pts
On s’intéresse à étudier les matrices circulantes carrée NxN, dont l’utilisateur spécifie seulement la
première ligne sous forme d’un vecteur de taille N.
Exemple :
Pour une table de N= 3 8 1 5 :
8 1 5 10 2
Pour une table de N= 6 8 1 5 10 2
2 8 1 5 10
10 2 8 1 5
5 10 2 8 1
1 5 10 2 8
1. Ecrire une Procédure itérative qui permet d’effectuer un décalage circulaire à droite d’un
tableau N d’une seule case
Deux Solutions :
Procédure itérative_Déc( T[],N : Entier) Procédure itérative_Déc( T[],N : Entier)
Variables : i,tmp : Entier Variables : i,tmp : Entier
Début tmp ←T[N-1]
Pour i de N-1 à 1 Faire Début
tmp ←T[i-1] Pour i de N-1 à 1 Faire
T[i-1]← T[i] T[i-1]← T[i]
T[i] ← tmp FPour
FPour T[0] ← tmp
FProcedure FProcedure
2/2
2. Ecrire une Procédure récursif qui permet d’effectuer un décalage circulaire à droite d’un
tableau N d’une seule case
Les deux solutions précédentes utilisables dans la version récursive :
Tmp=T[N-1]
Procédure Récursif _Déc( T[],N,tmp : Entier)
Si N=0 Alors T[0] ← tmp
Sion
T[i-1]← T[i]
Récursif_Déc(T[],N-1,tmp)
FProcedure
3. Comparer la complexité des deux algorithmes dans la question 1 et 2.
Les deux sont linéaire à l’ordre n
4. Ecrire une Procédure itérative qui permet de créer une matrice M à partir d’un tableau de
taille N entrée comme argument.
Procédure itérative_Matrix(M[][],T[],N : Entier)
Variables : i,j: Entier
Début
Pour i de 0 à N-1 Faire
Pour j de 0 à N-1 Faire
M[i][j] ←T[j]
FPour
Décalge(T[],N) // Procédure de décalage avant d’affecter les valeurs au prochaine ligne
FPour
FProcedure
5. Ecrire une Procédure récursive qui permet de créer une matrice M à partir d’un tableau de
taille N entrée comme argument.
Procédure récursive _Matrix(M[][],T[],N,i,j : Entier)
Si( i=0 && j<N) Alors
M[i][j] ←T[j]
récursive _Matrix(M[][],T[],N,i,++j : Entier)
FSi
Si(0<i<N)
Si (j=N-1) Décalge(T[],N) récursive _Matrix(M[][],T[],N,++i,0 : Entier)
Si(j<N-1) M[i][j] ←T[j] récursive _Matrix(M[][],T[],N,i,++j : Entier)
FSI
FProcedure
2/2
6. Ecrire la Procédure récursif qui permet d’affiche la matrice, i et j sont initialisés à 0
Procédure Récursive _Print(M[][],T[],N,i,j : Entier)
Si(i<N) Alors
Si (j<N)
Ecrire(M[i][j])
Récursive _Print(M[][],T[],N,i,++j : Entier)
Sinon
Ecrire (EOL)
Récursive _Matrix(M[][],T[],N,++i,0 : Entier)
FSI
FProcedure
7. On a la matrice M [3][3] qui est créé à partir de la table T [3] = {1,2,3} :
M=
2/2
7.1. Ecrire un sous-algorithme de Tri qui permet de ranger une matrice M’quelconque (quel que
soit les positions de 1,2,3) pour aller à M :
Chaque ligne contient les mêmes composantes :1,2,3
Les permutations faites seulement sous formes de décalage à droite
La vérification est faite pour chaque ligne indépendamment
3 2 1 1 2 3
M’= 3 1 2 M= 3 1 2
1 2 3 2 3 1
La solution est d’écrire 3 fonctions :
Vérification : qui vérifie seulement que le premier élément de la matrice (i,0) est celui
de la table de base T dans l’état initiale et après décalage de chaque ligne.
Recherche : qui cherche le positon de cet élément et renvoie le nombre de décalage à
faire
Permutation : qui permet de décaler la table m fois pour que l’élément retourne a sa
place
Procédure Verfication(M[][],T[],N : Entier)
Variables : i,j,k: Entier
Début
Pour i de 0 à N-1 Faire
Si(M[i][0]<>T[0])
k←Recherche_nbre_dec(T[],N,T[0])
Dec_fois(M[][],i,N,k)
Décalge(T[],N) // Procédure de décalage avant d’effectuer la prochaine comparaison
FSi
FPour
FProcedure
Fonction Recherche_nbre_dec(M[][],i,j,N,T[0]) :Entier
Variables : i,j :Entier
k ←0
Pour j de 0 à N-1 Faire
Si (M[i][j]<>T[0]) k++
Sinon return k
FP
FFonction
Procédure Dec_fois(M[][],i,N,k)
Variables : m : Entier
Pour m de 0 à k-1 Faire
Declage(M[i][], N) // le décalage faite seulement pour une ligne i
FP
FProcedure
2/2
7.2. Ecrire un sous-algorithme de Tri qui permet de ranger une matrice M’quelconque (quel que
soit les positions de 1,2,3) pour aller à M dont le diagonal est 1 :
Le diagonal doit avoir la valeur 1, les autres composantes :2,3 hors diagonales
Les permutations faites sous formes de décalage pour les lignes et les colonnes
La vérification est faite seulement pour le diagonal
1 2 1 1 3 3
M’= 3 1 2 M= 2 1 2
3 2 3 2 3 1
La solution est d’écrire 4 fonctions :
Verfication_de_nbre : Qui vérifie que pour chaque ligne on a seulement une seule
valeur de T [0] dans l’exemple c’est 1. Chaque ligne doit avoir un seul 1.
Verfication_de_positon : Qui vérifie que pour chaque élément dans le diagonale
égale au T [0] (avant décalage)
Decalage_sur_ligne : qui permet de décaler une ligne fois pour que l’élément
retourne à sa place (Question 1)
Declage_sur_colonne : qui permet de décaler une colonne fois pour que l’élément
retourne à sa place (Question 1 on décale les colonnes cad i a la place de i)
Procédure Verfication_de_nbre(M[][],T[],N : Entier)
Variables : i,j,k: Entier
Début
Pour i de 0 à N-1 Faire
Pour j de 0 à N-1 Faire
Tant Que(M[i][j]=T[i]) & i<>j)
Declage_sur_colonne(M[][],j)
FTQ
FPour
Décalge(T[],N) // Procédure de décalage avant d’effectuer la comparaison
FPour
FProcedure
Procédure Verfication_ de postion(M[][],T[],N : Entier)
Variables : i,j,k: Entier
Verfication_de_nbre(M[][],T[],N)
Début
Pour i de 0 à N-1 Faire
Tantque(M[i][i]<> T[i])
Declage_sur_ligne(M[][],j)
FTQ
Décalge(T[],N) // Procédure de décalage avant d’effectuer la comparaison
FPour
FProcedure
2/2
8. Proposer un sous-algorithme de Tri qui permet de ranger une matrice M’quelconque (quel que
soit les positions de 1,2,3) pour aller à M (Question 7.1) ; en utilisant seulement des
permutations sous forme de décalage dans les deux sens à droite et à gauche pour les lignes et
les colonnes.
2/2
