CONCEPTION D’UN ALGORITHME

CONCEPTION D’UN ALGORITHME

La conception d’un algorithme un peu compliqué se fait toujours en plusieurs étapes qui correspondent à des raffinements successifs. La première version de l’algorithme est autant que possible indépendante d’une implémentation particulière. En particulier, la représentation des données n’est pas fixée. À ce premier niveau, les données sont considérées de manière abstraite : on se donne une notation pour les décrire ainsi que l’ensemble des opérations qu’on peut leur appliquer et les propriétés de ces opérations. On parle alors de type abstrait de données. La conception de l’algorithme se fait en utilisant les opérations du type abstrait. Pour résoudre des problèmes nous allons appliquer une démarche descendante : on se donne la définition des types de données (on dit encore leur spécification), et on conçoit l’algorithme à ce niveau. On donne ensuite une représentation concrète des types et des opérations, qui peut être encore un type abstrait, et ceci jusqu’à obtenir un programme exécutable.

NOTION DE STRUCTURE DE DONNÉES

Une structure de données est un ensemble organisé d’informations reliées logiquement, ces informations pouvant être traitées collectivement ou individuellement. L’exemple le plus simple : le tableau monodimensionnel (un vecteur) est constitué d’un certain nombre de composantes de même type. On peut effectuer des opérations sur chaque composante prise individuellement mais on dispose aussi d’opérations globales portant sur le vecteur considéré comme un seul objet.  Dunod – La photocopie non autorisée est un délit 3 Exercices et problèmes d’algorithmique Une structure de données est caractérisée par ses composantes et leur arrangement mais surtout par son mode de traitement. Ainsi deux structures ayant les mêmes composantes, les mêmes arrangements comme les PILES et FILES d’ATTENTE sont considérées comme différentes car leurs modes d’exploitation sont fondamentalement différents.

LES BASES  DE LA PROGRAMMATION

LES TYPES DE DONNÉES

Un type en algorithmique est une information permettant de traduire les valeurs depuis une représentation binaire (celle de l’ordinateur) vers une autre représentation plus adaptée à leur programmation dans un langage évolué. Cette notion est tellement importante que toute valeur a forcément un type. Le rôle du type est d’assurer cette traduction en indiquant quelle place en mémoire occupe la valeur et quelle est la technique de codage utilisée. Nous distinguons quatre types élémentaires en algorithmique : • Le type entier sera utilisé pour stocker des valeurs entières, positives ou négatives. Un entier occupe quatre octets (32 bits) en mémoire. • Le type réel sera utilisé pour stocker les nombres à virgule. Un réel occupe huit octets (64 bits) en mémoire. • Le type caractère sera utilisé pour stocker les caractères. Un caractère occupe un octet (8 bits) en mémoire. • Le type booleén sera utilisé pour stocker les valeurs de type vrai/faux. Un booléen occupe un octet (8 bits) en mémoire. Attention au type dit « réel ». En effet, un ordinateur ne stocke ses valeurs que sur une place limitée, il ne stocke donc qu’un nombre limité de décimales après la virgule. Les valeurs de type réel en algorithmique ne sont donc que des valeurs approchées de leur version mathématique ! Remarque Le type utilisé pour stocker des caractères est un peu particulier, car un caractère est en fait un nombre entier ! L’ordinateur utilise une table de correspondance qui associe une valeur entière (un code) à un caractère qu’il s’agit de manipuler, c’est-à-dire, la plupart du temps, pour l’afficher à l’écran. Cette table de correspondance se nomme la table de symboles (table ASCII, Unicode). Pour la table ASCII, un caractère est stocké dans un octet (un groupement de 8 bits), la valeur entière peut donc aller de 0 à 255. Dans le tableau ne sont présentes que les valeurs de 32 à 127 : en deçà de 32, il s’agit de caractères non imprimables, au-delà de 127, ce sont des caractères optionnels, qui sont adaptés à un type de clavier ou de langue particulier, notamment les caractères accentués (é, à, è, ô, â, etc.). 5 Chapitre 1 • Les bases de la programmation 

LES VARIABLES

Une variable est une donnée qu’un programme peut manipuler. Tout variable possède : • Un type (entier, réel, caractère ou booléen). • Un nom ou identificateur que l’utilisateur choisit ; il permet au programme de reconnaître quelle donnée il doit manipuler. • Une valeur qui peut évoluer au cours du programme, mais qui doit respecter le type. Une variable dont le type est entier ne pourra donc jamais contenir de valeur à virgule. L’identificateur ou nom de la variable peut être quelconque, mais doit respecter les critères suivants : • un identificateur commence toujours par une lettre minuscule ; • à l’exception du premier caractère, il peut contenir : des lettres, des chiffres, et le symbole ’_’ (souligné ou underscore) ; • les majuscules et les minuscules sont des lettres différentes : les identificateurs toto et Toto sont différents ; • le nom de variable doit avoir une relation avec le rôle de cette variable et être compréhensible.

QUELQUES ÉLÉMENTS DE SYNTAXE POUR LE LANGAGE ALGORITHMIQUE

Pour écrire correctement un programme en langage algorithmique, il faut fournir certaines informations à l’ordinateur : le mot programme suivi du nom du programme, indique le nom du programme ainsi que son point de départ. Avant d’utiliser une variable dans un programme, il faut la définir, c’est-à-dire indiquer le mot VAR, puis le nom de la variable et enfin son type précédé de ’:’. Une variable s’appelant taux, et dont le type est réel, doit être définie de la manière suivante : VAR taux : réel Cette définition crée une variable nommée taux dans laquelle peuvent être stockés des nombres à virgule. Quelques exemples de définition de variables VAR solution_equation : réel définit une variable nommée solution_equation dont le type est réel ; VAR val_1 : entier définit une variable nommée val_1 dont le type est entier ; VAR lettre : caractère définit une variable nommée lettre dont le type est caractère. 6 1.4. Opérations et opérateurs de base Il est possible de définir plusieurs variables d’un même type en spécifiant le nom du type, puis la liste des noms de variables séparés par des virgules ’,’. Ainsi, les définitions suivantes sont strictement équivalentes : VAR val_a : entier, VAR val_b : entier, VAR val_c : entier ⇔ VAR val_a, val_b, val_c : entier .