Suivez-nous sur X
|
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z,
ALL
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
A propos d'Obligement
|
|
David Brunet
|
|
|
|
Programmation : Algorithmes et structures de données - tableaux
(Article écrit par Chorizo Kid et extrait d'A-News (Amiga News) - juin 1989)
|
|
Connaître la qualité d'un calendos est relativement aisé, mais connaître la qualité d'un programme l'est moins. Nous avons
pour cela quelques critères :
- L'écriture : elle doit être structurée (indentation) et modulaire (séparation en procédures et fonctions).
- La justesse : le résultat doit être correct (c'est loin d'être évident d'autant plus qu'on ne sait toujours pas faire
des preuves de validité des programmes (pour les "gros" programmes évidemment, pas pour printf("Bonjour").
De plus, le résultat attendu doit être atteint en un temps fini (problème des boucles infinies).
Les performances d'un programme se chiffrent en Pcoût en mémoire et en Pcoût en temps : un tableau de "n" valeurs aura un
Pcomplexité en espace de "n", une matrice n*n aura une complexité en espace de nA2. Je veux maintenant trouver si un élément
est dans le tableau (parcours du tableau), la complexité maximale en temps est en 0(n): 0 symbolise la complexité en
temps qui est ici de "n" ; en effet, au pire, le "n" cherché sera en bout de tableau, il faudra donc passer les "n"
cases. La complexité moyenne est en 0(n/2).
Ben après quand on va donner des algos, il faudra connaître sa complexité pour voir s'il est bon ou naze. Bon Frédéric Autechaud,
reprends tes markers au toluène et ton Sulitzer et va le colorier plus loin.
Les tableaux
Pour utiliser un tableau, il va falloir le déclarer par :
- Pvar T : tableau[1..dim] d'entier par exemple, où "T" est le nom du tableau comportant Pdim éléments entiers.
Si maintenant je veux une matrice je peux faire :
- Pvar M : tableau[1..max,1..max] de réels par exemple, ou commencer par déclarer le type colonne par...
- Ptype colonne = tableau[1..dim] de réels puis déclarer...
- Pvar M : tableau[1..dim] de colonne.
Recherche d'un entier dans un tableau
En termes algorithmique cela se traduit par "tant qu'on n'a pas trouvé et qu'on n'est pas à la fin du tableau, on teste". Soit :
La complexité est en 0(n) (au pire parcours des "n" cases de tab[]).
Tri
Dans le même style, on peut faire un programme de tri simple :
- On récupère le minimum du tableau[1..10] à la case IMIN.
- On échange la valeur des cases IMIN et 1.
- On récupère le minimum du tableau[2..10] à la case IMIN.
- On échange la valeur des cases IMIN et 2, etc.
- Arrivé à la case 10 le tableau est trié.
La complexité de cet algo est très mauvaise (0(n^2)).
Tableau trié
On veut maintenant chercher si une valeur donnée est dans un tableau trié de 10 éléments entiers.
On va pour cela procéder par dichotomie, c'est-à-dire partager le tableau en deux, chercher dans quelle partie se trouve
la réponse (Gauche ou Droite), puis recommencer le partage en deux avec la bonne partie, etc.
Essayez sur un exemple. En termes parler comme il faut que bien et tout l'algo s'écrit "tant qu'on peut (Gauche<=Droite) et
qu'on doit (Trouve=faux), on cherche".
La complexité est dans ce cas en 0(Log n). Pour un tableau de 10^6 éléments, il faudra 10^6 opérations pour un algo en
0(N), et seulement 20 coups pour un algo en 0(log N) !
Algorithme du drapeau français
Un tableau de "N" cases contient une couleur par case parmi le bleu, le blanc et le rouge (pour les lecteurs belges,
remplacez par du noir, du jaune et du rouge ; désolé pour les Suisses, l'algo ne fait pas de croix). En un seul parcours
du tableau, on veut ranger les cases dans l'ordre tous les bleus, tous les blancs, puis tous les rouges.
On a : I, indice de position, B position libre après les bleus, et R, position libre avant les rouges.
Sur ces dires nous allons nous quitter.
|
