Algorithme et programmation

ALGORITHME
Introduction
L'informatique est la science du traitement automatique (moyennant l'ordinateur) de
l'information. Elle a pour objet d'élaborer et de formuler l'ensemble de commandes, d'ordres ou
d'instructions permettant de commander l'ordinateur et de l'orienter lors du traitement. Pour cela
il faut :
 modéliser cette information,
 définir à l’aide d’un formalisme strict les traitements dont elle fera l’objet.
 et enfin traduire ces traitements dans un langage compréhensible par un ordinateur.
Les deux premiers points concerne l’algorithmique, alors que le dernier point relève de ce que
l’on nomme la programmation.
1. Architecture et composants matériels de l’ordinateur

Un ordinateur est composé de deux unités :

 L'unité centrale constituée de :
 L'unité de traitement (UT) qui commande tout traitement fait par l'ordinateur.
 L'unité de calcul (UC) qui effectue les opérations (arithmétiques, logiques…)
Commandées par l'UT. L'ensemble UT, UC est appelé processeur.
 La mémoire centrale qui sert de support de stockage de données. Il s’agit d’une mémoire
volatile.
 L'unité d'échange constituée de :
 Les périphériques d'entrée/sortie comme le clavier, la souris, l'écran et l’imprimante.
 La mémoire secondaire qui sert également de support de stockage de données. Elle est
permanente et se caractérise par une capacité supérieure à celle de la mémoire centrale.
Remarque :
Le composant mémoire est physiquement un ensemble de cellules mémoire (octets)
Contenant des données sous forme binaire. Un octet est constitué de 8 bits (digits
Contenant les chiffres 0 ou 1). Un kilooctet (kOctet) est composé de 1024 (210) octets.
2. Composants logiciels de l'ordinateur (aspect sofware)
Tout traitement automatique peut être réalisé au moyen d'un ou de plusieurs programmes. Un
programme est une série d'instructions (opérations) que la machine peut exécuter pour effectuer
des traitements donnés. Un logiciel est en général un ensemble de programmes visant à
effectuer automatiquement un traitement ou une tâche complexe.

Dr. Oumar DIA Page 1 sur 8

 Algorithme et programmation

Une machine peut héberger plusieurs logiciels au choix de son utilisateur. Cependant, un
Système d'exploitation dit aussi système opératoire est un logiciel de base qui doit faire l'objet
de la première installation.
Un système d'exploitation fut un ensemble de programmes assurant d'une part, le
fonctionnement de toutes les composantes matérielles d'un ordinateur et d'autre part, la
communication Homme/Machine. Il a pour exemples de fonctions :
 La gestion de la mémoire.
 La gestion des périphériques.
 La gestion de partage de ressources entre plusieurs utilisateurs.
 Système de fichiers.
 Interface utilisateur.
Comme exemples de systèmes opératoires, nous citons Windows, Unix, Linux, Ms Dos
(abréviation de Microsoft Disk Operating), Mac Os (Macintosh Operating Système créé par
Apple, Inc) ... Android iOS(iPhone OS)
3. Scenario d’un traitement automatique
Faire effectuer un traitement automatique par la machine nécessite de lui indiquer la source de
données (sur quoi porte le traitement), les opérations ou actions élémentaires à effectuer pour
atteindre l'objectif visé et la destination où elle doit renvoyer les résultats. L’ensemble de ces
informations constitue ce qu’on appelle un algorithme que le programmeur doit encore traduire
en programme exécutable par la machine.
Le travail d’un programmeur dans sa recherche de la solution à un problème s’effectue
généralement en trois étapes :
Solution dans
Solution dans un
Enoncé Recherche Traduction un langage de
Pseudo- langage
Le Problème de solution programmation
L’Algorithme
Le Programme

L'exécution d'un programme par l'ordinateur passe, en général, par les étapes suivantes :
 Le processeur extrait les données à traiter à partir de la source indiquée dans le
programme (soit auprès de l'utilisateur qui devrait les introduire au moyen du clavier, soit en
mémoire secondaire ou centrale).
 Il exécute, ensuite, la série d'opérations élémentaires de manière séquentielle (dans
l'ordre prévu par le programme) et mémorise tous les résultats intermédiaires.
 Il renvoie enfin le ou les résultats attendus à la destination (périphérique de sortie)
indiquée dans le programme.
1. Qu’est-ce que d’algorithme
Le mot algorithme est issu de la déformation du nom d’un savant perse du IXème siècle appelé
Al Khuwarizmi4. Donc, il n’y a aucun rapport avec le mot rythme, ce qui explique l’absence
de y dans le mot algorithme.
Avez-vous déjà indiqué un chemin à une personne égaré ? Avez-vous fait chercher un objet à
quelqu’un par téléphone ?

Dr. Oumar DIA Page 2 sur 8

 Algorithme et programmation

Ecrit une lettre stipulant comment procéder pour faire une bonne impression auprès d’un
public ? Si oui, vous avez déjà fabriqué – et fait exécuter – des algorithmes.
Algorithme : séquence finie d’actions permettant de résoudre un problème donné.
Un algorithme, c’est une suite d’instructions, qui une fois exécutée correctement, conduit
à un résultat donné. Si l’algorithme est juste, le résultat est le résultat voulu, et la personne qui
était égarée se retrouve là où il voulait aller. Si l’algorithme est faux, le résultat est, disons,
aléatoire, et décidément, cette personne ne retrouve pas là où il voulait aller.
La notion d’algorithmique est directement dérivée du concept d’algorithme : Algorithmique :
ensemble des méthodes permettant de définir et/ou d’étudier des algorithmes.
Les premiers algorithmes sont destinés à résoudre certains problèmes mathématiques simples,
par exemple multiplier ou diviser des nombres. Ils étaient appliqués manuellement, et sont
antérieurs de plusieurs siècles (voire millénaires) à l’invention des ordinateurs. Ceci permet
d’ores et déjà d’établir l’indépendance entre un algorithme et sa mise en œuvre, c’est à dire
(dans le cadre informatique) son implémentation.
Il existe également des algorithmes qui n’ont rien à voir avec les mathématiques, comme par
exemple les recettes de cuisine. Une recette est une séquence d’instructions à suivre pour
réaliser un plat donné, elle est mise en œuvre manuellement par un cuisinier.
2. Représentation d’un algorithme
Un algorithme est généralement décrit en pseudocode (pseudo-langage). C’est un langage
naturel, ou incomplètement formalisé : texte libre (description des différentes étapes en français
et indépendant de tout langage de programmation). Un algorithme peut aussi être décrit sous
forme d’algorigramme (organigramme) qui est une représentation graphique (diagramme
représentant les étapes).
Cela signifie donc que l’écriture d’un algorithme est souple, elle vise à exprimer une méthode
de résolution de façon compréhensible à un être humain. Mais pour la même raison, un
algorithme ne peut pas être traité directement par un ordinateur : il doit être formalisé,
transformé en un programme.
Il n’existe pas vraiment de norme pour les organigrammes représentant des algorithmes. On
peut tout de même mentionner certains points qui font consensus :
 Les étapes sont représentées par des nœuds et les transitions par des liens orientés entre
ces noeuds ;
 Les étapes de test sont représentées par des losanges ;
 Les étapes de début et de fin sont représentées par des rectangles aux coins arrondis ;
 Les étapes de traitement sont représentées par des rectangles ;
 Les appels à des fonctions ou procédures (aussi appelées sous-routines) sont représentés
par des rectangles dont les côtés sont dédoublés;
 Les étapes d’entrée/sortie sont représentées par des parallélogrammes.

Dr. Oumar DIA Page 3 sur 8

 Algorithme et programmation

L’inconvénient de cette représentation est qu’il est difficile de décrire des algorithmes
complexes tout en gardant un diagramme lisible.
Exemple : le même algorithme représenté sous forme d’organigramme puis de pseudocode
Version organigramme :

Version pseudocode :
Début
Afficher « début du traitement »
Compteur  =0
Tant que compteur  4
Faire un traitement x
Incrémenter le compteur
Fin tant que
Afficher « début du traitement »
Fin

Dr. Oumar DIA Page 4 sur 8

 Algorithme et programmation

Dans notre cas, le problème à résoudre est souvent compliqué, et l’algorithme permettant de le
résoudre n’est pas évident à définir. Pour cela, on utilise en général l’approche appelée divisé
pour régner. Cette méthode hiérarchique consiste à diviser notre problème complexe en
plusieurs sous-problèmes plus simples à résoudre.
L’approche s’applique récursivement aux sous-problèmes s’ils sont eux-mêmes trop
complexes, i.e. on les divise eux-mêmes en sous-problèmes plus simples si nécessaire. On
aboutit finalement à des sous-problèmes élémentaires, c'est-à-dire qu’on ne peut plus les réduire
à des sous-problèmes plus simples. La résolution de ces sous-problèmes est supposée facile, et
il en est de même pour la définition de l’algorithme correspondant.

3. INSTRUCTIONS
Les ordinateurs, quels qu’ils soient, ne sont fondamentalement capables de comprendre que
quatre catégories d'ordres (en programmation, on n'emploiera pas le terme d'ordre, mais plutôt
celui d'instructions). Les quatre familles d'instructions de base pouvant composer un
algorithme, décrites dans ce paragraphe sont :
 l’affectation de variables
 la lecture / écriture
 les tests
 les boucles
Un algorithme informatique se ramène donc toujours au bout du compte à la combinaison de
ces quatre petites briques de base. Il peut y en avoir quelques-unes, quelques dizaines, et jusqu’à
plusieurs centaines de milliers dans certains programmes de gestion. Rassurez-vous, dans le
cadre de ce cours, nous n’irons pas jusque-là (cependant, la taille d’un algorithme ne
conditionne pas en soi sa complexité : de longs algorithmes peuvent être finalement assez
simples, et de petits très compliqués).
3.1.INSTRUCTION DE BASE
Nous les traitons dans ce paragraphe en version pseudocode
3.1.1. L'AFFECTATION
Variable  expression

Dr. Oumar DIA Page 5 sur 8

 Algorithme et programmation

L'affectation, notée par le symbole (), est l'opération qui évalue une expression (constante
ou une expression arithmétique ou logique) et attribue la valeur obtenue à une variable.
Exemple:
Y  10 : y reçoit la constante 10
y  (2*y) +x : a reçoit le résultat de (2*y*b) +x
z  ‘m’ : z reçoit la lettre m
3.1.2. LA LECTURE
Lire variable
Cette opération permet d'attribuer à une variable une valeur introduite au moyen d'un organe
d'entrée (généralement le clavier).
Exemple :
Lire a : On demande à l'utilisateur d'introduire une valeur pour a
Lire (a,b,c) : On demande à l'utilisateur d'introduire 3 valeurs pour a, b et c respectivement
3.1.3. L'ECRITURE
Ecrire expression
Elle communique une valeur donnée ou un résultat d'une expression à l'organe de sortie.
Exemple :
Ecrire 'bonjour' Affiche le message bonjour (constante)
Ecrire 12 Affiche la valeur 12
Ecrire a,b,c Affiche les valeurs de a, b et c
Ecrire a+b Affiche la valeur de a+b
3.2. Instruction de control (ou conditionnée)
Nous les traitons sous forme pseudocode et sous forme d’organigramme. Ces instructions
donnent généralement des organigrammes structurés à plusieurs séquences.
3.2.1. Structure séquentielle
C’est une Structure dans laquelle plusieurs opérations (instructions) sont effectuées
successivement et sans condition.

3.2.2. Instructions sélectives ou Structure alternative

Dans cette structure l’opération effectuée est fonction d’une condition « si ».

Dr. Oumar DIA Page 6 sur 8

 Algorithme et programmation

Remarques :
 Une instruction de contrôle « si » peut se réduire à
Si condition vrai alors
Instruction(s)
fin
 On peut avoir un enchainement de » si »
si condition 1 vraie alors
si condition 2 vraie alors
si condition 3 vraie alors
Instruction(s) 1
sinon
Instruction(s) 2
sinon
Instruction(s) 3
sinon
Instruction(s) 4
fin
3.2.3. Instructions itératives ou Structure répétitive
Structure dans laquelle les opérations sont effectuées plusieurs fois.
a) Instruction pour
Elle permet de répéter un traitement un nombre de fois précis et connu en utilisant un compteur
(variable à incrémenter d'une itération à l'autre)
Pour compteur  valeur 1 à valeur n faire
Instruction(s)
Fin
Exemple : Afficher la somme des entiers compris entre 0 et une valeur n saisie au clavier (n≥0).
lire n
s0 Pour
i1 à n faire
ss+i
Fin
écrire s

Dr. Oumar DIA Page 7 sur 8

 Algorithme et programmation

b) Instruction Tant que

Elle permet de répéter un traitement tant qu'une condition est satisfaite
b1) Structure TANT QUE - FAIRE

Exemple : Calculer la somme s des entiers compris entre 0 et un nombre n saisi au clavier (on
suppose que n≥0).
lire n
s 0
Tant que n > 0 faire
ss+n
nn-1
Fin
Ecrire s
b2) Structure FAIRE - TANT QUE

Exemple : Calculer la somme s des entiers compris entre 0 et un nombre n saisi au clavier.
lire n
s0
i 0 Faire
ss+i
ii+1
Fin
Tant que i≤n
Ecrire s

Dr. Oumar DIA Page 8 sur 8