29/03/16

Les  tableaux  2D  

Les  tableaux  mul.dimensionnels
Les  tableaux  2D
et  quelques  traitements  classiques  
 
Les  tableaux  2D  et  quelques  traitements  classiques  
Généralisa;on  aux  tableaux  mul;dimensionnels  

29/03/16   Algo  2.  L1  math-­‐info.  PhL   2  

  Représenter  une  image

Tableaux  2D  et  des  images     Une  image  =  quadrillage  de  pixels  
-­‐  pixel  blanc  ou  noir  :  un  bit  0  ou  1,  respec;vement  
 
 
-­‐  niveaux  de  gris  :    
 un  en;er    
 niveaux/nuances  :  varia;on  de  l'en;er  
 entre  0  et  255  (format  PGM  :  foncé  -­‐>  clair)  
 
-­‐  couleurs  :    
 .  RGB  (rouge/vert/bleu)  
   .  G+B  =  cyan  (bleu  mers  du  sud)  ,  R+B  =  magenta  (violet),  R+G  =  jaune  
 .  triplet  d'en;ers  RGB  pour  les  nuances  
 
29/03/16   Algo  2.  L1  math-­‐info.  PhL   3  
 
29/03/16   Algo  2.  L1  math-­‐info.  PhL   4  

1  
 29/03/16  

Image  =  tableau  2D  de  pixels L'ami  du  tableau  2D  :  la  double-­‐boucle  imbriquée  
 
Un  premier  exemple
Avec  un  tableau  1D  :  
00000011100101000111000000  
t : tableau[25] d'entiers = [0,0,0,0,0,0,1,1,1,0,0,1,0,1,0,0,0,1,1,1,0,0,0,0,0,0] declare
    img : tableau[5,8] d'entiers // une image rectangulaire
Avec  un  tableau  2D  :    N/B    niveaux  de  gris   // de 5 lignes, 8 colonnes
     00000    0      0          0          0        0     i : entier // indice de parcours des lignes
     01110    0  128  128  128  0   j : entier // indice de parcours des colonnes
     01010    0  128        0    128    0  
     01110    0  128  128  128  0   debut
     00000    0        0            0        0        0   pour i de 0 à 4 faire // pour chaque ligne : il y en a 5
  pour j de 0 à 7 faire // pour chaque colonne : il y en a 8
img[i , j] = 128 // un pixel de gris
t : tableau[5,5] d'entiers = [ [0,0,0,0,0] , [0,1,1,1,0], [0,1,0,1,0], finpour // j'ai fini toutes les colonnes donc une
[0,1,1,1,0] , [0,0,0,0,0] ]     ligne
 -­‐  2  indices  :  ligne  /  colonne     finpour // j'ai fini toutes les lignes donc l'image ....
 -­‐  t[1, 2] == 1 et  t[4,4] == 0 fin //... comporte 40 pixels gris
 -­‐  t[3, 10] : tableau  rectangulaire  de  3  lignes  et  10  colonnes  
 
29/03/16   Algo  2.  L1  math-­‐info.  PhL   5   29/03/16   Algo  2.  L1  math-­‐info.  PhL   6  

Bien  comprendre  la  double-­‐boucle  imbriquée  

Etape  1  :  indices  indépendants  
1   -­‐3   5   -­‐7   9  
t : tableau[2, 5] d'entiers = initialisé comme celui-ci
à   -­‐2   4   -­‐6   8   -­‐10  
declare declare
t : tableau[2, 5] d'entiers = ... t : tableau[2, 5] d'entiers = ... i ,
i , j : entier j : entier
debut debut
pour i de 0 à 1 faire
pour j de 0 à 4 faire pour j de 0 à 4 faire
pour i de 0 à 1 faire
afficher( t[i , j]) L'instruc;on   afficher( t[i , j])
finpour
finpour d'affichage  n'est   afficher (sdl) // saut de ligne
afficher (sdl) // saut de ligne pas  modifiée  !!  
finpour
finpour
Des  algorithmes  sur  les  tableaux  2D fin
fin

D'abord  bien  comprendre  la  double  boucle  imbriquée   Parcours  "en  ligne   Seul  le  parcours   Parcours  "en  colonne  
d'abord"  :     ligne/colonne   d'abord"  :    
 indice  i,  puis  indice  j   du  tableau  est    indice  j,  puis  indice  i  
permuté   1    -­‐2  
-­‐3    4      
1    -­‐3    5    -­‐7    9   5    -­‐6    
-­‐2    4    -­‐6    8    -­‐10   -­‐7    8    
9    -­‐10  
29/03/16   Algo  2.  L1  math-­‐info.  PhL   7   29/03/16   Algo  2.  L1  math-­‐info.  PhL   8  

2  
 29/03/16  

Bien  comprendre  la  double-­‐boucle  imbriquée  

Etape  2  :  indices  liés  
1   -­‐3   5   -­‐7   9  
t : tableau[4, 5] d'entiers = initialisé comme celui-ci
à   -­‐2   4   -­‐6   8   -­‐10  
declare 11   13   15   17   19  
t : tableau[4, 5] d'entiers = ...
i , j : entier
debut 12   14   16   18   20  
pour i de 0 à 3 faire
pour j de i à 4 faire
afficher( t[i , j]) La  boucle  intérieure  
Les  indices  varient  comme  
dépend  de  la  boucle  
finpour suit  :  
afficher (sdl) // saut de ligne extérieure  
 

finpour i  =  0  
Les  valeurs  prises  par  j    j=  0,1,2,3,4  
fin dépendent  de  celles  de  i.  
Elles  changent  donc  chaque  
i  =1  
 j=  1,2,3,4  
Des  algorithmes  sur  les  images
fois  que  i  change.   i  =2   Exemples  en  interac;on  :  tableaux  2D  et  images  
 j=  2,3,4  
1    -­‐3      5    -­‐7      9  
i  =3  
4    -­‐6      8    -­‐10  
 j=  3,4  
15  17  19  
18  20  
 

29/03/16   Algo  2.  L1  math-­‐info.  PhL   9   29/03/16   Algo  2.  L1  math-­‐info.  PhL   10  

255  
Tout  gris  c'est  parfois  triste  ...   Tout  gris  c'est  parfois  triste  ...   192  
128  
Modifions  l'algo  de  créa;on  de  
declare L'algo  ci-­‐contre  donne  :      l'image  grise  pour  obtenir  ça  à     64  
img : tableau[5,8] d'entiers // une image rectangulaire
// de 5 lignes, 8 colonnes 0  
i : entier // indice de parcours des lignes 1.  Principe  de  l'algorithme  de  remplissage  en  5  niveaux  de  gris  :  
j : entier // indice de parcours des colonnes -­‐  remplir  chaque  ligne  du  même  niveau  de  gris  
valeurs    
debut -­‐  2  choix  symétriques  :   des  gris  
pour i de 0 à 4 faire // pour chaque ligne : il y en a 5 Aben;on  :  les  images  sont  souvent  indicées    
pour j de 0 à 7 faire // pour chaque colonne : il y en a 8 "à  l'inverse"  des  matrices    
img[i , j] = 128 // un pixel de gris
finpour // j'ai fini toutes les colonnes donc une ligne  .  du  haut  vers  le  bas  :  ligne  0  à  ligne  4    
finpour // j'ai fini toutes les lignes donc l'image ....  .  du  bas  vers  le  haut  :  ligne  4  à  ligne  0  
fin //... comporte 40 pixels gris
 
2.  Pe;te  difficulté  arithmé;que  :  comment  partager  la  plage  de  gris  0..255  en  5  gris  répar;s  de  façon  
équilibrée  ?    
Essayons  avec  les  8  valeurs    0  1  2  3  4  5  6  7    
 .  on  prend  les  2  extrêmes  :  0,    7  (noir,  blanc)  0  1  2  3  4  5  6  7    
 .  il  reste  5  valeurs  répar;es  de  1  à  6  et  on  veut  3  autres  valeurs  de  sépara;on    
Modifions  l'algo  de  créa@on  de      .  choix  équidistant  impossible  à  choix  arbitraire  :  par  exemple  2,  4,  6  qui  sont  équidistants  
 l'image  grise  pour  obtenir  ça  à     depuis  0    
 .  ce  qui  donne  0  2  4  6  7,  soit  0+2,  0+2+2,  0+2+2+2,  ...  soit  :  0  +  i  x  2  avec  i  =  0,1,2,3    
 .  et  on  rajoute  7  à  la  fin.    
 
Plus  généralement,  difficile  de  partager  un  nombre  pair  de  valeurs  en  un  nombre  impair  (>1)  de  tas  ...    
29/03/16   Algo  2.  L1  math-­‐info.  PhL   11   29/03/16   Algo  2.  L1  math-­‐info.  PhL   12  

3  
 29/03/16  

25 0   1   2   3   4   5   6   7   pour i de 4 à 1 par pas de -1 : (4,3,2,1)

5  
Tout  gris  c'est  parfois  triste  ...   19
1   Tout  gris  c'est  parfois  triste  ...   0 1 2 3 4 5 6 7 25
5  
2   2  
pour i de 4 à 1 par pas de -1 faire 1 19
Un  choix  (parmi  d'autres)  :   12 3   pour j de 0 à 7 faire 2  
.  on  part  d'en  bas  en  ajoutant  64  à  chaque  fois   8   img[i, j] = (4 – i)* inc 2
4   finpour 3
12
.  on  traite  à  part  la  première  ligne  (celle  d'en  haut  !)       64   8  
finpour
declare 0   4 64  
img : tableau[5,8] d'entiers // une image 5 lignes, 8 colonnes pour j de 0 à 7  
i : entier // indice de parcours des lignes D'autres  écritures  du  corps  de  boucle  sont  possibles  :  (inc=64)   0  
j : entier // indice de parcours des colonnes .  (4  –  i)*inc    vaut  successivement    (4-­‐4)*64,  (4-­‐3)*64,  (4-­‐2)*64,  (4-­‐1)*64  :  ok    
inc : constante entier = 64 // incrément de gris : 64 ici
debut .  256  –  i*inc  vaut  successivement    256-­‐(4*64),  256-­‐(3*64),  256-­‐(2*64),  256-­‐(1*64):  ok  
pour i de 4 à 1 par pas de -1 faire // pour chaque ligne en partant du bas sauf la "dernière"  
pour j de 0 à 7 faire // ne dépend pas de j
img[i, j] = (4 – i)* inc // numéro de ligne en partant du bas x incrément Autre  sol.  avec  une  addi;on  sur  inc   // initialisation ligne 4 // griser les lignes 3,2,1
de gris .  img[i,j]  =  img[i+1,  j]+inc     pour j de 0 à 7 faire pour i de 3 à 1 par pas de -1 faire
finpour // j'ai fini toutes les colonnes donc une ligne donne  les  mêmes  itéra;ons    
finpour // j'ai fini de griser les 4 lignes en partant du bas img[4, j] = 0 pour j de 0 à 7 faire
après  avoir  ini;alisé  img[4,  j]  =  0  
pour j de 0 à 7 faire finpour img[i, j] = img[i+1, j] + inc
  finpour
img[0, j] = 255 // je fini avec la première ligne (i=0) de blanc
finpour D'autres  boucles  (et  corps)  sont  bien  sûr   finpour
pour i de 1 à 4 faire // haut -> bas
fin aussi  possible  :     pour j de 0 à 7 faire
img[i, j] = 256 – i* inc
finpour
finpour
29/03/16   Algo  2.  L1  math-­‐info.  PhL   13   29/03/16   Algo  2.  L1  math-­‐info.  PhL   14  

Quelques  exercices  sur  des  images  

-­‐  Générer  le  néga;f  (reverse  vidéo)  d'une  image  NB  ou  par  niveau  de  gris    
-­‐  Générer  une  image  NB  à  par;r  d'une  image  niveau  de  gris  
-­‐  Générer  une  image  miroir  ver;cal  ou  horizontal  d'une  image  NB   Exemples  de  traitements  
-­‐  Augmenter  le  contraste  d'une  image  à  niveau  de  gris    
Principe  :  fixer  un  seuil  et  remplacer  les  pixels  plus  clairs  que  le  seuil  par  des  pixels  blancs,    
et  inversement  les  plus  sombres  que  le  seuil  par  des  pixels  noirs.    

-­‐  Augmenter  la  luminance  d'une  image  à  niveau  de  gris  

Principe  :  ajouter  ou  retrancher  une  constante  de  la  valeur  des  pixels.    
-­‐  Générer  les  contours  significa;fs  d'une  image      
Principe  :  on  remplace  par  un  pixel  noir  chaque  pixel  dont  la  varia;on  des  valeurs  de  ses  voisins  
varient  au  delà  d'un  certain  seuil,  sinon  on  le  remplace  par  un  pixel  blanc    
-­‐  Réduire  par  2  la  taille  d'une  image  à  niveau  de  gris  
Principe  :  chaque  carré  de  2x2  pixels  est  remplacé  par  1  pixel  de  valeur  la  moyenne  des  pixels  du  carré  

 
29/03/16   Algo  2.  L1  math-­‐info.  PhL   15   29/03/16   Algo  2.  L1  math-­‐info.  PhL   16  

4  
 29/03/16  

Matrices
Vocabulaire  
-­‐  matrice  =  tableau  2D  de  nombres  (en;ers,  flobants),  de  booléens  
-­‐  matrice  carrée  =  autant  de  lignes  que  de  colonnes                    
         
 
 
 
 
Des  algorithmes  sur  les  tableaux  2D -­‐  la  diagonale  de  la  matrice  A  :  A[i,i]    à  c'est  un  vecteur    
Suite  d'exemples  en  interac;on  :  les  matrices   -­‐  une  matrice  (carrée)  diagonale  :  A[i,  j]  =  0  pour  tous  les  i  ≠  j    
-­‐  la  matrice  (diagonale)  iden;té  I  ou  Id(n)  =  des  1  sur  la  diagonale,  des  0  
ailleurs  
-­‐  une  matrice  (carrée)  symétrique  :  A[i,j]  =  A[j,i]      
-­‐  ...    
29/03/16   Algo  2.  L1  math-­‐info.  PhL   17  
  29/03/16   Algo  2.  L1  math-­‐info.  PhL   18  

Matrices  et  premiers  algorithmes  

Vérifier  si  une  matrice  donnée  est  ou  n'est  pas  d'une  certaine  
forme  :  
 -­‐  diagonale  ?  symétrique  ?  égale  à  l'iden;té  ?    
 l'inverse  d'une  autre  matrice  donnée  ?...  
 fonc;on  à  réponse  booléenne  
 
Générer  une  matrice  ou  une  forme  matricielle  par;culière  à  par;r  
d'une  (ou  plusieurs)  matrice(s)  donnée(s)  :   Vérifier  si  une  matrice  donnée  est  symétrique  
 -­‐  matrice  transposée   ou  non  ?
 -­‐  matrice  symétrique  à  par;r  de  la  par;e  triangulaire  supérieure   Un  premier  problème  :  vérifier    
 
 -­‐  arithmé;que  matricielle  :  A+B,  AxB,  Axu,  ...  
 fonc;on/procédure  à  réponse  numérique/matricielle    

29/03/16   Algo  2.  L1  math-­‐info.  PhL   19   29/03/16   Algo  2.  L1  math-­‐info.  PhL   20  

5  
 29/03/16  

Vérifier  si  une  matrice  donnée  est  symétrique  ou  non  ? Vérifier  si  une  matrice  donnée  est  symétrique  ou  
Entrée  :  une  matrice  (carrée)  A  
non  ?
Premières  solu;ons  à  base  de  boucles  pour  imbriquées  
Sor;e  :  une  réponse  booléenne   -­‐  choix  1  :  parcourir  toute  la  matrice  
   
Principe  
-­‐  parcourir  chaque  valeur  A[i,j]  
declare
-­‐  la  comparer  à  A[j,i]   n : constante entier = ... // paramètre taille de l'une matrice carrée
-­‐  si  égalité,  on  con;nue   A : tableau[n, n] d'entiers = ... // une matrice carrée 4x4 initialisée ...
-­‐  sinon  la  réponse  est  connue   rep : booléen = VRAI // la réponse : vrai ou faux
i, j : entier // les indices de parcours ligne-colonne
  debut
Premières  solu;ons  à  base  de  boucles  pour  imbriquées   pour i de 0 à n-1 faire // pour chaque ligne
-­‐  choix  1  :  parcourir  toute  la  matrice   pour j de 0 à n-1 faire // pour chaque colonne
-­‐  choix  2  :  parcourir  une  moi;é  de  la  matrice  :  triangulaire  supérieure   si A[i , j] != A[j, i] alors // test de non-symétrie
rep = FAUX
  finsi
Erreurs  possibles   finpour // j'ai fini toutes les colonnes
-­‐  l'entrée  n'est  pas  une  matrice  carrée   finpour // j'ai fini toutes les lignes
fin
 
 
 29/03/16   Algo  2.  L1  math-­‐info.  PhL   21   29/03/16   Algo  2.  L1  math-­‐info.  PhL   22  

 
 
 

Vérifier  si  une  matrice  donnée  est  symétrique  ou   Vérifier  si  une  matrice  donnée  est  symétrique  ou  
non  ? non  ?
Premières  solu;ons  à  base  de  boucles  pour  imbriquées   Premières  solu;ons  à  base  de  boucles  pour  imbriquées  
-­‐  choix  1  :  parcourir  toute  la  matrice   -­‐  choix  2  :  ne  parcourir  que  la  par;e  triangulaire  supérieure    
   A[i,  j]  avec  i  <  j  
 

declare declare
n : constante entier = ... n : constante entier = ...
A: tableau[n, n] d'entiers = ... A : tableau[n, n] d'entiers = ...
rep : booléen = VRAI Cet  algorithme  n'oublie  rien   rep : booléen = VRAI Analyse  de  l'améliora;on  
i, j : entier -­‐  double  boucle  imbriquée  à  n2  tests  internes   i, j : entier -­‐  oui  :  parcours  de  la  par;e  triangulaire  
debut mais  n'est  pas  op;mal   debut supérieure  
pour i de 0 à n-1 faire -­‐  n  tests  inu;les  :     pour i de 0 à n-1 faire  
pour j de 0 à n-1 faire  la  diagonale  à  i=j  :  A[i,  i]  vs.  A[i,  i]     pour j de i+1 à n-1 faire -­‐  non  op@mal  encore  :  
si A[i , j] != A[j, i] alors -­‐  n/2  test  inu;les  :     si A[i , j] != A[j, i] alors si  A[1,2]  ≠  A[2,1]  et  taille  n  grande  ...  
rep = FAUX rep = FAUX
finsi  A[i,  j]  vs.  A[j,  i]  puis  A[j,  i]  vs.  A[i,  j]     finsi beaucoup  de  tests/d'itéra;ons  inu;les    
finpour   finpour  
finpour Améliora;on     finpour  
fin ne  parcourir  que  la  par;e  triangulaire  supérieure     fin Exercice  :  écrire  un  algorithme  qui  réduit  le  
nombre  d'itéra;ons/comparaisons  

29/03/16   Algo  2.  L1  math-­‐info.  PhL   23   29/03/16   Algo  2.  L1  math-­‐info.  PhL   24  

6  
 29/03/16  

Vérifier  si  une  matrice  donnée  est  symétrique  ou  

Sous  forme  de  fonc.on
non  ? declare
L'écrire  sous  forme  d'une  fonc;on   n : constante entier = ... En-­‐tête  
A: tableau[n, n] d'entiers = ...
  rep : booléen = VRAI   fonction VerifSym(n: entier, M: tableau[n,n] d'entiers) retourne booléen
i, j : entier    
Entrée  :  une  matrice  (carrée)  A,  sa  taille  n   debut    
Sor;e  :  une  réponse  booléenne   pour i de 0 à n-1 faire
Corps    
  pour j de i+1 à n-1 faire
fonction VerifSym(M: tableau d'entiers, n: entier) retourne fonction VerifSym(n: entier, M: tableau[n,n] d'entiers) retourne booléen
si A[i , j] != A[j , i] alors rep : booléen = VRAI
booléen rep = FAUX
fonction VerifSym(M: tableau[] d'entiers, n: entier) retourne finsi i, j : entier
booléen finpour debut
finpour
fin pour i de 0 à n-1 faire
fonction VerifSym(M: tableau[n,n] d'entiers, n: entier) retourne pour j de i+1 à n-1 faire
booléen si M[i , j] != M [j , i] alors

fonction VerifSym(n: entier, M: tableau[n,n] d'entiers) retourne
rep = FAUX
booléen finsi
  finpour
finpour
Erreurs  possibles  
retourne rep
Si  le  paramètre  effec;f  n'est  pas  une  matrice  carrée  :  
fin
-­‐  contrôler  la  taille  si  elle  n'est  pas  un  paramètre  formel  de  la  fonc;on,    
-­‐  puis   arrêter  le  traitement  si  besoin.     Algo  2.  L1  math-­‐info.  PhL  
29/03/16   25   29/03/16   Algo  2.  L1  math-­‐info.  PhL   26  
 .  ce  n'est  pas  le  cas  ici.  

Transposer  une  matrice  donnée

Entrée  :  une  matrice  A  
Sor;e  :  une  matrice  tA  
 
On  suppose  A  carrée    
Principe  ...  trop  naïf  pour  être  juste  
-­‐  parcourir  chaque  valeur  A[i,j]  à  double  boucle  pour  imbriquée  
-­‐  échanger  A[i,  j]  et  A[j,  i]  
declare
  A: tableau[3, 3] d'entiers = [ [1, 1, 1], [0, 2, 3], [2,
1, -1]]
Transposer  une  matrice  donnée Exemple     i, j, tmp : entier
-­‐    à  dérouler  sur  la  matrice    A   debut
Un  deuxième  problème  :  générer     pour i de 0 à 2 faire
-­‐  et  ...   pour j de 0 à 2 faire
 
Proposer  un  algorithme  correct.   classique tmp = A[i, j] // échange

  A[i, j] = A[j, i]
A[j, i] = tmp
  finpour
Algo   finpour PhL  
29/03/16   Algo  2.  L1  math-­‐info.  PhL   27  
 29/03/16   fin
2.  L1  math-­‐info.   28  

 
 
 
  7  
 29/03/16  

Calculer  un  produit  matrice  x  matrice

Entrée  :  2  matrices  A[m,  n]  et  B[n,p]  
Sor;e  :  une  matrice  C[m,  p]  
 
Principe  sur  un  produit  de  matrices  carrées  de  taille  n  :  C=A*B  
-­‐  calculer  la  matrice  produit  C  =  calculer  ses    n2  coefficients:    
 à  C[i,  j]  pour  i=0,n-­‐1  et  j=0,n-­‐1  
 à  double  boucle  pour  imbriquée  sur  i  (ligne  de  C)  et  j  (colonne  de  C)  
 
-­‐  pour  chaque  couple  (i,j),  calculer  la  valeur  du  coefficient  C[i,j]  :  
 à  C[i,  j]  =  Σ  A[i,  k]  *  B[k,  j]    
Calculer  un  produit  matrice  x  matrice      =  A[i,  0]*B[0,  j]  +  A[i,  1]*B[1,  j]  +  A[i,  2]*B[2,  j]  +  ...    
     +  ...  +  A[i,  k]*B[k,  j]  +  ...  +  A[i,  n-­‐1]*B[n-­‐1,  j]    
Un  troisième  problème  :  calculer    à  boucle  pour  sur  k  (une  ligne  de  A,  une  colonne  de  B)  
   
Conclusion  
-­‐  triple  boucle  pour  imbriquée,  sur  i,j  (parcourir  C),  k  (parcourir  A  et  B)  
 
29/03/16   Algo  2.  L1  math-­‐info.  PhL   29     29/03/16   Algo  2.  L1  math-­‐info.  PhL   30  

 
 
 
 

Calculer  un  produit  matrice  x  matrice j   Calculer  un  produit  matrice  x  matrice
 declare  
Exercice   facile  pour  se  détendre  
A: tableau[4, 2] d'entiers = [ [1, 1], [2, 3], [1, -1], [0,-2] ]
  B: tableau[2, 3] d'entiers = [ [1, 2, 3], [-2, 0,-4] ] k -­‐     expliciter  la  suites  des  indices  i,j,k  en  
C: tableau[4, 3] d'entiers déroulant   le  produit  matrice  x  matrice  ci-­‐
declare
  i, j, k : entier // itérateurs   A: tableau[4, 2] d'entiers = ....
contre.   B: tableau[2, 3] d'entiers = ....
i  
  // C est mise à zéro
debut      
C : tableau[4, 3] d'entiers =
i, j, k : entier
  pour i de 0 à 3 faire // exemple d'initialisation Remarques  
  debut
pour j de 0 à 2 faire // Bien voir pourquoi -­‐  l'ordre  du  parcours  de  C  est  arbitraire  
// C est mise à zéro
C[i, j] = 0 // la mise à zéro est nécessaire ! pour i de 0 à 3 faire
i   finpour   les  boucles  "i"  et  "j"  peuvent  être  
à   pour j de 0 à 2 faire
finpour permutées  
C[i, j] = 0
finpour
// calcul de C=A*B   finpour
pour i de 0 à 3 faire // ligne i Ques;on  
pour j de 0 à 2 faire // colonne j Autre  solu;on  pour   -­‐  l'ordre  de  l'accumula;on  dans  C[i,j]  est  aussi   // calcul de C=A*B
pour k de 0 à 1 // parcours k ini;aliser  C[i,  j]  avant   arbitraire  (au  moins  dans  IR)   pour i de 0 à 3 faire
C[i, j] = C[i,j] + A[i,k]*B[k,j] // vu ? à  la  boucle  sur  "k"  peut  être  aussi  permutée   pour j de 0 à 2 faire
finpour l'accumula;on  de  la   pour k de 0 à 1
finpour boucle  sur  k  ?   avec  celles  sur  "i"  ou  "j"   C[i, j] = C[i,j] + A[i,k]*B[k,j]
finpour       finpour
fin finpour
6  ordres  possibles  pour  ce  produit   finpour
fin
i-­‐j-­‐k,  i-­‐k-­‐j,  j-­‐i-­‐k,  k-­‐i-­‐j,  k-­‐j-­‐i,  j-­‐k-­‐i  
29/03/16   Algo  2.  L1  math-­‐info.  PhL   31      29/03/16   Algo  2.  L1  math-­‐info.  PhL   32  

8  
 29/03/16  

Calculer  un  produit  matrice  x  matrice Calculer  un  produit  matrice  x  matrice
L'écrire  sous  forme  d'une  fonc;on   L'écrire  sous  forme  d'une  procédure  
   
Entrées  :  une  matrice  A  de  taille  m  x  n    et  une  matrice  B  de  taille  n  x  p  (de  flobants)   Entrées  :  une  matrice  A  de  taille  m  x  n    et  une  matrice  B  de  taille  n  x  p  
Sor;e  :  une  matrice  C  de  taille  m  x  p  (de  flobants)   Sor;e  :  une  matrice  C  de  taille  m  x  p  
   
Problèmes  de  conven;on     procedure Produit(m: in entier, n: in entier, p: in entier
-­‐  une  fonc;on  peut  retourner  un  tableau  :  oui/non  ?   A: in tableau[m,n] de flottants,
à  ce  qui  implique  que  l'affecta;on  A = B est  autorisée  pour  A  et  B,     B: in tableau[n,p] de flottants,
C: inout tableau[m,p] de flottants)
Déjà  :  il  faut  2  tableaux  de  même  type  d'éléments  et  de  même  taille  ...  
 
 
Erreurs  possibles  
-­‐  si  oui,  faut-­‐il  préciser  la  taille  du  tableau  résultat  :  oui/non  ?  
Si  les  paramètres  effec;fs  ne  vérifient  pas  (m,  n)  x  (n,  p)  à  (m,  p)  
fonction Produit(....) retourne tableau de flottants
-­‐  contrôler  les  tailles  des  paramètres  effec;fs,  
fonction Produit(....) retourne tableau[m,p] de flottants
-­‐  puis,  arrêter  le  traitement  si  besoin  
 
-­‐  sinon,  une  procédure  convient.  
 

29/03/16   Algo  2.  L1  math-­‐info.  PhL   33   29/03/16   Algo  2.  L1  math-­‐info.  PhL   34  

Procédures  et  tableaux  2D   Procédures  et  tableaux  2D  

   
Appelant Sous  programmes  externes  :  lecture  et  affichage  de  matrices
declare procedure Lire(m: in entier, n: in entier, A : inout tableau[m,n] de flottants)
M: tableau[4,2] de flottants i, j : entier
debut
N: tableau[2,3] de flottants
pour i de 0 à m-1 faire
P: tableau[4,3] de flottants pour j de 0 à n-1 faire
Lire(A[i, j])
avec // en-tête des sous-programmes externes utilisés finpour
procedure Lire(m: in entier, n: in entier, A : inout tableau[m,n] de flottants) finpour
procedure Afficher(m: in entier, n: in entier, A : in tableau[m,n] de flottants) fin procedure

procedure Produit( m: in entier, n: in entier, p: in entier,

A: in tableau[m,n] de flottants, B : in tableau[n,p] de procedure Afficher(m: in entier, n: in entier, A : in tableau[m,n] de flottants)
flottants,
i, j : entier
C: inout tableau[m,p] de flottants) debut
pour i de 0 à m-1 faire
debut pour j de 0 à n-1 faire
Lire(4, 2, M) Afficher(A[i, j])
Lire(2, 3, N) // seules M et N sont initialisées. OK ? finpour
Afficher(sdl) // saut de ligne quand il faut
Produit(4, 2, 3, M, N, P)
finpour
Afficher(4, 3, P) fin procedure
fin  
 
29/03/16   Algo  2.  L1  math-­‐info.  PhL   35   29/03/16   Algo  2.  L1  math-­‐info.  PhL   36  

9  
 29/03/16  

Procédures  et  tableaux  2D  

 
Procédure  de  produit  matrice  x  matrice
procedure Produit(m: in entier, n: in entier, p: in entier,
A: in tableau[m,n] de flottants, B : in tableau[n,p] de flottants,
C: inout tableau[m,p] de flottants)
i, j, k : entier
debut

pour i de 0 à m-1 faire
pour j de 0 à p-1 faire
C[i, j] = 0.0 // autre façon d'initialiser C[i,j] avant
l'accumulation
pour k de 0 à n-1 faire Un  problème  de  synthèse
C[i, j] = C[i, j] + A[i, k]*B[k, j] Vérifier  qu'une  matrice  donnée  est  l'inverse  ou  non  
finpour
finpour d'une  autre  matrice  aussi  donnée  
finpour  
fin procedure  

 
29/03/16   Algo  2.  L1  math-­‐info.  PhL   37   29/03/16   Algo  2.  L1  math-­‐info.  PhL   38  

Vérifier  que  deux  matrices  données  sont    

l'inverse  l'une  de  l'autre
Le  peu  de  math  nécessaire  
-­‐  Déf.:    La  matrice  A  est  l'inverse  de  la  matrice  B  ssi  A*B  =  B*A  =  I  :  matrice  iden;té  
-­‐  Conséquence  :    le  produit  A*B  doit  commuter    
 donc  A  et  B  sont  carrées  de  même  taille,  celle  de  I  
 
Mise  en  place  de  l'algo  
-­‐  Entrées  :  deux  matrices  A  et  B  carrées  de  taille  n  
-­‐  Sor;e  :  un  booléen  
à      donc  peut  se  présenter  sous  forme  d'une  fonc;on  
fonction VerifInverse ( n: in entier,
A: in tableau[n,n] de flottants,
Quelques  remarques  avant  de  conclure
B: in tableau[n,n] de flottants) retourne booléen Généralisa;on  aux  tableaux  3D  et  plus  
-­‐  Principe  du  traitement   Aspects  pra;ques  
.  effectuer  le  produit  A*B  (ou  B*A)  
.  comparer  la  matrice  résultat  avec  I[n,n]  

29/03/16   Algo  2.  L1  math-­‐info.  PhL   39   29/03/16   Algo  2.  L1  math-­‐info.  PhL   40  

10  
 29/03/16  

Retour  sur  les  images  en  couleurs Remarques  sur  les  tableaux  
Une  image  =  quadrillage  de  pixels  couleur  
mul.dimensionnels  
img : tableau[1024,768] de  ...  pixels  couleurs En  pra;que,  les  tableaux  nD  sont  représentés  comme  des  vecteurs  
  -­‐  déroulage/dépliage  selon  les  lignes  OU  les  colonnes      
1  pixel  couleur  =  triplet  d'en;ers  RGB     1   2   3  
exemple  :  [255,  0,  0  ]  =                        [255,255,0]  =                  [127,127,127]=      
    4   5   6  
pixel : tableau[3] d'entiers
-­‐  ligne  vs.  colonnes  :  dépend  du  langage  de  programma;on  
 
   C  :  par  ligne        
Une  solu;on  :  le  tableau  3D   1   2   3   4   5   6  
imgCouleur : tableau[1024, 768, 3] d'entiers      
imgCouleur[i, j, 0] à composante R du pixel [i,j]    Fortran  :  par  colonne         1   4   2   5   3   6  
imgCouleur[i, j, 2] à composante B du pixel [i,j]      
-­‐  3  indices  :  ini;alisa;on/lecture/affichage  avec  triple  boucle  pour   Les  indices  mul;ples  sont  une  commodité  de  nota;on  à  s'en  
imbriquées  

servir  !!!!  
29/03/16   Algo  2.  L1  math-­‐info.  PhL   41    
29/03/16   Algo  2.  L1  math-­‐info.  PhL   42  

Ce  qui  reste  à  présenter  sur  les  tableaux Ce  qui  reste  à  présenter  sur  les  tableaux
Vu  :  tableau  sta;que     Vu  :  tableau  
la  taille  du  tableau  est  fixé  une  fois  pour  toute  lors  de  sa  déclara;on   un  tableau  regroupe  des  objets  de  même  type  
(ce  qui  ne  veut  pas  dire  qu'il  soit  ini;alisé)  
on  peut  être  amené  à  réserver  plus  de  place  que  nécessaire  
ses  éléments  sont  accédés  par  les  indices  
     
Pas  vu  :  tableau  dynamique  ou  redimensionnable   Pas  vu  :  enregistrement  
la  taille  du  tableau  n'est  pas  précisée  lors  de  sa  déclara;on   structure  de  données  qui  regroupe  des  valeurs  de  type  différents    
mais  il  existe  une  fonc;on  spéciale  pour  fixer  la  taille  de  la  mémoire   chaque  valeur  est  appelé  un  champ  
nécessaire  au  stockage  du  contenu  du  tableau    
à  alloca;on  dynamique  de  mémoire  
un  champ  est  accédé  par  son  nom  et  une  nota;on  pointée  (souvent)  

(et  une  autre  fonc;on  pour  libérer  cebe  "place  mémoire"  si  on  n'en  
n'a  plus  besoin)    
   
En  pra;que,  ces  tableaux  ne  sont  pas  stockés  dans  la  même  zone  
mémoire    
 
29/03/16   Algo  2.  L1  math-­‐info.  PhL   43   29/03/16   Algo  2.  L1  math-­‐info.  PhL   44  

11  
 29/03/16  

Enregistrements   Ce  qui  reste  à  présenter  sur  les  tableaux

declare
declare enregistrement pixelCouleur Vu  :  tableau  
enregistrement Etudiant R: entier = 0 // valeur par défaut les  indices  sont  des  en;ers  consécu;fs  entre  0  et  taille-­‐1  
NumEtud: entier G: entier = 0  
Nom: tableau[55] de caractères B: entier = 0
Prenom: tableau[55] de caractères finenregistrement Pas  vu  :  tableau  associa;f  ou  indice  énuméra;f    
finenregistrement un  type  énuméra;f  est  un  ensemble  de  valeurs  discrètes  
p: pixelCouleur = [255, 255, 0] Couleurs : [ Rouge, Orange, Vert ] // autres syntaxes possibles
Moi, MonVoisin: Etudiant // on peut convenir d'autres écritures feu: Couleurs = Rouge
// d'affectations  
debut AOen@on  :  Rouge ≠ "Rouge"
Moi.NumEtudiant = 432165 ImgCouleur: tableau[512, 384] de  
pixelCouleur
MonVoisin.Nom = "Machin" un  tableau  associa;f  est  indicé  par  les  valeurs  d'un  type  énuméra;f    
fin debut declare
  si ImgCouleur.R == p.G alors pixelCouleur : tableau[Couleurs] d'entiers
... p : pixelCouleur
finsi debut
fin p[Rouge] = 128
fin
 
29/03/16   Algo  2.  L1  math-­‐info.  PhL   45   29/03/16   Algo  2.  L1  math-­‐info.  PhL   46  

Les  tableaux  1D,  2D  et  plus  ...  en  une  diapo
Un  tableau  regroupe  des  objets  de  même  type  
Ses  éléments  sont  accédés  par  des  indices  
Autant  d'indices  que  de  dimensions  :  [i]  à  1D        [i,  j]  à  2D        [i,j,k]  à  3D  ...  
Les  indices  varient  entre  0  et  taille-­‐1  (en  général)  
La  taille  est  fixée  une  fois  pour  toute  à  la  déclara;on  (en  général)  
Déclarer  n'est  pas  ini;aliser  
Ini;aliser,  lire,  afficher  :  la  classique  boucle  pour  imbriquée  1  fois,  2  fois,  3  fois  ...  
Exemples  de  traitements  classiques  avec  des  images  et  des  matrices  
Les  sous-­‐programmes  avec  des  paramètres  tableaux  doivent  aussi  préciser  les  
Synthèse  sur  les  tableaux   tailles  correspondantes  
en  une  diapo    
Commencer  à  compter  le  nombre  d'itéra;ons  des  boucles  imbriquées,  et  leur  effet  
sur  le  nombre  d'opéra;ons  ou  d'instruc;ons  alors  exécutées  
Commencer  à  compter  la  place  mémoire  nécessaire  au  stockage  et  aux  traitements    
 
 
29/03/16   Algo  2.  L1  math-­‐info.  PhL   47    
29/03/16   Algo  2.  L1  math-­‐info.  PhL   48  

12