ce que l’algorithme est censé faire. Cependant, si les algorithmes complexes devaient être écrits ainsi, ce serait
encore une fois bien trop long et vous finiriez soit par vous lasser d’une écriture trop complexe, soit cela prendrait
trop de place. C’est pourquoi il faut utiliser une syntaxe précise et concise.
/* Commentaires : ce programme affiche bonjour */
PROGRAMME HelloWorld
/* Déclarations : variables, constantes, types, etc */
VAR
de:entier,
valeur:entier
/* Début du programme */
DEBUT
de←aléatoire(6)
valeur←0
Tant que valeurde Faire
Lire valeur
FinTantQue
Afficher "Bravo"
FIN
Si vous comprenez déjà le programme cidessus alors cet ouvrage vous sera encore plus agréable à lire. Sinon, la
suite vous donnera de toute façon toutes les explications nécessaires à la compréhension de chaque ligne de cet
algorithme. Il reprend de manière très détaillée toutes les étapes à suivre. Sous cette forme, il est presque possible
d’implémenter l’algorithme ligne à ligne dans un langage de programmation évolué.
C’est sous cette forme textuelle que les algorithmes seront représentés dans ce livre. Ce texte, programme ou
pseudocode algorithmique, est décomposé en plusieurs parties:
q Le nom du programme, qui n’amène pas de commentaires particuliers, situé après le mot "PROGRAMME".
q Une zone de déclaration des données utilisées par le programmes: variables, constantes, types, structures,
tableaux, etc. Si la signification de ces mots vous échappe, ceuxci seront expliqués au fur et à mesure des
différents chapitres. Cette zone commence par le mot "VAR".
q Le programme luimême, c’estàdire les divers traitements. Les instructions du programme sont encadrées
par les mots "DEBUT" et "FIN". Il vous est conseillé, pour plus de clarté et de lisibilité, d’indenter les diverses
lignes (de les décaler les unes par rapport aux autres) à l’aide des touches de tabulation. Le programme peut
être de n’importe quelle longueur: une ligne ou 10000 lignes, ceci n’a pas d’importance.
q Les commentaires: c’est un texte libre qui peut être étendu sur plusieurs lignes et encadré par les séquences
de caractères "/*" et "*/". Si votre commentaire tient sur une seule ligne, vous pouvez uniquement la
commencer par les caractères "//".
q Une dernière partie, ou plutôt première car lorsqu’elle est présente elle se situe avant toutes les autres, peut
être constituée des sousprogrammes, semblants de programmes complets appelés par le programme
principal. Ces sous programmes, appelés procédures ou fonctions, font l’objet d’un chapitre complet.
5. La complexité
L’exemple du lancé de dé est un algorithme très simple, court, concis et rapide. Ce n’est pas le cas de tous les
algorithmes. Certains sont complexes et le traitement résultant peut nécessiter beaucoup de temps et de ressources
de la machine. C’est ce qu’on appelle le "coût" de l’algorithme, et il est calculable. Si un algorithme est "gourmand" son
coût sera plus élevé. Il existe certains cas où il est possible d’utiliser plusieurs algorithmes pour effectuer une même
tâche, comme pour trier les éléments d’un tableau de valeurs. Certains algorithmes se révèlent être plus coûteux que
d’autres, passé un certain nombre d’éléments à trier. Le coût d’un algorithme reflète sa complexité ou en terme plus
simple son efficacité. Les mots "coût", "complexité" et "efficacité" reflètent ici la même définition. Plus un algorithme est
complexe, plus il est coûteux et moins il est efficace. Le calcul de cette complexité a comme résultat une équation
mathématique qu’on réduit généralement ensuite à une notion d’ordre général.
La complexité est noté O(f(n)) où le O (grand O) veut dire "d’ordre" et f est la fonction mathématique de n qui est la
quantité d’informations manipulée dans l’algorithme. Voici un exemple pour mieux comprendre : soit un algorithme qui
compte de 1 à n et qui affiche les valeurs correspondantes. Dans la pratique, vous allez utiliser une boucle (voir
chapitre correspondant) allant de 1 à n. Il faudra faire n passages pour tout afficher et donc vous aller manipuler n fois
l’information. La fonction mathématique donnant le coût sera alors f(n)=n. La complexité est alors linéaire et vous la
noterez O(n).
- 4 -
© ENI Editions - All rigths reserved - Jonifar lina
12
encore une fois bien trop long et vous finiriez soit par vous lasser d’une écriture trop complexe, soit cela prendrait
trop de place. C’est pourquoi il faut utiliser une syntaxe précise et concise.
/* Commentaires : ce programme affiche bonjour */
PROGRAMME HelloWorld
/* Déclarations : variables, constantes, types, etc */
VAR
de:entier,
valeur:entier
/* Début du programme */
DEBUT
de←aléatoire(6)
valeur←0
Tant que valeurde Faire
Lire valeur
FinTantQue
Afficher "Bravo"
FIN
Si vous comprenez déjà le programme cidessus alors cet ouvrage vous sera encore plus agréable à lire. Sinon, la
suite vous donnera de toute façon toutes les explications nécessaires à la compréhension de chaque ligne de cet
algorithme. Il reprend de manière très détaillée toutes les étapes à suivre. Sous cette forme, il est presque possible
d’implémenter l’algorithme ligne à ligne dans un langage de programmation évolué.
C’est sous cette forme textuelle que les algorithmes seront représentés dans ce livre. Ce texte, programme ou
pseudocode algorithmique, est décomposé en plusieurs parties:
q Le nom du programme, qui n’amène pas de commentaires particuliers, situé après le mot "PROGRAMME".
q Une zone de déclaration des données utilisées par le programmes: variables, constantes, types, structures,
tableaux, etc. Si la signification de ces mots vous échappe, ceuxci seront expliqués au fur et à mesure des
différents chapitres. Cette zone commence par le mot "VAR".
q Le programme luimême, c’estàdire les divers traitements. Les instructions du programme sont encadrées
par les mots "DEBUT" et "FIN". Il vous est conseillé, pour plus de clarté et de lisibilité, d’indenter les diverses
lignes (de les décaler les unes par rapport aux autres) à l’aide des touches de tabulation. Le programme peut
être de n’importe quelle longueur: une ligne ou 10000 lignes, ceci n’a pas d’importance.
q Les commentaires: c’est un texte libre qui peut être étendu sur plusieurs lignes et encadré par les séquences
de caractères "/*" et "*/". Si votre commentaire tient sur une seule ligne, vous pouvez uniquement la
commencer par les caractères "//".
q Une dernière partie, ou plutôt première car lorsqu’elle est présente elle se situe avant toutes les autres, peut
être constituée des sousprogrammes, semblants de programmes complets appelés par le programme
principal. Ces sous programmes, appelés procédures ou fonctions, font l’objet d’un chapitre complet.
5. La complexité
L’exemple du lancé de dé est un algorithme très simple, court, concis et rapide. Ce n’est pas le cas de tous les
algorithmes. Certains sont complexes et le traitement résultant peut nécessiter beaucoup de temps et de ressources
de la machine. C’est ce qu’on appelle le "coût" de l’algorithme, et il est calculable. Si un algorithme est "gourmand" son
coût sera plus élevé. Il existe certains cas où il est possible d’utiliser plusieurs algorithmes pour effectuer une même
tâche, comme pour trier les éléments d’un tableau de valeurs. Certains algorithmes se révèlent être plus coûteux que
d’autres, passé un certain nombre d’éléments à trier. Le coût d’un algorithme reflète sa complexité ou en terme plus
simple son efficacité. Les mots "coût", "complexité" et "efficacité" reflètent ici la même définition. Plus un algorithme est
complexe, plus il est coûteux et moins il est efficace. Le calcul de cette complexité a comme résultat une équation
mathématique qu’on réduit généralement ensuite à une notion d’ordre général.
La complexité est noté O(f(n)) où le O (grand O) veut dire "d’ordre" et f est la fonction mathématique de n qui est la
quantité d’informations manipulée dans l’algorithme. Voici un exemple pour mieux comprendre : soit un algorithme qui
compte de 1 à n et qui affiche les valeurs correspondantes. Dans la pratique, vous allez utiliser une boucle (voir
chapitre correspondant) allant de 1 à n. Il faudra faire n passages pour tout afficher et donc vous aller manipuler n fois
l’information. La fonction mathématique donnant le coût sera alors f(n)=n. La complexité est alors linéaire et vous la
noterez O(n).
- 4 -
© ENI Editions - All rigths reserved - Jonifar lina
12