Mme Ben Attia Imen Mme Ben Attia Imen

&&

Les élèves de la classeLes élèves de la classe

4 Sc.Info 14 Sc.Info 1

Vous souhaite la bien Vous souhaite la bien

venue venue

Quand peut-on parler d’un Quand peut-on parler d’un algorithme récurrentalgorithme récurrent

Quelle est la différence entre un Quelle est la différence entre un algorithme récurrent et un algorithme récurrent et un algorithme récursif algorithme récursif

Qu’est ce qu’une matriceQu’est ce qu’une matrice

RappelRappel

Algorithmes récurrentsAlgorithmes récurrents Un algorithme ou un traitement est dit récurrentrécurrent

s’il utilise un procédé itératifitératif ou récursifrécursif pour engendrer un résultat qui peut dépendre de p résultats précédents, nous parlons alors d’un algorithme ou d’un traitement récurrent d’ordre p.

Ordre 1:Ordre 1: Un algorithme récurrent est dit d’ordre 11 si son résultat dépend dudu résultat précédent.

Ordre 2:Ordre 2: Un algorithme récurrent est dit d’ordre 22 si son résultat dépend des deux résultatsdeux résultats précédents.

….. Ordre p:Ordre p: Un algorithme récurrent est dit d’ordre pp

si son résultat dépend des P résultatsP résultats précédents.

Différence entre un Différence entre un algorithme récursif et un algorithme récursif et un

algorithme récurrentalgorithme récurrent Dans un Module récurrent on obtient un Dans un Module récurrent on obtient un

résultat en fonction d’un ou de plusieurs résultat en fonction d’un ou de plusieurs résultats précédentsrésultats précédents

Dépendance entre les Dépendance entre les résultatsrésultats

Dans un module récursif on obtient un Dans un module récursif on obtient un résultat en faisant un ou de plusieurs résultat en faisant un ou de plusieurs appel au module lui-même avec appel au module lui-même avec changement de paramètres d’appel changement de paramètres d’appel

Auto-dépendanceAuto-dépendance du du modulemodule

Soit A une matrice de Soit A une matrice de NN lignes et de lignes et de MM colonnes d’entiers : colonnes d’entiers :

5511228877

23233388991111

55554432322121

141488212114141818

1515227715151010

N

L

ign

es=

5

M colonnes=5

Une matrice est un tableau à deux dimension de N lignes et de M colonnes de type éléments

Si M=N on dit qu’on a une matrice carrée.

Chaque ligne de la matrice L peut être assimilée à un tableau unidimensionnel de M cases.

Chaque colonne de la matrice C peut être assimilée à un tableau unidimensionnel de N cases.

CL

spécification du module itératif spécification du module itératif permettant de chercher le maximum permettant de chercher le maximum

d’une ligne de matrice d’une ligne de matrice Résultat = maxligneMaxTraitement : Initialiser la variable Max à A[L, 1] Utiliser 1 structure itérative complète Pour C De 1 A M Faire Pour chaque itération : tester Si Max < A[L, C] Alors Max A[L, C]

Donné = Matrice ( A ) / L,M30

0) fonction maxligne(L,M:entier;A:tab):entier1) MaxA[L,1] Pour C de 2 à M faire Si A[L,C]>Max alors

MaxA[L,C] Finsi

2) Finpour2) Finpour

3) Maxligne3) Maxlignemaxmax

4) Fin maxligne4) Fin maxligne

Algorithme itératif

T.D.Objets Locaux

C Entier Compteur sur les colonnes

Max entier Variable temporaire pour garder le maximum

0)procedure maxligne(L,C :entier;A:tab;var max:entier)1)Si C>1 alors maxligne(L,C-1,A,max) Finsi Si max<A[L,C] alors MaxA[L,C] Finsi 2) Fin maxligne

Algorithme récursif

Algorithme récursif pour la recherche Algorithme récursif pour la recherche du minimum d’une colonne de matrice  du minimum d’une colonne de matrice 

0) procedure mincolonne(L,C:entier;A:tab; var min:entier)1) Si L>1 alors mincolonne(L-1,C,A,min) Finsi2) Si min>A[L,C] alors Min A[L,C] Finsi3) Fin mincolonne

0)procedure maximum(L,C:entier;A:tab; var max:entier)1)Si L>1 alors maximum(L-1,C,A,max) Finsi maxligne(L,C,A,max) 2) Fin maximum

Algorithme récursif pour chercher le maximum

Tableau de codification des objets Locaux

Objet Type/Nature Rôle

Maxligne procédure Cherche le maximum d’une ligne

1)Debut procedure minimum(L,C:entier;A:tab; var min:entier)2)Si C>1 alors minimum(L,C-1,A,min) Finsi mincolonne(L,C,A,min) Fin maximum

Algorithme récursif pour chercher le minimum

Tableau de codification des objets Locaux

Objet Type/Nature Rôle

Mincolonne procédure Cherche le minimum d’une colonne

Réutilisation des modules Réutilisation des modules réalisés réalisés

Proposer une analyse du Proposer une analyse du programme qui permet de remplir programme qui permet de remplir une matrice une matrice AA de de NN lignes et de lignes et de MM colonnes puis chercher et afficher colonnes puis chercher et afficher son son maximummaximum et son et son minimumminimum en en déduire les algorithmes de chaque déduire les algorithmes de chaque module.module.

Décomposition Décomposition Modulaire Modulaire

Prog_Matrice

Saisir (Var Valeur)

Remplir(Var A ;L,C)

Maximum(l,c ;A ;var max)

Minimum(l,c ; A ;var min)

Remplir_ligne(var A ;L,C)

Maxligne(L,C ;A ;var max)

Mincolonne(L,C ;A ;var min)

Programme principal Programme principal

0) Début Prog_Matrice1) Saisir(N)2) Saisir(M)3) Remplir(A,N,M) 4) maximum(N,M,A,max)5) minimum(N,M,A,min)6) Ecrire("le maximum est :", max, "le minimum est :", min)7) Fin Prog_Matrice

Résultat=Ecrire ("le maximum est :", max, "le minimum

est :",min)Traitement :

La valeur de Max est déterminée suite à l’appel de la

procédure maximum(N,M,A,max),

La valeur de Min est déterminée suite à l’appel de la

procédure minimum(N,M,A,max)

Appel de la procédure remplir pour saisir les éléments de A

Appel de la procédure saisie une fois pour saisir N et une

autre fois pour saisie MDonnée : A,N,M

AlgorithmeSpécification

Chercher le minimum d’une matriceprocédureMinimum

Chercher le maximum d’une matriceprocédureMaximum

Remplir une matrice de N lignes et de M colonnes d’entiers

procédureRemplir

Saisir un entierProcédureSaisie

Variable temporaire pour garder le maximumEntierMax

Matrice de N lignes et de M colonnes d’entiersTabA

Compteurs de lignes et de colonnesentierL, C

RôleType/NatureObjet

Tableau de codification des objets globaux

Tab= tableau de 15 lignes et de 15 colonnes d’entiers

Tableau de déclaration de nouveaux types

La procédure Remplir La procédure Remplir récursif  récursif 

0) procedure remplir(varA:tab; L,C:entier)1) Si L>1 alors

remplir(A,L-1,C) Finsi

2) remplir_ligne(A,L,C);3) Fin remplir

Résultat = ATraitement :

Si L>1 (point d’appui) alors faire un appel récursif à la procédure en

diminuant le nombre de ligneDésempiler les appels récursif

tout en appelant la procédure remplir_ligne(A,L,C)

AlgorithmeSpécification

Tableau de codification des objets Locaux

Objet Type/Nature Rôle

Remplir_ligne procédure Permet de remplir une ligne de la matrice

0) procedure remplir_ligne(var A:tab; L,C:Entier)1) Si C>1 alors Remplir_ligne(A,L,C-1)

Finsi2) Ecrire("A[",L, ",",C, "]="),Lire(A[l,c]);3) Fin remplir_ligne

Résultat = remplir la ligne L

Traitement : Si C>1 (point

d’appui) alors faire un appel récursif à la

procédure en diminuant le nombre

de colonne Désempiler les

appels récursif tout en faisant la saisie

d’une case

Algorithme de la procédure remplir_ligneSpécification de la procédure remplir_ligne

0) procedure saisie(var valeur :entier)1) Ecrire("donner un entier : ")2) Lire(valeur)3) Si non(valeur dans [1..15]) alors

saisie (valeur) Finsi

1)Fin Saisie

Résultat = ValeurTraitement :

Saisir une valeur Si cette valeur ne

répond pas à la condition faire un appel

récursif de la même procédure

Donnée : valeur

Algorithme de la procédure Saisie

Spécification de la procédure Saisie

ProblèmeProblème On désire rechercher dans une matrice donnée A de N lignes et de M colonnes les On désire rechercher dans une matrice donnée A de N lignes et de M colonnes les

éléments qui sont à la fois un maximum sur leur ligne et un minimum sur leur éléments qui sont à la fois un maximum sur leur ligne et un minimum sur leur colonne. Ces éléments sont appelés des colonne. Ces éléments sont appelés des points colspoints cols. Afficher les positions et les . Afficher les positions et les valeurs de tous les points cols trouvés. Proposer une analyse à ce problème en valeurs de tous les points cols trouvés. Proposer une analyse à ce problème en déduire les algorithmes correspondants.déduire les algorithmes correspondants.

Exemples:Exemples: Les éléments soulignés sont des points cols: Les éléments soulignés sont des points cols: 1 8 3 4 0 4 5 1 8 3 4 0 4 5 88 6 3 5 6 6 3 5 6 77 7 1 2 7 7 1 2 7 6 6 77 2 7 0 3 8 9 3 4 2 2 8 9 4 5 2 7 0 3 8 9 3 4 2 2 8 9 4 5 66 3 4 9 3 6 3 2 9 7 7 8 9 3 4 9 3 6 3 2 9 7 7 8 9 Méthode:Méthode: Établir deux matrices d'aide Établir deux matrices d'aide MMAXMMAX et et MMINMMIN de même dimensions que de même dimensions que

A, telles que: A, telles que: 1 si A[L,C] est un maximum sur la ligne i1 si A[L,C] est un maximum sur la ligne iMMAX[i,j] =MMAX[i,j] = 0 sinon0 sinon 1 si A[L,C] est un minimum sur la colonne j1 si A[L,C] est un minimum sur la colonne jMMIN[i,j] =MMIN[i,j] = 0 sinon0 sinon Les points cols sont ceux qui vérifient l’égalité suivante : Les points cols sont ceux qui vérifient l’égalité suivante :

MMAX[L,C] = MMIN[L,C]=1MMAX[L,C] = MMIN[L,C]=1

SimulationSimulation

AnalyseAnalyse

5511228877

23233388991111

55554432322121

141488212114141818

1515227715151010

Max=15

0000001100

1100000000

0000001100

0000110000

1100001100

1111111111

0000000000

1100000000

0000000000

0000000000

Mmax

Mmin

Max=21Max=32Max=23Max=8

Min

=7

Min

=8

Min

=2

Min

=1

Min

=5

Matrice qui

repère les

maximums des

lignesMatrice qui

repère les

minimums des

colonnes

DECOMPOSITION DECOMPOSITION MODULAIREMODULAIRE

Points_cols

RemplirRemplir (VAR A ;L,C)

SaisieSaisie (VAR

valeur)

AfficherAfficher (A, N,M)

P P P

Pointpoint (N,M;A,mmin, mmax)

P

Remplir_MMaxRemplir_MMax (N,M;A;VAR

mmax)

Remplir_MMinRemplir_MMin (N,M;A;VAR

mmin)

MaxligneMax (L,C;A;VAR max)

MincolonneMin (L,C;A;VAR min)

P

P

Programme principal Programme principal 

0) Debut points_cols1) saisie(N)2) saisie(M)3) remplir(N,M,A)4) Ecrire("voila la matrice initiale")5) affiche(N,M,A)6) Ecrire("voila la matrice qui indique les positions des maximum de chaque ligne")7) remplir_mmax(N,M,Mmax)8) Ecrire ("voila la matrice qui indique les positions des minimum de chaque colonne")9) remplir_mmin(N,M,Mmin)10)Ecrire ("voila les positions des points cols")11)point(n,m,A,mmin,mmax)12)Fin points_cols

Résultat : Affichage des points colsTraitement : appel de la procédure point qui cherche et affiche les points cols en parcourant les 2 matrices Mmax et Mmin appel des procédures remplir_mmax et remplir_mmin pour remplir et afficher Mmax et Mmin qui indiquent respectivement les positions des maximum de chaque ligne et les positions des minimum de chaque colonne. Afficher la matrice A grâce à la procédure affiche La matrice A est remplie grâce al a procédure remplir N et M sont saisies par la procédure saisie

AlgorithmeSpécification

Matrice de N lignes et de M colonnes contenant 1 à la place des minimum dans les colonnes et 0 dans le reste

TabMmin

Matrice de N lignes et de M colonnes contenant 1 à la place des maximum dans les ligne et 0 dans le reste

TabMmax

Matrice de N lignes et de M colonnesTabA

Nombre de colonnes de la matriceEntierM

Nombre de lignes de la matriceEntierN

RôleType/NatureObjet

Tableau de déclaration des objets globaux

 Tab= tableau de 15 lignes et de 15 colonnes d’entiers

Tableau de déclaration de nouveaux types

Procédure pointProcédure point

0) Procedure point(N,M:entier;A,Mmin,Mmax:tab)1) Pour L de 1 à N faire pour C de 1 à M faire si (Mmin[L,C]=1)et(Mmax[L,C]=1) alors Ecrire("A[",L, ",",C, "]= ",A[L,C], " est un point cols") Finsi Finpour Finpour2) Fin point

Résultat= Affichage des points colsTraitement=

On parcours les 2 matrices tout en

comparant les éléments des matrices pour afficher

sauf les éléments répondant à la condition

(Mmin[L,C]=1)et(Mmax[L,C]=1)

On utilise 2 structures itératives complètes

Pour L de 1 à n faire

pour C de 1 à m faire

AlgorithmeSpécification

Tableau de déclaration des objets Locaux

Objet Type/Nature

Rôle

L Entier Compteur sur les lignes de la matrice

C Entier Compteur sur les colonnes de la matrice

procedure remplir_mmax procedure remplir_mmax

0) procedure remplir_mmax(N,M:entier;var MMax:tab)1) Pour i de 1 à N faire Maxa[i,1] maxligne(i,2,a,max) pour j de1 à M faire Si A[i,j]=max alors MMax[i,j]1 sinon MMax[i,j]0 Finsi Finpour Finpour2) affiche(N,M,MMax)3) Fin remplir_mmax

Résultat= Remplir et afficher la matrice MMaxTraitement=•Appel de la procédure affiche pour afficher MMax •Parcourir toutes les lignes Pour i de 1 à N faire•Pour chaque ligne chercher son maximum

oMaxA[i,1] maxligne(i,2,a,max)oParcourir les éléments de la matrice A pour cette ligne pour j de1 à M faireo Pour chaque élément tester

Si A[i,j]=max alors MMax[i,j]1 sinon MMax[i,j]0

AlgorithmeSpécification

Cherche le maximum d’une ligneprocédureMaxligne

Variable de sauvegarde du maximumEntierMax

Compteur sur les colonnes de la matriceEntierj

Compteur sur les lignes de la matriceEntieri

RôleType/NatureObjet

Tableau de déclaration des objets Locaux