Chap 1 Algo 2014

Télécharger au format doc, pdf ou txt
Télécharger au format doc, pdf ou txt
Vous êtes sur la page 1sur 4

Année académique 2013/2014 ALGORITHMIQUE ISIG IT/ELN 1

Chapitre 1 : NOTION D’ALGORITHME et LDA

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.

2. Etapes d’écriture d’un algorithme

On retrouve généralement trois étapes dans la construction d’un algorithme :


comprendre la nature du problème posé et préciser les données fournies (entrées ou input).
préciser les résultats que l’on désire obtenir (sorties ou output).
déterminer le processus de transformation des données en résultats.
Les trois étapes ne sont pas indépendantes et leur ordre peut être modifié.
Si l’algorithme est juste, il conduit au résultat escompté ; sinon il conduit à un résultat aléatoire.

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 …

II. NOTATIONS ALGORITHMIQUES

Il existe plusieurs conventions de représentations des algorithmes, essentiellement deux :


la représentation graphique et le pseudo code.

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.

On ne doit avoir qu’un seul symbole de ce type


Débu
t dans un organigramme.
Il indique le point de départ de l’algorithme
Symbole de début décrit.
A désigne un traitement quelconque. Lorsqu’on
arrive à une boîte rectangulaire par un arc
A
entrant, on exécute le traitement associé avant
de poursuivre suivant l’arc sortant qui est
La boîte rectangulaire unique.
C désigne une condition c'est-à-dire une
expression logique.
V F
C Lorsqu’on arrive dans un losange par un arc
entrant, on évalue la condition associée. Si le
Le losange résultat est vrai on doit poursuivre par l’arc
étiqueté par vrai « V », sinon on doit poursuivre
par l’arc étiqueté par faux « F »
Tout organigramme doit contenir au moins le
symbole de fin. Il sert à indiquer la marque de
fin du déroulement de l’algorithme décrit.
Fin

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

2. Structure d’un algorithme en pseudo-code

A/ Idée générale (bloc facultatif)


Bloc décrivant les principes généraux qui ont guidé la construction de la solution Ces principes
généraux peuvent concerner les règles de calcul ou la structuration du calcul des données.
B/ Données
On retrouve dans ce bloc les données fournies en entrées et qui peuvent être classées en
données constantes (exemple Taux TVA) et en données variables (exemple NbreKWH).
B.1/ Constantes (bloc facultatif)
B.2/ Variables
C/ Variables intermédiaires ou de travail (bloc facultatif)
Bloc décrivant les variables utilisées pour des calculs intermédiaires.
D/ Résultats
Bloc décrivant les résultats que doit fournir l’algorithme.
E/ Enchaînement des opérations
Début
Bloc de description et de l’enchaînement des différentes instructions (actions) de
transformation des données en résultats.
Fin

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

Dans ce bloc figurent toutes les déclarations de constantes, variables, types …


DEBUT

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

3. Qualités d’un bon algorithme ou d’un bon programme

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

Vous aimerez peut-être aussi