Données et traitements

2. Données et traitements

Un algorithme agit sur des données qui peuvent être élémentaires ou bien structurées. Une donnée élémentaire correspond à tout ce qui peut être représenté par un codage sur un mot-mémoire. Cela comprend des nombres, des symboles, ou tout autre élément de la réalité qui peut être codé simplement. Le nombre de bits qui compose un mot-mémoire conditionne le nombre d'objets élémentaires qu'on peut coder. Une structure de données permet de regrouper des données élémentaires de manière cohérente. Pour modéliser les données, on peut utiliser un type abstrait, à un niveau d'abstraction supérieur à celui de la structure de données.
Par exemple, en choisissant un codage sur 32 bits, on pourra représenter plus de quatre milliards d'entiers naturels ou relatifs, l'ensemble des caractères Unicode, ... ou l'ensemble des nouveaux-nés de l'année en cours. On pourra modéliser l'identité d'un individu par un type abstrait Ensemble groupant son nom, ses prénoms, sa date de naissance, etc. La structure de données matérialisant cet ensemble pourra contenir une chaine de n caractères pour le nom, une liste de chaines de p caractères pour les prénoms, un triplet d'entiers naturels pour la date de naissance, etc.

Chaque objet élémentaire ou structuré est représenté dans un algorithme par un identificateur (un nom). On ne donne pas au début d'un algorithme général la liste des identificateurs utilisés ni leurs types (il n'est même pas obligatoire de conserver un même type pour un identificateur !). Les identificateurs essentiels sont indiqués dans les rubriques Entrée et Sortie, et les autres variables (d'usage) sont découvertes à mesure. Par contre, dans un algorithme précisé, on peut ajouter une rubrique Variables d'usages (après Résultat ou Sortie) qui donne la liste de ces variables. Il n'y a pas lieu de différencier identificateurs de variables ou de constantes.

Quand on veut affecter une valeur à une variable on utilise le symbole ← (flèche gauche, souvent écrite <-). Par exemple n←3 pour placer la valeur 3 dans la variable n. Plus généralement, on utilise des notations littérales et des symboles mathématiques plutôt que des symboles venant des langages de programmation :

algorithmique	mathématiques	programmation
←		`= := let`
non	¯ ¬	`! ~ -`
et	* ∧	`& && and`
ou	+ ∨	`\| \|\| or`
Faux (F)	0	`0 False FALSE`
Vrai (V)	1	`1 True TRUE`
=	=	`= ==`
≠	≠	`<> != ~=`
>	>	>
≥	≥	`>=`
<	<	`<`
≤	≤	`<=`
exposant	exposant	`^ **`
div	division entière	`/ //`
mod	et son reste	`% %%`

Les actions élémentaires qu'effectue un algorithme sur ces données (lecture, modification, copie, etc.) constituent les traitements, lesquels peuvent être des suites d'instructions élémentaires constituant des blocs ou la structuration et l'imbrication de divers blocs d'instructions à l'aide de structures de contrôle (parfois appelées schémas de contrôle). Il y a un nombre fini d'instructions élémentaires sur un mot-mémoire, mais on peut créer des instructions structurées en les combinant. Quand un ensemble d'instructions porte sur un type abstrait, on peut créer une primitive qui réalisera une action de base pour ce type.
Par exemple, en utilisant l'addition comme instruction élémentaire, on pourra créer une instruction structurée qui réalisera une multiplication : « pour multiplier n par p, ajouter p fois n à lui-même » (bien évidemment, il est préférable de prévoir la multiplication comme instruction élémentaire!). Autre exemple, pour obtenir l'âge d'une personne, on effectue une suite d'opérations sur les années, mois et jours. Le type abstrait Date peut alors être associée à une primitive age(date_naissance,date_du_jour).

Structures de données usuelles :

Tableaux à une ou plusieurs dimensions. Les chaines de caractères peuvent être considérées comme des tableaux de caractères.
Un ou plusieurs indices donne un accès immédiat à chacun des éléments d'un tableau : T : T[1], ..., T[n] pour un tableau unidimensionnel de n éléments, T[i,j] pour deux dimensions, T[i,j,k] pour trois, etc.
Listes et autres structures ordonnées.
Dans une structure ordonnée, certains éléments sont accessibles immédiatement, les autres le sont indirectement (en passant par d'autres éléments). L'accès aux éléments est linéaire dans une liste, déterminé une arborescence, ou multiple dans un graphe orienté.
Ensembles.
Dans la mesure où les données en machine sont toujours placées dans un certain ordre (ne serait-ce qu'à cause du codage), un ensemble un type abstrait de données caractérisé par l'unicité d'une valeur présente dans l'ensemble et, généralement, par une référence à un ensemble plus vaste. Les opérateurs ∈ ⊂ sont notamment utilisés.
Un type abstrait Ensemble peut être matérialisé par diverses structures de données : tableau d'éléments, liste d'éléments, vecteur caractéristique, etc.
Structures combinatoires (arbres, graphes).
Les données élémentaires, formant un ensemble de sommets, sont liées deux-à-deux par une relation binaire, correspondant à un ensemble d'arêtes. L'accès à ces sommets se fait de proche en proche en suivant les arêtes.

Structures de contrôles usuelles :

Si-alors, la conditionnelle simple, avec deux mises en forme possibles :

Si condition alors instruction(s).

Si condition alors
BLOC_d'instructions.

Les instructions ne sont réalisées que si la condition est vraie.
Si-alors-sinon, la conditionnelle complète ou alternative :

Si condition
alors instruction(s)_1
sinon instruction(s)_2.

Si condition alors
BLOC_1
sinon
BLOC_2.

Selon que la condition est vraie ou fausse, l'algorithme s'oriente vers l'un ou l'autre des blocs d'instructions.
Selon-valeur, le choix multiple ou aiguillage :
Selon identificateur
valeur valeur n°1 : BLOC_1;
...
valeur valeur n°k : BLOC_k;
autrement : BLOC_k+1.

L'algorithme est aiguillé vers un des blocs selon la valeur d'un identificateur. La dernière clause autrement, qui est généralement facultative, gère toutes les valeurs non listées.
Selon-cas généralise le choix multiple. Chaque cas peut être quelque chose de plus complexe qu'une des valeurs possibles. On peut en particulier rechercher des motifs dans une expression, comme le fait l'instruction match de Caml (appariement).
Pour-faire, la boucle déterminée :
Pour variable_entière de valeur_initiale à valeur_finale faire
BLOC.

Cette boucle est utilisée quand le nombre d'itérations est connu avant de commencer la boucle. La variable entière prend la valeur_initial au début (très généralement 1), réalise le bloc avec cette valeur, puis prend la valeur entière suivante et réalise à nouveau le bloc mais avec cette deuième valeur, et ainsi de suite jusqu'à (y compris) la valeur_finale.
Certaines variantes donnent un pas k à l'incrément : on ajoute une valeur k donnée plutôt que 1, et/ou accepte une évolution décroissante descendant à (au lieu de à), mais il me parait plus simple de n'utiliser que la forme de base.
Pourchaque-faire généralise la boucle déterminée, les valeurs de la variable sont pris dans un ensemble quelconque, ce qui donne une certaine élégance à la mise en forme :
Pourchaque variable dans ensemble faire
BLOC.

Quand l'ensemble est un intervalle entier [n..p], on revient au cas précédent.
Tantque-faire, la boucle pré-contrôlée :
Tantque condition_de_poursuite faire
BLOC.

Le test de condition de poursuite est effectué avant d'entrer une première fois dans la boucle et de réaliser le bloc. Quand la condition n'est plus rempli, on sort de la boucle.
Répéter-jusqu'à, la boucle post-contrôlée :
Répéter
BLOC
jusqu'à condition_d'arrêt.
Le bloc est réalisé au moins une fois. Ce n'est qu'ensuite qu'on teste s'il faut sortir de la boucle. La condition logique est donc inversée.
Important : Utiliser une boucle (pré- ou post-)-contrôlée, nécessite une grande vigilance sur la condition, au risque de créer une boucle infinie.

Par convention, les instructions élémentaires sont séparées par un point-virgule ; la dernière instruction se termine par un point. L'indentation de la présentation met en évidence les blocs d'instructions, sans qu'il soit besoin d'indicateurs de fin de structure de contrôle (Finsi, Finpour, ...) ; dans un algorithme précisé, certains conservent toutefois ces indicateurs.

On peut effectuer des combinaisons emboîtées de structures de contrôle. Les deux plus fréquents sont sans doute l'imbrication de boucles déterminées et l'enchainement de conditionnelles :

Pour h de 1 à n faire

Pour i de 1 à p faire

BLOC_interne;

BLOC_externe;

Si condition_1 alors BLOC_1
sinon Si condition_2 alors BLOC_2
sinon BLOC_3

Remarque. Il n'y a pas lieu pour l'écriture des algorithmes de privilégier l'anglais, au contraire de la programmation où l'utilisation de mots-clés dans une autre langue favorise la visualisation des autres mots (identificateurs, fonctions, etc.) qui, dans un cadre francophone, peuvent être en français.