Obligement - L'Amiga au maximum

Samedi 18 novembre 2017 - 05:44  

Translate

En De Nl Nl
Es Pt It Nl


Rubriques

 · Accueil
 · A Propos
 · Articles
 · Galeries
 · Glossaire
 · Hit Parade
 · Liens
 · Liste jeux Amiga
 · Quizz
 · Téléchargements
 · Trucs et astuces


Articles

 · Actualité (récente)
 · Actualité (archive)
 · Comparatifs
 · Dossiers
 · Entrevues
 · Matériel (tests)
 · Matériel (bidouilles)
 · Points de vue
 · En pratique
 · Programmation
 · Reportages
 · Tests de jeux
 · Tests de logiciels
 · Tests de compilations
 · Articles divers

 · Articles in english
 · Articles in other languages


Twitter

Suivez-nous sur Twitter




Liens

 · Sites de téléchargements
 · Associations
 · Pages Personnelles
 · Moteurs de recherche
 · Pages de liens
 · Constructeurs matériels
 · Matériel
 · Autres sites de matériel
 · Réparateurs
 · Revendeurs
 · Presse et médias
 · Programmation
 · Développeurs logiciels
 · Logiciels
 · Développeurs de jeux
 · Jeux
 · Autres sites de jeux
 · Scène démo
 · Divers
 · Informatique générale


Jeux Amiga

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


Trucs et astuces

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


Glossaire

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


Partenaires

Annuaire Amiga

Amedia Computer

Relec

Hit Parade


Contact

David Brunet

Courriel

 


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 terme 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 :

ASD

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.

ASD
ASD

Essayez sur un exemple. En terme 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.

ASD

Sur ces dires nous allons nous quitter.


[Retour en haut] / [Retour aux articles] [Article précédent]