Concevoir, programmer et tester des algorithmes simples.

Concevoir, programmer et tester des algorithmes simples.

I- Notion d'algorithme
I-1-Généralité

Pour développer un programme, il est souhaitable de passé beaucoup de temps à réfléchie sur l'analyse de problème de la conception.

I-2- Définition
Un algorithme est un ensemble de règles précises bien structurées facilement transmissible à la
machine et qui définit un procédé à suivre pour abouti un résultat fixé au départ, un algorithme

aubier à trois règles généralement :

a. C'est un ensemble d'actions précises , claires, lisible et efficace compréhensible par tous le monde.

b. L'algorithme s'applique à des données variables.

c. L'algorithme donne au moins un résultat que l'on obtient juste lorsque les données sont bien choisissent.

Parmi les caractéristiques d'un algorithme :
• Décomposition du problème posé en sous problème facile et resoulable.
• L'ordre du succession des étapes.
• Les conditions déterminant l'exécution ou nom d'une étapes.
• Un début et une fin

II- Eléments de base
On distingue entre la lecture des données, l'écriture des résultats, l'affectation et des opérations arithmétiques et logiques utilisées dans le calcule.

Les trois grandes étapes sont :

- la réparation de traitement
- le traitement
- édition des résultats

II-1- la lecture
Cette primitive permet de donnée une valeur à un objet pré déclaré, on l'exprime par le verbe lire . Exemple : lire(N).

A la suite de cette instruction, la machine attente que le utilisateur lui fournisse une valeur afin de pouvoir poursuivre l'exécution de l'algorithme.

II-2- L'affectation
Elle consiste à affecter à une variable la valeur d'une expression de même type. Nous allons représenter une affectation par le symbole <=.
Exemple : a <= 2 signifie que a reçoit la valeur 2.

II-3- l'écriture
L'écriture permet à l'utilisateur de connaître la valeur d'un identificateur,elle s'exprime par le verbe écrire. Exemple écrire (''somme ='', S) signifie l'affichage de S.

II-4-Exemple
Algorithme calcule ;
var a : ENTIER ;
var b : ENTIER ;
début
lire (a) ; // lecture
b <= 2 * a ; // affectation
écrire (b) ; // écriture
fin

III- Types élémentaires de données
Lorsque l'ordinateur exécute une opération : Calculer le prix d'un produit, rechercher le nom d'un client, ou calculer la trajectoire d'un satellite, il manipule des données de natures très diverses : nombres entiers, nombres décimaux, du texte… C'est ce qu'on désigne par le mot type.

- Un type est constitué par un ensemble de valeurs et par des opérations définies sur cet ensemble.
- Une constante est une valeur particulière prise dans l'ensemble des valeurs du type.
- Une variable est un triplet (identificateur, type, valeur). L'identificateur, son nom, permet de la désigner dans le programme; le type est fixe; la valeur peut varier tout au long de l'exécution du programme. On remarque que seul ce troisième élément du triplet est effectivement variable.

III-1-Déclarations de variables
En général, les différentes variables utilisées dans un algorithme ont des types divers. Aussi devons nous préciser le type de chaque variable utilisée. Nous écrirons pour cela :

var NOM1, NOM2, ..., NOMK : TYPE
Où NOM1, ..., NOMK sont des identificateurs de variables et où TYPE est un identificateur de type préalablement défini (ou standard).

Exemples :
var I, J, K : ENTIER
var X, Y : REEL
var C : CHAR
var NOM, PRENOM : CHAINE

Remarque :
Il est utile de prendre l'habitude de déclarer systématiquement le type de chaque variable même si cela n'est pas obligatoire dans tous les langages. En effet, cela oblige à bien préciser la nature des objets que le programme manipule. De plus, lorsqu'on aura traduit l'algorithme en un programme dans un langage L, les déclarations permettront aux compilateurs de faire des contrôles et de signaler des erreurs comme une faute de frappe entraînant la présence d'une variable non déclarée et l'erreur sera signalée.

III-2-Types standard
a. Le type entier

Le type ENTIER désigne l'ensemble des nombres entiers, sans restriction à priori. Les opérateurs du type ENTIER sont les suivants :
+ (addition)
- (soustraction)
* (multiplication)
** (élévation à une puissance entière)
/ (division entière).
En fait, sur un ordinateur donné, l'ensemble des entiers représentables est un intervalle [min, max] .

b. Le type réel
Le type REEL désigne l'ensemble des nombres réels, sans restriction à priori. Les opérateurs du type REEL sont
+ (addition)
- (soustraction)
* (multiplication)
** (élévation à une puissance entière)
/ (division entière).
En fait, il faudra néanmoins garder à l'esprit que sur tout ordinateur manipulant des valeurs réelles, deux limitations sont toujours présentes :
- Comme pour les entiers, il n'est pas question de considérer des valeurs au-delà d'un certain intervalle [min, max] ;

- Tout intervalle sur l'axe des nombres réels, si petit soit-il, contient un nombre infini de valeurs. Il n'est donc pas question de représenter complètement un intervalle réel. Alors que pour un intervalle entier [M, N] tous les entiers à l'intérieur de cet intervalle sont représentés.

c. Le type caractère
Le type CHAR désigne un ensemble de caractères convenu. Dans presque tous les langages on trouve les 26 lettres de l'alphabet latin, les 10 chiffres décimaux et un certain nombre de caractères spéciaux, qui diffèrent légèrement d'un langage à l'autre. Pour nous, le type standard CHAR en représentera l'ensemble des caractères qu'il est possible d'entrer et de sortir. Cet ensemble contient bien sur A B C ... X Y Z 0 1 2 ... 9. Il contient aussi le caractère blanc, les caractères ? ' () , . ; . = :91 < > + * / et peut-être d'autres selon les besoins du problème considéré... Cette définition extensible nous laisse toute liberté pour manipuler tout caractère spécial ayant de l'intérêt pour un problème particulier.

Nous noterons entre apostrophes les constantes de type CHAR : 'A', 'B', etc.
Remarque : ' ' avec 1 blanc entre les deux apostrophes désigne le caractère blanc, qui est un caractère comme les autres. Il n'y a pas de caractère vide et '', sans blanc intercalé désigne la chaîne de caractères vide (voir le paragraphe suivant).

d. Le type chaîne de caractères
Le type CHAINE désigne l'ensemble des chaînes de caractères qu'il est possible de former à partir des caractères du type CHAR.
Ces chaînes sont de longueur quelconque. Elles peuvent contenir des chiffres, des lettres, des blancs, des caractères spéciaux. Nous noterons entre apostrophes les constantes de type CHAINE.
Remarque1 : On peut utiliser des guillemets pour une constante CHAINE d'un seul caractère. Ainsi, après avoir déclaré>
var C : CHAR
var S : CHAINE,

Il sera possible de donner à C la valeur 'A' et de donner à S la valeur "A".

Remarque2 : La chaîne vide est une valeur particulière du type CHAINE, que l'on peut noter avec deux apostrophes : "" (sans blanc entre les deux). A ne pas confondre avec ' ', 1 blanc intercalé qui désigne le caractère blanc.

e. Le type booléen
Le type BOOLEEN désigne l'ensemble des valeurs logiques, c'est-à-dire les deux constantes FAUX et VRAI. Les opérateurs du type BOOLEEN sont les suivants :
OU (OU logique inclusif)
ET (ET logique)
NON (Négation logique).

IV- L'algorithmique structuré

Un algorithme est dit structurer s'il obéît à la règle suivante :
Il est construit à partir de trois structures fondamentales suivantes : La séquence, la sélection et la répétition.

IV-1-La séquence
Dans un algorithme les instructions sont placées les uns à la suite des autres.

Exemple :
début
var a : ENTIER ;
lire (a) ;
a <= 2 * a ;
écrire (a) ;
fin

IV-2- la sélection
Dans un programme on a souvent besoin de choisir entre plusieurs possibilités selon la valeur d'une expression logique.
Cette situation est très courante et en exprime par : si … alors … sinon
Cette expression conditionnelle est utilisée de la manière suivante :
si " Expression booléenne " alors " action1 " sinon " action2 "

Exemple :
var Moyenne : REEL
var Réussir : BOOLEEN
si (Moyenne >= 10) alors Réussir <= VRAI sinon Réussir <= FAUX

IV-3- Primitive d'itérations
La notion d'itération est une notion fondamentale de l'algorithme, on utilise souvent quand on doit exercer plusieurs fois le même traitement sur un même objet ou sur plusieurs objets de même nature. Mais son réel intérêt réside dans le faite que l'on peut modifier à chaque répétition ,les objets sur lesquels s'exerce l'action répéter.

• Boucle pour
Cette boucle utilise un compteur pour spécifier le nombre de fois que les instructions seront répétées
var I,M,N : ENTIER
pour I de M à N répéter
instructions
Exemple : Dans cet exemple on calcule la somme des nombres entiers plus petits que M.
var I,M,Total : ENTIER
lire (M)
Total <= 0
pour I de 0 à M répéter
Total <= Total + I
•
Boucle jusqu'à
Toutes les instructions écrites entre répéter et jusqu'à sont exécuté au moins une fois, et leurs exécution et répéter jusqu'à ce que la condition placer derrière jusqu'à soit satisfaite
Syntaxe :
Répéter
instructions
Jusqu'à condition
Exemple : Dans cet exemple, on calcule la moyenne des notes des étudiants d'une classe. La boucle se répète jusqu'à ce que vous entrez le nombre 0.
Répéter
lire (numEtudiant)
lire (noteMaths, notePhysique, noteLangue)
moyenne <= (noteMaths, notePhysique, noteLangue)/3
si (moyenne>10) alors Réussir <= VRAI sinon Réussir <= FAUX
écrire (numEtudiant);
Jusqu'à (numEtudiant = 0)

• Boucle tant que
Dans ce cas le programme commence par évaluer une expression booléenne ensuite, selon la valeur de cette expression, exécute ou sort de la boucle.
Syntaxe :
tant que condition
Répéter
instructions
Exemple : division de l'entier a positif ou nul par l'entier b en utilisant des soustractions successives .
Tant que r>=b faire
r<=r-b ;
q<=q+1 ;
fin tant que
écrire(q,r) ;

V- Langages de programmation
Un programme permet d'utiliser la puissance d'un ordinateur pour réaliser différentes tâches.

V-1-Différents niveaux de langage
1. Langages machines
Les premiers programmes étaient écrits en langage machine, on parlait alors de codage. Cette façon de procéder présentait au moins trois défaut :

1- Difficulté d'écrire en langage machine
2- Limite des instructions et donc incapacité à résoudre des problèmes compliqués
3- Dépendance de la machine : à chaque modèle d'ordinateur correspond un langage machine
La fin des années 50 a vu la naissance de la programmation proprement dite. Ce terme comprend non seulement l'écriture des programmes, mais aussi, et surtout, la conception des algorithmes.

2. Langages de programmation
Les langages de programmation sont des intermédiaires entre les langages naturels et les langages machines : d'une part, ils sont suffisamment proches des langages naturels pour que les programmes puissent être facilement écrits, compris et modifiés; d'autre part, ils sont définis avec rigueur, afin que les programmes puissent être traduits dans le langage machine de tel ou tel ordinateur.
Il existe plusieurs centaines de langages de programmation et chacun de ces langages est orienté vers des familles de problèmes. On dit parfois en ce sens que les langages de programmation sont orientés problèmes.

Chaque langage possède ses propres avantages et inconvénients et est plus ou moins adapté à chaque type d'application : il n'existe pas un langage meilleur que les autres dans l'absolu, il en existe de meilleurs pour un type d'application, un type d'ordinateur et un type de méthode de programmation donné.

* Pédagogiques : Pascal, Ada
* Scientifique : Fortran, Basic, Pascal, Ada, Apl
* Prototypes : Apl, SmallTalk, Eiffel
* Gestion : Cobol, SQL pour Windows
* Intelligence Artificielle : Prolog, Lisp
* Base de données : SQL, DBASE
* Développement Systèmes et Réseaux : Assembleur, C, C++, Java
* Interfaces utilisateurs : Delphi, Visuel Basic, Java
Les principales étapes de la construction d'un programme sont :
Question ==> Enoncé ==> Résolution (algorithme) ==> Mise en oeuvre (programme(s))

VI-Traduction d'un algorithme simple en pascal
VI-1- Structure d'un programme.
Nous décrivons ici la structure générale d'un programme en Pascal. La signification et l'utilisation de chaque élément seront détaillés dans les chapitres suivants.

Program NOM_DU_PROGRAMME ;
Uses { Déclaration des bibliothèques utilisées }
{ Déclarations, chacune des sections suivantes peut apparaître}
{ plusieurs fois et dans un ordre différent }
Const { Déclarations des objets constants}
Type { Déclarations de nouveaux types}
Var { Déclarations des objets variables}
Procedure {Déclaration d'une procedure}
Function {Déclaration d'une fonction}
{ Corps du programme Principal }
Begin
instruction1 ;
instruction2 ;
...;
End
VI-2-Les types de variables.
• Shortint : entier compris entre -127 et 128
• Byte : entier compris entre 0 et 255
• Integer : entier compris entre -32 768 et 32 767
• Word : entier compris entre 0 et 65535
• Longint : entier long compris entre 147 483 648 et 2 147 483 647
• Real : réel compris entre 2,9 e 10-39 et 1,7 e 1038 avec 11 décimales
• Double : réel double précision compris entre 5,0e10-324 et 1,7e10308 avec 15 décimales.
• Extended : réel compris entre 1,9e 10--4951 et 1,1e 10-4932
• Char : caractère alphanumérique
• String : chaîne de caractères.
• Boolean : valeurs logiques égales à TRUE ou FALSE
VI-3- Quelques Exemples de programmes en Pascal
1. Les entrées sorties conversationnelles.
• write et writeln.

Exemple 1 :
Program tartenpion;
begin
write('je ','ne ');
write('vais pas à la ligne');
writeln;
writeln('je ','vais ');
write('à la ligne');
end.

Dans cet exemple la fonction write permet l'affichage des résultats en restant dans la même ligne.
La fonction Writeln retourne à la ligne et affichée les résultats.
• Read et readln :

Cette fonction permet de donnée une valeur à un objet pré déclaré.
• Les tests

Syntaxe générale de l'instruction if :

Elle peut prendre une de ces deux formes :
If expression_booléenne then instruction
If expression_booléenne then instruction_1
else instruction_2

Un else se rapporte toujours au dernier then rencontré auquel un else n'a pas encor été attribué.

Exemple:
program Exemple_d_instruction_if_2 ;
var n, p, max : integer ;
begin
writeln ('donnez 2 nombres entiers') ;
readln (n, p) ;
if n < p then
begin
max := p ;
writeln ('croissant')
end;
else
begin
max := n ;
writeln ('décroissant')
end;
writeln ('le maximum est ', max)
end.
•Répétition
Syntaxe de l'instruction for :

for compteur:= début to fin do instruction
for compteur:= fin downto début do instruction

Exemple :

program utilisation_du_compteur1;
var n : integer;
begin
for n:=1 to 8 do
writeln(n,' a pour triple ',3*n)
end.
Syntaxe de l'instruction repeat ... until :

repeat
instruction_1;
instruction_2;
...
instruction_n;
until expression_booléenne

Exemple :
Program exemple_boucle_jusqu_a;
var n : integer;
begin
repeat
write('Donner un entier positif : ');
readln(n);
until n<0;
writeln('vous venez de taper un nombre négatif')
end.
Syntaxe de l'instruction while ... do :

while expression_booléenne do instruction

Exemple :
program Exemple_boucle tant_que ;
var somme : integer ;
nombre : integer
begin
somme := O ;
while somme < 100 do
begin
write ('donnez un nombre ') ;
readln (nombre) ;
somme := somme + nombre
end ;
writeln ('somme obtenue : ', somme)
end.

» LES ACTIONS ALGORITHMIQUES SIMPLES