Analyse, algorithme, programme

Le mot algorithme vient de la déformation du nom de AL-KHWARIZMI Muhamad Ibn Moussa (780-850) , astronome et mathématicien, membre de la maison de la sagesse à Bagdad qui fut le centre du monde scientifique de l'an $800$ à l'an $1200$. Il fut également l'auteur du premier traité "abrégé de calcul pour l'al-jabr et de la muqabal" . Ce mot al-jabr donna naissance au mot algèbre.

A cette époque, à Bagdad, les nombres négatifs étaient inconnus. Al-Khwarizmi utilise un algorithme à support géométrique pour déterminer la solution positive des équations du second degré lorsqu'elle se présentent sous la forme $x^2 + bx = c$ où $b > 0$ et $c > 0$
Par exemple, pour résoudre l'équation $x^2 + 10 x =39$
Il propose de tracer un carré de côté $x$ et de compléter par deux rectangles de dimensions $x$ et la moitié de $10$ (c'est-à-dire $5$) pour obtenir un grand carré}

Ce grand carré a pour aire $(x^2 + 10x ) + 5^2$ c'est-à-dire $39 + 25$ soit $64$.
Donc il a pour côté $8$ . Il suffit alors de lui retirer $5$ pour obtenir le côté $x$ cherché : $x = 3$
Analyse, Algorithme, Programme
Il ne faut pas confondre Analyse, Algorithme et Programme. Les algorithmes existent depuis l'antiquité (exemple: l'algorithme d'Euclide),alors que l'informatique existe depuis les années 1940 mais depuis une soixantaine d'années, algorithmique et programmation vont aujourd'hui de pair.

Un algorithme est une marche à suivre pour traiter des données afin d'obtenir un résultat.
Donald KNUTH qui a créé Tex et MetaFont afin de rédiger son célèbre ouvrage The Art of Computer Programming (3 tomes) en donne la définition suivante :
"Un algorithme est un ensemble de règles qui donne un résultat à partir d'une situation donnée.Chaque étape est soigneusement définie pour que sa traduction soit claire en langage informatique et réalisable par l'ordinateur."

Un programme est le codage dans un langage de programmation d'une \textbf{analyse} qui peut comporter un ou plusieurs algorithmes.
Il doit être rédigé avec des commentaires appropriés et avoir la structure formelle suivante :

Nom du programme …..;
(* partie déclarations *)
constantes
types de variables
variables
sous programmes procédures
sous programmes fonctions

début (* du programme principal *)

(* entrée des données *)
...............................

(*traitement *)
.................................

(* affichage des résultats *)
..................................
fin. (* du programme principal *)

Il faut remarquer que certaines fois, les parties traitement et affichage des résultats seront confondues car les résultats peuvent être affichés au fur et à mesure du traitement.

Une démarche de résolution
- Etape 1 : Analyser le problème
- Etape 2 : Concevoir un algorithme de résolution de ce problème
- Etape 3 : Ecriture du programme qui sera exécuté par la machine.
- Etape 4 : Tester, améliorer et maintenir ce programme
Certaines analyses sont très simples
Par exemple :
L'affichage de la surface et du périmètre d'un cercle dont l'utilisateur tape au clavier le rayon :

On sait que $P = 2* \pi * R$ et $S = \pi*R^2$ avec $\pi \approx 3.14$
Donnée d ’entrée : le rayon de type entier positif
Données de sorties :
le périmètre de type réel
la surface de type réel

Voici un algorithme de résolution en Pseudo-code :

Algorithme CERCLE;

Constante PI = 3.14

Variables RAYON de type entier

PERIMETRE,SURFACE:de type réel ;

début

(*entrée des données *)

lire au clavier un nombre et le mettre dans la case mémoire RAYON

(* traitement *)

stocker dans la case PERIMETRE le calcul suivant:
2 *contenu de la case PI * le contenu de la case RAYON;

stocker dans la case SURFACE le calcul suivant :
le contenu de PI* le carré du contenu de la case RAYON;

(*sortie des résultats *)

afficher à l'écran les contenus des cases mémoires PERIMETRE et SURFACE.

fin.

Voici une écriture de ce programme en Turbo Pascal :

Program CERCLE;

uses WinCRT;

const PI = 3.14;

var RAYON:integer;

PERIMETRE,SURFACE:real;

begin

clrscr;

(*entrée des données *)

write('Veuillez taper le rayon au clavier :');

readln(RAYON);

(* traitement *)

PERIMETRE := 2*PI*RAYON;

SURFACE := PI*RAYON*RAYON;

(*sortie des résultats *)

writeln('Le périmètre du cercle est :',PERIMETRE);

write('La surface de ce cercle est :',SURFACE);

end.
Voici une écriture de ce programme en ALGOBOX :
1 VARIABLES
2 RAYON EST_DU_TYPE NOMBRE
3 PERIMETRE EST_DU_TYPE NOMBRE
4 SURFACE EST_DU_TYPE NOMBRE
5 DEBUT_ALGORITHME
6 AFFICHER "(* Entree des donnees *)"
7 AFFICHER "Veillez saisir au clavier la valeur du rayon :"
8 LIRE RAYON
9 AFFICHER "Le rayon du cercle est : "
10 AFFICHER RAYON
11 AFFICHER "(* Traitement *)"
12 PERIMETRE PREND_LA_VALEUR 2*Math.PI*RAYON
13 SURFACE PREND_LA_VALEUR Math.PI*pow(RAYON,2)
14 AFFICHER "(* Sortie des resultats*)"
15 AFFICHER "Le perimetre du cercle est :"
16 AFFICHER PERIMETRE
17 AFFICHER "La surface du cercle est : "
18 AFFICHER SURFACE
19 FIN_ALGORITHME

Il est intéressant de faire figure dans l'algorithme et le programme sous forme de commentaires
les 3 parties :
(* entrée des données *)
(* traitement *)
(* affichage des résultats *)

Certaines fois, on sera obligé de traiter et d'afficher durant le traitement.
Alors il n' y a aura que deux parties :
* entrée des données *)
(* traitement et affichage des résultats *)

Voici une écriture de ce programme en SCILAB :

r = input("Entrez un clavier le rayon R = ")
p = %pi * 2 * r
s = %pi *r^2
disp("périmètre P = "+string(p))
disp("surface S = " +string(s))

Voici une écriture de ce programme en PYTHON :

>>> r = input(" Entrez au clavier le rayon r = ")
>>> pi =3.14
>>> p = 2 * pi * r
>>> s = pi * r * r
>>> print(p)
>>> print(s)

D'autres analyses sont plus complexes.

Il faut en tout cas :

Bien lire le texte du problème et bien définir le problème à traiter.
Bien distinguer les données en entrée : imaginer éventuellement les écrans de saisie des données
Bien distinguer les résultats attendus : imaginer éventuellement les écrans d'affichage des résultats
Trouver un traitement à effectuer sur les données en raisonnant de telle façon que le programme soit juste par construction : Aussi il faut s'efforcer de choisir une structure de données intéressante .
Ce sont les actions sur les données qui déterminent la façon de les représenter.
Attention, la bonne représentation des données n'est pas forçément celle qui mime la réalité!
Il faut décomposer le problème en des sous problèmes plus faciles à résoudre. C'est ce que l'on appelle l'analyse descendante qui suit le précepte machiavélique suivant "Diviser pour régner " .
Ceci s'inspire du Discours de la Méthode de René Descartes : " diviser chacune des difficultés que vous examinerez en autant de parcelles qu'il se pourra et qu'il sera requis pour mieux les résoudre "
- Pour cela, il faut utiliser tous les (ou une partie des ) différents types de structures de contrôle :
  - La structure séquentielle
  - Les structures alternatives (si…alors…; si … alors …sinon …;)
  - Les structures itératives
    - la boucle pour (for ... do begin ...end;)
    - la boucle tant que (while ...do begin ...end; )
    - la boucle répéter (repeat … until ... 😉
  - Les sous programmes fonctions et les sous programmes procédures.
  - Ne pas oublier d'examiner la possibilité d'une vision récursive du problème.
    - calcul de factorielle
    - calcul de la puissance $n-ième$ d'un entier
    - tours de Hanoï
    - opérations sur les files, les listes,...
  - Tester votre programme en n'oubliant pas qu'une bonne analyse doit tourner à la main
  - Voici les 10 commandements du bon programmeur :1 - En aucun cas tu ne taperas au clavier directement.
    2 - L'énoncé tu préciseras point par point très complétement.
    3 - Les programmes tu diviseras en petits blocs de traitement.
    4 - C'est l'analyse descendante que tu feras à tout moment.
    5 - La solution construiras pas à pas itérativement.
    6 - Le problème tu résoudras quelquefois récursivement.
    7 - Procédures et fonctions n'éviteras pour structure logiquement.
    8 - Les commentaires utiliseras pour informer à bon escient.
    9 - La bidouille tu proscriras pour progresser rapidement.
    10 - En cas d'erreur, tu reprendras tout ton travail patiemment
    
    Bon programmeur tu deviendras si tu suis ces commandements !!!
    MICRO-JAH