Algorithme

1 Introduction

1 Qu’est-ce qu’un algorithme ?

Définition 1 : Un algorithme est une suite d’instructions, qui une fois exécutée correctement, conduit à un résultat donné.

Pour fonctionner, un algorithme doit donc contenir uniquement des instructions compréhensibles par celui qui devra l’exécuter.

Définition 2 : Un algorithme est une suite finie d’opérations élémentaires, à appliquer dans un ordre déterminé, à des données. Sa réalisation permet de résoudre un problème donné.

La maîtrise de l’algorithmique requiert deux qualités :

il faut avoir une certaine intuition, car aucune recette ne permet de savoir à priori quelles instructions permettront d’obtenir le résultat voulu.

il faut être méthodique et rigoureux. En effet, chaque fois qu’on écrit une série

d’instructions qu’on croit justes, il faut systématiquement se mettre à la place de la machine qui va les exécuter, pour vérifier si le résultat obtenu est bien celui que l’on voulait.

 Remarques :

1. Un algorithme doit être lisible de tous. Son intérêt, c’est d’être codé dans un langage informatique afin qu’une machine (ordinateur, calculatrice, etc.) puisse l’exécuter rapidement et efficacement.

2. Les trois phases d’un algorithme sont, dans l’ordre :

(a) l’entrée des données

(b) le traitement des données

(c) la sortie des résultats

3.Les ordinateurs, quels qu’ils soient, sont fondamentalement capables de comprendre quatre catégories d’ordres seulement (en programmation, on n’emploiera pas le terme d’ordre, mais plutôt celui d’instructions). Ces quatre familles d’instructions sont

l’affectation de variables   "Déclaration de variable"

la lecture / écriture

les tests

les boucles

Un algorithme exprime les instructions résolvant un problème donné indépendamment des particularités de tel ou tel langage de programmation.

Apprendre un algorithme, c’est apprendre àmanier la structure logique d’un programme informatique.

« Un langage de programmation est une convention pour donner des ordres à un

ordinateur.» (Pascal, Fortran, C++, PHP, Mathematica etc.)

2 Conventions pour écrire un algorithme

Historiquement, plusieurs types de notations ont représenté des algorithmes.

Il y a eu notamment une représentation graphique, avec des carrés, des losanges, etc. qu’on appelait des organigrammes. Cependant dès que l’algorithme commence à grossir un peu, ce n’est plus pratique.

On utilise généralement une série de conventions appelée « pseudo-code », qui

ressemble à un langage de programmation authentique dont on aurait évacuén la plupart des problèmes de syntaxe. Ce pseudo-code est susceptible de varier légèrement d’un livre (ou d’un enseignant) à un autre. C’est bien normal : le pseudo-code, encore une fois, est purement conventionnel ; aucune machine n’est censée le reconnaître.

I Les variables

1 Définition

Définition : Dès que l’on a besoin de stocker une information au cours d’un programme, on utilise une variable.

Pour employer une image, une variable est une boîte, que le programme (l’ordinateur) va repérer par une étiquette. Pour avoir accès au contenu de la boîte, il suffit de la désigner par son étiquette.

2 Déclaration des variables

La première chose à faire avant de pouvoir utiliser une variable est de créer la boîte et de lui coller une étiquette. C’est ce qu’on appelle la déclaration des variables.

Le nom de la variable (l’étiquette de la boîte) obéit à des impératifs changeant selon les langages. Toutefois, une règle absolue est qu’un nom de variable peut comporter des lettres et des chiffres, mais qu’il exclut la plupart des signes de ponctuation, en particulier les espaces. Un nom de variable correct commence également impérativement par une lettre. Quant au nombre maximal de signes

pour un nom de variable, il dépend du langage utilisé.

Une fois le nom choisi, il faut déterminer le type de la variable.On peut distinguer

3 types de variable (il y en a d’autres !) :

Type alphanumérique : du texte.

Type numérique : un nombre (entier, décimal, réel).

Type liste : ensemble de nombres ordonné.

Déclarer nouvelle variable (instruction AlgoBox)

Variables

n1, taux, x22 : nombre ; 3 variables de type nombre

prenom, nom : chaîne ; 2 variables de type chaîne de caractères

tab : liste ; 1 variable de type liste (tableau à une seule ligne)

Remarque : Chaque ligne se termine par un point-virgule.

Les variables d'un même type sont séparées par des virgules.

Le nom d'une variable commence par une lettre et ne contient ni espace, ni caractère accentué.

II – Le corps de l'algorithme : instructions basiques

Lecture et écriture d’une variable

Définition : Lire ou Entrer une variable signifie que l’utilisateur doit rentrer une valeur pour que le programme la lise.

Ecrire ou Afficher une variable signifie que le programme renvoie la valeur de la variable que le programme a trouvée.

1 – Lire une variable

Exemple: Ajouter LIRE variable (instruction AlgoBox)

...

Lire nom ; affiche une boîte de dialogue invitant l'utilisateur à taper la valeur de la variable nom.

Lire age ; affiche une boîte de dialogue invitant l'utilisateur à taper la valeur de la variable age.

...

Exemple: Ajouter LIRE variable (instruction AlgoBox)

Variables

age : nombre ;

nom : chaîne ;

Debut

Lire nom ; affiche une boîte de dialogue invitant l'utilisateur à taper la valeur de la variable nom.

Lire age ; affiche une boîte de dialogue invitant l'utilisateur à taper la valeur de la variable age.

Fin

Ecriture Cette  opération  permet de visualiser les informations placées en mémoire.

Lecture est une instruction qui permet de placer en mémoire les informations fournies par l'utilisateur.

2 Affectation d’une variable numérique

La seule chose qu’on puisse faire avec une variable, c’est l’affecter, c’est-à-dire lui attribuer une valeur.

On peut aussi affecter une variable à l’aide d’une opération :

On peut changer la valeur d’une variable avec elle-même :

2 – Affectation d'une valeur à une variable

Exemple: AFFECTER valeur à variable (instruction AlgoBox)

...

somme ← a + b ; L'algorithme affecte la valeur a + b à la variable somme

...

Exemple: AFFECTER valeur à variable (instruction AlgoBox)

Variables

a, b, somme : nombre ;

Debut

Lire a ;

Lire b ;

somme ← a + b ; L'algorithme affecte la valeur a + b à la variable somme

Fin

3 – Afficher à l'écran la valeur d'une variable

Exemple: Ajouter AFFICHER variable (instruction AlgoBox)

...

Afficher somme ; L'algorithme affiche à l'écran le contenu de la variable somme

...

Exemple: Ajouter AFFICHER variable (instruction AlgoBox)

Variables

a, b, somme : nombre ;

Debut

Lire a ;

Lire b ;

somme ← a + b ;

Afficher somme ; L'algorithme affiche à l'écran le contenu de la variable somme

Fin

4 – Afficher une chaîne de caractères

Exemple: Ajouter AFFICHER Message (instruction AlgoBox)

...

Afficher "La somme est : " ; L'algorithme affiche à l'écran la chaîne de caractères La somme est :

...

Exemple: Ajouter AFFICHER Message (instruction AlgoBox)

Variables

a, b, somme : nombre ;

Debut

Lire a ;

Lire b ;

somme ← a + b ;

Afficher"La somme est : " ; L'algorithme affiche à l'écran la chaîne de caractères La somme est :

Afficher somme ;

Fin

5 – Afficher un commentaire

Exemple: Commentaire (instruction AlgoBox)

...

// Voici un programme qui ne sert à rien !

...

 Exemple: Commentaire (instruction AlgoBox)

Variables

nom : chaîne ;

Debut

// Voici un programme qui ne sert à rien !

Lire nom ;

Fin

Remarque : :

En informatique une variable ne peut prendre à un moment donné qu’une valeur et une seule, contrairement à une équation qui peut éventuellement avoir plusieurs solutions.

Souvent l’affectation d’une variable se note : B = A ou B := A qui veut dire que B prend la valeur A, qui est alors différent de A = B ou A := B où A prend la valeur de B.

III Les tests

Il y a deux formes pour un test : soit la forme complète, soit la forme simplifiée :

La condition portant sur une variable peut être :

Une valeur à atteindre.

Une comparaison avec une autre variable (égalité, inégalité, non égalité).

 On peut aussi mettre un test qui se décompose en plusieurs conditions reliées par un opérateur logique :

condition 1 ET condition 2 : les deux conditions doivent être vérifiées en même temps.

condition 1 OU condition 2 : au moins l’une des deux conditions doit être vérifiée.

On peut aussi imbriquer un ou plusieurs autres tests à l’intérieur d’un test. On a alors le schéma suivant :

 Si condition 1 alors

Instructions 1

Sinon           Si condition 2 alors

 Instructions 2

Sinon

 Instructions 3

FinSi

FinSi

Si … Alors …Sinon

Les opérateurs de comparaison sont  =, ≠ ,< ,> , ≤ , ≥ .

En langage Algobox, les opérateurs de comparaison s'écrivent ==, !=, <, >, <=, >=.

La condition peut comporter plusieurs tests.

Les opérateurs logiques reliant ces tests sont ET , OU , NON.

 ( condition1 ) ET ( condition2 ) vraie, signifie que condition1 est vraie et que condition2 est vraie.

 ( condition1 ) OU ( condition2 ) vraie, signifie que condition1 est vraie ou que condition2 est vraie ou que les 2 conditions sont vraies.

 NON ( condition1 ) vraie, signifie que condition1 est fausse.

IV Les boucles

1 Définition

Définition 8 : Une boucle est une structure répétitive ou itérative, c’est à dire que la boucle effectue n fois un calcul sous le contrôle d’une condition d’arrêt.

2 La boucle conditionnelle

La boucle conditionnelle obéit au schéma suivant :

 Avec ce type de boucle, on répète l'exécution d'un bloc d'instruction tant qu'une condition préalablement définie est satisfaite. Le test s'effectue en début de boucle, à chaque passage. Dans ce cas, l’expression utilisée est :

   Dans le cas où la condition est toujours vérifiée, l’ordinateur tourne alors dans la boucle et n’en sort plus.
La « boucle infinie » est l’une des hantises les plus redoutées des programmeurs.

Cette faute de programmation est courante chez tout apprenti programmeur.

Exemple :

3 Boucler en comptant

Si l’on connaît à l’avance le nombre d’incrémentation (+1) ou décrémenté (–1) selon le cas, on a alors la structure suivante

:

4  Boucles itératives

Définition : Lorsque l’on doit répéter un nombre de fois connu à l’avance la même tâche, on utilise une boucle itérative de la forme « Pour.. allant de... à ».

Dans un algorithme, cette structure est codée de la façon suivante :

Pour variable allant de valeur_depart à valeur_fin faire

tâche 1

tâche 2

...

Fin pour

La variable utilisée dans la boucle est appelée compteur. À chaque passage dans la boucle, sa valeur est automatiquement augmentée de 1.

un algorithme ne dépend pas

-du langagedans lequel il est implanté,
-ni de la machinequi exécutera le programme correspondant.

.Algorithme en français

↓

Codage dans un langage de programmation

↓

Traduction automatique en langage machine (compilation)

↓

Exécution

Les problèmes fondamentaux en algorithmique

Complexité

-En combien de temps un algorithme va -t-il atteindre le résultat escompté?

-De quel espace a-t-il besoin?

Calculabilité:

-Existe-t-il des tâches pour lesquelles il n'existe aucun algorithme ?

-Etantdonnée une tâche, peut-on dire s'il existe un algorithme qui la résolve ?

Correction

-Peut-on être sûr qu'un algorithme réponde au problème pour lequel il a été conçu?