INTRODUCTION À L’ALGORITHMIQUE

INTRODUCTION À
L’ALGORITHMIQUE

Plan du chapitre :

I. Définitions
………………………………………………………………
……………………………………... 2
II. Cycle de vie d’un programme
………………………………………………………………
………. 2
III. Notion d’algorithmique et de programmation
…………………………………………….. 4
IV. Les étapes de résolution d’un
problème ……………………………………..
………………. 5
V. Les caractéristiques d’un algorithme
…………………………………………………………. 5
VI. Conventions d’écriture d’un
algorithme………………………………………………
……….. 6

Objectifs du chapitre :
1
 INTRODUCTION À L’ALGORITHMIQUE

 Acquérir les notions nécessaires et préalables à

l’algorithmique.
 Comprendre le cycle de création d’un programme et le rôle
de l’algorithme dans ce cycle.
 Connaître les caractéristiques et les conventions d’écriture
d’un algorithme.

1
I. Définitions :
 Le terme informatique : l’informatique est une science qui permet de traiter
automatiquement les informations.
 Le terme système informatique : un système informatique est un ensemble de moyens
matériel et logiciels permettant de satisfaire les besoins informatiques de l’utilisateur :
- Le Matériel informatique: Il s’agit des ressources matérielles qui sont exploitées pour
exécuter les différents logiciels destinés à satisfaire les besoins des utilisateurs : micro-
ordinateurs, imprimantes, scanners, etc.
- Les Logiciels: Un logiciel est un ensemble de programmes qui répond aux besoins
fréquents de l’utilisateur dans un domaine d’activités bien déterminé.
On distingue plusieurs types de logiciels tels que les logiciels de base comme le système
d'exploitation ou les programmes d'application (Traitement de texte, comptabilité ...).
 Le terme utilisateur : un utilisateur est une personne initié à l’informatique et autorisé à
exploiter et à manipuler les ressources du système informatique.

II. Cycle de vie d’un programme :

Un programme est une liste d’instructions qu’il faut exécuter pour atteindre un objectif donnée.
L’exécution du programme peut être effectuée par l’homme, par la machine ou bien par
l’ordinateur. Dans ce dernier cas, on parlera de programme informatique (Computer program).
Un programme représente une solution à un problème donné, pour y arriver il faut passer par un
cycle de programmation qui regroupe les différentes étapes de sa création. (Figure 1)

2
 INTRODUCTION À L’ALGORITHMIQUE

Problè Spécifications
me

Codage/Traduction
Algorit Programmeur (Langage
de programmation)
hme

Programme Exécution

Erreur
sémantique

Erreur Résult
syntaxique ats

Figure 1: Etapes de création d’un programme

L'analyse d'un problème posé consiste à définir les différentes étapes de sa résolution. C'est la
partie essentielle dans le processus de programmation. Elle permet de définir le contenu d'un2
programme en termes de données et d’actions. À chacun de ces derniers sera associé une
spécification formelle ayant des conditions d'entrée et le(s) résultat(s) que l'on souhaiterait
obtenir. L'ensemble de ces spécifications nous donne une première solution au problème :
l’algorithme.
La phase suivante consiste à traduire l’algorithme dans un langage de programmation donné. Ce
travail, quoiqu’il semble facile, exige le respect strict de la syntaxe du langage. Lors de l’étape
d’exécution, soit des erreurs syntaxiques sont signalées, ce qui entraîne des corrections en
général simples à effectuer, soit des erreurs sémantiques plus difficiles à découvrir.
Dans le cas d’erreur syntaxique, les retours vers le programme peuvent être fréquents. Dans le
cas d’erreur sémantique, le programme produit des résultats qui ne correspondent pas à ceux
souhaités: les retours vers l’analyse (algorithme) sont alors inévitables.
Exemple explicatif:
Problème : ensemble de familles qui demandent un logement.
Solution : immeuble pour regrouper ces familles.

3
 INTRODUCTION À L’ALGORITHMIQUE

Spécifications
Dimension du terrain
Nbr d’étages
Nbr d’appartement dans chaque étage
Nbr de pièces dans chaque appartement
...

Traduction/réalisation
Plan Entrepreneur (Ensemble
d’outils de construction)

Erreurs sémantiques Exécution/Utilisation

Absence des cuisines !
3 appartements par étage à la place de 4 !
4 pièces par appartement au lieu de 3 !
…

Erreurs de construction
Fuite d’eau dans la cuisine
Fenêtre/porte bloquée
….

Figure 2: Etapes de construction d’un immeuble

Le cycle de vie d’un programme est similaire à un cycle de construction d’un immeuble, le
tableau suivant contient les différentes analogies entre ces deux cycles :

Cycle de vie d’un programme Cycle de construction d’un immeuble

Le programme est la solution réelle d’un L’immeuble représente la solution réelle du
problème donné. problème donné.
L’algorithme représente une solution Le plan représente une solution théorique du
théorique d’un problème donné. problème donné.
L’algorithme est une solution sur papier du Le plan est une solution sur papier et non
problème et non utilisable. utilisable.
Pour réaliser le programme il faut le traduire Pour réaliser l’immeuble il faut donner le
par un programmeur. 3 plan à un entrepreneur ou une société.
Le programmeur à besoin d’un langage de L’entrepreneur à besoin des outils de
programmation pour la traduction. construction pour la réalisation.
L’utilisation du programme consiste à L’utilisation de l’immeuble consiste à
l’exécuter sur une machine par un utilisateur. l’exploiter par les familles.
A l’exécution on peut trouver : Pendant l’utilisation on peut trouver :
- des erreurs syntaxiques, généralement - des erreurs de construction, généralement
simples à corriger. (correction au niveau simples à corriger. (correction au niveau
du programme) de l’immeuble).
- des erreurs sémantiques généralement très - des erreurs sémantiques, généralement
difficiles à corriger (correction au niveau très difficiles à corriger (correction au
de l’algorithme) niveau du plan !)
Commentaires
L’algorithme joue, dans le cycle de vie d’un programme, le même rôle que celui d’un plan

4
 INTRODUCTION À L’ALGORITHMIQUE

dans le cycle de construction d’un immeuble.

Malgré que c’est une solution théorique, il y a des règles à respecter pour créer des plans, de
même, l’écriture des algorithmes est encadrée par un ensemble de règles et des conventions
standards.
Est-il possible de créer un programme sans passer par l’algorithme ?
Autrement dit : est-il possible de créer un immeuble sans passer par le plan ?
On peut dire que c’est possible dans deux cas :
- L’élément à construire est très simple (construction d’un petit mure).
- L’élément à construire a été réalisé plusieurs fois donc après une bonne expérience
(construction d’un ensemble de bâtiments similaires : cité).
Sinon la construction sans plan porte un grand risque est donne naissance à beaucoup de
problèmes tels que la reconstruction, la non fiabilité, etc.
De même, il est possible de créer un programme sans passer par l’algorithme, uniquement
pour les problèmes très simples ou après une bonne expérience de développement, mais
d’une façon générale l’algorithme reste un élément indispensable pour résoudre tout
problème.

Tableau 1: analogie entre cycle de construction d’un immeuble

et cycle de vie d’un programme

III. Notion d’algorithmique et de

programmation :
III.1 Définitions :

 Algorithme :
Un algorithme est une suite d'actions que devra effectuer un ordinateur, en un temps fini, pour
arriver à un résultat, à partir d'une situation donnée.
Un algorithme est une suite finie d'instructions indiquant de façon précise l'ordre dans lequel doit
être effectué un ensemble d'opérations pour obtenir la solution d’un problème.
Un algorithme, dérivé du nom du mathématicien arabe « Al-Khawarizmi », est une séquence
d’opérations pour résoudre un type de problème spécifique.
 Programme :
4
Un programme est un algorithme codé dans un langage compréhensible par ordinateur à l’aide
d’un compilateur (traducteur).
Un programme est une liste d’instructions qu’il faut exécuter pour atteindre un objectif donné.
Selon les définitions précédentes, on voit qu’il existe une grande similitude entre les termes
« programme » et « algorithme ». Les deux désignent une méthode pour résoudre un problème
donné. On emploie le terme « algorithme » lorsque la séquence d’instructions est écrite en
langage algorithmique et fait abstraction d’un ensemble de détail. On emploie le terme «
programme » lorsque la séquence d’instructions est écrite dans un langage compréhensible par la
machine.

 Notion d’algorithmique :
C’est la logique d’écrire des algorithmes. Pour pouvoir écrire des algorithmes, il faut connaître la
résolution manuelle du problème, connaître les capacités de l’ordinateur en terme d’actions
élémentaires qu’il peut assurer et la logique d’exécution des instructions.

5
 INTRODUCTION À L’ALGORITHMIQUE

III.2 Algorithmique et programmation :

Pourquoi apprendre l’algorithmique pour apprendre à programmer ? En quoi a-t-on besoin d’un
langage spécial, distinct des langages de programmation compréhensibles par les ordinateurs ?
Parce que l’algorithmique exprime les instructions résolvant un problème donné
indépendamment des particularités de tel ou tel langage. Pour prendre une image, si un
programme était une dissertation, l’algorithmique serait le plan, une fois mis de côté la rédaction
et l’orthographe. Or, vous savez qu’il vaut mieux faire d’abord le plan et rédiger ensuite que
l’inverse…
Apprendre l’algorithmique, c’est apprendre à manier la structure logique d’un programme
informatique. Cette dimension est présente quelle que soit le langage de programmation ; mais
lorsqu’on programme dans un langage (en C, en Visual Basic, etc.) on doit en plus se colleter les
problèmes de syntaxe, ou de types d’instructions, propres à ce langage.
Apprendre l’algorithmique de manière séparée, c’est donc sérier les difficultés pour mieux
les vaincre.

IV. Les étapes de résolution d’un problème :

1. Comprendre l’énoncé du problème.
2. Décomposer le problème en sous-problèmes plus simple à résoudre.
3. Associer à chaque sous problème, une spécification :
 Les données nécessaires
 Les données résultantes
 La démarche à suivre pour arriver au résultat en partant d’un ensemble de données.
4. Elaborer l’algorithme.

V. Les caractéristiques d’un algorithme :

1. Claire: l’algorithme ne doit pas présenter des ambiguïtés (instruction interprétable de
plusieurs manières) et facile à lire et à comprendre.
2. Correct: Il faut que l’algorithme exécute correctement les tâches pour lesquelles il a été
conçu.
3. Complet: Il faut que l’algorithme considère tous les cas possibles et donne un résultat dans
chaque cas.
4. Fini : l’algorithme doit se terminer quelle que soit la machine ainsi que le temps et la date5
d’exécution.
5. Efficacité : l’algorithme doit effectuer le travail demandé avec l’utilisation du minimum de
ressources.

VI. Avec quelles conventions écrit-on 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.
Aujourd’hui, cette représentation est quasiment abandonnée, pour deux raisons. D’abord, parce
que dès que l’algorithme commence à grossir un peu, ce n’est plus pratique du tout du tout.

6
 INTRODUCTION À L’ALGORITHMIQUE

Ensuite parce que cette représentation favorise le glissement vers un certain type de
programmation, dite non structurée (nous définirons ce terme plus tard), que l’on tente au
contraire d’éviter.
C’est pourquoi 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é 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.