Aujourd’hui
Chap. 3 : les tableaux à deux
dimensions (matrices)
Chap. 4 : décidabilité et complexité
1
Chapitre 3
Les tableaux à deux dimensions
(matrices)
2
Tableaux à n dimensions
Un tableau à une dimension
représente un vecteur
T[i] correspond à Ti
Un tableau à deux dimensions
représente une matrice
M[i][j] correspond à Mij
3
Tableau à deux dimensions
Un tableau de N lignes et M colonnes sera
représenté comme une matrice N x M
M colonnes
0
M-1
0
N lignes
N-1
4
1) Déclaration et initialisation
Syntaxe
type ident [ cste1 ] [cste2] ;
où
cste1 définit le nombre de lignes
cste2 définit le nombre de colonnes
5
Exemples
Une matrice 50x100 d’entiers :
int Mat [50][100];
Une matrice 10x20 de caractères :
#define N 10
char Dico [N][2*N];
Une matrice peut être initialisée à la
déclaration :
int Mat[2][3] = {{1,2,3},{4,5,6}};
6
2) Utilisation
Chaque ident [exprEnt1][exprEnt2] s’utilise
comme une variable du type du tableau.
Les indices (ligne, colonne) doivent
appartenir aux intervalles de définition
correspondants
Exemple
Mat[20][30] = 0;
printf(‘‘%c’’,Dico[5][15]);
7
3) Exemple
Problème
Calculer le produit d’une matrice
d’entiers NxM par un entier z.
Il faut multiplier chaque valeur de la
matrice par l’entier.
8
Exemple
5
-1
10
-2
2
0
4
0
-4
10
-8
20
25
1
50
2
x2
9
Programme (début)
#define N 50
#define M 100
int main()
/* Multiplie une matrice par un entier */
{
int matrice[N][M];
int i, j;
/* indices de parcours */
int z;
/* entier à multiplier */
10
Programme (fin)
/* lecture de z et de la matrice */
…
/* multiplication de la matrice par z */
for (i = 0 ; i < N ; i++ )
for (j = 0 ; j < M ; j++ )
matrice[i][j] *= z;
}
11
4) Passage de matrice en paramètre
Le paramètre formel indique le type, le nom et les
dimensions de la matrice.
Exemple
void lire_matrice(int mat [N] [M] )
/* lit au clavier les valeurs de la matrice en paramètre */
{
int i, j;
/* indices de parcours */
}
for (i = 0 ; i < N ; i++ )
for (j = 0 ; j < M ; j++ )
scanf(‘‘%i’’, &mat[i][j]);
Les dimensions permettent de calculer, à l’exécution, l’adresse
d’un élément de la matrice.
12
Passage de matrice en paramètre
Le paramètre effectif est le nom de la matrice
(comme pour un tableau)
Exemple
printf(‘‘Donnez les valeurs de la matrice’’);
lire_matrice(matrice);
printf(‘‘Donnez la valeur de l’entier’’);
scanf(‘‘%i’’, &z);
Seul le pointeur est passé en paramètre, non les
valeurs.
13
Chapitre 4
Décidabilité et complexité
14
Introduction
Pour résoudre un problème, on
conçoit un algorithme.
Peut-on associer un algorithme à
tout problème ? (décidabilité)
Tous les algorithmes sont-ils
réalisables en pratique ?
(complexité)
15
1) Décidabilité
Théorème (Gödel, 1931)
Certains problèmes sont indécidables, c’està-dire qu’il n’existe pas d’algorithme
général pour les résoudre.
Exemple : peut-on écrire un algorithme qui
prenne en entrée un algorithme P et ses
données D,
décide si P exécuté sur D s’arrête ou non,
et ceci pour tout P et pour tout D?
On peut démontrer que non.
16
Problèmes non calculables
Certains problèmes sont théoriquement
décidables,mais non calculables en
pratique car trop complexes.
Exemples
Trouver une stratégie gagnante aux jeu
d’échecs (temps et mémoire quasi-infinis)
Traduire un texte d’une langue à une
autre (nécessite une théorie des langues)
17
Calculabilité pratique et théorique
Problèmes
Problèmes
décidables
Problèmes
calculables en
pratique
18
2) Complexité
L’exécution d’un programme possède
un coût qui se mesure à l’aide de
deux paramètres
La complexité en temps (la durée
d’exécution)
La complexité en espace (la place
mémoire nécessaire)
19
Pourquoi mesurer la complexité?
Évaluer a priori la complexité permet:
de savoir si un algorithme est
calculable en pratique
de comparer deux algorithmes du
point de vue de leur efficacité.
20
Remarques
La complexité s’évalue indépendamment
de la machine et du langage utilisés (à
distinguer des mesures de performance
qui comparent des implémentations)
La complexité en temps et la complexité
en espace sont opposées: il faut
rechercher le meilleur compromis. Le
temps est souvent le point sensible.
21
Définition
La complexité en temps d’un
algorithme est l’ordre de grandeur
du nombre d’opérations
élémentaires à effectuer, en fonction
de la taille des données
22
Opérations élémentaires
La définition peut varier selon les
problèmes, par exemple
Une opération = une instruction
Ignorer certaines instructions
(entrées-sorties)
Pour comparer deux algorithmes, il
faut utiliser les mêmes critères.
23
Taille des données
En général, le nombre d’opérations
varie en fonction de la taille des
données : il faut estimer le volume
des données à traiter.
Exemple
Calculer la somme de n nombres
requiert n opérations.
24
Ordre de grandeur O(…)
Soit n la taille des données, f(n) le nombre
d’opérations effectuées.
L’ordre de grandeur g(n) est la plus petite
fonction définie par
c : constante quelconque
n0: seuil minimal pour la taille des données
25
3) Principales classes de complexité
Par ordre croissant
Complexité
Complexité
Complexité
Complexité
Complexité
Complexité
constante
logarithmique
linéaire
quasi-linéaire
polynomiale
exponentielle
O(1)
O(log n)
O(n)
O(n log n)
O(nk)
O(kn)
26
Rappel : logarithme décimal
Le logarithme de base b d'un réel positif n,
noté logb(n), est la puissance à laquelle il
faut élever la base b pour obtenir n.
En base 2 : log2(n) = x 2x = n
Exemples
log2(16) = 4 car 24=16
log2(32) = 5 car 25=32
log2(64) = 6 car 26=64
27
Complexité constante : O(1)
La complexité est indépendante de la
taille des données
Exemple
Calculer la somme des entiers allant
de 1 à i. Le coût est fixe, tel que
soit i
s = i*(i+1)/2
28
Complexité logarithmique : O(log n)
Le problème est décomposé en sousproblèmes tels qu’il suffit de résoudre un
seul sous-problème pour résoudre le
problème initial.
Exemple
Recherche dichotomique dans un tableau
trié de taille n : O(log2 n)
Si n = 100, 6 < log2 n < 7
puisque log2(6) = 64 et log2(7) = 128
29
Complexité linéaire : O(n)
Un traitement identique est effectué
sur chaque donnée.
Exemples
Calculer la somme de n nombres
O(n)
Lire n valeurs, les stocker dans un
tableau puis les afficher dans l’ordre
inverse : O(2*n)
30
Complexité quasi-linéaire : O(n log n)
Le problème est décomposé en sousproblèmes tels qu’il faut résoudre
tous les sous-problèmes pour
résoudre le problème initial.
Exemple
Tri rapide, tri par fusion de n valeurs:
O(n log2 n)
Si n = 100, 600 < n log2 n < 700
31
Complexité polynômiale O(nk) k>1
Un traitement identique est effectué sur
chaque k-uplet (doublet, triplet…) de
données
Exemples
Parcours d’une matrice NxN : O(N2)
Multiplication de deux matrices NxN:
O(N3)
Les cas les plus fréquents: complexité
quadratique O(n2) et cubique O(n3)
32
Complexité exponentielle : O(kn) k>1
Lorsqu’il faut énumérer toutes les
solutions potentielles du problème.
Exemples
Énumérer tous les sous-ensembles
d’un ensemble de taille n
Trouver une stratégie gagnante au
jeu d’échecs
33
Comparaison graphique
34
En pratique
Les problèmes de complexités linéaire
O(n) et polynomiale O(nk) sont les plus
fréquents
Les choses se gâtent au-delà d’une
complexité linéaire ou quasi-linéaire :
Les algorithmes polynomiaux sont considérés
comme lents dès que k >3
Les algorithmes exponentiels sont incalculables
dès que n dépasse quelques dizaines
35
Exemples de temps d’exécution
On suppose qu’une instruction s’exécute en 10 -6 secondes
n
10
100
1 000
1 000 000
36
Exemples de temps d’exécution
On suppose qu’une instruction s’exécute en 10 -6 secondes
n
O(n)
10
100
1 000
1 000 000
0,00001 s.
0,0001 s.
0,001 s.
1 s.
37
Exemples de temps d’exécution
On suppose qu’une instruction s’exécute en 10 -6 secondes
n
O(n)
O(n2)
10
100
1 000
1 000 000
0,00001 s.
0,0001 s.
0,001 s.
1 s.
0,0001 s.
0,01 s.
1 s.
2,8 heures
38
Exemples de temps d’exécution
On suppose qu’une instruction s’exécute en 10 -6 secondes
n
O(n)
O(n2)
O(2n)
10
100
1 000
1 000 000
0,00001 s.
0,0001 s.
0,001 s.
1 s.
0,0001 s.
0,01 s.
1 s.
2,8 heures
0,001 s.
1014 siècles
astronomique
astronomique
39
Temps d’exécution « raisonnable »
La notion de « temps raisonnable »
varie selon les applications
Pilotage d’un avion, interface de
dialogue: immédiat
Prévisions météo, statistiques:
quelques heures
Démonstration de théorème:
plusieurs jours
40
4) Cas de complexité
La complexité peut dépendre
uniquement de la taille des données
(ex: addition de valeurs)
Elle peut dépendre aussi de la
configuration de ces données (ex:
recherche d’un élément dans un
tableau). On distingue alors trois
cas possibles.
41
Complexité dans le meilleur des cas
Elle correspond au plus petit nombre
d’instructions qui sera exécuté
Exemple
L’élément recherché dans le tableau est en
première position : on effectue une seule
comparaison
Elle est simple à calculer, mais apporte peu
d’information sur l’algorithme
42
Complexité dans le pire des cas
Elle correspond au plus grand nombre
d’instructions qui sera exécuté
Exemple
L’élément recherché dans le tableau est soit
absent, soit en dernière position : on
effectue n comparaisons
Elle est simple à calculer, mais encore
insuffisante : le pire cas peut se produire
très rarement
43
Complexité en moyenne
C’est l’espérance mathématique des complexités, en
tenant compte des probabilités d’apparition des
données
Exemple
Si l’élément recherché est présent et que tous les
emplacements sont équiprobables, on effectue en
moyenne n/2 comparaisons
Elle donne une bonne idée du comportement usuel
de l’algorithme mais peut masquer des coûts
élevés (dans le pire cas).
Elle nécessite de connaître la probabilité de
répartition des données
44
Bilan
Il n’existe pas de mesure idéale de la
complexité
La complexité au pire et la complexité
en moyenne permettent de
déterminer si le comportement de
l’algorithme est acceptable dans les
cas courants et les cas extrêmes.
45
5) Comparaison d’algorithmes
Définition 1
Un algorithme A est plus efficace
qu’un algorithme B (respectivement
au pire ou en moyenne) si la
complexité de A est inférieure à
celle de B (respectivement au pire
ou en moyenne)
46
Comparaison d’algorithmes
Définition 2
Un algorithme A est optimal si sa
complexité est la plus faible parmi
tous les algorithmes de sa classe
(c’est-à-dire résolvant le même
problème)
47
6) Conclusion
Certains problèmes ne peuvent pas être
résolus avec un algorithme raisonnable
(voire un algorithme tout court)
Il est important de choisir des algorithmes
efficaces (quand la différence de
complexité est importante)
La complexité est mesurable a priori,
tandis que les mesures de performance
comparent des implémentations
48
Conclusion
La recherche d’un élément dans un
tableau est une opération fréquente
La complexité de la recherche
séquentielle est en O(n), celle de la
recherche dichotomique en O(log2 n)
Il est donc intéressant de trier les
tableaux où l’on cherchera souvent des
valeurs
Ceci explique l’importance des
algorithmes de tri et de leur complexité
49
Auto-évaluation
50
Question 1
Déclarer une matrice de réels de
dimensions 30 x 20 appelée
« donnees »
51
Question 1
Déclarer une matrice de réels de
dimensions 30 x 20 appelée
« donnees »
float donnees[30][20];
52
Question 2
#define N 50
#define M 100
int Mat[N][M];
Faire afficher les valeurs de la ligne
d’indice 30 de cette matrice
53
Question 2
#define N 50
#define M 100
int Mat[N][M];
Faire afficher les valeurs de la ligne d’indice
30 de cette matrice
int j;
for(j=0; j<M;j++)
printf(‘‘%i ’’,Mat[30][j]);
54
Question 3
#define N 50
#define M 100
int Mat[N][M];
Faire afficher les valeurs de la colonne
d’indice 15 de cette matrice
55
Question 3
#define N 50
#define M 100
int Mat[N][M];
Faire afficher les valeurs de la colonne
d’indice 15 de cette matrice
int i;
for(i=0; i<N;i++)
printf(‘‘%i ’’,Mat[i][15]);
56
Question 4
Ranger ces complexités par ordre de
grandeur croissante
complexité
complexité
complexité
complexité
exponentielle
linéaire
logarithmique
polynomiale
57
Question 4
Ranger ces complexités par ordre de
grandeur croissante
1.
2.
3.
4.
complexité
complexité
complexité
complexité
logarithmique O(log n)
linéaire O(n)
polynomiale O(nk)
exponentielle O(kn)
58
Question 5
« Pour déterminer si le comportement
d’un algorithme est raisonnable, il
faut connaître sa complexité dans le
meilleur des cas et dans le pire des
cas »
Vrai ou faux ?
59
Question 5
« Pour déterminer si le comportement d’un
algorithme est raisonnable, il faut
connaître sa complexité dans le meilleur
des cas et dans le pire des cas »
La complexité dans le meilleur des cas est
peu utile. On utilise plutôt
- la complexité en moyenne (cas général)
- la complexité au pire
60
© Copyright 2025 ExpyDoc
