Module Algorithmique – Master IM ISAMM – 1ère année 2014/2015

___________________________________________________________________________________________
CH I. Introduction à l’algorithmique

I. Définitions
I.1. Algorithme

C’est la description des étapes à suivre pour chercher une solution à un problème quelconque
en suivant une logique bien déterminée.
C’est une suite finie et ordonnée d’opérations élémentaires (instructions) constituant un
schéma de calcul ou de résolution d’un problème ou classe de problèmes. Cette suite est
structurée puisque l’ordre suivant lequel les opérations se déroulent est fondamental. Il
permet de passer d’un ensemble fini de variables appelées données à un ensemble fini de
variables appelées résultats.
Un algorithme est un langage de programmation abstrait, non destiné à la machine. Il doit
être traduit à n’importe quel langage de programmation concret.
Le mot Algorithme revient à celui qui l’a inventé : le mathématicien Al-Khawarizmi.

Exemple 1 : pour aller à la poste, il faut prendre la première à droite, aller tout droit
jusqu'au feu, prendre à gauche, et c'est le 4ième bâtiment après le supermarché.

Exemple 2 : pour faire une tarte aux fraises, il faut faire une pâte brisée, l'étaler dans un
moule, la faire cuire; pendant ce temps là il faut faire une crème pâtissière; quand la pâte
est cuite, étaler la crème sur la tarte et mettre des fraises. Il faudra peut-être préciser
comment faire une pâte brisée et une crème pâtissière, ça dépend à qui on s'adresse.

Le savoir faire d'un cuisinier se transmet par une recette, avec un langage bien particulier,
celui d'un informaticien par un algorithme, qui demande aussi un langage particulier.

Exemple 3 : On veut calculer la moyenne des notes d’un élève dans une matière donnée.
On suppose que le nombre de notes est égal à 3.

Algorithme Moyenne

Var
Nom, Matière : chaîne
Moyenne, Note1, Note2, Note3 : réel
Début
1 : Lire (Nom, Matière, Note1, Note2, Note3)
2 : Calculer la moyenne : Moyenne (Note1+Note2+Note3)/3
3 : Ecrire (Nom, Matière, Moyenne)
Fin

• Un ensemble d’actions ou d’opérations à exécuter.

Tout algorithme est caractérisé par :

• Un ordre d’exécution de ces différentes opérations déterminé par la logique

• Un début et une fin.

d’enchaînement et conditionné par les structures mises en œuvre.

I.2. Programme

Un programme est la description (ou la traduction) d'un algorithme dans un langage accepté
par la machine. C’est à dire une suite d’instructions exprimées dans un langage de
programmation (exemple : Pascal, C, java, etc.). A l’aide de tels langages, le programmeur
S. Ben Abdallah Ben Lamine
1
Module Algorithmique – Master IM ISAMM – 1ère année 2014/2015
___________________________________________________________________________________________
écrit dans un éditeur de texte le programme (code source). Celui-ci n’est pas directement
exécutable par l’ordinateur ; il faut traduire en langage machine (code objet : formé par 0 et
1) : c’est le rôle du compilateur et de l’interpréteur.

Un langage de programmation n’est pas très adapté à la communication entre gestionnaires et

informaticiens. C’est pourquoi on utilise au préalable le langage algorithmique (proche du
langage naturel), afin de décrire pas à pas une solution au problème posé.

Un algorithme, à l'inverse d'un programme, est indépendant du langage de programmation (et

donc de la machine).

I.3. langage compilé et langage interprété

Un langage est interprété si la traduction en langage machine se fait au moment de
l’exécution et instruction par instruction. S’il y a une erreur syntaxique l’exécution s’arrête et
l’interpréteur affiche l’erreur et sa nature. Ex : Basic, Maple , …
100
0 E t

Programme Exécution
source

Etape d‘interprétation

Figure 1 : Langage interprété

Un langage est compilé si la totalité du code source est transformé en code exécutable par la
machine après avoir corrigé toutes les erreurs détectées par le compilateur. Exemple :
C,C++.
Programme Programme Exécution
source exécutable

Etape de compilation

Figure 2 : Langage compilé

II. Principe de déroulement d’un programme sur l’ordinateur

II.1. Constituants d’un ordinateur

Un ordinateur est capable, dans la limite de ses capacités en espace mémoire (nécessairement
finies) et en vitesse de calcul, d'exécuter n'importe quel algorithme qu'on lui fournit sous
forme de programme (enregistré dans la mémoire), sur n'importe quelle donnée discrète,
qu'on lui fournit également et de communiquer et d’archiver ces informations.
On distingue alors trois constituants principaux:

• Unité Centrale de Traitement (UCT), en anglais CPU (Central Processing Unit) ;

• Mémoires, parmi lesquelles on distingue plusieurs types :
o la mémoire ROM (Read Only Memory : mémoire à accès en lecture seule) :
ensemble de bits dont l'état est fixé une fois pour toute, lors de la construction
de l'ordinateur. Elle sert à stocker des informations permanentes (procédures
de démarrage...) ;
o la mémoire RAM ou «mémoire vive» (Random Access Memory : mémoire à
accès aléatoire) : ensemble de bits modifiables à volonté, où se trouvent
stockées les données sur lesquelles travaille l'ordinateur. Aléatoire veut dire
non séquentiel ; cela signifie que l'on peut avoir accès directement à tout
endroit de cette mémoire (comme les chansons dans un CD ou les chapitres
dans un film en DVD), sans avoir à la parcourir bit à bit (comme dans les
S. Ben Abdallah Ben Lamine
2
Module Algorithmique – Master IM ISAMM – 1ère année 2014/2015
___________________________________________________________________________________________
cassettes audio ou vidéo). Cette mémoire est volatile, c'est-à-dire qu'elle ne
conserve les données que tant que la machine est sous tension. Ordre de
grandeur 1Giga-octet.
o les mémoires secondaires ou auxiliaires : permettent de stocker des bits de
façon stable (qui reste fixée même si on éteint la machine) tout en étant
généralement modifiable. Exemples : les disques durs, les disquettes, les
bandes magnétiques, les clés USB... La capacité des disques durs actuels se
compte en Giga-octets.
• Périphériques : qui peuvent être :
o d'entrée, permettant à un utilisateur extérieur de fournir des informations
(données/programmes) à la machine sous forme numérique : souris, clavier,
scanner, joystick, appareil photo numérique, camescope numérique... Ce sont
des numériseurs puisqu'ils transforment un comportement (l'appui sur la
touche d'un clavier, le mouvement de la souris) ou un objet (une photo
analogique pour le scanner, …) en une suite de bits.
o de sortie, c'est-à-dire permettant de visualiser ou de transmettre des données
internes à l'extérieur : écran, imprimante, IPod, vidéo-projecteur... A l'inverse
des numériseurs, ces dispositifs traduisent des suites de bits en information
interprétable par les humains.

La logique de cette organisation est donnée par la figure suivante :

Figure 3 : Organisation générale d’un ordinateur

II.2. Architecture de Von Neumann

L'homme à l'origine de la conception des ordinateurs actuels est John Von Neumann.
Le schéma général de l'architecture de Von Neumann est représenté par la figure suivante.

Figure 4: Architecture de Von Neumann

Les deux innovations majeures introduites par Von Neumann par rapports aux calculateurs
existant à son époque sont, l'intégration :

• d'une «unité de commande» qui donne les ordres et synchronise les opérations ;
• d'une mémoire centrale interne permettant de stocker aussi bien des données (entrées,
résultats, intermédiaires) que des programmes.

S. Ben Abdallah Ben Lamine

3
Module Algorithmique – Master IM ISAMM – 1ère année 2014/2015
___________________________________________________________________________________________
II.3. Cycle d’exécution d’une instruction
Supposons que la mémoire centrale de notre ordinateur contienne un programme et des
données, et que l'on souhaite exécuter ce programme sur ces données. Lancer cette exécution
revient à mettre dans le compteur ordinal (CO) l'adresse où se trouve stockée la première
instruction du programme. A partir de là, le programme est exécuté étape par étape,
instruction par instruction. L'exécution d'une instruction élémentaire, se fait suivant un cycle
comprenant 3 phases :

• phase 1 : L'instruction courante, dont l'adresse est stockée dans le CO, est recopiée
dans le registre d'instruction (RI) en transitant par le bus «instructions» ;
• phase 2 : cette instruction courante est décodée à destination de l'UAL (Unité
Arithmétique et Logique) ; ainsi le bus «ordres» transfère le code de l'opération (les 4
premiers bits) et le bus «données/résultats» transfère dans les registres appelés
«donnée 1» et «donnée 2» le contenu des mots mémoire se trouvant aux adresses
référencées dans l'instruction ;
• phase 3 : l'UAL exécute l'opération qui lui est demandée en mettant à jour son registre
«résultat» et transfère ce résultat dans la mémoire centrale, à l'adresse référencée dans
l'instruction, en utilisant le bus «données/résultats» ; par ailleurs le CO est
automatiquement incrémenté, pour signifier que l'instruction suivante à exécuter doit
se trouver normalement à l'adresse qui suit immédiatement la précédente. Un nouveau
cycle peut commencer alors pour la nouvelle instruction courante.

Ces cycles sont rythmés par les tops d'horloge, chaque phase correspondant à un nombre fixe
de «tops» successifs. Dans notre exemple, pour la phase 1, qui nécessite de faire transiter
l'instruction courante de la mémoire vers le RI en utilisant le bus d'instruction, 4 tops
d'horloge seront nécessaires (car, dans cet exemple, un mot mémoire fait 16 bits et le bus n'a
une capacité que de 4 bits).

Illustrons ce fonctionnement à l'aide d'un exemple donné par la figure suivante :

Figure 5: Exécution d'une instruction

S. Ben Abdallah Ben Lamine

4
Module Algorithmique – Master IM ISAMM – 1ère année 2014/2015
___________________________________________________________________________________________
III. Les phases d’une activité de programmation
Les phases de la démarche de programmation peuvent être résumées par le schéma suivant :

- Analyse du problème : c’est une étape de

réflexion : trouver une façon « comment » aboutir
aux résultats attendus à partir des données dont on
dispose. Donc définir : les entrées, les sorties, le
« comment » (construire les résultats à partir des
données). On dispose ainsi d’algorithmes
informels.
- Conception : ordonnancer les actions à effectuer,
définir la forme des structures de données et
décomposer éventuellement le problème en entités
faciles à implémenter et à tester. Ecrire le tout dans
un langage de programmation abstrait ou
algorithmes formels.
- Implémentation (codage) et tests : exprimer
l’algorithme dans un langage de programmation
concret (évolué). Vérifier ensuite le bon
fonctionnement des unités de programmation (tests
unitaires) et le bon fonctionnement de tout le
programme (tests d’intégration). Figure 6: Phases de
- Maintenance : corrective, perfective, évolutive. programmation

IV. Le cycle de vie du logiciel (CVL)

Où positionnez-vous l’activité de conception d’algorithmes et de programmation dans le
CVL :

Figure 7: Cycle de vie du logiciel

V. Qualités d’un algorithme

- Qualité d'écriture : un algorithme doit être structuré, indenté, modulaire, avec des
commentaires pertinents, etc. Il faut pouvoir comprendre la structure d'un coup d'oeil
rapide, et pouvoir aussi revenir dessus 6 mois plus tard et le comprendre encore.
S. Ben Abdallah Ben Lamine
5
Module Algorithmique – Master IM ISAMM – 1ère année 2014/2015
___________________________________________________________________________________________
- Terminaison : le résultat doit être atteint en un nombre fini d'étapes.
- Validité : le résultat doit répondre au problème demandé. Attention, un jeu d'essais ne
prouve JAMAIS qu'un programme est correct. Il peut seulement prouver qu'il est
faux.
- Performance : étude du coût (complexité) en temps et en mémoire.
La complexité en mémoire (c'est à dire la place mémoire prise par l'algorithme) est un
problème de moins en moins primordial vu les capacités techniques actuelles.

VI. Le langage algorithmique

Pour communiquer, deux personnes utilisent un langage commun. Les informaticiens ont
aussi besoin d'un langage plus ou moins codifié pour se comprendre, il faut donc se définir un
langage algorithmique. Ce langage doit être :

- spécialisé (pour écrire des algorithmes, pas des poèmes ni des recettes de cuisine)
- de haut niveau (déchargé de détails techniques, ce n'est pas un langage de
programmation)
- concis ("si ça ne tient pas en une page, c'est que c'est trop long")
- (donc) modulaire
- typé

Dans la suite de ce cours, nous allons découvrir ce langage algorithmique.

VII. Sites Web

Pour aller plus loin :

http://fr.wikipedia.org/wiki/Accueil et http://fr.wikiversity.org/wiki/Accueil
A lire parfois avec précautions (puisque n'importe qui peut y écrire) mais les rubriques scientifiques et
techniques sont en général fiables.

http://interstices.info/
http://www.commentcamarche.net/
http://www.grappa.univ-lille3.fr/

S. Ben Abdallah Ben Lamine

6