Université Ibn Tofail

Faculté des Sciences

Département d’Informatique

Cours : Algorithmique II

SMI - Semestre 3

Pr. A. MOULOUDI

Année universitaire 2016/2017

1
[Link]
 Plan du cours

Chapitre 1 : Compléments algorithmiques (3 séances)

• Rappels
• Fonctions et procédures
o Les sous-programmes
o Notions de variables locales, globales et de paramètres
o Procédures sans paramètres
o Procédures avec paramètres fixes
o Fonctions et Procédures avec paramètres modifiables
• Types structurés et enregistrements
o Déclaration d'un type structuré
o Déclaration d'un enregistrement à partir d'un type structuré
o Manipulation d'un enregistrement
• Fichiers
o Généralités sur les fichiers
o Les accès aux fichiers
o Manipulation des fichiers

Chapitre 2 : Récursivité (2 séances)

• Définitions et exemples
• Types de récursivité
• Dérécursification

Chapitre 3 : Conception des algorithmes (2 séances)

• Analyse du problème
• Approche incrémentale
• Recherche exhaustive
• Méthodes approchées
o Algorithme glouton
o Diviser pour régner
o Heuristiques

Chapitre 4 : Complexité algorithmique (3 séances)

• Introduction à la complexité
• Notations asymptotiques
• Calcul de la Complexité d’algorithmes
• Complexité des algorithmes récursifs
• Analyse des algorithmes de tri

Chapitre 5 : Preuve d’algorithmes (2 séances)

• Introduction à la notion de preuve
• Preuves de la correction d’un algorithme

2
[Link]
Chapitre 1 : Compléments algorithmiques

Chapitre 1

Compléments algorithmiques
I. Rappels
I.1 INTRODUCTION

L’algorithmique est une science apparue, il y a très longtemps, bien avant l’idée
même d’ordinateur.
• Citons, vers 1800 avant J-C, les babyloniens de l’époque d’Hammurabi
formulant des règles précises pour la résolution de certains types d’équations.
• Plus tard, au 3ème siècle avant J-C, chez les grecs, fleurisse un grand nombre de
procédés de calcul, dont le célèbre algorithme d'Euclide.
• En Perse, au 9ème siècle après J-C, on trouve l’origine du mot «algorithme », qui
provient du nom de Abu Ja'far Mohammed Ibn Mûsâ Al-Khowâ-rismi, qui écrit
un ouvrage d’arithmétique utilisant les règles de calcul sur la représentation
décimale des nombres, et montra l’inutilité des tables et abaques. Il eut une
influence capitale pendant plusieurs siècles.
• Au fil du temps, la signification du mot s’élargit et finalement vient à désigner
tout procédé de calcul systématique, voire automatique, mais sans référence
nécessaire à une machine.
• Côté informatique du 21ème siècle et en première approche, on peut dire qu'un
algorithme est un « mode d'emploi pour résoudre un problème ».

I.2 NOTION D’ALGORITHME

I.2.1 Qu’est-ce qu’un algorithme ?

Définition
Un algorithme est un procédé de calcul automatique composé d’un ensemble
fini d’étapes, chaque étape étant formée d’un nombre fini d’étapes élémentaires, qui
permet de résoudre le problème en donnant la sortie requise. Chaque étape
élémentaire est :
▪ définie de façon rigoureuse et non ambiguë
▪ effective, c-à-d, pouvant être réalisée par une machine
De plus, un algorithme doit toujours terminer après un nombre fini d’opérations,
quelle que soit la donnée en entrée, et fournir un résultat.
Les algorithmes que nous considérons sont déterministes : toute exécution de
l’algorithme sur les mêmes données donne le même résultat.
À tout algorithme écrit en langage naturel ou pseudo-code, on peut associer un
programme implémentant l’algorithme. Ce programme écrit avec des règles
syntaxiques rigoureuses et destinées à être compris par une machine.
En résumé, un algorithme doit être

3
[Link]
Chapitre 1 : Compléments algorithmiques

Précis: Il doit indiquer:

- l'ordre des étapes qui le constituent
- à quel moment il faut cesser une action
- à quel moment il faut en commencer une autre
- comment choisir entre différentes possibilités
Déterministe
- Une suite d'exécutions à partir des mêmes données doit produire des
résultats identiques.
Fini dans le temps
- c'est-à-dire s'arrêter au bout d'un temps fini.

I.2.2 Place de l'algorithme dans la résolution d'un problème

informatique
La résolution d'un problème informatique se décompose en quatre phases:
- Phase d'étude
Inventorier les paramètres connus ou observables et définir les objectifs à
réaliser.
- Phase de réalisation du modèle
Déterminer l'enchaînement des opérations. Cette phase aboutit à l'élaboration
d'un schéma de résolution.
- Phase de spécification
Exprimer le schéma de résolution de manière plus précise en utilisant
éventuellement un pseudo-langage. Cette phase débouche sur des algorithmes.
- Phase de traduction
Mettre en œuvre les algorithmes en les traduisant en un programme compris par
la machine utilisée.

I.2.3 Notion de pseudo-langage

Aujourd'hui, on dispose d'une grande variété de langages de programmation.
Certains langages très connus du grand public sont largement utilisés dans des
domaines très divers (PASCAL, C, LISP, ADA, COBOL etc...).
On distingue généralement les langages de bas niveau (proches de la machine :
Assembleur) et les langages évolués (dits de haut niveau).
De tout temps, les chercheurs ont essayé de mettre au point des langages
permettant de se détacher le plus possible de la machine sur laquelle les
programmes seront exécutés.
D'un autre côté, un algorithme n'a d'intérêt que s'il peut être compris et utilisé par
un grand nombre de programmeurs.
Il a donc fallu élaborer un langage de description suffisamment formel, pour
permettre des implantations dans différents langages de programmation peu
fastidieuses, et d'un niveau suffisant pour qu'il soit un outil de communication
efficace. Un tel langage s'appelle pseudo-langage.

I.2.4 Elaboration d'un algorithme.

Quatre phases principales:
- Analyse du problème

4
[Link]
Chapitre 1 : Compléments algorithmiques

- Expression d'une solution en langage courant

- Expression d'une solution en pseudo-langage
- Tests et Vérification de l'adéquation de la solution

Analyse du problème:
Bien comprendre l'énoncé du problème: Il est inutile et dangereux de passer à la
phase suivante si vous n'avez pas bien discerné le problème.
Expression du raisonnement
Bien souvent, quelques lignes écrites en langage courant suffisent pour décrire
succinctement l'essentiel du problème. L'intérêt de cette étape est qu'elle permet
de vérifier rapidement que l'on se trouve sur la bonne voie. De plus, ces quelques
lignes seront un support efficace lors de l'écriture de l'algorithme.
Expression d'une solution en pseudo-langage
Il peut arriver que plusieurs solutions répondent à un problème donné. Il faudra
choisir la solution la plus judicieuse et rester cohérent jusqu'au bout.
Tests et Vérification de l'adéquation de la solution
Vérifier l'exactitude du comportement de l'algorithme, son bon déroulement. Si
l'algorithme ne répond pas parfaitement à toutes les requêtes exprimées dans
l'énoncé du problème, retournez à la phase n°1.

I.3 OBJETS SIMPLES ET ACTIONS ELEMENTAIRES

Un algorithme va manipuler des objets au sens informatique. Ces objets pourront
être des données qui seront fournies en entrée, des résultats produits par
l'algorithme ou des outils nécessaires au bon déroulement de l'algorithme.

I.3.1 Type d'un objet

En mathématiques, lorsque l'on utilise des objets, on précise leur type.

Exemple: xIR ; iIN

x et i appartiennent à des types dont on connaît les propriétés.
En informatique, les objets manipulés par un algorithme doivent appartenir à un
type connu au moment de leur utilisation.
Tout objet simple peut être caractérisé par un type qui indique les ensembles de
valeurs que peut prendre l'objet.
Les objets simples sont:
Type entier : prend ses valeurs dans un sous-ensemble des entiers relatifs. C'est un
ensemble fini dans lequel chaque élément possède un successeur et un
prédécesseur.
Type réel : prend ses valeurs dans un sous-ensemble de réels décimaux signés.
Dans la plupart des langages, cet ensemble n'est pas un ensemble fini. On ne peut
trouver de successeur ou de prédécesseur à un réel donné.
Type caractère : prend ses valeurs dans l'ensemble des caractères de la table
ASCII.

5
[Link]
Chapitre 1 : Compléments algorithmiques

Type chaîne de caractère : se compose d'une suite de symboles de type caractère

Type booléen : type logique qui peut prendre les valeurs VRAI ou FAUX.
On distingue généralement:
- les types scalaires qui sont par définition totalement ordonnés
- les types structurés qui regroupent sous un même nom une collection d'objets
élémentaires qui peuvent être de même type (type homogène) ou de type
différents (type hétérogène).
Un objet simple peut être une constante ou une variable.
Pour désigner ces différents objets, on utilisera des chaînes de caractères,
appelées les identificateurs des objets. Pour différentier un identificateur d'un
nombre, un identificateur commence par une lettre et ne comporte pas d'espace.
De plus, on essaiera toujours de choisir des noms explicites afin de faciliter la
relecture.

I.3.2 Déclaration des variables

La première chose à faire avant de pouvoir utiliser une variable est de la déclarer
et de lui coller une étiquette. Ceci se fait tout au début de l’algorithme, avant
même les instructions proprement dites.

Exemple :

VAR g : ENTIER
PrixHT, TauxTVA, PrixTTC : REEL

I.3.3 Actions élémentaires

Les actions élémentaires sur une donnée dépendent évidemment du type de cette
donnée et de sa catégorie (variable ou constante).

I.3.3.1 Opérateurs sur les types simples

6
[Link]
Chapitre 1 : Compléments algorithmiques

Dans ce tableau, les opérateurs sont classés par ordre de priorité décroissante
mais prudence! dans l'utilisation des priorités car il existe souvent des différences
d'un langage de programmation à l'autre.
En absence de parenthèses, l'évaluation se fait de gauche à droite.
I.3.3.2 Affectation
L'affectation a pour rôle d'attribuer une valeur, résultat d'une évaluation, à un
objet. La valeur doit être compatible avec le type de la valeur à gauche de
l'affectation. Le symbole utilisé pour l'affectation est .

Exemple:
nb_kg : ENTIER
prix_du_kg, prix_total : REEL
……………
prix_total  nb_kg * prix_du_kg

I.3.3.3 Lecture et écriture

Ces actions permettent d'assurer l'interface entre l'environnement externe

(l'utilisateur) et l'algorithme.
LIRE(Valeur1, Valeur2 ...)
ECRIRE(Valeur3, Valeur4 ...)
ECRIRE('Le résultat du calcul est : ',prix_total)

Exemple d'algorithme
ALGORITHME Epicier
VAR
prix_total , prix_du_kg : REEL
nb_kg : ENTIER
DEBUT
ECRIRE('Entrez le prix d'un kilogramme de choux : ')
LIRE(prix_du_kg)
ECRIRE('Entrez le nombre de kilogramme de choux : ')
LIRE(nb_kg)
prix_total  prix_du_kg * nb_kg
ECRIRE('Le prix total de l''achat est :',prix_total)
FIN

I.3.3.4 Commentaires
Afin d'améliorer la lisibilité d'un algorithme, on peut utiliser des commentaires.
Un commentaire est une suite de caractères quelconques encadrée par les
symboles /* et */.
Dans le même but, on utilise des sauts de lignes et des espaces blancs en tête des
lignes de façon à ce que l’écriture de l’algorithme (ou le programme) mette en
valeur sa structure intrinsèque.

7
[Link]
Chapitre 1 : Compléments algorithmiques

Exemple:
/* ceci est un commentaire */

I.4 LES STRUCTURES FONDAMENTALES

I.4.1 Notion de programme propre

On appelle programme propre un traitement qui possède une seule entrée et une
seule sortie.
Avantage: si l'on doit apporter des modifications dans ce programme propre, il est
beaucoup plus facile de déterminer l'impact de ces modifications.

Les structures fondamentales utilisées pour écrire les algorithmes sont au

nombre de 3.

I.4.2 Enchaînement des actions

On utilisera cette structure lorsqu'une action doit succéder à une autre

T1, T2 : traitements ou algorithmes (programmes propres)

Exemple:
DEBUT /* traitement T1 */
T1
FIN /* fin du traitement T1 */
T2
DEBUT /* traitement T2 */
FIN /* fin du traitement T2 */

I.4.3 Structure alternative ou conditionnelle

8
[Link]
Chapitre 1 : Compléments algorithmiques

SI Condition ALORS
T1
SINON
T2
FSI

Condition désigne une expression booléenne dont la valeur est VRAI ou FAUX.
T1 et T2 désignent une suite d'instructions (pouvant elles mêmes être des
structures alternatives).
La structure alternative est une structure parenthésée, chaque partie étant
délimitée par les symboles SI, ALORS, SINON et FSI.
Le traitement T2 est facultatif.
Exemple :

ALGORITHME Maximum_de_Deuxnombres
VAR
nb1,nb2 : ENTIER; /* les deux nombres à comparer */
max : ENTIER; /* le plus grand */
DEBUT
ECRIRE( Entrez le premier nombre :)
LIRE(nb1);
ECRIRE(Entrez le deuxième nombre :)
LIRE(nb2);
SI nb1 >= nb2 ALORS
max  nb1
SINON
max  nb2
FINSI
ECRIRE(le maximum de , nb1, et de ,nb2, est : ,max)
FIN

On pourrait remplacer la conditionnelle de cet exemple par

max  nb2;
SI nb1 > nb2 ALORS
max  nb1
FINSI
On remarque que cette alternative ne comporte pas de clause SINON.

I.4.4 Structure itérative

La notion d'itération est l'une des notions fondamentales de l'algorithmique. Elle
est utilisée lorsque l'on doit exercer plusieurs fois le même traitement sur un

9
[Link]
Chapitre 1 : Compléments algorithmiques

même objet. Si le nombre de répétitions est grand, il serait fastidieux de réécrire n

fois le même algorithme et même impossible si n était inconnu.
Lorsque la condition a pour valeur
VRAI, on exécute le traitement T1 puis
on revient tester la condition. Il est
donc nécessaire que l'action T1 modifie
la condition sinon l'itération ne
s'arrêtera pas.
Lorsque la condition a pour valeur
FAUX, le traitement séquentiel
continue. L'itération est terminée.

En pseudo-langage, on écrira la structure itérative de la façon suivante:

TANTQUE Condition FAIRE
T1
FINTANTQUE
Il existe bien d'autres méthodes pour représenter une itération.
Théorème :
Tout programme propre peut être ramené à l'un de ces trois types de
structures.

I.5 LES STRUCTURES COMPLEMENTAIRES

I.5.1 L'alternative généralisée

Suivant la valeur de l’exxpression, T1, T21 suivi de T22, T3, T4 ou T-autre est
exécuté.

Beaucoup de langages proposent en outre un traitement pour les autres cas.

En pseudo-langage, on écrira :

10
[Link]
Chapitre 1 : Compléments algorithmiques

CAS valeur_Expression
valeur1 : T1
valeur2 :
DEBUT
T21
T22
FIN
valeur3 : T3
valeur4 : T4
AUTRE :
T_Autre
FINCAS
Ce traitement pourrait être obtenu à l'aide de SI imbriqués.
SI valeur_Expression = valeur1 ALORS
T1
SINON
SI valeur_Expression = valeur2 ALORS
T21
T22
SINON
SI valeur_Expression = valeur3 ALORS
T3
SINON
SI valeur_Expression = valeur4 ALORS
T4
FSI
FSI
FSI
FSI

I.5.2 La répétition

On effectue le traitement T Si la condition

est égale à FAUX, on recommence le
traitement T L'itération se terminera
lorsque la condition sera égale à VRAI

Traduction de la répétition en pseudo-langage

REPETER
T
JUSQU'A condition (Ici, la condition est une condition de terminaison)

11
[Link]
Chapitre 1 : Compléments algorithmiques

A l'aide des structures fondamentales, on aurait le schéma suivant:

DEBUT
T
TANT QUE NON Condition FAIRE
T
FINTANTQUE
FIN

I.5.3 Autres formes d’itérations

On pourrait utiliser la structure suivante en pseudo-langage

POUR i DEPUIS 1 JQA 10 FAIRE

T1
T2
FINPOUR
Pour toutes les valeurs de i(variable de boucle) comprises entre1(valeur initiale)
et 10(valeur finale) ….
Eventuellement, on peut fixer un pas d’incrémentation différent de 1
POUR i DEPUIS 1 JQA 10 FAIRE PAS 2
T1
T2
FINPOUR
Ici i varie de 1 jusqu’à 10 au pas de 2 soit 1, 3, 5, 7, 9.

II. Fonctions et procédures

II.1 Les sous-programmes

Ce nouvel objet (au sens algorithmique) permet au programmeur de traiter un

problème sans s'embarrasser des détails des sous problèmes.
En effet, à l'intérieur du programme (principal) en question, le traitement relatif
à un sous problème est simplement désigné par un identificateur (appel de sous-
programme).
Le détail de ce sous-programme est décrit par ailleurs dans la partie déclaration
de sous-programme.
Jusqu'à présent, un identificateur était associé à une valeur (donnée), il est ici
associé à une suite d'instructions.

12
[Link]
Chapitre 1 : Compléments algorithmiques

Un sous-programme peut comporter des données (types, variables etc...) qui lui
sont propres. On parle alors de variables locales au sous-programme. On peut
noter dès à présent que ces variables existeront uniquement pendant l'exécution
du sous-programme.

II.2 Procédures sans paramètres

Traduction de la procédure sans paramètre en pseudo-langage
PROCEDURE id_procedure
VAR
i : ENTIER
DEBUT
T
FIN
Dans le programme principal, l'appel à ce sous-programme se fera de la façon
suivante:
ALGORITHME Nom_algo
DEBUT
...
id_procedure
...
FIN

II.3 Procédures avec paramètres fixes (non modifiables)

Bien souvent, une procédure utilise des données fournies par le programme
principal (ou par une autre procédure).

La procédure sera écrite avec des arguments fictifs appelés paramètres formels
auxquels on fera correspondre lors de l'appel les données réelles appelées
paramètres effectifs ou réels.
Traduction de la procédure avec paramètre fixe en pseudo-langage
PROCEDURE id_procedure ( parametre_formel : type du paramètre)
VAR
i : ENTIER
DEBUT
T
FIN

Dans le programme principal, l'appel à ce sous-programme se fera de la façon

suivante:
ALGORITHME Nom_algo
VAR
i, j, k : ENTIER
DEBUT

13
[Link]
Chapitre 1 : Compléments algorithmiques

...
id_procedure(j)
...
id_procedure(5)
...
FIN

II.4 Fonctions
Lorsqu'un sous-programme doit rendre un résultat unique de type simple, il est
commode de définir ce sous-programme comme une fonction dont l'utilisation est
analogue à celui des fonctions mathématiques usuelles (SIN(x), TANG(x), COS(x)
etc...).
Traduction de la fonction en pseudo-langage

FONCTION Id_Fonction(parametre_formel : type du paramètre) : type_resultat

VAR
i : ENTIER
DEBUT
TRAITEMENT
RETOURNER (RESULTAT)
FIN

Dans le programme principal, l'appel à ce sous-programme se fera de la façon

suivante:

ALGORITHME Nom_algo
VAR
i, j, k : ENTIER
DEBUT
...
i  Id_Fonction(j)
...
FIN

II.5 Procédures avec paramètres modifiables

Alors qu'une fonction ne rend qu'un seul résultat, il est quelquefois intéressant
d'utiliser des procédures qui rendent plusieurs résultats. Ceci se réalise à l'aide
de procédures à paramètres modifiables.
Traduction de la procédure à paramètres modifiables en pseudo-langage
PROCEDURE id_procedure ( VAR parametre1_formel : type du paramètre1 , VAR
parametre2_formel : type du paramètre2 etc...)
VAR
i : ENTIER
DEBUT
T
FIN

14
[Link]
Chapitre 1 : Compléments algorithmiques

Dans le programme principal, l'appel à ce sous-programme se fera de la façon

suivante:
ALGORITHME Nom_algo
VAR
i, j, k : ENTIER
DEBUT
...
id_procedure(i,j)
...
FIN
A la fin (ou au cours) de l'exécution du sous-programme, les valeurs de i et j
auront pu être changées.

III Types structurés et enregistrements

Un enregistrement (ou record ou structure) est une structure constituée d'un
nombre fixe de composants appelés champs. Les champs peuvent être de
différents types et chaque champ comporte un identificateur de champ
permettant de le sélectionner.
Exemple:
TYPE T_abonne = structure
nom : CHAINE
prenom : CHAINE
age : ENTIER
salaire : REEL
Fin structure
Une variable du type T_abonne, par exemple abonne1, sera déclarée et utilisée de la
façon suivante:
VAR
abonne1 : T_abonne
Dans l’algorithme utilisant cette variable, [Link] identifie le champ nom de
l'enregistrement abonne1 de type T_abonne. Les opérations permises sur le type
chaîne seront possibles sur [Link] (lecture, écriture, affectation, comparaison,
etc...).
Si on déclare une autre variable abonne2 du type T_abonne, les opérations
d'affectation seront possibles entre abonne1 et abonne2.

IV Les fichiers
IV.1 Généralités sur l'organisation des informations

On a souvent besoin de stocker différentes informations sur des supports physiques

pour une utilisation éventuelle ultérieure.
La notion d'accès à une information rangée devient fondamentale.
Les différentes primitives sur les supports d'information sont:
- accès à un élément.

15
[Link]
Chapitre 1 : Compléments algorithmiques

- recherche d'un élément.

- insertion d'un nouvel élément.
- suppression d'un élément.
- copie d'une partie des informations.
- éclatement de l'ensemble en plusieurs sous-ensemble.
- fusion de plusieurs sous-ensembles en un seul.
- tri d'un ensemble.

IV.2 Notion de fichier

Les différentes informations que l'on aura à traiter seront donc stockées sur un
support physique.
Il va donc falloir organiser les différents transferts entre la mémoire et ce support
physique grâce à différentes primitives d'accès.
L'organisation d'un fichier est la structure logique permanente établie au moment où
le fichier est créé.
Définition
Un fichier est un ensemble organisé d'informations (articles ou enregistrements) de
même nature susceptibles de faire l'objet de traitements divers.

IV.3 Les accès aux fichiers

On accède généralement aux fichiers par deux méthodes principales:
-accès séquentiel.
-accès direct.
IV.3.1 Accès séquentiel
Soit F un fichier: ce fichier est dit à accès séquentiel si l'on ne peut accéder à un
élément quelconque de rang n qu'après avoir accédé aux (n-1) éléments qui le
précèdent.
On se déplace dans ce type de fichier en passant d'un élément à son suivant. Il
existe deux éléments particuliers: le premier qui nous permet d'accéder au fichier
et le dernier qui nous signale qu'il n'a pas de suivant.
IV.3.2 Accès direct
Soit F un fichier: ce fichier est dit à accès direct lorsqu'il suffit de connaître le rang
n de l'élément recherché pour y accéder, sans parcourir le reste du fichier.
Cette méthode est en général plus intéressante en temps et en efficacité.

IV.4 Les fichiers en algorithmique

IV.4.1 Déclaration d'une variable de type fichier

VAR F : FICHIER

Où F est l'identificateur (= nom logique).

Assignation d'un nom de fichier logique

16
[Link]
Chapitre 1 : Compléments algorithmiques

ASSIGNER (nom_logique, nom_physique)

où nom_physique est soit une constante chaîne soit une variable chaîne.
Le nom du fichier physique correspond au nom du fichier sur le support physique
(en général disque magnétique, bande, etc...). Ce nom peut comprendre le chemin
(absolu ou relatif) du fichier.
L'opération d'assignation est obligatoire, tous les accès au fichier se feront à l'aide
du nom de fichier logique.
IV.4.2 Actions et opérations sur les fichiers
Ouverture.
- en écriture : OUVRIRECR(nom_de_fichier_logique)
- en lecture : OUVRIRLEC(nom_de_fichier_logique)

Fermeture.
FERMER(nom_de_fichier_logique)

Ecriture dans un fichier

ECRIRE(nom_de_fichier_logique,expression)
ECRIRE(F,expression) écrit à partir de la position courante de la tête d'écriture
sur le fichier F la valeur de l'expression. La tête d'écriture est ensuite positionnée
sur l'élément suivant.
Lecture à partir d’un fichier
LIRE(nom_logique, variable)
LIRE(F,variable)
Comme pour une lecture à partir du clavier, le type de la variable doit être le
même que celui de l'élément lu. La tête de lecture est ensuite déplacée sur
l'élément suivant à la fin de l'opération.
Fin de fichier : EOF(fic)

On peut trouver également FF(fic)

17
[Link]
Chapitre 2 : Récursivité

Chapitre 2

Récursivité
I. Définitions et Exemples
I.1 Introduction
La récursivité est un domaine très intéressant de l'informatique, un peu abstrait,
mais très élégant; elle permet de résoudre certains problèmes d'une manière très
rapide, alors que si on devait les résoudre de manière itérative, il nous faudrait
beaucoup plus de temps et de structures de données intermédiaires.
La récursivité, c'est la possibilité de faire figurer dans la définition d'un objet une
référence à ce même objet. Beaucoup de langages autorisent la récursivité simple
et la récursivité croisée.
I.1.1 Définitions

Une procédure P, qui s'appelle elle-même ou qui appelle une autre procédure P'
contenant un appel de P est une procédure récursive.
Elle possède 2 propriétés:
• Il doit exister des critères pour lesquels les appels cessent
• Chaque fois que la procédure s'appelle (directement ou indirectement), elle doit
être plus proche des ses critères d'arrêt.
Il y a récursivité simple lorsqu'une fonction (ou procédure) en cours d'exécution
s'appelle elle-même :
Fonction f1(…) : type_fonction
var x : type_fonction
debut
x = f1(…)
fin
Il y a récursivité croisée (ou appel indirect) lorsqu'une fonction (ou procédure) f1
appelle une fonction (ou procédure) f2 qui elle-même appelle la procédure f1 :
Fonction f1(…) : type_fonction Fonction f2( …) : type_foction
var x : type_fonction var x : type_fonction
debut debut
x = f2(…) x = f1( …)
fin fin
A chaque appel du sous-programme récursif, les variables locales, les paramètres
et l'adresse de retour sont empilés dans une zone mémoire appelée pile.

18
[Link]
Chapitre 2 : Récursivité

A la fin de chaque exécution du sous-programme, les éléments empilés sont

dépilés.
I.1.2 Critères de récursivité
▪ Expression récursive du problème :
C’est l’ « équation » de la récursivité.
▪ Condition d’arrêt :
Quand est-ce qu’on arrête les appels récursifs ?
▪ Convergence (vers la condition d’arrêt):
Une petite « preuve» qui nous assure qu’un jour on va atteindre la condition
d’arrêt.

I.2 Exemples
I.2.1. Calcul de la factorielle d'un nombre n
n! = n(n-1)(n-2) ... 2*1 si n > 0
n! = 1 si n = 0
- Expression récursive du problème :
n! = n ( n – 1) … (2) (1) = n (n – 1)!
- Condition d’arrêt:
n = 1 ou n = 0
- Convergence (vers la condition d’arrêt):
Si n = 1 ou n = 0, alors on a « convergé »!
Si n > 1, alors la soustraction à l’étape suivante nous approche de n = 1. D’où la
convergence
On peut bien entendu résoudre ce problème de manière itérative classique

ALGORITHME Factorielle( n: ENTIER): ENTIER

VAR
factorielle: ENTIER
DEBUT
factorielle  1
TANT QUE n > 1
factorielle  factorielle*n
n  n-1
FINTANTQUE
Retourner factorielle
FIN
Si on désire résoudre le problème par un algorithme récursif on utilise la méthode
suivante:
- Paramétrage du problème : on détermine les éléments dont dépend la
solution et qui caractérisent la taille du problème.
- Recherche du cas trivial qui donne la solution (condition d'arrêt) ici
lorsque n = 1 on connaît le résultat
- Décomposition du cas général en cas plus simples : tant que le cas
trivial n'est pas atteint, il y a modification de la valeur du paramètre et un nouvel
appel de la fonction. D'où l'algorithme:

19
[Link]
Chapitre 2 : Récursivité

ALGORITHME Calcul FONCTION Fact(n : ENTIER): ENTIER

VAR DEBUT
nb: ENTIER SI n=1 ALORS
DEBUT RETOURNER (1)
ECRIRE(‘ Donner un nombre :‘) SINON
LIRE(nb) RETOURNER (n*Fact(n-1))
ECRIRE(‘ La factorielle de :‘,nb) FINSI
ECRIRE(‘ vaut ‘,Fact(nb)) FIN
FIN
On constate, et il le faut, que les paramètres de l'appel récursif changent; en effet,
à chaque appel, l'ordinateur stocke dans la pile les variables locales; le fait de ne
rien changer dans les paramètres ferait que l'ordinateur effectuerait un appel
infini à cette procédure, ce qui se traduirait en réalité par un débordement de pile,
et d'arrêt de l'exécution de la procédure en cours. Grâce à ces changements, tôt ou
tard l'ordinateur rencontrera un ensemble de paramètres vérifiant le test d'arrêt,
et donc à ce moment la procédure récursive aura atteint le "fond" (point
terminal). Ensuite les paramètres ainsi que les variables locales sont désempilées
au fur et à mesure qu'on remonte les niveaux.
I.2.2 Suite de Fibonacci
Elle est définie par:

F = 1 si n = 0 ou n =1
 n

F = F + Fn −1 si n 1
 n n−2

L’expression récursive du problème est:

Fn = Fn − 2 + Fn −1

La condition d’arrêt est:

F0 = F1 = 1

FONCTION Fibonacci(n: ENTIER): ENTIER

DEBUT
SI (n < 0) ALORS /* hypothèse de convergence : n>=0 */
SORTIR
SI (n =0 ou n = 1) ALORS
RETOURNER 1 /* condition d’arrêt */
SINON /* appels récursifs */
RETOURNER Fibonacci(n–2)+Fibonacci(n-1)
FINSI
FINSI
FIN
I.2.3 Algorithme d'Euclide pour le calcul du pgcd
Ici, la version itérative est une variante simplifiée de l'algorithme d'Euclide déjà
présenté, où l'on n'admet que des entiers non négatifs comme entrée.

20
[Link]
Chapitre 2 : Récursivité

PROCEDURE EuclideItératif(a, b : ENTIER) : ENTIER /* a , b  0 */

VAR
r : ENTIER
DEBUT
TANTQUE b ≠ 0 FAIRE
r ← a mod b
a←b
b←r
FINTANTQUE
RETOURNER a
FIN

PROCEDURE EuclideRécursif(a, b : ENTIER) : ENTIER

DEBUT
SI b = 0 ALORS
RETOURNER a
SINON
RETOURNER EuclideRécursif(b, a mod b)
FINSI
FIN

Remarque
Ces deux derniers algorithmes sont basés sur le fait que :
pcgd(a, b) = pgcd(b, a mod b).
I.2.4 Le problème des Tours de Hanoi

On dispose de 3 tiges (ou piliers) et de N disques de rayons strictement croissants,

percés de manière à pouvoir être enfilé sur les tiges. Au départ, les N disques sont
placés sur la première tige, par ordre de rayons décroissants. L'objectif est de les
placer sur la seconde en respectant les règles:
- un seul disque peut être déplacé à la fois (et doit donc être posé sur une tige à la
fin du déplacement),
- à tout instant, sur chacune des tiges, les disques doivent être placés de telle sorte
qu'au dessus d'un disque on ne trouve que des disques de rayon inférieur.
Le fait d'indiquer la troisième pile n'ajoute pas d'information, puisque celle-ci
peut se déduire de la définition des deux autres.
PROCEDURE deplacer (depuis: ENTIER, vers: ENTIER)
DEBUT
ECRIRE(‘Je déplace le disque du pilier n°‘,depuis,‘ vers le pilier n°‘,vers )
FIN
PROCEDURE Hanoi(n: ENTIER, a: ENTIER, b: ENTIER)
/* résout le problème de la tour de Hanoi pour déplacer n disques du pilier a vers b. a et b
différents et égaux à 1, 2 ou 3 */
VAR c: ENTIER /* c pilier intermédiaire */
DEBUT
CAS (a+b)

21
[Link]
Chapitre 2 : Récursivité

3:c3
4:c2
5:c1
FINCAS
SI (n = 1) ALORS deplacer(a,b) /* déplace le disque du haut de a vers b */
SINON
Hanoi(n-1, a, c)
deplacer (a, b)
Hanoi(n-1, c, b)
FINSI
FIN /* fin de la procedure Hanoi */

Exemple d’application :

Voici les résultat de l'appel Hanoi(n,1,3), avec n = 3 c'est-à-dire déplacer 3

disques du pilier 1 vers le pilier 3 :

1ère étape:
Je déplace un disque du pilier n°1 vers le pilier n°3

2ème étape:
Je déplace un disque du pilier n°1 vers le pilier n°2

3ème étape:
Je déplace un disque du pilier n°3 vers le pilier n°2

22
[Link]
Chapitre 2 : Récursivité

4ème étape:
Je déplace un disque du pilier n°1 vers le pilier n°3

5ème étape:
Je déplace un disque du pilier n°2 vers le pilier n°1

6ème étape:
Je déplace un disque du pilier n°2 vers le pilier n°3

7ème étape:
Je déplace un disque du pilier n°1 vers le pilier n°3

II. Traduction d’une procédure itérative en une

procédure récursive
II.1 Transformer une boucle en une procédure récursive
23
[Link]
Chapitre 2 : Récursivité

Soit la procédure suivante :

PROCEDURE compter
VAR i: ENTIER
DEBUT
POUR i  1 à 10 FAIRE
ECRIRE(i)
FINPOUR
FIN

Cette procédure peut être traduite en une procédure récursive, qui admet un
paramètre; l'instruction qui l'appellera sera "compter(1)":
PROCEDURE compter(i: ENTIER)
DEBUT
SI i < 11 ALORS
ECRIRE(i)
compter(i + 1)
FINSI
FIN

II.2 Transformer deux boucles imbriquées en une procédure

récursive
Supposons qu'on ait maintenant deux boucles imbriquées. Nous allons traduire
progressivement cette procédure itérative en une procédure récursive avec deux
paramètres :
PROCEDURE affiche
VAR a, b : ENTIER
DEBUT
POUR a  0 à 3 FAIRE
POUR b  0 à 9 FAIRE
ECRIRE(a * 10 + b)
FINPOUR
FINPOUR
FIN
Pour supprimer les deux boucles, on commence par supprimer la première en
suivant l'exemple ci-dessus; on obtient la procédure suivante que l'on appelle
avec "affiche(0)" :
PROCEDURE affiche(a: ENTIER)
VAR b: ENTIER
DEBUT
SI a < 4 ALORS
POUR b  0 à 9 FAIRE
ECRIRE(a * 10 + b)
FINPOUR

24
[Link]
Chapitre 2 : Récursivité

affiche(a + 1)
FINSI
FIN

Il ne nous reste plus qu'à supprimer la deuxième boucle; en sachant que lorsque
b=10 dans la procédure initiale, le programme revient à la boucle sur a et remet b
à zéro, alors on a 2 appels récursifs :

• le premier dans le cas où b est inférieur à 10 et alors on appelle la

procédure avec a inchangé et b incrémenté de 1
• le deuxième où b=10 et alors on appelle la procédure avec a incrémenté de
1 et b initialisé à 0.
L'appel sera "affiche(0,0)".
PROCEDURE affiche(a, b: ENTIER)
DEBUT
SI a < 4 ALORS
SI b < 10 ALORS
ECRIRE(a * 10 + b))
affiche(a, b + 1)
SINON
affiche(a + 1, 0)
FINSI
FINSI
FIN

III. Types de récursivité

III.1 Récursivité terminale et non terminale
Une fonction récursive est dite terminale si aucun traitement n'est effectué à la
remontée d'un appel récursif (sauf le retour d'une valeur).
Une fonction récursive est dite non terminale si le résultat de l'appel récursif est
utilisé pour réaliser un traitement (en plus du retour d'une valeur).
Exemple de non terminalité : forme récursive non terminale de la factorielle, les
calculs se font à la remontée.
fonction factorielleNT(n : entier) : entier
début
si (n = 1) alors
retourne 1;
sinon
retourne n*factorielleNT(n-1);
finsi
fin

Exemple de terminalité : forme récursive terminale de la factorielle, les

calculs se font à la descente.

25
[Link]
Chapitre 2 : Récursivité

// la fonction doit être appelée en mettant résultat à 1

fonction factorielleT(n : entier, resultat : entier) : entier
début
si (n = 1) alors
retourne resultat;
sinon
retourne factorielleT(n-1, n * resultat);
finsi
fin
factorielleT(3,1)

factorielleT(2,3)

factorielleT(1,6)

III.2 Intérêt de la récursivité terminale

Une fonction récursive terminale est en théorie plus efficace (mais souvent moins
facile à écrire) que son équivalent non terminale : il n'y a qu'une phase de
descente et pas de phase de remontée.
En récursivité terminale, les appels récursifs n'ont pas besoin d'êtres empilés
dans la pile d'exécution car l'appel suivant remplace simplement l'appel
précédent dans le contexte d'exécution.
Certains langages utilisent cette propriété pour exécuter les récursions
terminales aussi efficacement que les itérations.
Il est possible de transformer de façon simple une fonction récursive terminale en
une fonction itérative : c'est la dérécursivation.

III.3 Dérécursification
Une fonction récursive terminale a pour forme générale :

fonction recursive(P) : T T est le type de retour

début P est la liste des paramètres
Bloc I0 C est la condition d'arrêt
si (C) alors I0 le bloc d'instructions exécuté dans
Bloc I1 tous les cas
sinon I1 le bloc d'instructions exécuté si C est
Bloc I2 vraie
recursive(f(P)); I2 et le bloc d'instructions exécuté si C
finsi est fausse
fin f la fonction de tranformation des
paramètres

La fonction itérative correspondante est :

fonction iterative(P) : T
début
Bloc I0
tantque (non C) faire

26
[Link]
Chapitre 2 : Récursivité

Bloc I2
P <- f(P);
Bloc I0;
fintantque
Bloc I1
fin

Exemple : dérécursification de la factorielle terminale

// Cette fonction doit être appelée avec a=1
fonction factorielleRecurTerm(n : entier, a : entier) : entier
début
si (n <= 1) alors
retourne a;
sinon
retourne factorielle(n-1,n*a);
finsi
fin
fonction factorielleIter(n : entier, a : entier) : entier
début
tantque (n > 1) faire
a <– n*a;
n <– n-1;
fintantque
retourne a;
fin
Une fonction récursive non terminale a pour forme générale :

fonction recursive(P) : T T est le type de retour

début P est la liste des paramètres
Bloc I0 C est la condition d'arrêt
si (C) alors I0 le bloc d'instructions exécuté dans
Bloc I1 tous les cas
sinon I1 le bloc d'instructions exécuté si C est
Bloc I2 vraie
recursive(f(P)); I2 et I3 les blocs d'instructions exécutés
Bloc I3 si C est fausse
finsi f la fonction de tranformation des
fin paramètres

La fonction itérative correspondante doit gérer la sauvegarde des contextes

d'exécution (valeurs des paramètres de la fonction).
La fonction itérative correspondante est donc moins efficace qu'une fonction
écrite directement en itératif.

27
[Link]
Chapitre 3 : Conception des algorithmes

Chapitre 3

Conception des algorithmes

• Analyse du problème
• Approche incrémentale
• Recherche exhaustive
• Méthodes approchées
o Algorithme glouton
o Diviser pour régner
o Heuristiques

I. Analyse du problème
I.1 Analyse descendante
I.1.1 Buts
- Obtenir une analyse et une programmation de haut en bas selon une
décomposition arborescente qui autorise le fractionnement des programmes en
modules de taille facilement lisible (par exemple de la taille d'une page de listing).
- Supprimer, grâce à cette analyse descendante, la phase d'intégration (partie très
délicate lors de projets importants).
- Rendre possible la lecture des modules de haut niveau par des non-spécialistes.
- Faciliter la maintenance et l'extensibilité en donnant la possibilité de modifier
une arborescence, sans affecter ce qui est au niveau supérieur.
- Diminuer les risques d'erreurs de programmation.
- Fournir aux programmeurs un mode commun de décomposition des problèmes.

I.1.2 Principe
C'est une méthode de décomposition des problèmes.
Soit le problème A à résoudre

On a tout d'abord décomposé le problème A en 2 actions intermédiaires (AI1 et

AI2) et une action élémentaire AE2
AI1 est ensuite décomposé en 3 actions élémentaires AE11, AE12 et AE13

28
[Link]
Chapitre 3 : Conception des algorithmes

AI2 est ensuite décomposé en 2 actions élémentaires AE21 et AE22

Une telle situation peut sembler idéale, mais il y a une contrepartie: l'analyse
descendante ne permettra que rarement de définir des sous-programmes
identiques appelés de points différents.
L'analyse descendante doit être le guide général, mais il peut être profitable,
dans le cas de traitements complexes, d'osciller quelque peu entre analyse
descendante et ascendante.

I.2 Analyse ascendante

Elle consiste à identifier dès le début les actions élémentaires qu'il faudra savoir
résoudre.
Avec la méthode descendante appliquée de façon rigide, il est possible de
rencontrer ou de résoudre plusieurs fois le même problème ou des problèmes
voisins. La méthode ascendante consiste à déterminer les objets (ou classes
d'objets) de l'application, une classe d'objets étant caractérisée:
- par un ensemble de valeurs ou d'états (on parle aussi d'attributs ou de
propriétés),
- et par un ensemble d'actions ou d'opérations sur ces objets d'autre part.

I.3 Les méthodes dirigées par les données

Dans la méthode descendante, l'accent est mis sur la décomposition en actions.
Les données manipulées et nécessaires sont affinées au fur et à mesure mais ne
jouent pas un rôle stratégique dans la décomposition.
Dans un système de gestion de base de données (SGBD), le programmeur
commence par décrire les données de l'application (parce que les données jouent
le rôle central). Il utilise pour cela un langage de description de données (LDD) qui
permet de décrire les objets ou les classes d'objets qu'il utilise ainsi que les
associations entre classes d'objets et les contraintes d'intégrité éventuelles. On
construit ainsi le modèle conceptuel des données. On écrit ensuite les
programmes qui permettront la création, la mise à jour de la base de données en
utilisant un langage de manipulation de données (LMD).
Lorsqu’il est devant l’impossibilité de répondre à la question théorique posée et
qu’il n’a pas à sa disposition des algorithmes exacts efficaces, l’utilisateur se
tourne souvent vers des méthodes approchées qui donnent une solution proche
de l’optimum

II. Approche incrémentale

Il existe de nombreuses façons de concevoir un algorithme. On peut par
exemple adopter une approche incrémentale ; c’est le cas du tri par insertion :
après avoir trié le sous-tableau tab[0]...tab[j-1], on insère l’élément tab[j] au bon
emplacement pour produire le sous-tableau trié tab[0]...tab[j]. Comme dans un jeu
de cartes dans la main gauche. A chaque étape, on met à la place voulue dans la
main droite (qui était libre au début) une carte du jeu de la main gauche : on fait
grandir le tas de cartes de la main droite

29
[Link]
Chapitre 3 : Conception des algorithmes

III. Recherche exhaustive

On cherche la solution à un problème et on teste toutes les solutions
possibles (potentiellement un nombre infini) Par exemple l’attaque par force
brute : on cherche le mot de passe de quelqu’un, et on teste toutes les possibilités
les unes après les autres. Cela ne marchera que si le mot de passe est court, et c’est
évidemment exponentiel en la taille du mot de passe.
On peut compléter une recherche exhaustive par une recherche par dictionnaire
qui permet de tester certains mots plus probable, par exemple le nom du chien de
la personne visée.
Un autre exemple : un rubik’s cube mélangé se résout en appliquant un certain
nombre de rotations de certaines de ses faces. Une attaque par force brute va
essayer chaque mouvement qui utilise une rotation, puis chaque mouvement qui
en prend deux, etc. jusqu’à résoudre le cube.
Au-delà des dix mouvements, c’est déjà largement trop long (une rotation d’une
face se fait en temps constant, mais nécessite un certain nombre d’opérations de
base).

IV. Méthodes approchées

IV.1 Algorithmes gloutons (”greedy”)
Construction d’une solution réalisable en se ramenant à une suite de décisions
qu’on prend à chaque fois au mieux en fonction d’un critère local sans remettre en
question les décisions déjà prises. Généralement, la solution obtenue est approchée.
Intérêt : algorithmes simples à implémenter.
Défauts : solutions approchées obtenues plus ou moins bonnes, critère local

Exemple : Placement optimal de pièces 2D (Bin Packing).

On dispose de plaques rectangulaires toutes identiques dans lesquelles on veut placer des
pièces rectangulaires sans chevauchement. Les pièces à placer ont des dimensions
différentes.
On veut trouver le placement pour minimiser le nombre de plaques utilisées.

Algorithme glouton : trier les pièces en fonction de leur taille et placer d’abord les pièces
les plus grandes.

Les problèmes à traiter se présentent généralement sous la forme suivante :

On se donne un ensemble E fini et à chaque élément e de E est affectée une valeur
v(e) qui est un réel positif. On se donne de plus une condition C sur l’ensemble des
parties de E. Le problème consiste à construire un sous ensemble F de E tel que :
eF v(e) est maximal parmi les parties F satisfaisant C
Dans plusieurs cas la condition C est fermée par sous-ensemble, c’est-à-dire : Si F
satisfait C alors tout sous ensemble de F le satisfait. Il est alors naturel de
proposer un algorithme très simple consistant à initialiser F à , puis à ajouter
successivement des e à F suivant un certain critère (par exemple par valeurs
décroissantes) jusqu’à obtenir un ensemble auquel on ne peut plus ajouter
d’éléments sans contredire C. On appelle algorithme glouton ce genre
d’algorithme. Ce qualificatif décrit le fait qu’on se précipite sur l’élément le plus

30
[Link]
Chapitre 3 : Conception des algorithmes

intéressant en premier sans se préoccuper des conséquences ultérieur de ce

choix.
Les questions relatives à l’affectation d’une ou plusieurs ressources à des
utilisateurs (Clients, processeurs, etc..) constituent une classe importante de
problèmes qu’on peut tenter de résoudre par un algorithme glouton

Exemple : La question de la location d’une voiture.

Des clients formulent un ensemble de demandes de location et, pour
chaque demande sont donnés le jour du début de la location et le jour de la
restitution du véhicule ; le but est d’affecter le véhicule de façon à satisfaire le
maximum de clients (et non pas de maximiser la somme des durés de location.
On vérifie que ce problème rentre dans le cadre général considéré plus haut.
L’ensemble E est celui des demandes de location, pour chaque élément e de E, on
note d(e) la date du début de la location et f(e) > d(e) la date de fin. La valeur v(e)
de tout élément e de E est égal à 1 et la contrainte C à respecter pour le sous
ensemble F de E à construire est la suivante, (Cette contrainte exprime que deux
clients ne peuvent disposer en même temps du même véhicule)
e1, e2, e1F et e2F  [d(e1), f(e1)] [d(e2), f(e2)]=
L’algorithme glouton, décrit comme suit donne une solution optimale:
- Etape 1 :
Classer les éléments de E par ordre de dates de fin croissantes. Les
éléments de E forment alors une suite e 1, e2, …, en telle que f(e1) f(e2) …
f(en)
- Etape 2 :
Initialiser F
Pour i variant de 1 à n, ajouter e i à F si celle-ci ne chevauche pas la dernière
demande appartenant à F.
Remarque
On peut noter que si le but est de maximiser la durée totale de location du
véhicule, l’algorithme décrit ci-dessus ne donne pas l’optimum.

IV.2 Diviser pour régner

Principe
- On décompose le problème en plusieurs sous-problèmes
- On résout chaque sous-problème récursivement
- On combine les solutions des sous-problèmes en une solution globale
Par exemple, le tri rapide, le tri fusion, la recherche dichotomique. Cette approche
fournit des algorithmes plus rapides. Les algorithmes récursifs utilisent
généralement une approche diviser pour régner
- Diviser le problème en un certain nombre de sous-problèmes
- Régner sur les sous-problèmes en les résolvant de manière récursive. Le cas
échéant, on les résoud directement, ou en utilisant un autre algorithme
mieux adapté (exemple, le tri par insertion qui est efficace sur un petit
nombre d’éléments, et qu’on peut utiliser dans un tri rapide)
- Recombiner les solutions obtenues des sous-problèmes pour en déduire la
solution du problème de départ.

31
[Link]
Chapitre 3 : Conception des algorithmes

Autre exemple, le tri rapide, le tri fusion, l’exponentiation rapide, recherche dans
un dictionnaire

IV.3 Heuristique
Une heuristique est un algorithme qui fournit rapidement une solution pas
nécessairement optimale à un problème d’optimisation. Ce n’est donc pas un
algorithme exact. Sur certains problèmes, un algorithme qui donnera une solution
exacte pourra être de complexité exponentielle (la complexité est expliquée plus
loin), donc très longs.

Définition
Une heuristique est une méthode de calcul qui fournit rapidement
(en temps polynomial) une solution réalisable, pas nécessairement optimale, pour
un problème d'optimisation NP-difficile.
Pour les problèmes de grandes tailles :
- pas de temps de calculs ”raisonnables” avec les méthodes exactes
- recherche de ”bonnes” solutions approchées.
Méta-heuristiques : algorithmes d’optimisation (généralement de type
stochastique) combinant plusieurs approches heuristiques.
Quelques méthodes heuristiques
- Programmation dynamique
- Recuit simulé
- Algorithmes génétiques
- Algorithme de colonies de fourmis, recherche Tabou, · · ·

V. Et des mélanges
On n’est pas obligé de suivre un modèle de conception d’algorithme, il peut
être avantageux de prendre le meilleur dans chaque modèle. Par exemple, on va
voir que sur les petites valeurs, le tri par insertion est très efficace, mais que sur
les grandes valeurs, le tri rapide l’emporte. On choisit donc d’utiliser le tri rapide,
avec pour restriction que, si à un moment donné, l’algorithme de tri est appelé sur
moins de 15 éléments, alors on trie ces éléments avec le tri par insertion.

32
[Link]
Chapitre 4 : Complexité algorithmique

Chapitre 4

Complexité algorithmique
I. Complexité des algorithmes
I.1. Introduction
Ce que l’on entend par complexité des algorithmes est une évaluation du coût
d’exécution d’un algorithme en termes de temps (complexité temporelle) ou
d’espace mémoire (complexité spatiale).
Ce qui suit traite de la complexité temporelle, mais les mêmes notions permettent
de traiter de la complexité spatiale.
Ce coût d’exécution dépend de la machine sur laquelle s’exécute l’algorithme, de la
traduction de l’algorithme en langage exécutable par la machine. Mais nous ferons
ici abstraction de ces deux facteurs, pour nous concentrer sur le coût des actions
résultant de l’exécution de l’algorithme, en fonction d’une “taille” n des données
traitées. Ceci permet en particulier de comparer deux algorithmes traitant le
même calcul. Nous verrons également que nous sommes plus intéressés par un
comportement asymptotique (que se passe-t-il quand n tend vers l’infini?) que
par un calcul exact pour n fixé. Enfin, le temps d’exécution dépend de la nature des
données (par exemple un algorithme de recherche d’une valeur dans un tableau
peut s’arrêter dès qu’il a trouvé une occurrence de cette valeur. Si la valeur se
trouve toujours au début du tableau, le temps d’exécution est plus faible que si
elle se trouve toujours à la fin). Nous nous intéresserons d'abord dans ce qui suit à
la complexité en “pire des cas”, qui est une manière, pessimiste, d’ignorer cette
dépendance (on évaluera le temps d’exécution, dans le cas évoqué ci-dessus, en
supposant qu’il faut parcourir tout le tableau pour trouver la valeur cherchée).

I.2. Exemples
Considérons l’exemple 1 suivant:
{début}
R0
I1
{#1}
TANT QUE I ≤ N {#2} FAIRE
R  R+T[I] {#3}
I  I+1 {#4}
FINTANTQUE
{fin}
Le temps d’exécution t(n) de cet algorithme en supposant que:
- N=n
- t1 est le temps d’exécution entre {début} et {#1}
- t2 est le temps d’exécution de la comparaison {#2}
- t3 est le temps d’exécution de l’action {#3}

33
[Link]
Chapitre 4 : Complexité algorithmique

- t4 est le temps d’exécution de l’action {#4}

- t1, t2, t3, t4 sont des constantes (c.à.d. ne dépendent pas de n) s’écrit:

et en définissant le temps tit d’exécution d’une itération (condition comprise), on

obtient:
tit = (t2 + t3 + t4)
d’où t(n) = t1+ t2+ n × tit
Ce qui signifie que le temps d’exécution dépend linéairement (plus précisément
est une fonction affine) de la taille n.
Nous avons dit que nous nous intéressions au comportement asymptotique: que
dire de t(n) quand n tend vers l’infini ?
t( n )
On a : lim =1
n →  tit  n

Autrement dit t(n) est équivalent à l’infini à (tit x n), ce qui s’écrit:
t ( n )  tit  n

L’algorithme est donc asymptotiquement linéaire en n.
Dans cet exemple simple l’évaluation en “pire des cas” est immédiate puisque t(n)
ne dépend pas de la nature des données, ce qui n’est pas le cas de l’exemple 2
suivant:
{début}
R0
I1
{#1}
TANT QUE I ≤ N {#2} FAIRE
R  R+T[I] {#3}
SI R>1000 {#3’} Alors
R  2*R {#3’’}
FINSI
I  I+1 {#4}
FINTANTQUE
{fin}
Ici, le pire des cas (celui qui conduit au temps d’exécution le plus grand) est celui
où la condition {#3’} est toujours vraie. En effet dans ce cas là R 2*R {#3’’} est
exécutée à chaque itération.
Ce qui correspond à l’évaluation suivante du temps d’exécution:

Ici encore l’algorithme est asymptotiquement linéaire en n.

Un usage courant est d’associer un temps constant à chaque type d’opération ou
d’action élémentaire. Ainsi en notant:
- taff le temps correspondant à une affectation,

34
[Link]
Chapitre 4 : Complexité algorithmique

- tp, tm, tc les temps associés respectivement à une addition, une multiplication
et une comparaison, on obtient le temps suivant:

Pour simplifier encore, on confondra les temps associés à plusieurs opérations

différentes (par exemple additions et multiplications seront associées au même
temps to).
Enfin puisque ce qui nous intéresse est l’ordre de grandeur asymptotique de ce
temps, on simplifiera encore en s’intéressant à une catégorie d’opérations ou
d’actions. Par exemple, dans le cas ci-dessus on comptera, plutôt que le temps, le
nombre de telles opérations, ce qui donne, en notant no, le nombre d’additions et
multiplications:
no = 3n
Ce procédé est surtout intéressant si on compte ainsi des opérations
caractéristiques au sens intuitif suivant : le nombre de ces opérations est
asymptotiquement proportionnel au temps d’exécution. Dans le cas ci-dessus, par
exemple, compter les divisions n’aurait pas de sens (il n’y en a pas), alors que le
nombre d’additions et multiplications est asymptotiquement linéaire en n, ce qui
est également le cas du temps d’exécution.
C’est un point important, en effet un algorithme linéaire est bien préférable à un
algorithme quadratique (c.à.d dont le temps d’exécution est asymptotiquement
proportionnel au carré de n) même si pour des valeurs petites de n, le temps réel
d’exécution serait plus faible pour ce dernier.
En effet, à partir d’une certaine valeur de n, l’algorithme quadratique devient
beaucoup plus lent que l’algorithme linéaire. C’est cette évaluation de la tendance
de l’algorithme qui nous intéresse plus qu’une évaluation précise du temps
d’exécution. Comparons ainsi deux algorithmes dont les temps d’exécution ta et tb
seraient les suivants:
ta(n) = 100xn
tb(n) = 2 × n2
Pour n = 50 les deux temps sont identiques, mais pour
n=100, ta = 10.000, tb =20.000
n=1000, ta = 100.000, tb = 2.000.000
n = 10.000, ta =1.000.000, tb = 200.000.000

I.3. Les notations asymptotiques O et Θ

Définition
Soient f et g deux fonctions de IN dans IR +* ,
On dit que f est en O(g) ( f est asymptotiquement dominée par g) s’ il existe un réel
c >0 et un entier positif (un rang) n0 tel que :
Pour tout n > n0, f(n) ≤ c.g(n)

Exemple 1
f(n) = 3n +1, g(n) = n
3n+1 est en O(n)

35
[Link]
Chapitre 4 : Complexité algorithmique

En effet pour n0 = 2, et c = 4 on a bien pour n> n0, l’inégalité 3n +1 ≤ 4n

Définition
Soient f et g deux fonctions de IN dans IR +* ,
On dit que f est en Θ(g) (f et g sont de même ordre de grandeur asymptotique) si f
est en O(g) et g est en O(f).
Exemple 2
f(n) = 3n +1, g(n) = n
3n+1 est en Θ (n)
En effet d’une part, 3n+1 est en O(n), d’autre part pour n0 = 0, et c = 1 on a bien,
pour n> n0, l’inégalité n ≤ (3n+1) et donc n est en O(3n+1)
En pratique f représente une quantité à étudier (temps, nombre d’opérations) et
g fait partie d’une échelle de fonctions simples (n, n2, nlog2(n), etc...) destinée à
informer sur le comportement asymptotique de f.
Remarquons que, si nous reprenons l’exemple 2, il est correct d’affirmer que 3n+1
est en O(n2) cependant, implicitement, on s’intéresse à dominer (3n+1) par la plus
petite fonction possible. C’est ce que permet, intuitivement, d’affirmer la notation
Θ. Dans cet exemple on remarque facilement que (n2) n’est pas en O(3n+1), et donc
que (3n+1) n’est pas en Θ(n2). En effet quelle que soit la valeur de c, il n’existe pas
de rang à partir duquel on aurait (n2) ≤ c(3n+1): il suffit d’essayer de résoudre (n2
– c(3n+1)=0 et d’observer que le discriminant ((3c)2+ 4c) est toujours positif, et
donc qu’à l’extérieur des racines (c’est à dire de rangs particuliers) le polynôme
est >0, ce qui exclut naturellement de trouver un rang à partir duquel on aurait
(n2) ≤c(3n+1).
Propriété 1
f est en Θ(g) si et seulement si:
Il existe c, d réels >0 et un rang n0 tels que, pour tout n > n0, on a :
d. g(n) ≤ f(n) ≤ c.g(n)
La notation Θ se ramène donc à un encadrement (à partir d’un certain rang) de la
quantité f étudiée.
Propriété 2
f(n)
1) Si lim = a  0 alors f est en Θ(g)
n→ g( n )
f(n)
2) Si lim = 0 alors f est en O(g) mais f n' est pas en Θ(g)
n→ g( n )
f(n)
3) Si lim =  alors f n’ est pas en O(g) et donc f n' est pas en Θ(g)
n→ g( n )

Cette propriété permet dans la plus part des cas d’évaluer f.

En pratique on cherchera des équivalents à l’infini de f.
Exemple 3
f(n) = 3n +1
3n + 1
lim = 3  0 Donc f est en Θ(n)
n→ n

36
[Link]
Chapitre 4 : Complexité algorithmique

Exemple 4 : (deux boucles imbriquées sans dépendance des indices).

B0
I1
POUR I  1 à N FAIRE
B  B+2
POUR J  1 à N FAIRE
T[I,J]  (1+T[J,I])*B
FINPOUR
FINPOUR
Soit Op(n) le nombre d’additions et multiplications avec N=n,
n
 n
 n
Op ( n ) =   1 +  2  =  (1 + 2 n ) = n ( 1 + 2 n ) = 2 n 2 + n
 
i =1  j =1  i =1
( 2n + n )
2

lim = 2  0  Op(n) est en Θ(n2)

n→ n2

Exemple 5 : (deux boucles imbriquées avec dépendance des indices)

B0
I1
POUR I  1 à N FAIRE
B  B+2
POUR J  1 à i FAIRE
T[I,J]  (1+T[J,I])*B
FINPOUR
FINPOUR

Remarque importante:
L’affectation, la lecture, l’écriture d’une variable de type élémentaire se fait
en un temps constant (indépendant de n) et est compté comme une opération. Il
en va différemment de l’affectation d’une variable de type non élémentaire,
lorsque ce type dépend de n (qui est une copie de la valeur d’une expression dans
une variable). Ainsi soit un tableau T de taille n, alors:
T2  T correspond à n affectations élémentaires, et si on note Aff(n) le nombre
d’affectations et d’opérations dans l’algorithme suivant:
T[1]  T[N] -T[N-1]
TAMP  T
T  T2
T2  TAMP

37
[Link]
Chapitre 4 : Complexité algorithmique

On obtient Aff(n) =2 + 3n

I.4 Règles du calcul de la complexité «en pire des cas»

Nous essayons ici de fixer des règles pour aider à l’évaluation de la complexité en
temps ou en nombre d’opérations d’un algorithme.
Notons TA(n) le temps ou le nombre d’opérations, « en pire des cas »
correspondant à la suite d’actions A, ou au calcul de l’expression A. Une suite
d’actions est considérée ici comme une action non élémentaire.
Règle 1: Enchaînement
Soient deux suites d’actions A1 et A2, et A1+A2, la suite « A1 suivi de A2 ». Alors:
T(A1+A2)(n) = TA1(n)+ TA2(n)
Règle 2: Conditionnelle
Soit une action A de la forme « SI C ALORS A1 SINON A2 FINSI »
Alors: TA(n) = TC(n) + Max( TA1(n), TA2(n))
En effet, dans le pire des cas, c’est toujours la plus coûteuse des deux actions qui
s’exécute.
Exemple 6
POUR i  1 à N FAIRE
Res  X+Y+Z+Res
SI T[i] + K < B ALORS
{Action1}
POUR j 1 à N FAIRE
Res  Res +T[j]
FINPOUR
SINON
{Action2}
ResRes+T[i]
FINSI
FINPOUR
Soit Op(n) le nombre d’additions « en pire des cas », avec N=n.
Notons Opc(i,n) le nombre d’additions dans la structure «SI.....SINON...FINSI » à la
ième itération de la boucle externe, Op1(i,n) le nombre d’additions dans Action1 et
Op2(i,n) le nombre d’additions dans Action2 :

38
[Link]
Chapitre 4 : Complexité algorithmique

En ce qui concerne les structures itératives, une règle générale pourrait être la
suivante:
Règle 3: Itération (TANTQUE)
Soit une action A de la forme « TANTQUE C FAIRE A1 FINTANTQUE»
En notant niter(n) le nombre d’itérations, on a:

Cependant cette règle est trop abstraite et ce qu’il faut en retenir est surtout le
lien entre les structures répétitives et la sommation, comme nous l’avons vu
précédemment. En particulier il est bon de lier la variable indice de la sommation
avec une variable « compteur » de la structure
répétitive lorsqu’elle existe. Il est cependant intéressant de noter que:
- La condition C est exécutée dans le « TANTQUE» une fois de plus que
le « corps » A1 de la boucle.
- TC n’est pas toujours une constante, mais peut dépendre de n et du rang i de
l’itération, qui est souvent lié à une variable.
Exemple 7
// Nous nous intéressons ici au nombre d’opérations (+,-,*), Op(n), avec N=n
// Nous supposons ici que Truc(l,n)<n et que Truc(l,n) nécessite Tt(n)= (n-l) opérations
// On suppose aussi que Tab est de dimension Nmax ≥ N+1
Res  0
L2
TANTQUE L ≤ Truc(L, N) FAIRE
Res  Res+2*Tab[L+1]+Truc(L,N)
L  L+2
FINTANTQUE
Remarquons d’abord que L augmente de 2 à chaque itération et que dans le pire
des cas la condition testée est L≤ N, pour toute valeur de L (puisque Truc(L,N) ≤N).
Nous pouvons alors écrire Op(n) de la manière suivante:

Pour se ramener à des pas de 1 on pose 2k=l, ce qui permet d’écrire:

39
[Link]
Chapitre 4 : Complexité algorithmique

Remarquons que, sans faire tous les calculs, on pouvait anticiper que Op(n) serait
en Θ(n2) en remarquant que le terme de plus haut degré serait de degré 2.
En ce qui concerne la structure « POUR ........ FAIRE ......... FINPOUR » on procèdera
de la manière suivante: on considère la boucle TANTQUE équivalente:
POUR I  ideb à ifin FAIRE
Action1
FINPOUR
est considéré équivalent à
I  ideb -1
TANTQUE I < ifin FAIRE
I  I+1
Action1
FINTANTQUE
C’est à dire que l’on compte en plus des (ifin-ideb+1) itérations, (ifin-ideb+2)
affectations, additions, comparaisons.
Remarquons qu’une pratique courante consiste à négliger (lorsque cela ne change
pas la complexité) ces opérations implicites dans le «POUR..... », comme nous
l’avons fait ci-dessus.
Exemple 8
POUR I  1 à N FAIRE
Res  Res+I
FINPOUR
Le nombre d’additions est ici N si on néglige ces opérations implicites, et 2N+1 si
on les compte (ici ifin-ideb+1 = N).
Règle 4 : Fonctions et Procédures non récursives
On évalue d’abord les fonctions et procédures qui ne contiennent pas d’appels à
d’autres fonctions et procédures, puis celles qui contiennent des appels aux
précédentes, etc....
Exemple 9
Algorithme Truc
VAR C: CARACTERE
N, R0, R1,I: ENTIER
PROCEDUR A (VAR R : ENTIER)
VAR I: ENTIER
DEBUT
POUR I  1 à N FAIRE
R  R*I
FINPOUR
FIN
PROCEDUR B (Var R: ENTIER)
VAR I,J: ENTIER
DEBUT
J1
POUR I  1 à N FAIRE
A(J)

40
[Link]
Chapitre 4 : Complexité algorithmique

R  R*J
FINPOUR
FIN
DEBUT
LIRE(C)
LIRE(N)
R0  1
R1  1
{debut #1}
SI C =‘#’ ALORS
{début ##1}
POUR I  1 à N FAIRE
R1  2*R1
B(N)
FINPOUR
{fin ##1}
FINSI
{Fin #1}
{début #2}
A(N)
{fin #2}
FIN
Nous calculons ici le nombre de multiplications Op(n) pour N=n.
Nous observons d’abord que l’algorithme, dans le pire des cas (ici C=‘#’)

où OpA(n) et OpB(n) représentent le nombre de multiplications correspondant à

l’exécution de A et de B.
De plus on a:

Et finalement

Le calcul se déroule alors ainsi:

Remarque importante:
Lorsqu’on fait un appel, il faut en toute rigueur compter l’appel lui-même
comme une opération particulière, mais aussi compter les opérations
correspondant au passage de l’argument.

41
[Link]
Chapitre 4 : Complexité algorithmique

Plus précisément: lors d’un passage par valeur quelles sont les opérations mises
en jeu? Pour chaque argument passé il faut évaluer l’argument (par exemple
l'addition pour Factorielle(n+1), et affecter cette valeur à une nouvelle variable
(locale à la fonction). On néglige souvent cette dernière opération, cependant si
l’argument passé est un tableau de taille N, alors l’affectation correspond à N
affectations élémentaires, et ce coût n’est plus négligeable. C’est en particulier une
des raisons pour lesquelles on évite souvent de passer par valeur un tableau
même si sa valeur ne doit pas être modifiée par la procédure (ou fonction). En
effet un passage par adresse ne correspond pas à N affectations élémentaires
puisque seule l’adresse en mémoire du tableau est fournie à la procédure lors de
l’appel.

I.5. Comparaison de deux algorithmes

Considérons ici le problème suivant: nous disposons d’un tableau T de N entiers (N
pair) ayant la propriété suivante: les N/2 premiers éléments de T se retrouvent
dans la seconde moitié du tableau mais en ordre inverse (par exemple
T=(1,3,5,7,7,5,3,1) ). Nous donnons ci-dessous deux fonctions calculant la somme
des éléments du tableau:
Const N = 100
TYPE Tabentier = ENTIER [1..N]
FONCTION Somme1( T:Tabentier): ENTIER
VAR I, R: ENTIER
DEBUT
I1
R0
TANTQUE I <= N FAIRE
R  R+T[I]
I  I+1
FINTANTQUE
retourner (R)
FIN
FONCTION Somme2(T:Tabentier) : ENTIER
VAR I,R,M: ENTIER
DEBUT
I1
R0
M  N/2
TANTQUE I <= M FAIRE
R  R+T[I]
I  I+1
FINTANTQUE
retourner (R+R)
FIN
Comptons les nombres d’additions Op1(n) et Op2(n) dans les deux fonctions:
Op1(n) = 2n, Op2(n) = 2 (n/2) +1= n+1
Si nous comparons ces deux fonctions, les nombres d’additions sont de même
ordre de grandeur asymptotique:

42
[Link]
Chapitre 4 : Complexité algorithmique

Plus précisément :

C’est à dire qu’asymptotiquement Somme2 nécessite deux fois moins d’opérations

que Somme1.
Plus généralement lorsqu’on compare deux algorithmes effectuant la même tâche,
on comparera surtout les ordres de grandeur asymptotique (L’un est-il
quadratique et l’autre linéaire?) mais aussi plus finement, comme dans le cas ci-
dessus, le rapport asymptotique des nombres d’opérations ou des temps
d’exécution.

I.6. Cas des procédures et fonctions récursives

Dans ce cas on obtient, lorsqu’on calcule un temps d’exécution ou un nombre
d’opérations, des équations de récurrence.
Exemple 1
Considérons le cas de n!, pour lequel nous avons écrit précédemment la fonction
Fact, en utilisant les propriétés suivantes:
Fact(0) =1
Fact(n) = n*fact(n-1)
Si nous nous intéressons au temps d’exécution, nous obtenons l’équation suivante
(où t0 et t1 sont des constantes):
Op(0) = t0
Op(n) = Op(n-1) + t1
Nous résolvons cette équation par substitutions successives. Une méthode pour
présenter les substitutions consiste à écrire les équations de manière à ce qu’en
sommant celles-ci on ait à gauche Op(n) et à droite une expression non
récurrente:
{1} Op(n) = Op(n-1) + t1
{2} Op(n-1) = Op(n-2) + t1
{3} Op(n-2) = Op(n-3) + t1
.......
{k} Op(n-k+1) = Op(n-k) + t1
........
{n-1} Op(2) = Op(1) + t1
{n} Op(1) = t0 + t1
------------------------------------
Op(n) = t0+ n.t1 Donc Op(n) est en Θ(n).
Le cas où il y a plusieurs appels, est souvent plus difficile. Par exemple l’équation
de récurrence correspondant à Fib(n) est la suivante:
Op(0)= Op(1) = t0
Op(n) = Op(n-1) + Op(n-2) + t1
Cette équation est assez difficile, mais nous reviendrons plus tard sur une
majoration.
Un cas plus simple est le suivant:

43
[Link]
Chapitre 4 : Complexité algorithmique

FONCTION Mib(N:ENTIER; P: ENTIER): ENTIER

VAR Res : ENTIER
/* on suppose que N≥0 et P≤N */
DEBUT
SI N = 0 ALORS
Res  P
SINON
Res  Mib(N-1,P-1) + Mib(N-1,P) + P
FINSI
RETOURNER(Res)
FIN
Ici nous obtenons les équations de récurrence suivantes, en remarquant que le
temps d’exécution ne dépend pas de la valeur de P:
Op(0) = t0
Op(n) = 2Op(n-1) +t1
On peut utiliser la méthode précédente, mais pour obtenir les simplifications
voulues on double chaque nouvelle équation:
{1} Op(n) = 2Op(n-1) + t1
{2} 2 Op(n-1) = 22 Op(n-2) + 2t1
{3} 2 Op(n-2)
2 = 2 Op(n-3)
3 + 22 t1
.......
{k} 2 Op(n-(k-1)) = 2k Op(n-k) + 2k-1 t1
k-1

........
{n-1} 2n-2 Op(2) =2n-1 Op(1) +2n-2 t1
{n} 2n-1 Op(1) = 2n t0 + 2n-1 t1
------------------------------------
Op(n) = 2n t0 + ( 1+2 + 22+ ...+2n-1) t1
= 2 t0 +((2 -1) / (2-1)) t1
n n

Donc Op(n) est en Θ(2n)

I.7. Complexité en moyenne

En ce qui concerne la complexité moyenne, le point de vue adopté est probabiliste
: plutôt que calculer une quantité en considérant la pire situation, c’est à dire la
pire configuration des données d’entrée, on considère l’univers de toutes les
configurations possibles, chacune associée à une probabilité, et on fait une somme
pondérée, par ces probabilités, des valeurs prise par cette quantité dans les
différentes configurations. C’est ce qu’on appelle l’espérance mathématique, ou
plus communément, la moyenne de cette quantité selon ce modèle de probabilité.
Une quantité, considérée dans le cadre probabiliste, s’appelle une variable
aléatoire.

II. Analyse des algorithmes de tri

Il s'agit d'un problème classique (et utile) de l'algorithmique. On considère un
ensemble d'éléments possédant une relation d'ordre total (Exemple: entiers,
réels, caractères).
On cherche à ordonner cet ensemble dans l'ordre croissant (ou décroissant).

44
[Link]
Chapitre 4 : Complexité algorithmique

II.1. TRI PAR SELECTION

II.1.1 Principe
Soit un ensemble de n éléments indicés de 0 à n-1. On suppose que les m premiers
éléments (0 à m-1) sont triés.
On cherche la position k du plus petit élément parmi les éléments m à n-1. On le
permute avec l'élément m. L'ensemble se trouve donc trié de l'indice 0 à l'indice
m.
On parcourt ainsi l'ensemble de l'élément m=0 à l'élément n-2.

II.1.2 Illustration
En gras, les éléments déjà triés, en italique, les éléments à permuter.

Algorithme

Soit à trier un tableau de N éléments (entiers), t[0] à t[N-1]

POUR m  0 à N-2 FAIRE

k  p (indice du plus petit élément entre t[m] et t[N-1])
SI k est différent de m ALORS
permuter t[k] et t[m]
FIN SI
FIN POUR
II.1.3 Analyse
Cet algorithme nécessite n2/2 comparaisons et n permutations. Pour un nombre
d'éléments donné, il effectue le même nombre d'opérations que les éléments
soient pratiquement déjà triés ou totalement en désordre. Sa complexité est en
O(n2).

II.2. TRI A BULLES

II.2.1. Principe
Le principe consiste à parcourir les éléments de l'ensemble de i=0 à n-1 en
permutant les éléments consécutifs non ordonnés.
L'élément le plus grand se trouve alors en bonne position. On recommence la
procédure pour l'ensemble de i=0 à n-2 sauf si aucune permutation n'a été

45
[Link]
Chapitre 4 : Complexité algorithmique

nécessaire à l'étape précédente. Les éléments les plus grands se déplacent ainsi
comme des bulles vers la droite du tableau.
II.2.2. Illustration

En italique, les deux éléments à comparer, en gras les éléments en bonne place.

Algorithme

j  N-1
FAIRE
POUR i  0 à J-1 FAIRE
SI t[i] > t[i+1] ALORS
permuter t[i] et t[i+1]
permutation  VRAI
FIN SI
FIN POUR
TANT QUE permutation=VRAI

II.2.3 Analyse
Dans le pire des cas, le nombre de comparaisons et le nombre de permutations à
effectuer sont de n2/2. Dans le meilleur des cas (ensemble déjà trié), le nombre de
comparaisons est de n-1 et l'algorithme est donc de complexité linéaire.

II.3. TRI PAR INSERTION

II.3.1 Principe
On prend 2 éléments et on les met dans l'ordre. On prend un troisième élément
qu'on insère dans les 2 éléments déjà triés, etc..
Un élément m va être inséré dans l'ensemble déjà trié des éléments 0 à m-1. Ce qui
donnera m+1 éléments triés (0 à m).

46
[Link]
Chapitre 4 : Complexité algorithmique

L'insertion consiste à chercher l'élément de valeur immédiatement supérieure ou

égale à celle de l'élément inséré. Soit k l'indice de cet élément, on décale les
éléments k à m-1 vers k+1 à m et l'on place l'élément à insérer en position k.

II.3.2 Illustration

En gras, l'élément à insérer dans la partie triée du tableau.

Algorithme

POUR i  0 à N-1 FAIRE /* insérer le ième element */

POUR j  i à 1 FAIRE
SI t[j] < t[j-1] ALORS
permuter t[j] et t[j-1]
FIN SI
FIN POUR
FIN POUR

II.3.3 Analyse
Dans le pire des cas, le nombre de comparaisons et de n2/2. Dans le meilleur des
cas il est de N.
L'algorithme est de complexité O(N2) mais il est plus efficace que les deux
précédents si le tableau est en partie trié.

II.4 TRI PAR FUSION

II.4.1 Principe
Cet algorithme divise en deux parties égales le tableau de données en question.
Après que ces deux parties soient triées d’une manière récursive, elles sont
fusionnées pour le tri de l’ensemble des données.

II.4.2 Illustration

47
[Link]
Chapitre 4 : Complexité algorithmique

Algorithme
On considère un nouveau tableau temp de même type que t

PROCEDURE mergesort(t: ENTIER[], temp: ENTIER[], left: ENTIER, right: ENTIER)

VAR
i, j, k, mid: ENTIER
DEBUT
mid  (left+right)/2
SI (left = right) ALORS
Retourner
FINSI
mergesort(t, temp, left, mid) /* la première moitié */
mergesort(t, temp, mid+1, right) /* la deuxième moitié */
// Pour l’opération de fusion, copier les deux moitiés dans temp
POUR (i  left à mid) FAIRE
temp[i]  t[i]
FINPOUR
POUR (j  1 à right-mid ) FAIRE
temp[right-j+1]  t[j+mid]
FINPOUR
// fusionner les deux moitiés dans t
POUR (I  left, j  right, k left à right) FAIRE
SI (temp[i] < temp[j]) ALORS
t[k]  temp[i]
i  i+1
SINON
t[k]  temp[j]
j  j-1

48
[Link]
Chapitre 4 : Complexité algorithmique

FINSI
FINPOUR
FIN

II.4.3 Analyse
La complexité de cet algorithme est donnée par la relation suivante:

O ( 1 ) Si n = 1
T(n) = 
T ( n / 2  ) + T ( n / 2  ) + O ( n )
 Si n  1
n étant le nombre d’éléments dans le tableau.
Dans le but de simplifier la résolution de l’équation ci-dessus, nous supposons
que n=2k pour un entier k ≥ 0. En remplaçant O(n) par n, on obtient (en principe,
on doit la remplacer par cn):

1 Si n = 1
T(n) = 
 2T ( n / 2 ) + n Si n  1


T(n) = 2T(n/2) + n
= 4T(n/’) + 2n
= 8T(n/8) + 3n
:
= 2k T(n/2k) + kn
:
= nT(1) + nlog2(n)
= n + nlog2(n)
La complexité temporelle de tri par fusion est donc en O(n log n).

II.5 LE TRI RAPIDE

II.5.1 Principe
La stratégie de l’algorithme de tri rapide (Quicksort) consiste, dans un premier
temps, à diviser le tableau en deux parties séparées par un élément (appelé pivot)
de telle manière que les éléments de la partie de gauche soient tous inférieurs ou
égaux à cet élément et ceux de la partie de droite soient tous supérieurs à ce pivot
(dans l’algorithme donné ci-dessous, la partie qui effectue cette tâche est appelée
partition). Ensuite, d’une manière récursive, ce procédé est itéré sur les deux
parties ainsi crées. Au départ, le dernier élément du tableau est choisi comme
pivot.
Algorithme
PROCEDURE tri_rapide_bis(tableau: ENTIER[], debut: ENTIER, fin : ENTIER)
VAR
pivot : ENTIER
DEBUT
SI (debut<fin) ALORS
pivot  partition(tableau,debut,fin)
tri_rapide_bis(tableau,debut,pivot-1)

49
[Link]
Chapitre 4 : Complexité algorithmique

tri_rapide_bis(tableau,pivot+1,fin)
FINSI
FIN

PROCEDURE tri_rapide(tableau: ENTUER[], n : ENTIER)

DEBUT
tri_rapide_bis(tableau,0,n-1)
FIN

PROCEDURE echanger(tab : ENTIER[], i : ENTIER, j : ENTIER)

VAR
memoire : ENTIER
DEBUT
Memoire  tab[i]
tab[i]  tab[j]
tab[j]  memoire
FIN

FONCTION partition(tableau: ENTIER[], deb : ENTIER, fin : ENTIER) : ENTIER

VAR
pivot : ENTIER
i : ENTIER
DEBUT
pivot  tableau[fin]
i  debut
j  fin
FAIRE
i  i+1
TANTQUE (tableau[i] < pivot)
ii+1
FINTANTQUE
TANTQUE (tableau[j] > pivot)
j  j-1
FINTANTQUE
SI (i < j) ALORS
echanger (tableau,i,j)
FINSI
TANTQUE (i < j)
tableau[deb]  tableau[j]
tableau[j]  pivot;
RETOURNER(j)
FIN
II.5.2 Choix du pivot

Le choix idéal serait que ça coupe le tableau exactement en deux parties

égales. Mais cela n’est pas toujours possible. On peut prendre le premier élément.
Mais il existe plusieurs autres stratégies!

50
[Link]
Chapitre 4 : Complexité algorithmique

Partitionnement :
On parcourt le tableau de gauche à droite jusqu'à rencontrer un élément
supérieur au pivot

On parcourt le tableau de droite à gauche jusqu'à rencontrer un élément inférieur

au pivot

On échange ces deux éléments

et on recommence les parcours gauche-droite et droite-gauche jusqu'à avoir :

il suffit alors de mettre le pivot à la frontière (par un échange)

II.5.3 Illustration

II.5.4 Analyse
À l’appel de QuickSort (1,n), le pivot se place en position i. Ceci nous laisse avec un
problème de tri de deux sous parties de taille i-1 et n-i. L’algorithme de partition a
une complexité au plus de cn, pour une constante c.

51
[Link]
Chapitre 4 : Complexité algorithmique

Voyons les trois cas possibles de complexité:

Cas défavorable
Le pivot est à chaque fois le plus petit élément. La relation de récurrence devient :

………….. …………………………

En ajoutant membre à membre, on obtient : T ( n ) = O ( n )

2

Cas favorable
Dans le meilleur des cas, le pivot est, à chaque fois, situé au milieu de la partie à
trier.

Ce développement s’arrête dès qu’on atteint T(1). Autrement dit, dès que

II.6 ALGORITHME DE RECHERCHE DANS UN ENSEMBLE

Un problème courant est la recherche d'un élément particulier dans un ensemble.
La solution la plus simple consiste à parcourir l'ensemble des éléments jusqu'à
trouver celui que l'on cherche.
Dans le cas où l'ensemble de recherche est trié, une solution plus efficace consiste
à faire une recherche dichotomique.
On peut aussi utiliser des tables de hachage. Le principe consiste à associer à
chaque élément de l'ensemble une clé calculée, cette clé permettant un accès
direct à un élément. Le calcul de la clé pour l'élément recherché permet d'y
accéder directement.
On crée en général un index contenant l'information sur lequel se fera la
recherche.

52
[Link]
Chapitre 4 : Complexité algorithmique

II.6.1 Recherche séquentielle

La recherche séquentielle consiste à parcourir chaque élément de l'ensemble avec
celui recherché.
En général cette recherche se fait sur une information particulière de l'élément ou
dans une table d'index. Cette méthode fonctionne que l'ensemble soit trié ou non.
Dans le meilleur cas, cela prendra une seule comparaison, dans le pire des cas, il
faudra effectuer n comparaisons. En moyenne on aura n/2 comparaisons à
effectuer.
La complexité de l'algorithme est donc en O(n).

II.6.2 Recherche dichotomique

Dans le cas ou l'ensemble est trié par rapport à l'index sur lequel doit se faire la
recherche (par exemple le nom pour un annuaire), un algorithme plus efficace
que la simple recherche séquentielle peut être utilisé.
On compare l'élément recherché avec celui du milieu de l'ensemble. Si c'est le
même, la recherche est terminée sinon c'est qu'il est plus grand ou plus petit et on
recommence en ne gardant que la moitié de l'ensemble. On divise ainsi l'ensemble
de recherche par deux à chaque itération. La complexité de l'algorithme est donc
en O(log n).
II.6.3 Tables de hachage
Le hachage consiste à calculer une clé h(x) (nombre entier) pour chaque élément
x. h(x) contient l'endroit ou l'on trouve x dans l'ensemble. Si l'application est
injective (une clé unique par élément), il suffit de calculer la clé de l'élément
recherché et, s'il existe, on y accède directement.
Pour des chaînes de caractères S = s0s1s2…sl n utilise par exemple la fonction:
h(S) = (s0Bl-1 + s1Bl-2 + …. + sl-2 B + sl-1) mod N

53
[Link]
Chapitre 4 : Complexité algorithmique

Où N est la taille de la table de hachage (on choisi un nombre premier) et B une

puissance de 2.
si est le code ASCII du caractère d'indice i de la chaîne.
En pratique, l'unicité de la clé pour une entrée est rarement réalisable. On peut
donc avoir plusieurs éléments ayant la même clé. On parle de collision. Une
méthode simple de gérer les collisions et de les lister dans une table parallèle.

54
[Link]
Chapitre 5 : Preuve d’algorithmes

Chapitre 5

Preuve d’algorithmes

I. Introduction
La question principale qui se pose à tout informaticien est :
Comment savoir qu’un algorithme donne le résultat espéré ?
Voici quelques exemples où il est nécessaire d’avoir des algorithmes corrects
• Contrôle de pilote automatique
• Contrôle des commandes d’un avion
• Centrale nucléaire
• Robots médicaux
• Bases de données critiques : Chemins de fer, Banque, etc
• Circuits électroniques
• Sécurité des systèmes d’information
• Sécurité des puces électroniques
Comment faire en sorte que l’on soit sûr de la correction de l’algorithme ?
• Générer un ensemble de tests. Mais la plupart du temps, on n’a pas de
garantie que l’algorithme est correct.
• Vérifier que l’algorithme correspond bien aux attentes. Cette opération
couvre plusieurs méthodes, parfois compliquées mais très sûr (à condition
de ne pas faire d’erreur dans la preuve…)
Exemple : Recherche du maximum dans un tableau de réels
FONCTION maximum(T :Reel[0..n]) : Reel
VAR Max : Reel
i : Entier
Début
Max  T[0]
POUR i1 a n-1 FAIRE
SI T[i-1]<T[i] ALORS
Max  T[i]
FIN SI
FIN POUR
Retourner Max
FIN
• La fonction donne-t-elle bien l’élément maximum du tableau
• En général les étudiants sont très confiants de leur algorithme

II. Preuves de correction d’un algorithme

55
[Link]
Chapitre 5 : Preuve d’algorithmes

II.1 Preuve par invariant de boucle

II.1.1 Description de la méthode
Une preuve d’algorithme par invariant de boucle utilise la démarche suivante :
▪ Nous prouvons tout d’abord que l’algorithme s’arrête en montrant qu’une
condition d’exécution de boucle finit par ne plus être réalisée.
▪ Nous exhibons alors un invariant de boucle, c’est-à-dire une propriété P
qui, si elle est valide avant l’exécution d’un tour de boucle, est aussi valide
après l’exécution du tour de boucle. Nous vérifions alors que les conditions
initiales rendent la propriété P vraie en entrée du premier tour de boucle.
Nous en concluons que cette propriété est vraie en sortie du dernier tour de
boucle. Un bon choix de la propriété P prouvera qu’on a bien produit l’objet
recherché.
La difficulté de cette méthode réside dans la détermination de l’invariant de
boucle. Quand on le trouve, il est en général simple de montrer que c’est bien un
invariant de boucle.

II.1.2 Exemples
▪ Algorithme de division euclidienne par soustraction
Bb
Ra
Q0
TANT QUE R >= B FAIRE
RR−B
QQ+1
FINTANTQUE
Remarquons que les conditions initiales donnent :
a = B x Q + R.
Montrons que la propriété a = B x Q + R est un invariant de boucle : notons R′, B′, Q′
les nouvelles valeurs en sortie de B, Q et R. Alors
R′= R − B et Q′= Q + 1.
Ceci prouve que
B′x Q′+ R′= B xQ+ R.
De plus la quantité entière R-B diminue strictement à chaque tour, donc le
programme se termine et après la boucle on a :
a = B x Q + R et R < B.
▪ Version binaire de l’algorithme de division euclidienne
On calcule avant toute chose par duplications successives le plus petit entier n ≥ 0
tel que 2nb > a.
Bb
Ra
Q0
Nn
Aux  2NB

56
[Link]
Chapitre 5 : Preuve d’algorithmes

TANT QUE N > 0 FAIRE

Aux  Aux/2
NN−1
SI R < Aux ALORS
Q2xQ
SINON
Q2xQ+1
R  R − Aux
FINSI
FINTANTQUE
Montrons que les conditions :
 Aux = 2 N B

 a = Aux * Q + R

 0  R  Aux

 N0
Constituent un invariant de boucle. Ces conditions sont bien réalisées à l’état
initial. Nous noterons Aux′, Q′, R′, N′ les valeurs en sortie de Aux,Q,R,N. Si en entrée
de boucle les conditions précédentes sont remplies alors : dans la boucle Aux′ =
Aux/2 et N′ = N - 1 donc
Aux′ = 2N′B. De plus :

• 1er cas : R < Aux′

Dans ce cas R′= R, Aux est divisé par 2 tandis que Q est multiplié par 2. On a donc
bien les conditions indiquées en sortie.

• 2ème cas : Si R ≥ Aux′ alors on sait que :

Aux′≤ R < Aux = 2 x Aux′
On a aussi Aux′= Aux/2, Q′= 2 x Q + 1, R′= R − Aux′ et R′< Aux′. On a donc bien les
conditions attendues.
De plus N décroît strictement, donc le programme se termine avec N = 0. Quand N
= 0 la variable Aux contient b, Q contient q et R contient r.
▪ Algorithme d’Euclide de calcul du pgcd

R0  |a|
R1  |b| /* b différent de 0 */
TANT QUE R1 > 0 FAIRE
R  Reste_Division(R0,R1)
R0  R1
R1  R
FINTANTQUE
En sortie R1 = 0 et R0 = pgcd(a, b).
Les conditions :
• L’ensemble des diviseurs communs de R0 et R1 est l’ensemble des
diviseurs communs de a et b.

57
[Link]
Chapitre 5 : Preuve d’algorithmes

• R1 ≥ 0
Constituent un invariant de boucle.
Remarquons qu’initialement l’ensemble des diviseurs communs de R0 et R1 est
l’ensemble des diviseurs communs de a et de b. Notons R0′, R1′ les nouvelles
valeurs de R0, R1 en sortie d’un tour de boucle. Nous avons alors
R0′= R1 et R1′= R0 - QR1 avec 0 ≤ R1′< R1.
Donc tout diviseur de R1 et R0 est diviseur de R0′ et R1′, et réciproquement.
Cet algorithme se termine car R1 décroît strictement à chaque tour de boucle. A la
fin R1 = 0, donc l’ensemble des diviseurs de R0 et de R1 est l’ensemble des
diviseurs de R0, et par conséquent R0=pgcd(a,b).
▪ Algorithme d’Euclide étendu

Là encore nous supposerons que a≥0 et b>0. Le cas général s’en déduit. Notons
d=pgcd(a, b).
Voici un algorithme (algorithme d’Euclide étendu, adaptation de l’algorithme
précédent) qui permet de trouver explicitement un couple (u,v) qui vérifie : ua +
vb = d.
R0  a /* a ≥ 0 */
R1  b /* b > 0 */
U0  1
U1  0
V0  0
V1  1
TANT QUE R1 > 0 FAIRE
Q  Quotient_Division(R0,R1)
R  Reste_Division(R0,R1)
U  U0 − Q x U1
V  V0 − Q x V1
R0  R1
R1  R
U0  U1
U1  U
V0  V1
V1  V
FINTANTQUE
Remarquons qu’il s’agit d’une amélioration de l’algorithme d’Euclide donné
précédemment pour le calcul du pgcd. Comme précédemment l’algorithme se
termine avec R1 = 0 et R0 = pgcd(a, b).
Montrons que les conditions :
 U 0 a + V 0 b = R0

 U 1a + V 1b = R1

 R 1  0

58
[Link]
Chapitre 5 : Preuve d’algorithmes

Constituent un invariant de boucle. Pour cela notons R0′, R1′, U0′, U1′, V0′, V1′ les
nouvelles valeurs de R0, R1, U0, U1, V0, V1 en sortie d’un tour de boucle. On a :
R0 = Q x R1 + R,
U = U0 − Q x U1,
V = V0 − Q x V1,
puis
R0′= R1
R1′= R = R0 − Q x R1
U0′= U1
U1′= U = U0 − Q x U1
V0′= V1
V1′= V = V0 − Q x V1
Si bien que :
U0′a + V0′b = U1a + V1b = R1 = R0′
La première condition est bien réalisée en sortie. De même on a :
U1′a + V 1′b = U0a + V0b − Q x (U1a + V1b) = R0 − Q x R1 = R′1.
Donc la deuxième condition est aussi réalisée.
Il est facile de voir qu’à l’instant initial ces deux conditions sont bien réalisées. En
sortie on a R1 = 0 et R0 = pgcd(a, b) si bien que U0 et V0 contiennent une solution
du problème.
▪ Calcul d’une puissance
Soit n ≥ 1 un entier. On veut calculer an (a est par exemple dans Z/nZ ou dans R,
C,...). On considère l’algorithme suivant:
Aa
Nn
R1
TANT QUE N > 0 FAIRE
SI N pair ALORS
AAxA
N  N/2
SINON
RRxA
NN−1
FINSI
FINTANTQUE
Cet algorithme se termine et en sortie R contient an.
Preuve :
La valeur de N ≥ 0 décroît strictement à chaque tour de boucle, donc
l’algorithme se termine.
Au début on a AN × R = an.
Si en entrée de boucle AN × R = an alors il est facile de voir que dans les deux cas N
pair ou N impair on a la même égalité en sortie de boucle. Mais à la fin on a N = 0 et
par conséquent R = an.

III. TESTS

59
[Link]
Chapitre 5 : Preuve d’algorithmes

Définition
Le test consiste à essayer de trouver des erreurs ou à augmenter la
confiance dans la correction d’une implantation par rapport à sa spécification
Spécification : propriété (abstraite) qui caractérise une fonction de l’algorithme
Implantation : programme exprimant un algorithme dans un langage donné

En fait, le test n’a pas pour but d’établir la correction d’un algorithme..
Avec un langage impératif
- Dans ce cas l’état peut être l’état de la mémoire :
Après chaque opération, un état de la mémoire est attendu
- Il faut alors tester toutes les transitions possibles et comparer à l’état
attendu
- Ou alors exhiber un contre-exemple, trouver une exécution où le résultat
attendu est différent du résultat constaté
Il est possible d’automatiser cette opération mais nous n’allons pas le faire dans
ce cours.
Exemple
FONCTION maximum(T :Reel[0..n]) : Reel
VAR Max : Reel
i : Entier
Début
Max  T[0]
POUR i1 a n-1 FAIRE
SI Max<T[i] ALORS
Max  T[i]
FIN SI
FIN POUR
Retourner Max
FIN

On augmente la probabilité que l’algorithme soit correct avec le nombre de tests.

Erreurs fréquemment rencontrées

Conseil éternel dans votre pratique informatique (ou non) :

Au moins faire 1 test !
Imaginer des séquences qui peuvent poser problème :
- Début et fin de tableau
- Répétition d’un même élément
- Valeurs critiques : taille nulle, etc..

Attention : ce n’est pas parce que l’algorithme fonctionne sur 1 exemple que l’on
peut généraliser
Exemple : Recherche du maximum dans un tableau de réels

60
[Link]
Chapitre 5 : Preuve d’algorithmes

FONCTION maximum(T :Reel[0..n]) : Reel

VAR Max : Reel
i : Entier
Début
Max  T[0]
POUR i1 a n-1 FAIRE
SI T[i-1]<T[i] ALORS
Max  T[i]
FIN SI
FIN POUR
Retourner Max
FIN
On s’attend que Max contient toujours le maximum du tableau lu entre 0 et n.
Il est facile de trouver un contre-exemple :
8 2 3 1
Pour i=1, Max =8
Pour i=2, max =3

61
[Link]
 Série d’exercices à traiter en TD

Exercices d’ordre général

Exercice 1
Ecrivez un algorithme permettant, à l’utilisateur de saisir les notes d'une classe. Une fois la
saisie terminée, l’algorithme renvoie le nombre des notes supérieures à la moyenne de la classe.

Exercice 2
Ecrire un algorithme qui calcule, à une valeur approchée u donnée, la racine carrée d'un
nombre a > 0 sachant que la suite suivante :
X1 = a
Xn = (a/Xn-1 + Xn-1 ) / 2
converge vers la racine carrée de a.

Exercice 3
Considérons un tableau T de N nombres entiers (N > 1). On veut écrire un seul algorithme
qui répond aux questions suivantes :
- déterminer le troisième nombre premier s'il existe,
- déterminer le deuxième carré parfait s'il existe,
- déterminer le nombre de diviseurs du premier nombre pair et du dernier nombre impair.
Pour cela, créer et utiliser les fonctions suivantes dans l’algorithme développé :
- la fonction prem(nombre) de type booléen qui est égal à vrai si le paramètre nombre est
premier, faux sinon.
- la fonction carré(nombre) de type booléen qui est égal à vrai si le paramètre nombre est
un carré parfait, faux sinon.
- la fonction nbdiv(nombre) de type entier qui donne le nombre de diviseurs du paramètre
nombre.

Exercices sur les structures et les fichiers

Exercice 1
Ecrivez un algorithme qui permet de modifier un renseignement (pour simplifier, disons
uniquement le nom de famille) d’un membre du carnet d’adresses. Il faut donc demander à
l’utilisateur quel est le nom à modifier, puis quel est le nouveau nom, et mettre à jour le fichier. Si
le nom recherché n'existe pas, le programme devra le signaler.

Exercices sur la récursivité

Exercice 1
Soit la fonctions f donnée par :
Fonction f(n: entier, Var cmpt : entier): entier
Début
cmpt cmpt + 1
Si (n < 2) Alors
Retourner n
Sinon
Retourner f(n-1, cmpt) + f(n-2, cmpt)
Fin Si
Fin

62
 Série d’exercices à traiter en TD

On fait appel à la fonction f avec n=3 et cmpt=0. Quelle est la valeur retournée par cet appel ?
Quelles sont les valeurs de n et de cmpt après l’exécution de cet appel ?
Exercice 2
On considère la procédure suivante :
Procédure mystere (T: Entier[1..N])
Var i, j : entier
Début
i 1
j N
Tant que (i < j) Faire
Si (T[i] = 0) Alors
i i+1
Sinon
Echanger(T[i], T[j])
j j-1
Fin Si
Fin Tant que
Fin
Où Echanger(T[i],T[j]) est la procédure qui permute les valeurs des cases d’indices i et j.
1. Que fait-elle en supposant que le tableau T ne contient que des 0 et des 1 ?
2. Modifier la procédure de façon à l'appliquer à des tableaux contenants, au plus, trois valeurs
différentes : par exemple 0, 1 et 2 (rappel : chaque élément de T doit être examiné au maximum
une fois).
3. Donner une version récursive de la procédure.

Exercice 3 : Dérécursification de la fonction d’Euclide

La fonction récursive, ci-dessous, nous donne le PGCD de deux entiers n et m
FONCTION PGCD(n, m: ENTIER): ENTIER
// n>=0, m>=0
DEBUT
SI (m = 0) ALORS
Retourner(n)
SINON
Retourner PGCD(m, n MOD m)
FIN SI
FIN
Transformer cette fonction récursive en une fonction itérative

Exercice 4 : Dérécursification de la fonction de Fibonacci

Considérons la suite de Fibonacci, dont voici la définition :
f ( 1 ) =1
f ( 2 ) =1
f ( n ) = f ( n-1 ) + f ( n-2 ),  n >2.

La fonction récursive, ci-dessous, nous donne le nème terme de la suite de Fibonacci :

FONCTION fibo_rec(n: ENTIER): ENTIER
DEBUT
SI (n<=0) ALORS
ECRIRE("La valeur de n doit etre un entier strictement positif")
Sortir
FIN SI

63
 Série d’exercices à traiter en TD

SI (n < 3 ET n> 0) ALORS Retourner 1

SINON
Retourner fibo_rec(n - 1) + fibo_rec(n - 2)
FIN SI
FIN

Transformer cette fonction récursive en une fonction itérative

Exercice 5 :
Ecrire une procédure itérative puis récursive permettant de renverser les éléments d’un
tableau T[1..N] de réels.

Exercice 6 :
Ecrire une fonction itérative puis récursive qui retourne Vrai si un tableau T[1..N] de réels
est trié par ordre croissant, sinon elle retourne Faux.

Exercices sur la complexité des algorithmes

Exercice 1
Montrer que pour toutes constantes réelles a et b avec b > 0, nous avons :
(n + a)b = O(nb)
Cette relation est-elle vraie pour la notation  ?

Exercice 2
Trouver l’ordre de grandeur des fonctions suivantes :
1. n2 + 2n ; log n2
2. log 3n ; n + 1/n
3. n + log n

Exercice 3
Parmi les relations suivantes, quelles sont celles qui sont correctes.
1. O(1) = O(10); O(1) = 10; n+1 = O(n),  étant une constante
n
2. (n + 1)! = O(n!) ; 2 = O(n!), ; n! = O(2n); log nn = O(log n!); nn = O(n!)

Exercice 4
Quelle est la valeur de k à la sortie de la boucle de la portion d’algorithme ci-dessous :
k 1
Tant que (k <= n) Faire
kk*2
Fin tant que
En déduire la complexité temporelle de cette portion d’algorithme

Exercice 5
Calculer les complexités temporelles en fonction de la variable n des portions d’algorithme
ci-dessous.

Algorithme 1
d 1
Tant que (d*d <= n) Faire
dd*2
Fin Tant que

Algorithme 2

64
 Série d’exercices à traiter en TD

d1
Tant que (d*d <= n) Faire
dd*2+1
Fin tant que

Algorithme 3
Pour (i0; i<n; ii+1) Faire
Pour (j0; j<n; jj+1) Faire
ss+1
Fin Pour
Fin Pour
Exercice 6
Que font les fonctions récursives suivantes :
1. Fonction mystere1( n: Entier): Entier
Début
SI (n = 0) Alors
retourner 0
Fin Si
Retourner (mystere1(n-1) + n*n)
Fin
2. Fonction mystere2(b : Reel, n: Entier): Reel
Début
SI (n = 0) Alors
retourner 1
Fin Si
retourner (1+ b*mystere2(b,n-1))
Fin

Exercice 7
Déterminer pour chacune de ces fonctions récursives sa complexité temporelle.
Exercice 8 : Puissance récursive
La fonction ci-dessous calcule récursivement nk avec n  0 et k≥ 0
FONCTION puissance( n : ENTIER, k : ENTIER) : ENTIER
DEBUT
SI ( k = 0 ) ALORS
Retourner 1
SINON
SI ( k MOD 2 = 0 ) ALORS
Retourner puissance( n*n , k DIV 2 )
SINON
Retourner n*puissance( n*n , k DIV 2 )
FIN SI
FIN SI
FIN
Déterminer la complexité temporelle de la fonction puissance(n, k)

Exercice 9
On considère un ensemble de n ≥ 2 entiers distincts stockés dans un tableau T (T n’est
pas supposé trié). Résoudre les questions suivantes :
1 - Proposer un algorithme en O(n) pour trouver deux éléments x et y de T tels que :
|x − y|≥|u − v| pour tout u, v T.
2 - Proposer un algorithme en O(n log n) pour trouver deux éléments x et y de T tels que : x  y et
|x− y|  |u − v| pour tout u, v  T, u  v.

65
 Série d’exercices à traiter en TD

3 - Soit m un entier arbitraire (pas nécessairement dans T), proposer un algorithme en O(nlog n)
pour déterminer s’il existe deux éléments x et y de T tels que x + y = m.

Exercice 10 : Plus petit et plus grand

Dans cet exercice, on ne s’intéresse qu’à la complexité dans le pire des cas et en nombre de
comparaisons des algorithmes.
1- On s’intéresse maintenant au calcul (simultané) du maximum et du minimum de n entiers.
Donner un algorithme naïf et calculer sa complexité.
2 - Une idée pour améliorer l’algorithme est de regrouper par paires les éléments à comparer, de
manière à diminuer ensuite le nombre de comparaisons à effectuer. Décrire un algorithme
fonctionnant selon ce principe et analyser sa complexité.
Exercice 11: Un nouvel algorithme de tri
Soit T un tableau contenant n entiers distincts, la procédure Nouveau_Tri est définie de la manière
suivante :

Procédure Nouveau_Tri (T : Entier[1..n] ; i : Entier ; j : Entier)

Var i, j, k : Entier
Début
Si T[i] > T[j] Alors
Echanger(T[i] , T[j])
Fin Si
Si (i <= j – 2) Alors //Le sous tableau T[i..j] contient au moins 3 éléments
k  (j − i + 1)/3
Nouveau_Tri(T, i, j − k)
Nouveau_Tri(T, i + k, j)
Nouveau_Tri(T, i, j − k)
Fin Si
Fin

1 - Montrer que Nouveau_Tri(T, 1, n) trie correctement le tableau T.

2 - Donner la complexité en nombre de comparaisons de cet algorithme. Comparer avec les
complexités des algorithmes de tri vus en cours (Rappel : ln(2) ≈ 0, 7 et ln(3) ≈ 1, 1).

Exercices sur la preuve de correction des algorithmes

Exercice 1
FONCTION f1(n : Entier) : Entier
VAR R, V, I : Entier
DEBUT
R1
V 1
i 1
TANT QUE ( i < n) FAIRE
V 2 * V
RR+V
ii+1
FIN TANT QUE
Retourner R
FIN
1. Faites la trace de l'exécution de f1(4) en indiquant sous forme d'un tableau les valeurs des
variables R, V et i à chaque itération.
2. Montrer que R = 2i -1 et V = 2(i-1) sont 2 propriétés invariantes pour la fonction f1.
3. Quelle est la valeur retournée par la fonction f1 ?

66
 Série d’exercices à traiter en TD

Exercice 2 :
FONCTION g(n : Entier) : Entier
//Données : un entier n appartenant à IN
VAR m, i, R : Entier
DEBUT
R0
mn
TANT QUE (m > 0) FAIRE
POUR (i  1 à m) FAIRE
1. RR+1
FIN POUR
POUR (i  m à n) FAIRE
2. RR+1
FIN POUR
mm-1
FIN TANT QUE
Retourner R
FIN
a) Exprimez en fonction de la donnée n, le nombre de fois que la fonction g exécute les
affectations des lignes 1 et 2. Vous donnerez l'expression exacte de ce nombre ainsi que les
étapes de son calcul.
b) Donnez, en fonction de n, l'ordre de grandeur du nombre d'affectations exécutées par la
fonction g.
c) Quelle est la valeur renvoyée par g(n) ?

Exercice 3
Montrer la correction de l’algorithme de tri par insertion vu à la fin du dernier cours :
On prouvera un invariant pour chaque boucle. Donner le pire et le meilleur cas pour la complexité
et évaluer cette complexité dans les deux cas.
Exercice 4
On se donne un tableau S d’entiers triés par ordre croissant et un entier cible x. Proposer
un algorithme linéaire pour trouver s’il existe deux éléments de S dont la somme vaut x. Prouver
que la boucle termine (quelle quantité décroît à chaque itération ?) et que votre algorithme est
correct (en utilisant la méthode par invariant de boucle).

67