L ’ Algorithme

Introduction
L’algorithmique est un terme d’origine arabe, hommage à Al Khawarizmi (780-
850) auteur d’un ouvrage décrivant des méthodes de calculs algébriques.
Un algorithme est une méthode de résolution de problème énoncée sous la
forme d'une série d'opérations à effectuer. La mise en œuvre de l'algorithme
consiste en l'écriture de ces opérations dans un langage de programmation et
constitue alors la brique de base d'un programme informatique.
1. Une recette de cuisine est un algorithme!
2. Le mode d’emploi d’un magnétoscope est aussi un algorithme!
3. Indiqué un chemin à un touriste égaré ou faire chercher un objet à
quelqu’un par téléphone c’est fabriquer - et faire exécuter - des
algorithmes.
• Un algorithme, c’est une suite d’instructions, qui une fois exécutée correctement,
conduit à un résultat donné.

1. Si l’algorithme est juste, le résultat est le résultat voulu, et le touriste se

retrouve là où il voulait aller.
2. Si l’algorithme est faux, le résultat est, disons, aléatoire, et décidément, ce
magnétoscope ne marche pas!
L’algorithmique
• Principe
• Définition : Un algorithme est une séquence bien définie d’opérations
(calcul, manipulation de données, etc.) permettant d’accomplir une
tache en un nombre fini de pas.
• En principe un algorithme est indépendant de toute implantation. Cependant
dans la pratique de la programmation il s’avère indispensable de tenir compte
des capacités du langage de programmation utilisé.
• La conception d’un algorithme passe par plusieurs étapes :
• Analyse : définition du problème en terme de séquences d’opérations ;
• Conception : définition précise des données, des traitements et de leur séquencement ;
• Implantation : traduction et réalisation de l’algorithme dans un langage précis ;
• Test : Vérification du bon fonctionnement de l’algorithme.
Les caractéristiques d’un Algorithme
•
Un algorithme est une marche à suivre :
1. dont les opérations sont toutes définies et portent sur des objets
appelés informations,
2. dont l’ordre d’exécution des opérations est défini sans ambiguïté,
3. qui est réputée résoudre de manière certaine un problème ou
une classe de problèmes,
4. s’exprime dans un langage indépendant.
L’algorithmique et la programmation

• Un programme est la traduction d’un algorithme dans un certain

langage de programmation. Il faut savoir qu’à chaque instruction d’un
programme correspond une action du processeur.
• Le but de la programmation :
1. Utiliser l’ordinateur pour traiter des données afin d’obtenir des
résultats.
2. Abstraction par rapport au matériel (indépendance application /
plate forme matérielle).
3. Intermédiaire entre le langage machine (binaire) et le langage
humain
 Langages de programmation
• Le langage utilisé par le processeur, est appelé langage machine. Il s'agit
d'une suite de 0 et de 1 (du binaire). Toutefois le langage machine est
difficilement compréhensible par l'humain. Ainsi il est plus pratique de
trouver un langage intermédiaire, compréhensible par l'homme, qui sera
ensuite transformé en langage machine pour être exploitable par le
processeur.
• L'assembleur est le premier langage informatique qui ait été utilisé. Celui-ci
est encore très proche du langage machine mais il permet déjà d'être plus
compréhensible. Toutefois un tel langage est tellement proche du langage
machine qu'il dépend étroitement du type de processeur utilisé (chaque type
de processeur peut avoir son propre langage machine). Ainsi un programme
développé pour une machine ne pourra pas être porté sur un autre type de
machine (on désigne par le terme "portable « un programme qui peut être
utilisé sur un grand nombre de machines). Pour pouvoir l'utiliser sur une
autre machine il faudra alors parfois réécrire entièrement le programme!
Langages de programmation

Il y a trois catégories de langage de programmations : les langages

interprétés et les langages intermédiaires et les langages compilés.
•
Langages de programmation
 Langage interprété

Langage interprété est un langage de programmation par

définition différent du langage machine. Il faut donc le traduire pour le
rendre intelligible du point de vue du processeur. Un programme écrit
dans un langage interprété a besoin d'un programme auxiliaire
(l'interpréteur) pour traduire au fur et à mesure les instructions du
programme. Exemples de langages interprétés : Le langage HTML (les
pages web), le langage Maple (calcul mathématique), Prolog (Intelligence
artificielle), etc.
Langages de programmation
 Langages de programmation
 Langage compilé
Un programme écrit dans un langage dit "compilé" va être traduit une fois pour
toutes par un programme annexe (le compilateur) afin de générer un nouveau fichier qui sera
autonome, c'est- à-dire qui n'aura plus besoin d'un programme autre que lui pour s'exécuter
(on dit d'ailleurs que ce fichier est exécutable).
Un programme écrit dans un langage compilé a comme avantage de ne plus avoir besoin, une
fois compilé, de programme annexe pour s'exécuter. De plus, la traduction étant faite une fois
pour toute, il est plus rapide à l'exécution. Toutefois il est moins souple qu'un programme
écrit avec un langage interprété car à chaque modification du fichier source il faudra
recompiler le programme pour que les modifications prennent effet.
D'autre part, un programme compilé a pour avantage de garantir la sécurité du code source.
En effet, un langage interprété, étant directement intelligible (lisible), permet à n'importe qui
de connaître les secrets de fabrication d'un programme et donc de copier le code voire de le
modifier. Il y a donc risque de non-respect des droits d'auteur.
D'autre part, certaines applications sécurisées nécessitent la confidentialité du code pour
éviter le piratage (transaction bancaire, paiement en ligne, communications sécurisées, ...).
Exemples de langages compilés : Le langage C (Programmation système), le langage C++
(Programmation système objet), le Cobol (Gestion) etc.
Langages de programmation
Langages de programmation

 Langages intermédiaires
Certains langages appartiennent en quelque sorte aux deux
catégories précédentes (LISP, Java, Python, ..) car le programme écrit avec
ces langages peut dans certaines conditions subir une phase de
compilation intermédiaire vers un fichier écrit dans un langage qui n'est
pas intelligible (donc différent du fichier source) et non exécutable
(nécessité d'un interpréteur). Les applets Java, petits programmes insérés
parfois dans les pages Web, sont des fichiers qui sont compilés mais que
l'on ne peut exécuter qu'à partir d'un navigateur Internet (ce sont des
fichiers dont l'extension est .class).
La démarche de programmation

• La résolution d'un problème passe par toute une suite d'étapes :

• Phase d'analyse et de réflexion (algorithmique)
• Phase de programmation
- choisir un langage de programmation
- traduction de l'algorithme en programme
- programme (ou code) source
- compilation : traduction du code source en code objet
- traduction du code objet en code machine exécutable et
compréhensible par l'ordinateur
• • Phase de test
• Phase d’exécution
La démarche de programmation

Enoncé d’un problème Analyse du problème

Programmation à l’aide d’un langage

Algorithme
de programmation

Programme source Compilation

Exécution du programme Programme binaire

exécutable

Résultats
La démarche de programmation et analyse descendante
• Le travail est ici surtout basé sur l'analyse du problème et l'écriture de l'algorithme.
• La réalisation d'un programme passe par l'analyse descendante du problème : il faut
réussir à trouver les actions élémentaires qui, en partant d'un environnement initial,
nous conduisent à l'état final.
• L’analyse descendante consiste à décomposer le problème donné en sous-problèmes, et
ainsi de suite, jusqu’à descendre au niveau des primitives.
• Les étapes successives donnent lieu à des sous algorithmes qui peuvent être considérés
comme les primitives de machine intermédiaires (procédures en Pascal, fonction en C).
• Le travail de l’analyse est terminé lorsqu’on a obtenu un algorithme ne comportant que :
•
• Des primitives de la machine initiale,
• Des algorithmes déjà connus.
L’approche descendante
L’approche ascendante
Pseudo langage

• Un algorithme doit être lisible et compréhensible par plusieurs

personnes. Il doit donc suivre des règles précises, il est composé de trois
parties principales :
• l’entête : cette partie sert à donner un nom à l’algorithme. Elle est
précédée par le mot Algorithme;
• La partie déclarative : dans cette partie, on déclare les différents objets
que l’algorithme utilise;
• Le corps de l’algorithme : cette partie contient les instructions de
l’algorithme. Elle est délimitée par les mots Début et Fin
Pseudo langage

• Le plus important pour un algorithme sont les déclarations ainsi

que les instructions qui constituent le corps de l’algorithme. Il existe
des instructions qui ne servent qu’à la clarté de l’algorithme
(l’ordinateur les ignore complètement), ce sont les commentaires. Un
commentaire a la syntaxe suivante :
• /* ceci est un commentaire */
Pseudo langage

Entête Algorithme : NomAlgorithme

Partie déclarative Constante Identificateur = valeur

Variable Identificateur : Type

Début
Instruction 1
Corps de Instruction 2
l’algorithme …….
Instruction n
Fin

Structure de base d’un algorithme