Part 1 : Introduction à l’algorithmique

Chapitre 1

Introduction à l’algorithmique

1.1. Démarche pour la résolution d’un problème

Pour résoudre un problème, en informatique, plusieurs étapes sont

nécessaires :
1. Environnement : la connaissance précise de l’environnement
(machine utilisée, processeur,...)
2. Problème : la définition précise du problème.
3. Analyse : l’analyse du problème et sa décomposition en sous-problèmes
simples et distinctes.
4. Algorithme : la formulation de la solution sous une forme textuelle.
Description des opérations { mettre en œuvre expliquant comment
obtenir un résultat à partir de données. Il s'agit d'une description
compréhensible par un être humain de la suite des opérations à effectuer
pour résoudre le problème.

1.2. De l’algorithmique à la programmation

Pour automatiser la résolution d’un problème, nous devons traduire un

algorithme en un programme. En effet, un programme ce n’est que la traduction
d’un algorithme dans un langage de programmation compréhensible par la
machine utilisée. Ainsi, pour obtenir un programme exécutable, nous devons
passer par les étapes suivantes :

-1-
 Part 1 : Introduction à l’algorithmique

ANALYSE CODIFICATION
Problème Algorithme Programme

COMPILATION

INCORRECTS

EXECUTION
Résultats Exécutable

CORRECTS

Fin

Figure 1.1-Démarche de résolution d’un problème

1.3. Définition d’un Algorithme

Un algorithme peut être définit comme suit :

« Un algorithme est une suite finie d'opérations ou règles à appliquer dans un
ordre déterminé, à un nombre fini de données, pour arriver à en un nombre fini
d'étapes, à un certain résultat et cela indépendamment des données (La Page de
l'algorithmique, 2008)».
A noter que le mot algorithme vient du nom du mathématicien arabe El
Khawarizmi, originaire de la ville de Khawarizmi (La Page de l'algorithmique,
2008)

1.4. Exemple

Pour déterminer le PGCD (Plus Grand Commun Diviseur) de deux entiers

naturels a et b nous suivons la démarche suivante :
 Début
 Données de a et b
 si (a,b) premiers entre eux alors pgcd(a,b) = 1
 sinon
 décomposer a en facteurs premiers
 décomposer b en facteurs premiers

-2-
 Part 1 : Introduction à l’algorithmique

 pgcd(a,b) = produit des facteurs premiers communs à a et

b, avec les exposants les moins forts.
 Fin

A partir de cette démarche, nous pourrons donner la structure générale d’un

algorithme et nous détaillerons dans le chapitre suivant ses différents composants.

1.5. Structure d’un algorithme

Pour construire un algorithme, nous devons mettre en évidence les 3 parties

suivantes :

Algorithme Nom_algorithme
Nom de l’algorithme

Déclarations de types
Déclarations Déclarations de variables
Déclarations de constantes
Début
Corps de l’algorithme Bloc d’instructions
Fin
Figure 1.2- Les trois parties Figure 1.3- Structured’un
d’un algorithme algorithme

Où :
 Nom de l’Algorithme : c’est l’identification ou le nom.
 Déclarations : description de tous les objets utilisés dans
l'algorithme, définition de variables, de constantes et de types.
 Instructions: séquence d'actions à exécuter sur l'environnement afin
de résoudre le problème. Cette partie est également appelée le
corps de l’algorithme.

1.6. Conclusion

Nous venons d’introduire la notion d’algorithme et les différentes étapes pour

l’obtention d’un programme exécutable. Pour tout algorithme, nous devons
définir une structure de données adéquate pour utiliser les objets traités qui
seront détaillés dans le chapitre suivant.

-3-
 Part 2 : Introduction aux Structures de Données

Part 2

Introduction aux Structures de Données

2.1. Introduction

Un ordinateur manipule des objets. Chaque objet a besoin de trois qualificatifs

pour sa définition.

Type Objet Identificateur

valeur

Figure 2.1- Les trois qualificatifs d’un objet

Un objet est caractérisé par son nom (identificateur), sa valeur, son type (figure
2.1). La valeur de l’objet peut être constante ou variable. Le type de l’objet peut
être simple ou composite. Un type simple comme : entier, réel, caractère, etc. Un
type composite peut être : tableau, enregistrement, etc. Toutes ces nouvelles
notions seront détaillées dans les sections suivantes.

2.2. Constante et variable

Une constante est un objet dont la valeur ne varie pas tout au long du
programme. Un objet dont la valeur change est nommé variable.

2.3. Identificateur

Un identificateur est dénomination d’un objet qui doit respecter les règles
suivantes :
Un identificateur est soit :

-4-
 Part 2 : Introduction aux Structures de Données

Une suite alphanumérique qui ne doit pas commencer par un chiffre. En

algorithmique et en programmation le symbole '_' est aussi considéré comme une
lettre.

2.4. Type

Un type de donnée définit un ensemble dans lequel les variables prennent leur
valeur. Chacune des variables d’un algorithme doit être associée { un type de
donnée et un seul. A chaque type de donnée est associé un ensemble d’opérateurs
qui sont possibles sur les variables et les constantes de ce type. Il y a cinq types
élémentaires standards :
 Entier
 Réel
 Booléen
 Caractère
 Chaîne de caractère

2.4.1. Le type entier

Une variable de type entier prend ses valeurs dans l’ensemble des nombres
entiers. Les opérateurs qui sont appliqués à des entiers, donnent un résultat entier
sont :
 Addition (+)
 Soustraction (-)
 Multiplication (*)
 Division entière (DIV)
 Reste de la division entière (MOD).

2.4.2. Le type réel

Une variable de type réel fait partie des nombres réels.

2.4.2.1. Les opérateurs réels

Le résultat des opérateurs suivants est réel, si au moins l’un des opérandes est
réel (l’autre pouvant être entier) :
 Addition (x+y)
 Soustraction (x-y)
 Multiplication (x*y)
 Division (x/y)
-5-
 Part 2 : Introduction aux Structures de Données

2.4.2.2. Les fonctions sur les réels

Les fonctions suivantes donnent un résultat réel, pour un argument entier ou

réel :
sin(x), cos(x), exp(x), ln(x), sqrt(x), arctan(x), etc.

L’argument des fonctions suivantes est réel, et le résultat est entier :

 trunc(x) : partie entière de x,

 round(x) : entier le plus proche de x.

2.4.3. Le type booléen

Une variable booléenne ou de type logique doit prendre pour valeurs la

constante TRUE (pour VRAI) ou la constante FALSE (pour FAUX). Ces valeurs
pouvant être obtenues par l’évaluation d’une expression logique.
2.4.3.1. Les opérateurs booléens

Les opérateurs booléens (ou logiques) sont :

 Non (NOT: Négation)
 ET (AND logique)
 OU (OR logique)
a NOT(a)

FAUX VRAI
VRAI FAUX

Tableau 2.1 – Table de vérité de l’opérateur NOT

a b a OR b a AND b

FAUX FAUX FAUX FAUX

FAUX VRAI VRAI FAUX
VRAI FAUX VRAI FAUX
VRAI VRAI VRAI VRAI

Tableau 2.2 – Table de vérité de l’opérateur OR et de l’opérateur AND

2.4.3.2. Propriétés des opérateurs logiques

Quelques propriétés des opérateurs logiques sont importantes, notons les plus
utilisées :
 a ET (b OU c) = (a ET b) OU (a ET c)
 a OU (b ET c) = (a OU b) ET (a OU c)

-6-
 Part 2 : Introduction aux Structures de Données

 NON(a ET b) = NON(a) OU NON(b)

 NON(a OU b) = NON(a) ET NON(b)
2.4.3.3. Les opérateurs de comparaison

Une expression logique contient un ou plusieurs opérateurs comparaison et/ou

un ou plusieurs opérateurs logiques. Les opérateurs relationnels sont :
 = : égal à
 <> : différent de
 < : inférieur à
 > : supérieur à
 <= : inférieur ou égal à
 >= : supérieur ou égal à
La priorité des opérateurs logiques est : NON– ET – OU, cet ordre peut être
modifié par l’utilisation de parenthèses.

2.4.4. Le type caractère

Le type caractère peut être : des lettres minuscules, des lettres majuscules, des
chiffres et des signes spéciaux. En règle générale, cet ensemble correspond à celui
des caractères qui sont représentés sur le clavier d’un ordinateur.
Un caractère est représenté sur 8 bits, ce qui donne 256 combinaisons possibles.
Le code, couramment utilisé, est le code ASCII (American Standard Code for
Information Interchange).

Les opérateurs de comparaison définis précédemment s’appliquent également

sur les caractères avec les conventions :

 ‘A’ < ‘B’ < … < ‘Z’

 ‘0’ < ‘1’ < ... < ‘9’
Les fonctions suivantes sont utiles pour les opérations sur les caractères :
 SUCC : pour successeur
 PRED : pour prédécesseur
 ORD : pour rang
 CHR : la fonction CHR n’admet pour paramètre qu’un nombre entier.
Elle fournit comme résultat le caractère dont le numéro d’ordre est
spécifié comme paramètre.
Les fonctions CHR et ORD sont des fonctions inverses.

Exemples :

-7-
 Part 2 : Introduction aux Structures de Données

 ORD(‘A’) = 65
 CHR(65) = ‘A’
 SUCC(‘X’) = ‘Y’
 PRED("G") = ‘F’

2.4.5. Le type chaîne de caractères

Le type chaîne de caractères est l’ensemble des séquences de caractères que

l’on peut former. Une chaîne vide est une chaîne qui ne contient aucun caractère.
Une chaîne peut contenir au maximum 256 caractères.

2.5. Les expressions

La formation des expressions est définie par récurrence : Les constantes et les
variables sont des expressions. Les expressions peuvent être combinées entre elles
par des opérateurs et former ainsi des expressions plus complexes (FABER, 2009)
Une expression arithmétique a pour valeur un nombre entier ou réel. Une
expression booléenne a pour valeur le type de données booléen.
Pour composer un algorithme, nous aurons souvent à exprimer des expressions
qui seront par la suite évalués au moment de l'exécution. Pour écrire une
expression, nous écrirons très souvent une comparaison entre deux valeurs de
même type. Une telle comparaison est appelée expression booléenne simple.
Lorsque l’expression simple ne suffit pas pour exprimer une situation, nous
utilisons des expressions composées à partir de d’expressions simples par
l'emploi d’opérateurs logiques.

Exemples :

Si X et Y sont deux variables numériques de valeurs respectives 5 et 10, nous

aurons :
Expression valeur
booléenne

x=y Faux

x<y Vrai

x>2 Vrai

Tableau 2.3 – Exemple d’évaluation d’expressions booléennes

Evaluez les deux expressions suivantes lorsque x, y et z ont pour valeurs

respectives 1, 3 et 2 :
 (x = 1 OU y = 2) ET z > 3
 x = 1 OU (y = 2 ET z > 3)

-8-
 Part 2 : Introduction aux Structures de Données

Il est parfois nécessaire d'utiliser des parenthèses dans l'expression d'une

expression composée. Les expressions entre parenthèses sont alors évaluées en
premier.

2.6. Hiérarchie entre les opérateurs

Nous présentons dans le tableau ci-dessous la hiérarchie entre les différents

opérateurs. En effet, c'est la priorité d'évaluation dans l'ordre décroissant (du plus
prioritaire au moins prioritaire) :
Opérateur Intitulé

() les parenthèses
NON la négation
/, * la multiplication et la division
+, - l'addition et la soustraction
,>,<,<=,>=,< les opérateurs relationnels
>
ET ET logique
OU OU logique

Tableau 2.4 – Hiérarchie entre les opérateurs

Dans l'évaluation d'une expression sans parenthèses, les opérations sont

effectuées par ordre de priorité. Les opérations de même priorité sont effectuées
de la gauche vers la droite. Ainsi, pour effectuer B + C/D – E*F, nous calculons
d'abord C/D puis E*F. Nous pouvons évidemment modifier les priorités en utilisant
des parenthèses. Dans l'expression B + C/(D-E), nous calculerons d'abord D-E.

-9-
 Part 3 : Instructions élémentaires et structure d’un algorithme

Part 3

Instructions élémentaires et structure d’un

algorithme

3.1. Structure d’un algorithme

Comme nous l’avons mentionné dans le chapitre 1, un algorithme est composé

de trois parties :
Le nom de l’algorithme, la partie déclarative et le corps de l’algorithme. Dans
ce qui suit, nous détaillons ces différentes composantes.

3.2. Déclaration de variables

 a, b, c : entier : ⇔ a : entier
B:
entier C
: entier
 x, y, z : réel
 n, v : booléen
 mot : chaîne de caractère
 c : caractère

3.3. Déclaration de constantes

 Pi = 3,14159
 ch. = 'calcul'
 C = 'R'
 test = TRUE
Dans la partie déclarative de l'algorithme, nous devons énumérer :
1. La liste des variables, tout en précisant leurs types respectifs.
2. La liste des constantes, en leur affectant leurs valeurs.
3. Les types qui ne sont pas standards.

-
10-
 Part 3 : Instructions élémentaires et structure d’un algorithme

3.4. L’affectation

Dans un environnement donné, pour affecter (attribuer) à une variable (V) une
valeur (e), nous utilisons la notation suivante : V  e
Où :
 V : le nom de la variable à laquelle on doit attribuer la valeur,
  : symbole, caractérisant l'affectation,
 e : représente la valeur à affecter et peut être :
- Une constante.
- Le nom d'une autre variable qui contient la valeur.
- Une expression de même type que V qui peut être une
expression logique ou une expression arithmétique.

Exemples :

a) X  1
b) NOM  "Mohamed"
c) TOTAL  SOMME
d) NB A+B
 L'action (a) affecte à la variable numérique X la valeur 1.
 L'action (b) affecte à la variable nom la chaîne "Mohamed"; pour
que cette action soit correcte, il faut que NOM soit de type
chaîne de caractères.
 dans ces 2 premières affectations, la valeur à affecter est indiquée à
l'aide d'une constante.
 dans (c), la valeur à affecter est une variable. TOTAL et SOMME
doivent être de même type.
 Dans (d), nous affectons à NB, le résultat d'un calcul numérique.
NB, A et B doivent être de même type. L'action (d) s'exécute en
deux temps :
- calcul de la valeur de l'expression arithmétique (A+B)
- affectation de cette valeur à la variable NB.
Dans une affectation, seule la variable dont le nom apparaît à gauche du signe 
change de valeur.

3.5. Fonctions d’entrées/sorties

La fonction d’entrée lire() permet d'affecter, à une variable, une valeur saisie au
clavier. Cette fonction est validée par la frappe de la touche (entrée).
lire(v) : saisit une valeur au clavier et la mettre dans la variable v.
-
11-
 Part 3 : Instructions élémentaires et structure d’un algorithme

La fonction de sortie ecrire() permet d’afficher la valeur d’une constante,

d’une variable ou d’une expression.

Exemples :

 ecrire ('Calcul de la somme des n premiers entiers')

 ecrire (i)
 ecrire ('Résultat du calcul = ', S+i)

3.6. Les commentaires

Pour qu’un algorithme ou un programme soit clair et compréhensible, il est

conseillé de le commenter. Les commentaires sont des textes rédigés lors de
l’élaboration de l’algorithme (ou programme). Le commentaire est ignoré par le
processeur lors de l'exécution du programme. Généralement ce texte est inséré
entre { et } ou bien (* et *) ou encore entre /* et*/.

3.7. Les instructions

Le corps d'un algorithme se compose d'instructions. Nous distinguons les

instructions simples (une seule action) et les instructions composées (un bloc
contenant des séquences d'instructions et comptant pour une seule instruction).

3.8. Exemple d’algorithme

Ecrire un algorithme intitulé « calculs » permettant de saisir trois réels

quelconques, de calculer ensuite leur somme, leur produit et leur moyenne et
d’afficher les résultats obtenus.
Méthode (ou analyse) : nous distinguerons trois étapes :
1. Obtention des trois nombres : il nous faudra trois objets de type réel pour
recevoir ces nombres.
2. Calcul des différents résultats : il nous faudra déclarer trois objets de type
réel qui reçoivent le résultat de chacune des opérations : somme, produit et
moyenne.
3. affichage des résultats.

-
12-
 Part 3 : Instructions élémentaires et structure d’un algorithme

Solution :

Algorithme calculs
Variable
Somme, Produit, Moyenne, nb1, nb2, nb3 : réel
Débu
t (* saisie des trois nombres *)
ecrire ("entrez les trois nombres")
lire (nb1, nb2, nb3)
(* réalisation des différentes opérations *)
Somme  nb1 + nb2 + nb3
Produit  nb1 * nb2 * nb3
Moyenne  somme / 3
(* édition des résultats *)
ecrire ("la somme des trois nombres est : ", Somme)
ecrire ("le produit des trois nombres est : ", Produit)
ecrire ("la moyenne des trois nombres est : ", Moyenne)

Fin

-
13-
 Part 3 : Instructions élémentaires et structure d’un algorithme

Remarque :

Nous pouvons afficher directement le résultat des opérations sans passer par
les variables Somme, Produit et Moyenne. Ce qui donne une seconde version de
l’algorithme (calculs_v2) plus compacte et plus optimisée :
Algorithme calculs_v2
Variable
nb1, nb2, nb3 : réel

Début

(* saisie des trois nombres *) ecrire

("entrez les trois nombres") lire
(nb1, nb2, nb3)
(* réalisation des différentes opérations et édition des résultats *)
ecrire ("la somme des trois nombres est : ", nb1+nb2+nb3)
ecrire ("le produit des trois nombres est : ", nb1 * nb2 * nb3)
ecrire ("la moyenne des trois nombres est : ", (nb1 + nb2 + nb3) / 3)

fin

-
14-
 Part 3 : Instructions élémentaires et structure d’un algorithme

Début

-
15-
Part 3 : Instructions élémentaires et structure d’un algorithme

-
16-