1. Algorithme et programme

Introduction

Objectif : résolution de problèmes sur l'ordinateur

=> traitement automatique de l'information

Ordinateur : c'est une simple machine qui a des contraintes matérielles et des limitations (capacité, mémoire, calcul...). De plus, celle-ci ne fait que ce que l'on dit de faire.

Programme : c'est un moyen de communication enter une machine et une personne (le programmeur)

Problème à résoudre ======> algorithme ======> programme
                   (analyse)

Algorithme indépendant du langage.

Problème à résoudre en langage naturel (spécification, cahier des charges)

L'analyse du problème permet de passer à l'algorithme.

Programmer, c'est traduire l'algorithme dans un langage compréhensible par l'ordinateur (C, Lisp, Fortran, Pascal par exemple)

données ===> algorithme ===> résultats

Analyse : c'est une suite d'étapes qui conduisent à l'algorithme.

La première étape primordiale est de définir les informations à traiter, les données (glossaire).

L'analyse descendante consiste à décomposer le problème en sous-problèmes plus faciles à résoudre ... jusqu'à obtenir des instructions de base. "diviser pour régner"

La dernière étape est la validation de l'algorithme : les jeux de test.

Ordinateur

• organes d'entrées : clavier, mulot, supports magnétiques ou optiques , tablette graphique
• organes de sortie : écran, imprimantes, supports magnétiques ou optiques
• unité centrale
  • processeur : rangement des données et du programme
  • mémoire centrale : exécute les instructions

supports magnétiques : disque dur, disquette (normale, cochonnerie de ZIP...),
supports optiques : CD, DVD
supports électroniques : clé USB

Ach, petit dessin

Traitement de l'information = 5 fonctions essentielles

• introduction
• restitution
• traitement (calcul)
• mémorisation
• commande (assure la mise en oeuvre des 4 autres dans un ordre déterminé par le prgm.)

Un algorithme, c'est

• est une suite ordonnée d'instructions
• est séquentiel (1 instruction à la fois)
• doit s'arrêter (nombre fini d'opérations)
• déterministe (réponse non aléatoire) : A entrées équivalentes, résultats identiques.

Remarque : il n'y a pas forcément qu'un seul algorithme pour un problème donné. En général, on peut les classer suivant différents critères (performance, occupation mémoire, lisbilité, extensibilité ...)

Langage algorithmique

• algorithme de principe en langage naturel
• algorithme
  • langage algorithmique : plus précis, plus simple que le langage naturel
  • organigramme (représentation graphique)

Le langage algorithmique est souvent plus lisible que le les languages de programmation (en tout cas, il est indépendant de ceux-ci)

Exemple : calcul de a * b

Ach, soyons un peu plus illustratif

2. Formulation de l'algorithme

Affectation (mémorisation)

La mémoire centrale peut être vue comme un ensemble d'emplacements, de cases, de mots. Une case mémoire qui dispose d'un nom permettant de l'identifier est appelée une variable. Une variable est un contenant. Sa valeur le contenu.

L'affectation est une opération élémentaire qui permet de ranger une valeur dans une variable. On la note := ou <-.

Exemple : X := 4

La variable X conservera la valeur 4 jusqu'à ce qu'une nouvelle instruction lui affecte une nouvelle valeur.

Le terme de gauche d'une affectation est toujours un nom de variable. Le terme de droite peut être une constante (valeur immédiate), une autre variable ou une expression.

On peut très bien envisager différents types de variables : entières, réelles, booléennes ... (type)

Ach, expression arithmétique, et expression booléenne.

EXERCICE 1 : échange de deux variables

EXERCICE 2 : permutation circulaire de trois variables.

La définition d'une variable permet d'écrire des choses comme i := i + 1.

Lecture/Ecriture

(introduction/restitution, mémorisation)

 lire(A); signifie qu'il faut mettre dans la case(variable) A la valeur présente sur un périphérique d'entrée de la machine à préciser => saisie des données

 écrire(A); signifie placer sur un organe de sortie de la machine à préciser le contenu de la variable A.

Ne pas oublier les pictogrammes

La machine lit sur l'organe d'entrée et écrit sur un organe de sortie. L'utilisateur fait l'inverse.

L'algorithme conditionnel

orientation du traitement en fonction des données.

SI condition ALORS traitement 1
             SINON traitement 2
FSI;

SI condition ALORS traitement FSI;

La condition peut être

• une expression logique : =, différent, <, inférieur ou égal, >, supérieur ou égal, ET, OU , NON, ...
• une variable booléenne : vrai ou faux, du doux nom de George (1815-1864)

EXERCICE : écrire l'algo qui donne la plus grande valeur de deux valeurs saisies au clavier. Si la méthode choisie fait intervenir plusiseurs commandes "afficher", donner une verison qui ne laisse qu'une occurence.

EXERCICE : écrire l'algo qui affiche a l'écran la comparaison de deux variables A et B avec les messages suivants : A < B, B< A ou A=B

NOTE 1 : expliquer différence SI SINON SI et plusieurs SI a la suite.

NOTE 1 : c'est quoi le sinon de SI a=0 ET b=0

EXERCICE : appartenance d'un nombre à un intervalle

SELON expression =
   valeur 1 : action 1;
   valeur 2 : action 2;
   valeur 3 : action 3;
   défaut   : action 4;
FSELON;

EXERCICE : comparer 3 nombre et renvoyer le plus grand A, B, C ---> R

LIRE (A, B, C);

SI (A>=B) ALORS R=A SINON R=B FSI;
SI (R<=C) ALORS R=C FSI;

EXERCICE : solution de l'équation A X ² + B X + C = 0

SI (A=0) ALORS 
   SI (B=0) ALORS
      SI (C=0) ALORS ECRIT (IR est solution);
      SINON ECRIRE (pas de sol)
      FSI;
   SINON
      ECRIRE ( 1 solution = -C/B);
   FSI;
SINON
   D = B*B - 4 A*C;
   SI (D>=0) ALORS
      SI (D=0) ALORS ECRIRE ( 1 solution = -B/(2A) );
      SINON ECRIRE ( 2 solutions ...);
      FSI;
   SINON ECRIRE (solutions complexes);
   FSI;
FSI;

L'itération

répétition d'un traitement sur un ou plusieurs objets de même nature. L'arrêt du traitment est réalisé par une condition.

Insistons bien sur les différentes phases : initialisation, test, incrémentation, boucle

Algorithme à récurrence fixe : POUR

Pour un algorithme à récurrence fixe, le nombre de répétitions est connu d'avance.

EXEMPLE : calcul de Y = sum(Ai) pour i de 1 à N , N fixe

LIRE (N);
Y := 0;

POUR I:=1 JUSQU'A N PAS 1 FAIRE
   LIRE (A);
   Y := Y + A; 
FAIT/FINPOUR; 

ECRIRE (Y);

Ach deux organigrammes

EXERCICE : calcul de n!

Algorithme à récurrence variable : TANT QUE

Le nombre de récurrneces non fixé à l'avance est déterminé dans le processus de traitement.

Deux formes : TANT QUE et REPETER

TANT QUE condition
   traitement
FAIT/FTANTQUE;

REPETER
   traitement
JUSQU'A condition FAIT;

ATTENTION : il faut être sûr que l'algo se termine quelles que soient les entrées.

EXERCICE : saisie de deux nombres positif au clavier.

EXERCICE : écire le POUR avec un TANT QUE

EXERCICE : division de l'entier a positif par l'entier b strictement positif en supposant que l'on ne connaît que l'addition et la soustraction.

Trouver q et r positifs tels que a = b q + r avec r < b :

LIRE (A,B);
Q := 0;
R := A;

TANT QUE (R>=B) FAIRE
   Q := Q +1;
   R := R - B;
FAIT; 

ECRIRE (Q,R);

EXERCICE : Résolution de l'équation x=f(x) par approximations successives

Partant de x₀ quelconque, on calcule successivement x₁,..,x_n jusqu'à ce que | x_i - x_i-1| < EPSILON.
La convergence est vérifiée si la norme infinie de la dérivée est strictement plus petite que 1.

LIRE (X1,E,MAX);
I := 0;

REPETER
   X0 := X1;
   X1 := f(X0);
JUSQU'A ((abs(X1-X0)<E) OU (I>MAX)) FAIT; 

ECRIRE (X0);

Attention ici à l'indice de boucle. Il se justifie par le fait qu'il peut être difficile de vérifier que la fonction f a la bonne propriété ou alors que l'algo "diverge" avec les erreurs dues à la précision machine.