Chap 1 Algo 2014
Chap 1 Algo 2014
Chap 1 Algo 2014
I. GENERALITES
1. Définitions
L’algorithme est une suite d’opérations à exécuter sur un certain ensemble de données dans un
ordre précis afin d’obtenir un certain résultat.
Selon le Robert : l’algorithme est un ensemble de règles opératoires propre à un calcul. Le calcul
étant dans ce cas un enchaînement d’actions nécessaires à l’accomplissement d’une tache.
Le nom algorithme provient de la contraction et de la déformation du nom d’un célèbre
mathématicien arabe de la première moitie du IXe siècle : Ibn Musa Al Khwarizmi.
Selon Knuth dans son livre « The art of computer programming », l’algorithme est un ensemble de
règles (instructions) ayant les caractéristiques suivantes :
1/ Il doit être fini, et se terminer après un nombre fini d’opérations.
2/ Il doit être défini et précis : chaque instruction doit être définie sans ambiguïté.
3/ S’il y a des données d’entrée, les champs d’application doivent être précisé (entier, réel, …).
4/ Il doit posséder au moins un résultat en sortie
5/ Il doit être effectif : toutes les opérations doivent pouvoir être exécutées exactement et dans un
temps fini par un homme utilisant des moyens manuels.
L’algorithmique est la science des algorithmes, l’art de bâtir des algorithmes. Il a pour but de
concevoir les algorithmes, d’analyser leurs performances, et de comparer entre eux différents
algorithmes résolvant les mêmes problèmes.
3. Analogie
Pour comprendre davantage l’objet de l’algorithmique, on peut faire remarquer que, dans la vie
courante, de nombreuses activités sont en fait des algorithmes mis en application (nous en avons
alors plus ou moins conscience).
L’exemple le plus typique est une recette de cuisine (Expliquer pourquoi !).
On pourrait citer le fonctionnement d’un robot …
1. La représentation graphique
La représentation graphique est une représentation dans laquelle l’algorithme est écrit sous forme
d’organigramme(on dit aussi algorigramme ou ordinogramme ).
Page 1 sur 4
Année académique 2013/2014 ALGORITHMIQUE ISIG IT/ELN 1
La construction des organigrammes s’appuie sur quelques symboles de base qu’on relie à l’aide
d’arcs orientés.
Symbole de fin
Dans le passé, la représentation graphique était utilisée pour écrire les algorithmes. Aujourd’hui,
elle 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. Ensuite parce que cette représentation favorise
la programmation non structurée (Suite de branchements).
Pour pallier aux insuffisances de la notation sous forme d’organigramme, on utilise généralement
une série de conventions appelée "pseudo-code" ou "langage de description algorithmique"
(LDA), qui ressemble à un langage authentique, les problèmes de syntaxe étant mis de côté.
Page 2 sur 4
Année académique 2013/2014 ALGORITHMIQUE ISIG IT/ELN 1
Page 3 sur 4
Année académique 2013/2014 ALGORITHMIQUE ISIG IT/ELN 1
En pratique, nous adopterons dans l’écriture de nos algorithmes, le schéma minimaliste suivant :
PROGRAMME <nom_du_programme>
VAR
Ici se situe l’essentiels de l’algorithme (le corps) i.e les instructions (ou actions)
détaillées qui vont conduire au résultat du problème
FIN
L’algorithme et le programme étant liés, pour avoir un bon programme, il faut partir d’un bon
algorithme. Un bon algorithme doit posséder les qualités suivantes :
Etre clair et facile à comprendre pour tous ceux qui le lisent (structure et documentation). Ne
donc pas omettre les commentaires lors de l’écriture.
Etre le plus général possible afin de répondre au plus grand nombre de cas.
Etre d’utilisation aisée notamment grâce à un dialogue clair et précis avec l’utilisateur.
Etre optimisé afin d’être performant tant au niveau de l’occupation disque que du temps
d’exécution. Ceci fait l’objet de la complexité des algorithmes ou analyse des algorithmes
(chapitre qui sera vu si temps disponible).
Page 4 sur 4