ALGORITHMIQUE

L ANGAGE
16
ET COMPLEXITÉ
16.1 P OURQUOI UN AUTRE LANGAGE ?
L’informatique comprend de nombreux langages de programmation (C, C++, Java,
Caml, Fortran, Pascal, Lisp, Prolog, Cobol, etc.). Programmer dans tous ces langage
requiert une connaissance de base qui est indé pendante du langage de programma-
tion : l’algorithmique. Pour cela, on doit distinguer les algorithmes, qui sont des
méthodes applicables par des ordinateurs pour ré soudre diffé rents problè mes, de leur
implé mentation dans tel ou tel langage particulier.
Nous é tudions dans ce chapitre un langage algorithmique qui n’est pas un langage
de programmation. Ce langage n’est pas trè s é loigné conceptuellement du langage C
é tudié jusqu’à maintenant, mais il permet tout de mê me de concevoir les algorithmes
indé pendamment de leur implé mentation en C.

16.2 T YPES
Les types de base du langage sont :
• entier : c’est le type nombre entier, correspondant au type int du C, sauf qu’il
n’est pas nécessairement codé sur 4 octets.
• reel : c’est le type nombre réel, pouvant correspondre avec les types double ou
float du C.
• caractere : c’est le type caractè re, correspondant au type char du C. Pour un tel
caractere c, la fonction ASCII(c) donnera le code ASCII de c.

16.3 E NTRÉES - SORTIES

16.3.1 Clavier et écran
La fonction lire permet de lire une variable. Si x est une variable (de type entier,
© Dunod. La photocopie non autorisé e est un dé lit.

ré el, caractè re ou chaîne de caractères), l’instruction :

Lire(x);

permet de lire au clavier la valeur de x.

La fonction ecrire permet d’é crire le contenu d’une variable à l’écran. Si x est
une variable (de type entier, réel, caractère ou chaîne de caractè res), l’instruction :
ecrire(x);

permet d’afficher la valeur de x.

157
Chapitre 16 • Langage algorithmique et complexité

16.3.2 Fichiers texte

Le type fichier permet de lire et d’écrire dans un fichier. Pour cela, il faut d’abord
dé clarer et ouvrir un fichier :

Fichier f;
f ← ouvrir("nom.txt", "lect");

Les modes d’ouverture de fichiers peuvent ê tre "lect" (lecture seule), "ecr"
(é criture seule), ou bien le mode lecture-é criture "lectEcr".
La fonction lireF permet de lire une variable dans un fichier. Si x est de type
entier, ré el, caractè re ou chaîne de caractè res, et f un fichier ouvert en lecture, l’ins-
truction :

lireF(x, f);

met dans x la première valeur lue dans le fichier (et avance la position courante
dans le fichier).
La fonction ecrireF permet d’é crire une variable dans un fichier texte. Si x est de
type entier, ré el, caractè re ou chaîne de caractè res, et f un fichier ouvert en é criture,
l’instruction :

ecrireF(x, f);

permet d’é crire la valeur de x dans le fichier (et avance la position courante dans le
fichier).

16.4 S YNTAXE
L’affectation est noté e ←, le test d’égalité est noté =.

Exemple 1
L’algorithme suivant calcule et affiche 2n , où n est saisi au clavier.
Algorithme
début
entier i, n, puiss;
puiss ← 1;
lire(n);
pour i ← 0 à n-1 pas 1 faire
puiss ← puiss * 2;
fin faire
ecrire(puiss);
fin

158
 16.5. Fonctions et procédures

Exemple 2
Voici une version interactive de l’algorithme précédent :
Algorithme
début
entier i, n, puiss;
caractere choix;
ecrire("Voulez-vous calculer une puissance de 2 ? ")
lire(choix);
si choix = ’y’ faire
puiss ← 1;
i ← 0;
lire(n);
tant que i<n faire
puiss ← puiss * 2;
i ← i+1
fin faire
ecrire(puiss);
fin faire
fin

16.5 F ONCTIONS ET PROCÉDURES

16.5.1 Fonctions
Une fonction en langage algorithmique aura un prototype de la forme :

FONCTION NomFonction(Type1 nom1, type2 nom2,...): TypeRetour

où :
• TypeRetour est le type de la valeur retourné e par la fonction ;
• NomFonction est le nom de la fonction ;
• Type1, Type2... sont les types respectifs des paramè tres ;
• nom1, nom2... sont les identificateurs respectifs des paramè tres.
© Dunod. La photocopie non autorisé e est un dé lit.

Exemple 3
L’algorithme ci-dessus calculant 2n peut être restructuré à l’aide d’une fonction :

FONCTION DeuxPuiss(entier n): entier

début
entier i, puiss;
puiss ← 1;
pour i ← 0 à n-1 pas 1 faire
puiss ← puiss * 2;
fin faire

159
Chapitre 16 • Langage algorithmique et complexité

retourner puiss;
fin

Algorithme
début
entier n, puiss;
lire(n);
puiss ← DeuxPuiss(n);
ecrire(puiss);
fin

16.5.2 Procédures
Une procé dure est similaire à une fonction, mais elle ne retourne aucune valeur. Une
procé dure aura un prototype de la forme :

PROCEDURE NomFonction(Type1 nom1, typ2 nom2,...)

Exemple 4
Dans l’ exemple suivant, la procédure Affiche permet l’ affichage d’une donnée de
type entier.
FONCTION DeuxPuiss(entier n): entier
début
entier i, puiss;
puiss ← 1;
pour i ← 0 à n-1 pas 1 faire
puiss ← puiss * 2;
fin faire
retourner puiss;
fin

PROCEDURE Affiche(entier a)
début
ecrire("l’entier vaut : ");
ecrire(a);
fin

Algorithme
début
entier n, puiss;
lire(n);
puiss ← DeuxPuiss(n);
Affiche(puiss);
fin

160
 16.6. Enregistrements

16.6 E NREGISTREMENTS
Un enregistrement correspond à une structure C.

Exemple 5
enregistrement TypeArticle
début
entier code;
caractere nom[100];
reel prix;
fin

PROCEDURE Affiche(TypeArticle A)
début
ecrire(A.code);
ecrire(A.nom);
ecrire(A.prix);
fin

Algorithme
début
TypeArticle A;
ecrire("Entrez le code, le nom et le prix");
lire(A.code, A.nom, A.prix);
Affiche(A);
fin

16.7 P OINTEURS , ADRESSES ET ALLOCATION

En langage algorithmique, les pointeurs et adresses fonctionnent comme en C.

entier n;
entier *p;
n ← 2;
p ← &n;
© Dunod. La photocopie non autorisé e est un dé lit.

*p ← *p+1;
ecrire(n); /* affiche 3 */

La diffé rence avec le C se situe au niveau des fonctions d’allocation. L’opé rateur
nouveau permet d’allouer de la mémoire en langage algorithmique.

Exemple 6

enregistrement TypeArticle
début
entier code;

161
Chapitre 16 • Langage algorithmique et complexité

caractere nom[100];
reel prix;
fin

FONCTION AlloueTableau(entier* adr_n): TypeArticle*

début
TypeArticle *resultat;
entier n;
ecrire("Entrez le nombre d’éléments : ");
lire (n);
*adr_n = n;
/* allocation d’un tableau de n TypeArticle */
resultat ← nouveau TypeArticle[n];
retourner resultat;
fin

16.8 N OTION DE COMPLEXITÉ

D ’ UN ALGORITHME

16.8.1 Définition intuitive de la complexité

La complexité d’un algorithme est une estimation du nombre d’opé rations de base
effectué es par l’algorithme en fonction de la taille des donné es en entré e de l’algo-
rithme.
Par exemple, si un algorithme é crit dans une fonction prend en entrée un tableau
de n é lé ments, la complexité de l’algorithme sera une estimation du nombre total
d’opé rations de base né cessaires pour l’algorithme, en fonction de n. Plus n sera
grand, plus il faudra d’opé rations. La nature de l’algorithme sera diffé rente selon que
sa complexité sera plutô t de l’ordre de n, de n2 , de n3 , ou bien de 2n . Le temps de
calcul pris par l’algorithme ne sera pas le mê me.
Une opé ration de base pourra ê tre une affectation, un test, une incré mentation, une
addition, une multiplication, etc.

16.8.2 Notion de grand O

On appelle opé ration de base, ou opération é lé mentaire, toute affectation, test de
comparaison =, >, <, ≤, . . ., opération arithmétique +, −, ∗, /, appel de fonctions
comme sqrt, incré mentation, dé crémentation. Lorsqu’une fonction ou une procé -
dure est appelé e, le coû t de cette fonction ou procé dure est le nombre total d’opé ra-

162
 16.8. Notion de complexité d’un algorithme

tions é lé mentaires engendrées par l’appel de cette fonction ou procé dure. Le temps
de calcul pris par l’algorithme (sur une machine donné e) est directement lié à ce
nombre d’opé rations.
En fait, il est hors de question de calculer exactement le nombre d’opé rations en-
gendré es par l’application d’un algorithme. On cherche seulement un ordre de gran-
deur (voir figure 16.1). L’ordre de grandeur asymptotique est l’ordre de grandeur
lorsque la taille des donné es devient trè s grande.
O(2 n)
nombre d’opérations

O(n 3)

)
O (n 2

n )
og
nl
O(
)
O (n

zone √
O ( n)

transitoire O(log n)

O(1)

n
Figure 16.1– Ordres de grandeurs asymptotiques

Soit un algorithme dé pendant d’une donné e d de taille n (par exemple un tableau de

n é lé ments). Notons NB = (d, n) le nombre d’opé rations engendrées par l’algorithme.
On dit que l’algorithme est en O(n) si et seulement si on peut trouver un nombre
© Dunod. La photocopie non autorisé e est un dé lit.

K tel que (pour n assez grand) :

NB(d, n) ≤ K.n

Dans ce cas, on dit aussi que l’algorithme est liné aire.

On dit que l’algorithme est en O(n2 ) si et seulement si on peut trouver un nombre
K tel que (pour n assez grand) :

NB(d, n) ≤ K.n2

Dans ce cas, on dit aussi que l’algorithme est quadratique.

163
Chapitre 16 • Langage algorithmique et complexité

On dit que l’algorithme est en O(2n ) si et seulement si on peut trouver un nombre

K tel que (pour n assez grand)

NB(d, n) ≤ K.2n

Dans ce cas, on dit aussi que l’algorithme est exponentiel.

Exercices

Pour chacun des exercices de cette partie, on é valuera la complexité de l’algorithme

proposé .

16.1 (∗) É crire un algorithme qui initialise un tableau de n entiers, le nombre n é tant
saisi au clavier, la valeur d’indice i du tableau valant 1 si 3i2 + i − 2 est multiple de 5
et 0 sinon.

16.2 (∗) É crire une fonction en langage algorithmique qui prend en paramè tre un
entier i et calcule la valeur u(i) dé finie par récurrence par :

u0 = 1 ; u1 = 2

u j+1 = 3 ∗ u j − u j−1 pour j ≥ 1

16.3 (∗) É crire une fonction en langage algorithmique qui saisit les éléments d’un
tableau dont le nombre d’é lé ments n est passé en paramè tre. On supposera que le
tableau a déjà é té alloué et est passé en paramè tre.

16.4 (∗) É crire une fonction en langage algorithmique qui prend en paramè tre un
entier n et un tableau à deux dimensions de taille n × n d’entiers. La fonction calcule
la somme des é lé ments du tableau.

16.5 (∗∗) É crire une fonction en langage algorithmique qui calcule les valeurs d’un
tableau T de taille n, le nombre n é tant saisi au clavier, dont les valeurs T [i] sont
telles que T [0] = 1 et pour i ≥ 1 :

T [i] = i ∗ (T [0] + T [1] + · · · + T [i − 1])

16.6 (∗∗) Soit la fonction

3x2 + x + 1 si x ≥ 1
f (x) =
0 sinon

164
 Exercices

a) É crire une fonction en langage algorithmique qui prend en paramè tre un entier x
et calcule f (x).

b) É crire une fonction en langage algorithmique qui prend en paramè tre un entier n
et calcule la somme :

S n = f (n) + f (n − 1) + f (n − 2) + f (n − 3) + f (n − 4) + · · ·
On arrê tera la somme lorsque la valeur f calculé e est nulle.

c) É crire une fonction en langage algorithmique qui prend en paramè tre un entier n
et calcule la somme :

T n = f (n) + f (n/22 ) + f (n/32 ) + f (n/42 ) + f (n/52 ) + · · ·

Dans cette somme, les divisions sont des divisions euclidiennes. On arrê tera la
somme lorsque la valeur f calculé e est nulle.

d) É crire une fonction en langage algorithmique qui prend en paramè tre un entier n
et calcule la somme :

Un = f (n) + f (n/2) + f (n/4) + f (n/8) + f (n/16) + · · ·

Dans cette somme, les divisions sont des divisions euclidiennes. On arrê tera la
somme lorsque la valeur f calculé e est nulle.

16.7 (∗ ∗ ∗) (Recherche dichotomique) On cherche à savoir si un tableau de n

nombres entiers contient une certain nombre a. On suppose que le tableau est trié
dans l’ordre croissant, c’est-à-dire que chaque é lément est infé rieur ou é gal au sui-
vant dans le tableau.
On pourrait é videmment tester tous les nombres du tableau en les comparant à a,
mais cela nécessiterait (dans le pire des cas) n comparaisons. On se propose d’appli-
© Dunod. La photocopie non autorisé e est un dé lit.

quer une mé thode qui né cessite moins d’opé ration. La mé thode s’appelle la recherche
dichotomique.
À chaque é tape, on recherche un é lé ment é gal à a entre deux indices imin et imax . Au
dé part, l’élément peut se trouver n’importe où (entre imin = 0 et imax = n − 1).
On compare l’é lé ment d’indice i = (imin + imax )/2 avec a. Trois cas peuvent se pro-
duire :

• Si l’é lé ment d’indice i est égal à a, l’algorithme se termine : le nombre a se trouve

bien dans le tableau.

165
Chapitre 16 • Langage algorithmique et complexité

• Si l’é lé ment d’indice i est supé rieur à a, un é lé ment é gal à a ne peut se trouver qu’à
un indice plus petit que i, puisque le tableau est trié. Le nouvel imax vaut i − 1.
• Si l’é lé ment d’indice i est inférieur à a, un é lément é gal à a ne peut se trouver qu’à
un indice plus grand que i. Le nouvel imin vaut i + 1.

Á chaque é tape, un élé ment é gal à a ne peut se trouver qu’entre imin et imax . On itè re
ce procé dé jusqu’à ce que imin devienne strictement supé rieur à imax . Il ne reste plus
qu’à tester un seul é lé ment.
Comme à chaque é tape le nombre d’é léments est divisé par 2, le nombre k d’étapes
n
est tel que k ≥ 1. Donc k ≤ log2 (n).
2
a) É crire une de recherche dichotomique d’un nombre x dans un tableau de n
nombres. La fonction renvoie 1 si l’élément se trouve dans le tableau et 0 sinon.

b) Quelle est la complexité ?

Corrigés

16.1
Algorithme
début
entier i, n, puiss;
entier *tab;
lire(n);
tab ← nouveau entier[n];
pour i ← 0 à n-1 pas 1 faire
si (3*i*i+i-2)%5 = 0 faire
tab[i] ← 1;
sinon faire
tab[i] ← 0;
fin faire
fin

166
 Corrigés

La complexité est de O(n)

16.2
FONCTION Calculu(entier i): entier
début
entier j;
entier U0, U1, U2;
U0 ← 1;
U1 ← 2;
si i=0 faire
retourner U0;
fin faire
si i=1 faire
retourner U1;
fin faire
j ← 2;
tant que j<=i faire
U2 ← 3 * U1-U0;
U0 ← U1;
U1 ← U2;
j ← j+1;
fin faire
retourner U2;
fin
La complexité est de O(i)

16.3
PROCEDURE Saisit(entier n, entier *tab)
début
entier i;
pour i ← 0 à n-1 pas 1 faire
lire (tab[i]);
fin faire
fin
© Dunod. La photocopie non autorisé e est un dé lit.

La complexité est de O(n)

16.4
FONCTION Somme(entier n,entier **tab): entier
début
entier i, j;
entier somme ← 0;
pour i ← 0 à n-1 pas 1 faire
pour j ← 0 à n-1 pas 1 faire

167
Chapitre 16 • Langage algorithmique et complexité

somme ← somme + tab[i][j];

fin faire
fin faire
retourner somme;
fin
La complexité est de O(n2 )

16.5
FONCTION CalculerT(entier *nb): entier *
début
entier n, i;
entier *tab;
lire(n);
*nb ← n;
tab ← nouveau entier[n];
tab[0] ← 1;
pour i ← 0 à n-1 pas 1 faire
tab[i] ← 0;
pour j ← 0 à i-1 pas 1 faire
tab[i] ← tab[i] + tab[j];
fin faire
tab[i] ← tab[i]*i;
fin faire
retourner tab;
fin
La complexité est de O(n2 )

16.6
a)
FONCTION CalculerFx(entier x): entier
début
si x<1 faire
retourner 0;
fin faire
retourner 3*x*x+x+1;
fin
La complexité est de O(1)
b)
FONCTION CalculerSn(entier n): entier
début
entier j ← n;

168
 Corrigés

entier S ← 0;
tant que j>0 faire
S ← S + CalculerFx(j);
j ← j-1;
fin faire
retourner S;
fin
La complexité est de O(n)
c)
FONCTION CalculerTn(entier n): entier
début
entier i, j, Fx;
entier T ← 0;
i ← n;
j ← 2;
Fx ← CalculerFx(i);
tant que Fx !=0 faire
T ← T + Fx;
i ← n/(j*j);
j ← j+1;
Fx ← CalculerFx(i);
fin faire
retourner T;
fin
√
La complexité est de O( n)
d)
FONCTION CalculerUn(entier n): entier
début
entier i, j, Fx;
entier U ← 0;
i ← n;
j ← 1;
© Dunod. La photocopie non autorisé e est un dé lit.

Fx ← CalculerFx(i);
tant que Fx !=0 faire
U ← U + Fx;
j ← j * 2;
i ← n/j;
Fx ← CalculerFx(i);
fin faire
retourner U;
fin
La complexité est de O(log2 (n))

169
Chapitre 16 • Langage algorithmique et complexité

16.7
a)
FONCTION Recherchedicho(entier a, entier *tab, entier n): entier
début
entier debut ← 0, fin ← n-1, milieu;
tant que debut <=fin faire
milieu ← (debut+fin)/2;
si a= tab[milieu] faire
retourner 1;
si a < tab[milieu] faire
fin=milieu-1;
sinon faire
debut=milieu + 1;
fin faire
retourner 0;
fin
b) La complexité est de O(log2 (n))

170