Embed Size (px)
Citation preview
STRUCTURES DE DONNEES ET
ALGORITHMES
M. Benjelloun, G. Libert
1ère bachelier en sciences de l'ingénieur (Faculté Polytechnique - UMONS)
Edition: 2014-2015
PREFACE
L'enseignement de Structures de données et algorithmes, destiné aux étudiants de la première année de
bachelier en Ingénieur civil de la Faculté Polytechnique de l'Université de Mons (UMONS) est organisé,
en trois parties:
1. Le cours magistral qui comprend l'étude des principaux concepts de base de l'informatique logicielle,
des composants matériels de l'ordinateur et de l’exécution des algorithmes, sujets traités dans ce syllabus;
2. Les séances d'exercices qui sont consacrées à l'étude de la syntaxe d'un langage de programmation et
à l'écriture de programmes illustratifs, un syllabus est dédicacé à cela,
3. Les séances de travaux pratiques qui permettent de mettre en œuvre sur ordinateur des programmes
écrits dans un langage de programmation.
Les objectifs de cet enseignement sont donc:
1. La connaissance des principes de base pour développer des algorithmes informatiques
2. La maîtrise d'un langage de programmation et d'un poste de travail informatique.
M. Benjelloun et G. Libert
14 octobre 2014
Je propose de considérer la question: "Les
machines peuvent-elles penser ?"
Alan TURING (1912-1954)
"Computing Machinery and Intelligence",
Mind, vol. LXI, n° 236 (1950)
TABLE DES MATIERES
CHAPITRE 1 : INTRODUCTION 1 1.1 ORDINATEURS ET ALGORITHMES 1
1.2 PROGRAMMES ET LANGAGES DE PROGRAMMATION 2
1.3 LA HIERARCHIE LOGICIEL – MATERIEL 3
1.4 L'IMPORTANCE DES ALGORITHMES 4
CHAPITRE 2 : LA CONCEPTION DES ALGORITHMES 7 2.1 ALGORITHMES, PROGRAMMES, LANGAGES DE PROGRAMMATION 7
2.2 SYNTAXE ET SEMANTIQUE 8
2.3 AFFINEMENT PROGRESSIF DES ALGORITHMES 11
2.4 SEQUENCE 13
2.5 SELECTION 14
2.6 ITERATION 16
2.7 SEQUENCE, SELECTION ET ITERATION ENSEMBLE 24
2.8 MODULARITE 27
2.9 RECURSION 33
CHAPITRE 3 : STRUCTURES DE DONNEES 39 3.1 INTRODUCTION 39
3.2 LE CONCEPT DE TYPE DE DONNÉES 41
3.3 LES TYPES DE DONNÉES PRIMITIFS 43
3.4 TYPES PRIMITIFS STANDARD 44
3.5 TYPES INTERVALLE 45
3.6 LA STRUCTURE DE TABLEAU 46
3.7 LA STRUCTURE DE RECORD 48
3.8 LA STRUCTURE DE SUITE 51
CHAPITRE 4 : STRUCTURES DE DONNÉES DYNAMIQUES 53 4.1 TYPES DE DONNEES RECURSIFS 53
4.2 POINTEURS 55
4.3 LISTES LINEAIRES 57
CHAPITRE 5 : STRUCTURES DE DONNEES ELABOREES 62 5.1 TYPE ABSTRAIT ET STRUCTURE DE DONNEE 62
5.2 STRUCTURES LINEAIRES 63
5.3 ARBRES 72
CHAPITRE 6 : RECHERCHE ET TRI 84 6.1 INTRODUCTION 84
6.2 RECHERCHE DICHOTOMIQUE DANS UN TABLEAU TRIE 84
6.3 COMPLEXITE D‘UN ALGORITHME DE TRI 85
6.4 TRI SELECTION 86
6.5 TRI INSERTION 87
6.6 TRI RAPIDE 87
6.7 ARBRE BINAIRE DE RECHERCHE 91
6.8 STRUCTURE DE TAS ET TRI TAS 92
CHAPITRE 7 : TIRER PARTI DE LA REPETITION 97 7.1 LE DRAPEAU TRICOLORE DE DIJKSTRA 97
7.2 PROBLEME DU PLUS GRAND CARRE DE 1 100
CHAPITRE 8 : L'ARCHITECTURE DES ORDINATEURS 103 8.1 STRUCTURE DES ORDINATEURS 103
8.2 PHYSIQUE ET ELECTRONIQUE 104
8.3 LES COMPOSANTS 105
8.4 COMMUNIQUER AVEC LE MONDE EXTERIEUR 109
CHAPITRE 9 : L'EXECUTION DES ALGORITHMES 116 9.1 INTRODUCTION 116
9.2 TRADUCTEURS DE LANGAGE DE PROGRAMMATION 118
9.3 LES SYSTEMES D'EXPLOITATION 120
1
CHAPITRE 1 : INTRODUCTION
1.1 ORDINATEURS ET ALGORITHMES
Un ordinateur est une machine qui peut effectuer des tâches intellectuelles de routine en exécutant très
rapidement des opérations simples. La simplicité des opérations (l'addition ou la comparaison de deux
nombres en sont des exemples typiques) est compensée par la vitesse à laquelle elles sont exécutées. Le
résultat est que ces très nombreuses opérations permettent d'exécuter des travaux conséquents.
Naturellement un ordinateur ne peut accomplir que les tâches spécifiées dans les termes des opérations
simples qu'il est capable de réaliser. On doit indiquer à l'ordinateur quelles opérations il doit accomplir,
en d'autres termes, on doit lui décrire comment la tâche doit être menée à bien. Cette description est appelée
un algorithme. Un algorithme décrit une succession d'opérations qui, si elles sont fidèlement exécutées,
produiront le résultat désiré.
La notion d'algorithme n'est pas spécifique à l'informatique. Certains algorithmes décrivent toutes sortes
de tâches quotidiennes. Une recette de cuisine est un algorithme de même qu'une partition musicale. En
règle générale, la force agissante qui exécute une tâche est appelée un processeur. Un processeur peut être
une personne, un ordinateur ou tout autre dispositif électronique ou mécanique. Un processeur obéit aux
actions (les exécute) que l'algorithme lui décrit. L'exécution d'un algorithme implique l'exécution de
chacune de ses étapes constitutives.
Un ordinateur est donc simplement un processeur particulier. Naturellement c'est un processeur très
particulier, sinon il n'aurait pas eu cet impact important et rapide sur tant d'aspects de notre vie.
Un ordinateur actuel comporte trois composants essentiels qui sont:
1) l'unité centrale de traitement (UCT), qui fait les opérations de base;
2) la mémoire qui contient
a) l'algorithme spécifiant les opérations à exécuter;
b) l'information, ou les données, à partir desquelles les opérations agissent;
3) les dispositifs d'entrée et de sortie (dispositifs E/S) grâce auxquels l'algorithme et les données entrent
en mémoire et l'ordinateur communique les résultats.
Ces composants forment la partie matérielle de l'ordinateur. Ce sont les unités physiques à partir
desquelles les ordinateurs sont construits.
2
1.2 PROGRAMMES ET LANGAGES DE PROGRAMMATION
Un processeur effectue un traitement selon un algorithme approprié. Par exemple, le cuisinier doit suivre
une recette, le pianiste une partition et ainsi de suite. Dans chaque cas l'algorithme doit être énoncé d'une
manière telle que le processeur puisse le comprendre et en exécuter les instructions. On dit que le
processeur doit être capable d'interpréter l'algorithme, ce qui signifie qu'il doit être capable de
comprendre ce que chaque étape signifie et
faire l'opération correspondante.
Lorsque le processeur est un ordinateur, l'algorithme doit être exprimé sous la forme d'un programme. Un
programme est écrit dans un langage de programmation, et l'activité qui consiste à écrire un algorithme
sous la forme d'un programme est appelée la programmation. Chaque étape de l'algorithme est exprimée
par une instruction du programme. Un programme consiste donc en une séquence d'instructions, chacune
d'entre elles spécifiant les opérations que l'ordinateur doit faire.
La nature des instructions d'un programme dépend du langage de programmation utilisé. Il existe de
nombreux langages de programmation et chaque langage comporte son propre répertoire d'instructions.
Les langages les plus élémentaires, appelés les langages machine, sont conçus de manière que chaque
instruction puisse être directement interprétée par l'ordinateur: cela veut dire que l'unité centrale est
capable de comprendre chaque instruction et de faire l'opération correspondante. Cependant, puisque les
instructions sont si élémentaires (par exemple additionner deux nombres), chacune d'elle exprime
uniquement une infime partie d'un algorithme. Il faudra donc un grand nombre d'instructions pour
exprimer la plupart des algorithmes, et de ce fait la programmation en langage machine est fastidieuse.
Pour rendre la programmation plus facile, d'autres types de langages ont été développés. Ces langages
évolués sont plus pratiques que les langages machine en ceci que chaque instruction peut exprimer une
étape plus importante d'un algorithme. Naturellement, chaque énoncé devra être réinterprété par
l'ordinateur et il faudra que les capacités de l'unité centrale soient augmentées en conséquence. C'est
certainement l'augmentation des capacités de l'unité centrale qui rend possible l'interprétation des
programmes évolués, mais, en fait, il existe une solution plus économique et plus souple.
C'est la traduction des programmes évolués en langage machine avant leur exécution. La traduction
consiste à transformer chaque instruction du programme évolué en une séquence équivalente
d'instructions en langage machine. Ces instructions en langage machine peuvent alors être interprétées par
l'unité centrale. La procédure complète est illustrée par la figure 1.1.
3
programmation
traduction
interprétation par l'UCT
Le traitement souhaité est exécuté
Figure 1.1: Etapes d'exécution d'un algorithme par un ordinateur
La traduction d'un langage évolué en un langage machine est une tâche qui peut être exécutée par
l'ordinateur. Le programme qui exécute cette tâche est un traducteur de langage. Les constructeurs
d'ordinateurs fournissent des traducteurs pour la plupart des langages de programmation les plus usuels.
Les langages de programmation actuels vont des langages évolués (comme C, C++, PASCAL, Java, …)
via des niveaux intermédiaires tels que le Fortran et le Basic, jusqu'aux niveaux les plus élémentaires que
constituent les langages machine. On peut dire que les langages évolués rendent la tâche de
programmation plus facile aux dépens de l'interprétation et de la traduction. Puisque la première opération
est accomplie par l'homme et que les autres le sont par la machine, il n'y a aucune hésitation sur le choix.
1.3 LA HIERARCHIE LOGICIEL - MATERIEL
Un ordinateur exécute des programmes, lesquels sont uniquement l'expression d'algorithmes permettant
de mener à terme des traitements. On désigne souvent les programmes sous le terme générique de logiciel,
ce qui permet de les distinguer du matériel (ou équipement physique) à partir duquel est construit
l'ordinateur. Certains logiciels sont écrits par les utilisateurs eux-mêmes, mais en fait la plupart de ces
derniers ne programment pas du tout. Ils se servent de l'ordinateur en tant qu'outil pour des opérations
Algorithme
Programme en langage évolué
Programme en langage machine
4
dont les algorithmes sont bien connus et les programmes déjà écrits. Par exemple, un comptable utilisera
un ordinateur pour la mise à jour des livres, un ingénieur l'utilisera pour la conception d'un pont, un
médecin pour surveiller l'état d'un patient et un notaire pour préparer des actes juridiques.
Un ensemble de programmes écrits pour une application particulière est un ensemble de logiciels
d'application (ou "package" d'application). Il existe des ensembles logiciels pour tous les domaines
d'application que nous venons de mentionner et pour beaucoup d'autres encore. L'utilisateur d'un logiciel
d'application se le procure généralement chez le constructeur de son matériel ou dans des entreprises
spécialisées dans la vente de logiciels. L'utilisateur peut être amené à programmer, selon les circonstances,
lorsqu'il faut modifier le logiciel.
Ainsi, l'utilisateur veut souvent faire quelque chose que le logiciel ne lui permet pas de faire. Il doit alors
écrire ses propres programmes ou faire appel à quelqu'un pour les lui écrire. Ces programmes pourront
ensuite être vendus comme logiciels à d'autres utilisateurs dont les besoins sont similaires.
Les ensembles logiciels d'application (packages) et les programmes écrits par les utilisateurs sont des
logiciels d'application. Les logiciels d'application sont généralement écrits en langages évolués et
demandent de ce fait des traducteurs de langage appropriés. Les traducteurs ne sont pas les seuls
programmes sur lesquels s'appuient les logiciels d'application. Il y a de nombreux autres programmes qui
rendent d'importants services aux logiciels d'application; ces programmes, dont les traducteurs de langage,
sont appelés logiciels de base. Un des éléments notables des logiciels de base est le logiciel système qui
comprend surtout le système d'exploitation dont l'un des services comporte normalement la gestion du
dispositif des entrées et des sorties d'un ordinateur, le stockage de l'information sur une très grande période
et la possibilité d'accès à l'ordinateur par plusieurs utilisateurs de manière simultanée.
Il ressort de cette discussion qu'un système informatique peut être considéré comme une hiérarchie de
composants logiciels et matériels. Au niveau le plus élevé, on trouve le logiciel d'application qui prend
appui sur le logiciel système. A son tour le logiciel système s'appuie sur l'unité centrale de l'ordinateur et
sur les dispositifs E/S. En fait, la hiérarchisation ne s'arrête pas là puisque les composants matériels eux-
mêmes sont construits à partir de composants plus simples.
1.4 L'IMPORTANCE DES ALGORITHMES
Nous avons vu qu'afin de mener à bien un traitement sur un ordinateur on doit
1) concevoir un algorithme qui décrit comment le traitement doit être fait;
5
2) exprimer l'algorithme sous la forme d'un programme en un langage de programmation adéquat;
3) faire en sorte que l'ordinateur exécute le programme.
Le rôle de l'algorithme est fondamental. Sans algorithme, il n'y aurait pas de programme, et sans
programme, il n'y aurait rien à exécuter. Les algorithmes sont fondamentaux en un autre sens: ils sont à
la fois indépendants du langage dans lequel ils sont énoncés et de l'ordinateur qui les exécute. Par exemple,
les systèmes de réservation d'une compagnie aérienne comportent un algorithme de réservation. Dans
chaque système, l'algorithme peut être écrit en un langage de programmation différent et exécuté sur un
ordinateur différent. Pourtant, dans tous les cas, l'algorithme est fondamentalement le même.
Pour revenir au domaine technique, tous les ordinateurs peuvent globalement mener à bien les mêmes
opérations de base; il faut noter des différences de détail et de rapidité, mais en règle générale les capacités
des ordinateurs actuels sont les mêmes. Bien plus, ces capacités n'ont pas été affectées par l'innovation
technologique. Cette innovation ne changera pas ce que les ordinateurs font, même si elle affecte la
vitesse, le coût et la fiabilité. Cela signifie que les algorithmes peuvent être conçus et étudiés
indépendamment de la technologie du jour. Les résultats resteront valables malgré l'arrivée de nouveaux
ordinateurs et de nouveaux langages de programmation.
Pour les spécialistes de la science informatique, les algorithmes sont plus essentiels que les langages de
programmation et les ordinateurs. Un langage n'est qu'un moyen pratique d'énoncer un algorithme, et un
ordinateur est un simple processeur qui l'exécute. Le langage de programmation et l'ordinateur ne sont
que des moyens, le but étant l'exécution de l'algorithme et le déroulement du traitement correspondant.
Puisque les algorithmes sont essentiels en informatique, quels sont les aspects et les propriétés que les
chercheurs étudient ? Un des aspects les plus importants est la conception des algorithmes. Face à la
possibilité de nouvelles applications informatiques, comment peut-on concevoir des algorithmes pour
mener à bien les traitements concernés ? La conception d'un algorithme est une activité intellectuelle
difficile, beaucoup plus difficile que de transformer l'algorithme en programme. Les chercheurs essaient
de venir à bout de cette difficulté par l'élaboration de schémas directeurs dans lesquels le processus de
conception peut s'inscrire et se développer. Cependant, la conception de la plupart des algorithmes requiert
créativité et intuition, et pour cela on ne peut pas formuler de règles générales. En d'autres termes, il
n'existe aucun algorithme pour concevoir des algorithmes.
Cette observation soulève un certain nombre de questions intéressantes. Y a-t-il d'autres problèmes pour
lesquels il n'existe pas d'algorithme? De tels processus intellectuels correspondent-ils à ce que nous
6
appelons créativité? Etant donné un processus, comment peut-on déterminer s'il y a ou non un algorithme
qui le décrit ? La dernière question est importante, car si un processus ne peut être décrit par un algorithme,
il n'a aucune chance d'être exécuté par un ordinateur, quels que soient son importance, ses performances
et son coût. Ces questions sont globalement classées sous le titre calculabilité, c'est-à-dire l'étude de ce
qui est informatisable et de ce qui ne l'est pas.
Etant admis qu'un problème peut être décrit par un algorithme, il est pertinent de se demander combien
de ressources informatiques seront nécessaires à son exécution. En particulier, combien il faudra de temps
et de mémoire. S'il existe plusieurs algorithmes décrivant le même problème, lequel d'entre eux est le plus
"performant" au niveau de la consommation minimale de ressources informatiques? Quels sont les
moyens minimaux nécessaires pour résoudre un problème donné et quels moyens sont utilisés par
l'algorithme le plus performant possible? Existe-t-il des problèmes pour lesquels le meilleur algorithme
nécessite tant de ressources informatiques que son exécution est irréalisable ? Toutes ces questions font
référence à la notion de complexité de l'algorithme.
Un autre sujet d'intérêt pour les chercheurs est celui de l'exactitude des algorithmes. Puisque la conception
des algorithmes est si difficile, comment peut-on être certain de leur exactitude? Comment peut-on savoir
si un algorithme particulier correspond exactement au problème? Le manque de certitude a conduit à des
erreurs spectaculaires. Au fur et à mesure que le nombre des applications informatiques augmente, on
rencontre un plus grand nombre de cas dans lesquels un algorithme incorrect serait désastreux.
En résumé, la notion d'algorithme est fondamentale à l'informatique. C'est le concept unificateur de toutes
les activités dans lesquelles s'engagent les chercheurs. Nous consacrerons donc l'essentiel de cet
enseignement à la conception et l'étude des algorithmes. Les séances d'exercices seront dédiées à l'étude
d'un langage de programmation et les travaux pratiques seront utilisés pour écrire les programmes
d'algorithmes construits durant les enseignements.
7
CHAPITRE 2 : LA CONCEPTION DES ALGORITHMES
Au chapitre 1, nous avons fait porter la discussion sur la centralité de la notion d'algorithme en
informatique. Dans ce chapitre, nous allons examiner de plus près ce que sont les algorithmes en
considérant des problèmes tels que leur structure, la manière dont ils peuvent être imaginés et comment
ils peuvent être exprimés sous une forme adaptée à leur exécution.
2.1 ALGORITHMES, PROGRAMMES, LANGAGES DE PROGRAMMATION
Nous avons défini un algorithme comme la description de l'exécution d'une tâche, ou processus. Il existe
des algorithmes pour exécuter toutes sortes de procédures utiles. Dans de nombreux cas, il y a interaction
entre le processus et son environnement: il en reçoit des entrées et lui renvoie des sorties. Les processus
exécutés par ordinateur nécessitent souvent des entrées sous la forme d'information et produisent
généralement des sorties sous la forme d'information complémentaire. (Pour cette raison, on appelle
certains aspects de l'informatique "traitement de l'information".) Prenons comme exemple le traitement
informatisé du salaire mensuel qui nécessite l'entrée d'informations concernant le taux du salaire ainsi que
le nombre d'heures effectuées, pour produire en sortie des informations portant sur le salaire dû ainsi que
sur la déduction des taxes. Il faut noter que les entrées et les sorties font partie de la spécification du
processus, et font donc nécessairement partie de l'algorithme décrivant ce dernier bien qu'elles demeurent
indépendantes du processeur qui l'exécute. Dans cet exemple, le salaire de base est une information
nécessaire pour le processeur, que ce soit un ordinateur ou un employé, même si on peut l'exprimer sous
des formes différentes selon les cas, comme nous le verrons par la suite.
Comme nous l'avons mentionné au chapitre 1, un algorithme ne peut être exécuté que s'il est exprimé sous
la forme que le processeur concerné peut comprendre. Puisque l'anglais ou le français est trop complexe
pour être compris par les ordinateurs, les algorithmes exécutables doivent être écrits plus simplement.
Nous avons mentionné qu'un algorithme exprimé sous une telle forme portait le nom de programme et
qu'un programme était écrit dans un langage de programmation.
Par analogie avec les langages naturels, chaque langage de programmation a son propre vocabulaire et ses
propres règles grammaticales, qui dictent les conditions dans lesquelles le vocabulaire peut être utilisé.
Dans la plupart des cas, le vocabulaire consiste en certains symboles mathématiques, en quelques mots
anglais et en des règles grammaticales assez simples pour permettre à l'ordinateur d'interpréter des
programmes. En raison de ces différences inhérentes au vocabulaire et à la grammaire, les langages de
programmation diffèrent naturellement dans les formes d'expressions autorisées.
8
Les concepteurs de langages de programmation essaient de concilier entre eux plusieurs objectifs dont les
plus importants sont les suivants:
1) Le langage doit permettre l'expression concise et facile d'algorithmes dans le domaine d'application
pour lequel il a été conçu.
2) Le langage doit être compréhensible par l'ordinateur.
3) Les programmes écrits dans le langage doivent être rapidement compris par les utilisateurs, de telle
sorte qu'ils puissent être modifiés et corrigés là où c'est nécessaire.
4) Les programmes doivent être conçus pour réduire les risques potentiels d'erreurs lors de la
transformation d'un algorithme en programme.
5) L'examen d'un programme permet de constater que son exécution correspondra véritablement à la
procédure désirée.
Ces objectifs ne sont pas tous compatibles entre eux. La concision ou la justesse d'une expression peut
nuire à une compréhension facile (par exemple l'utilisation d'acronymes), de même qu'un langage
clairement conçu pour les gens peut ne pas être compris par un ordinateur.
Dans ce syllabus, nous aurons besoin d'exprimer de nombreux algorithmes de différentes sortes.
Heureusement, nous bénéficierons de l'avantage considérable que les algorithmes présentés n'auront pas
à être exécutés sur ordinateur mais seulement "compris" par l'utilisateur. C'est pourquoi nous nous
satisferons d'un sous-ensemble du langage PASCAL qui nous permettra d'exprimer clairement les étapes
de l'algorithme tout en nous familiarisant à des notations classiques des langages de programmation.
2.2 SYNTAXE ET SEMANTIQUE
Au chapitre 1, nous avons dit qu'un processeur devrait être capable d'interpréter un algorithme pour
exécuter le processus décrit. Ce qui signifie que le processeur doit être en mesure de
1) comprendre la forme sous laquelle l'algorithme est exprimé (par exemple, un modèle de tricot ou une
partition musicale)
2) exécuter les opérations correspondantes.
Dans cette section nous examinerons plus attentivement la première de ces étapes.
Comprendre l'écriture même de l'algorithme se décompose en deux étapes. En premier lieu, le processeur
doit être capable de reconnaître et de comprendre les symboles par lesquels est exprimé l'algorithme, que
ce soient des mots français ou anglais, des abréviations, des symboles mathématiques ou des notes dans
9
une partition musicale. Pour être en mesure de faire cela le processeur doit connaître le vocabulaire et la
grammaire du langage dans lequel l'algorithme est écrit.
L'ensemble des règles grammaticales qui régissent la manière dont les symboles dans un langage doivent
être légitimement utilisés est appelé la syntaxe du langage. Ainsi la syntaxe du français régit l'utilisation
du mot "syllabus", celle des mathématiques l'utilisation du symbole "=" et celle de la musique l'utilisation
du symbole "#". Un programme qui respecte la syntaxe du langage dans lequel il est écrit est dit
syntaxiquement correct. Tout écart de syntaxe dans le langage est appelé une erreur de syntaxe. Une
syntaxe correcte est généralement un préalable nécessaire à l'interprétation d'un programme d'ordinateur
et donc à son exécution.
La deuxième étape de la compréhension de l'écriture d'un algorithme consiste à donner une signification
à chaque énoncé en termes d'opérations que le processeur doit effectuer. Par exemple
maille à 1'envers
indique comment manipuler les aiguilles et la laine; et
coût := prix * quantité
signifie que deux nombres appelés prix et quantité doivent être multipliés pour donner un troisième
nombre appelé coût.
La signification de formes données d'expressions dans un langage est appelée la sémantique du langage.
Les langages de programmation sont conçus de telle sorte que leur syntaxe et leur sémantique soient
relativement simples et qu'un programme puisse être analysé du point de vue de la syntaxe sans référence
sémantique. Ceci est totalement différent des langages naturels dans lesquels, comme nous l'avons vu
dans la section précédente, la syntaxe et la sémantique sont très complexes et souvent corrélatives. Dans
les langages naturels, il est possible d'écrire des phrases à la syntaxe correcte mais pourtant dépourvues
de signification. La phrase
L'éléphant mangea la cacahuète
est une phrase qui a un sens alors que la phrase
La cacahuète mangea l'éléphant
n'en a pas, bien que les deux phrases soient correctes quant à la syntaxe. De même un énoncé dans un
algorithme peut être syntaxiquement correct mais dépourvu de signification. Par exemple
afficher le nom du 1er mois de l'année
et
afficher le nom du 13ème mois de l'année
10
sont des énoncés algorithmiques syntaxiquement corrects (écrits en langage naturel) mais dont seul le
premier a une signification.
La détection des incohérences sémantiques dépend de la connaissance des objets auxquels elles renvoient.
Elle dépend en particulier de la connaissance des attributs de ces objets et de leurs rapports entre eux.
C'est pourquoi les exemples absurdes présentés ci-dessus sont reconnus comme tels parce que le lecteur
sait faire la distinction entre les attributs d'un éléphant et d'une cacahuète, et ainsi de suite. Un processeur
ne pourra détecter des incohérences sémantiques dans l'écriture d'un algorithme que s'il a une connaissance
suffisante des objets auxquels renvoie l'algorithme. Sinon les incohérences n'apparaîtront que lors de
l'exécution de l'algorithme. Considérons par exemple un processeur devant la commande
afficher le nom du 13ème mois de l'année
Si le processeur sait qu'une année ne comporte que douze mois, il peut détecter l'incohérence sémantique
de la commande avant de l'exécuter. S'il est plus ignorant, il cherchera à l'exécuter probablement en
cherchant le nom de ce mois dans un calendrier. C'est seulement pendant l'exécution (ici la consultation
du calendrier) que le processeur découvrira qu'il n'y a pas de 13ème mois et que l'incohérence apparaîtra.
Certaines incohérences sémantiques sont plus subtiles, pouvant être le résultat d'un énoncé algorithmique
un peu hâtif. Par exemple l'algorithme
pensez à un nombre de 1 à 13
appelez ce nombre N
affichez le nom du Nième mois de l'année
contient une incohérence en puissance qui ne se matérialisera que si l'exécution de la première ligne donne
le nombre 13 comme résultat. Lorsqu'une incohérence provient d'un algorithme, il n'y a en général aucune
chance de la détecter avant son exécution.
Cette discussion peut être résumée ainsi: afin d'interpréter chaque énoncé algorithmique, un processeur
doit être en mesure de
1) donner un sens aux symboles dans lesquels l'énoncé est écrit;
2) donner une signification à l'énoncé en termes d'opérations à exécuter;
3) exécuter les opérations correspondantes.
Les erreurs de syntaxe peuvent être détectées au premier niveau et certaines erreurs sémantiques au
second. D'autres erreurs sémantiques ne seront pas détectées avant le troisième niveau. Quand le
processeur est un ordinateur, les niveaux 1 et 2 peuvent être franchis par un traducteur qui transforme
chaque étape du programme en une opération appropriée que le processeur peut conduire à son terme. Un
11
traducteur différent est nécessaire pour chaque langage de programmation. Lorsqu'il s'agit d'un traducteur
pour un langage de programmation spécifique, ce traducteur possède toutes les connaissances nécessaires
à la compréhension de la syntaxe du langage. (Cette condition est tout à fait réalisable puisque la syntaxe
est, dans sa conception même, un ensemble fini de règles bien définies.) Le traducteur peut donc détecter
toute erreur de syntaxe dans les programmes à exécuter. Cependant il ne peut détecter toutes les erreurs
sémantiques ou même plusieurs d'entre elles. Les erreurs qui subsistent apparaîtront seulement lors de
l'exécution du programme.
Outre des erreurs de syntaxe et de sémantique, il faut faire état d'une troisième catégorie d'erreurs. Il s'agit
de l'erreur logique. Un programme peut être correct du point de vue syntaxique et ne comporter aucune
incohérence sémantique mais peut tout simplement ne pas décrire d'une manière adéquate le traitement
désiré. Considérons par exemple l'algorithme suivant qui consiste à calculer la circonférence d'un cercle
calculer la circonférence en multipliant le rayon par
Cet algorithme est syntaxiquement et sémantiquement correct mais le résultat produit sera faux en raison
de l'erreur logique qui consiste en l'omission de la multiplication du rayon par 2.
Un processeur ne peut détecter les erreurs logiques puisqu'il n'a aucune idée du traitement que l'algorithme
est censé décrire. Les erreurs logiques ne peuvent être détectées que si l'on compare le résultat désiré au
résultat obtenu. Les erreurs logiques et les méthodes qui permettent de les éviter seront présentées dans la
section suivante.
2.3 AFFINEMENT PROGRESSIF DES ALGORITHMES
Nous avons vu que pour qu'un processeur puisse exécuter une procédure, il est nécessaire de lui fournir
un algorithme approprié. La conception d'un tel algorithme est généralement très difficile, au moins
lorsque la procédure à exécuter n'est pas courante. Les difficultés de conception d'un algorithme
augmentent lorsque le processeur est un ordinateur, dans la mesure où les ordinateurs manquent de
l'intuition ou du sens commun qui leur permettrait de voir quand l'algorithme ne décrit pas précisément la
procédure désirée. Très souvent, l'algorithme décrit est presque celui qu'on a eu l'intention d'écrire mais
pas totalement.
Un exemple pris dans la vie courante est celui de l'ami qui nous. indique l'itinéraire pour aller chez lui.
L'algorithme qu'il donne: "tourne à droite au magasin, va jusqu'au prochain croisement, puis prends la
troisième à gauche..." est presque parfait à quelques détails essentiels près (à quel magasin tourner, par
exemple) et risque fort d'entraîner son visiteur vers une toute autre rue que la sienne et même vers une
12
autre banlieue. Dans cet exemple, le processeur est une personne assez censée pour reconnaître l'erreur et
demander son chemin à un passant. Malheureusement les ordinateurs n'ont pas cette ressource.
Une autre erreur classique avec les algorithmes provient du fait que la procédure, qui normalement doit
être exécutée, ne l'est pas dans certaines circonstances (imprévisibles ou par oubli de la part du
concepteur). Prenons, par exemple, le simple algorithme suivant qui décrit comment calculer la durée d'un
vol à partir d'un tableau d'affichage d'une compagnie aérienne:
consulter l'heure de départ
consulter l'heure d'arrivée
soustraire l'heure de départ de celle d'arrivée
Le résultat obtenu sera la plupart du temps correct, excepté dans le cas où le lieu du départ et celui de
destination sont dans des fuseaux horaires différents. Pire encore s'il y a l'heure d'été à un point et pas a
l'autre: l'algorithme donnera le résultat correct en hiver et pas en été.
La morale de ces exemples est que le concepteur d'un algorithme doit vérifier attentivement que
l'algorithme décrit précisément la procédure qu'il doit exécuter et que tous les cas de figures possibles ont
bien été prévus. Si le résultat attendu est très complexe, la tâche du concepteur est extrêmement difficile.
A dire vrai le concepteur a très peu de chances de réussite à moins d'avoir une approche très
rigoureusement méthodique. Une telle approche, connue sous le nom d'affinement progressif de
l'algorithme (ou conception descendante), est décrite ci-dessous.
L'affinement progressif est une variation actuelle sur le vieux thème "diviser pour régner". L'idée consiste
à fragmenter l'ensemble du traitement à exécuter et à établir un nombre donné d'étapes dont chacune peut
être décrite par un algorithme plus petit et plus simple que celui qui concerne l'ensemble du traitement.
Etant donné que chaque sous-algorithme est plus simple que l'algorithme entier, le concepteur peut mieux
en concevoir la construction, et de ce fait entrer plus dans les détails que s'il avait essayé de manipuler
l'ensemble de l'algorithme en une seule fois. Les sous-algorithmes peuvent être divisés en parties plus
élémentaires qui, grâce à leur simplicité, peuvent de nouveau comporter plus de détails et de précisions.
L'affinement de l'algorithme se poursuit jusqu'à ce que chaque étape soit suffisamment détaillée et précise
pour que son exécution par le processeur concerné soit possible.
Quand il procède à des affinements des différentes étapes, le concepteur d'un algorithme doit
naturellement savoir où s'arrêter. Autrement dit, il doit savoir quand une étape donnée constitue une
primitive adéquate au point de ne pas avoir besoin d'affinement supplémentaire. Cela signifie
13
naturellement qu'il doit connaître quelle sorte d'étape le processeur peut interpréter. La connaissance des
capacités du processeur est nécessaire non seulement pour savoir arrêter le processeur mais aussi pour
donner une direction à la procédure d'affinement elle-même. Si un concepteur sait qu'un processeur peut
interpréter une catégorie donnée d'étapes, alors il organisera l'affinement en étapes de la même catégorie.
Cette discussion démontre que l'affinement des étapes d'un algorithme ne peut se faire dans le vide. Le
concepteur doit être au fait des capacités d'interprétation du processeur prévu, si bien qu'il peut pousser
l'affinement dans des directions données et savoir quand il doit arrêter l'affinement de chaque partie.
Quand le processeur prévu est une personne, la tâche du concepteur est compliquée du fait que les
capacités d'interprétation des gens varient considérablement. Ce qui est facilement compris par une
personne peut être tout à fait inintelligible pour une autre. Les capacités d'interprétation d'un ordinateur
sont définies avec beaucoup plus de précision: un ordinateur peut interpréter tout ce qui est exprimé d'une
manière appropriée dans un langage de programmation déterminé. De ce fait le concepteur d'un algorithme
d'informatique l'affine de sorte que les étapes puissent être écrites en un langage de programmation
approprié et arrête l'affinement quand chaque étape est exprimée dans le langage concerné.
2.4 SEQUENCE
Un tel algorithme est une séquence d'étapes, voulant dire par là que:
1) Les étapes sont traitées une par une.
2) Chaque étape n'est traitée qu'une fois, aucune n'est répétée, aucune n'est omise.
3) L'ordre dans lequel les étapes sont parcourues est le même que celui dans lequel elles ont été écrites.
4) Terminer la dernière étape implique de finir l'algorithme.
Dans ce syllabus, les étapes successives dans une séquence seront séparées par ; qui est le symbole utilisé
par le PASCAL pour séparer des instructions.
Un algorithme qui n'est qu'une séquence d'étapes est extrêmement rigide puisque le déroulement du
traitement est fixé et ne peut être modifié selon les circonstances. Comme exemple de rigidité inhérente à
une séquence d'étapes, examinons l'algorithme suivant qui décrit comment voyager du centre de Londres
à celui de New York
prendre le métro pour l'aéroport d'Heathrow de Londres;
gagner par avion l'aéroport Kennedy de New York;
prendre un taxi de l'aéroport Kennedy au centre de New York; (2.1)
14
Cet algorithme est très rigide. Il ne fournit aucune alternative si des circonstances extraordinaires se
présentent, telles qu'une grève de métro à Londres ou une grève des taxis à New York. Une séquence est
une structure algorithmique très primitive. Nous en examinerons de moins primitives dans les sections
suivantes.
2.5 SELECTION
Nous venons de voir que lorsqu'un algorithme n'a qu'une structure séquentielle, il n'est pas possible d'en
modifier le traitement selon les circonstances. Ainsi une grève des transports urbains londoniens jetterait
dans l'embarras le voyageur transatlantique. Dans ce cas, ce qui serait utile, serait la capacité d'exécuter
une étape du type
prendre un taxi pour l'aéroport d'Heathrow de Londres;
si les transports urbains sont en grève et de sauter cette étape dans le cas contraire. Une telle capacité est
appelée sélection. La sélection, dans l'étape ci-dessus, peut s'exprimer en récrivant l'affinement de l'étape
(2.1) sous la forme
(2.1.1) prendre le métro pour l'aéroport d'Heathrow de Londres;
(2.1.2) if le métro est en grève
then prendre un taxi pour l'aéroport d'Heathrow de Londres;
(2.1.3) gagner par avion l'aéroport Kennedy de New York;
(2.1.4) prendre un taxi de l'aéroport Kennedy au centre de New York;
L'étape cruciale est 2.1.2 qui exprime à la fois l'étape devant être sélectionnée (prendre un taxi pour
l'aéroport d'Heathrow de Londres) et la condition (le métro est en grève) dont dépend la sélection.
L'étape 2.1.2 est un cas particulier d'une étape de forme très générale, selon la syntaxe du PASCAL,
if condition
then étape;
où condition détermine la circonstance dans laquelle 1'étape doit être accomplie. Si la condition est vraie,
alors l'étape doit être exécutée; dans le cas inverse, elle ne doit pas l'être. Le processeur doit être en mesure
d'interpréter les conditions qui figurent dans un algorithme de la même manière qu'il est capable
d'interpréter les étapes. Les conditions doivent cependant être affinées jusqu'à ce qu'elles soient
suffisamment détaillées et précises pour permettre au processeur de les interpréter.
Dans notre exemple, la sélection est utilisée pour déterminer si une étape donnée doit être exécutée ou
non. Une extension de cette forme de sélection est une forme qui détermine laquelle de ces deux étapes
15
possibles doit être accomplie. Par exemple, l'algorithme du voyage transatlantique 2.1 peut être
considérablement amélioré par la réécriture de la première étape
if le métro est en grève
then prendre un taxi pour l'aéroport d'Heathrow de Londres
else prendre le métro pour l'aéroport d'Heathrow de Londres;
Cela est un cas particulier de sélection entre deux étapes. La forme générale d'une telle sélection est
if condition
then étape 1
else étape 2;
où condition détermine clairement laquelle des étapes (1 ou 2) doit être parcourue. Nous emploierons des
retraits (comme ci-dessus) afin que les diverses étapes possibles ressortent du texte qui les entoure.
Pour prendre un autre exemple d'utilisation de la sélection, voici un algorithme (2.2) concernant l'approche
des feux de signalisation routière:
if le signal est rouge ou orange
then s'arrêter
else continuer; (2.2)
Un algorithme un peu meilleur (2.3) admet la possibilité que les signaux ne soient pas en état de marche
if pas de signal
then avancer prudemment
else if signal rouge ou orange
then s'arrêter
else continuer; (2.3)
Cet algorithme contient deux occurrences de la sélection, la seconde étant incluse dans la première et
exécutée seulement si le signal marche. Notez combien l'usage des retraits rend tout à fait claire la lecture
des étapes de l'algorithme et à quelle partie de la sélection elles se rattachent. Sans cette forme d'écriture
l'algorithme serait beaucoup plus difficile à comprendre (2.4)
if pas de signal
then avancer prudemment
else if signal rouge ou orange
then s'arrêter
else continuer; (2.4)
16
Un autre exemple de sélection imbriquée apparaît dans l'algorithme suivant, qui décrit comment
déterminer le plus grand de trois nombres donnés alors que le processeur ne peut en comparer que deux à
la fois. Appelons les nombres X, Y, et Z. Une première version de l'algorithme peut être:
if X > Y
then choisir entre X et Z
else choisir entre Y et Z;
Le choix entre X et Z pourrait être affiné en:
if X > Z
then MAX := X
else MAX := Z;
et le choix entre Y et Z affiné de la même façon. En suivant la syntaxe du PASCAL, nous avons enregistré
notre choix en écrivant dans l'entité nommée MAX, à l'aide du symbole d'affectation :=, la valeur de X.
On obtient alors l'algorithme final suivant (2.5):
if X > Y
then if X > Z
then MAX := X
else MAX := Z
else if Y > Z
then MAX := Y
else MAX := Z; (2.5)
Notez à nouveau à quel point sont rendus clairs les énoncés de l'algorithme des différentes parties des
sélections grâce à l'utilisation des retraits.
L'effet de la sélection permet à un processeur de suivre un algorithme selon différents chemins en fonction
des circonstances. Sans la sélection, il serait impossible d'écrire un algorithme qui puisse avoir une
signification pratique quelconque.
2.6 ITERATION
Examinons le processus qui consiste à chercher, dans une liste de noms et d'adresses, l'adresse d'une
personne (le nom de la personne étant indiqué)
17
examiner le premier nom de la liste;
if ce nom est le nom donné
then extraire l'adresse correspondante S1
else examiner le nom suivant;
if ce nom est le nom donné
then extraire l'adresse correspondante S1
else examiner le nom suivant;
if ... (2.6)
L'inconvénient de cet algorithme (en dehors de l'empiétement sur la marge de droite qui se produira
inévitablement à un certain moment) tient au fait que l'auteur ne sait pas quand il doit s'arrêter d'écrire.
Plus précisément l'auteur ne sait pas combien de fois il doit écrire l'instruction S1 afin de s'assurer que le
nom est celui recherché. Un problème identique surgit dans l'algorithme (2.7) qui décrit comment calculer
le premier nombre premier qui soit plus grand qu'un nombre de "départ" (entier positif).
De nouveau il n'apparaît pas clairement combien de fois il faut écrire la séquence S2 pour être sûr que le
processeur produise un nombre premier. Par exemple S2 doit être écrite une seule fois si le nombre de
départ est 4, et quatre fois si c'est 13, mais combien de fois faudra-t-il récrire la séquence si le nombre de
départ est 7394485?
obtenir le nombre de départ appelé PREMIERPOT;
PREMIERPOT := PREMIERPOT + 1; {ajouter 1 au nombre de départ}
tester PREMIERPOT pour voir s'il est premier; S2
if PREMIERPOT est premier
then afficher PREMIERPOT
else PREMIERPOT := PREMIERPOT + 1;
tester PREMIERPOT pour voir s'il est premier; S2
if PREMIERPOT est premier
then afficher PREMIERPOT
else PREMIERPOT := PREMIERPOT + 1;
... (2.7)
Ces exemples montrent que les séquences et les sélections ne sont pas en elles-mêmes suffisantes pour
exprimer des algorithmes dont la longueur peut varier selon les circonstances. Ce qui est nécessaire, c'est
le moyen de répéter certaines instructions dans un algorithme un nombre quelconque de fois. Pour ce
18
faire, nous allons introduire les mots repeat et until dans les algorithmes, de telle sorte que notre exemple
2.6 puisse être récrit de la manière suivante:
examiner le premier nom de la liste;
repeat
if ce nom est le nom donné
then extraire l'adresse correspondante S1
else examiner le nom suivant;
until le nom soit trouvé ou la liste épuisée; (2.8)
De la même manière, l'algorithme 2.7 peut être récrit sous la forme suivante
obtenir le nombre de départ appelé PREMIERPOT;
repeat
PREMIERPOT := PREMIERPOT + 1;
tester PREMIERPOT pour voir s'il est premier;
until PREMIERPOT soit premier;
afficher PREMIERPOT; (2.9)
Ces exemples illustrent la répétition ou l'itération dont la forme générale est
repeat
partie de l'algorithme;
until condition;
ce qui signifie que la partie de l'algorithme comprise entre les mots repeat et until doit être répétée tant
que la condition spécifiée après until n'est pas vraie. Dans l'algorithme 2.8, la partie répétée est l'examen
successif des noms de la liste. La répétition cesse lorsque le nom est trouvé ou que la liste est épuisée.
Dans l'algorithme 2.9, la répétition concerne le test appliqué à des nombres successifs et s'achève dès que
le premier nombre premier est rencontré.
L'occurrence d'itération est généralement appelée une boucle et la partie de l'algorithme qui est répétée
(c'est-à-dire celle qui est comprise entre les mots repeat et until) est connue sous le nom de corps de la
boucle. La condition qui apparaît après until est appelée la condition d'achèvement de la boucle. Dans ce
syllabus, nous utiliserons les retraits pour distinguer le corps d'une boucle du texte qui l'entoure.
L'intérêt de l'itération est la description d'un processus de durée indéterminée par un algorithme de
longueur finie. Cela implique une démarche supplémentaire: celle d'assurer un achèvement effectif de
l'itération au moment prévu. L'algorithme 2.9 se termine parce qu'il existe toujours un nombre premier
19
plus grand que tout nombre donné. Dans l'algorithme 2.8, l'itération se termine parce que la condition de
clôture (nom trouvé ou liste épuisée) devient vraie. A noter cependant que l'omission de la deuxième partie
de la condition de fin (liste épuisée) peut provoquer un désastre puisque si le nom recherché n'est pas
présent, le processeur continue sa recherche au-delà de la fin de la liste. Une des erreurs les plus courantes
dans la conception des algorithmes est l'omission des conditions de fin.
Naturellement, certains processus, comme nous l'avons suggéré dans la section 2.1, ne sont pas censés se
terminer, et un algorithme décrivant un tel processus doit contenir une boucle sans fin. Une telle boucle
peut être écrite de cette manière
repeat
corps de la boucle
until condition jamais satisfaite;
Comme autre exemple d'itération, examinons à nouveau l'algorithme 2.9 concernant les nombres
premiers. La boucle contient l'instruction
tester PREMIERPOT pour voir s'il est premier;
Il est improbable que le processeur soit en mesure de voir immédiatement si un nombre donné est premier
ou non. Donc cette instruction demande un affinement supplémentaire. Par définition, un nombre est
premier s'il n'a pas d'autre diviseur que 1 ou lui-même. De ce fait, tester un nombre pour savoir s'il est
premier revient à déterminer s'il comporte des diviseurs non triviaux. Cela peut être réalisé grâce à
l'algorithme suivant dans lequel le nombre à tester est appelé premier potentiel:
diviser premier potentiel par chacun des nombres compris entre 1 et lui-même;
if aucune division n'est exacte
then le premier potentiel est premier
else le premier potentiel n'est pas premier;
La première instruction implique évidemment une itération dans laquelle le nombre premier potentiel est
divisé par les facteurs possibles à partir de 2. L'itération peut prendre fin lorsque l'une des divisions est
exacte (dans ce cas le premier potentiel n'est pas un nombre premier) ou lorsque le diviseur possible est
égal au premier potentiel (dans ce cas le nombre est réellement premier). En fait il n'est pas nécessaire de
prolonger l'itération jusque là: un peu de réflexion montre qu'il suffit d'aller jusqu'à la racine carrée du
potentiel premier. L'algorithme qui permet de tester si un nombre est premier est donc:
20
DIVPOS := 2; {poser comme diviseur possible 2}
repeat
diviser le premier potentiel par DIVPOS;
DIVPOS := DIVPOS + 1;
until la division soit exacte ou que DIVPOS > SQRT (premier potentiel);
if aucune division n'est exacte
then le premier potentiel est premier
else le premier potentiel n'est pas premier; (2.10)
Nous rappelons que l'algorithme 2.10 est un affinement de la seule instruction
tester PREMIERPOT pour voir s'il est premier;
de l'algorithme 2.9. L'algorithme 2.9 peut de ce fait être récrit de la façon suivante:
obtenir le nombre de départ appelé PREMIERPOT;
repeat
PREMIERPOT := PREMIERPOT + 1;
DIVPOS := 2;
repeat
diviser PREMIERPOT par DIVPOS;
DIVPOS := DIVPOS + 1;
until la division soit exacte ou DIVPOS > SQRT (premier potentiel);
if aucune division n'est exacte
then PREMIERPOT est premier
else PREMIERPOT n'est pas premier;
until PREMIERPOT soit premier;
afficher PREMIERPOT; (2.11)
Cet algorithme comporte deux boucles dont l'une est emboîtée dans l'autre. La boucle externe est exécutée
une fois pour chaque nombre premier potentiel, et la boucle interne est exécutée une fois pour chaque
diviseur possible d'un nombre premier potentiel. Les deux boucles sont essentielles dans cet algorithme.
Il faut également remarquer à quel point le temps de traitement peut être économisé dès lors que la racine
carrée est utilisée comme condition pour mettre fin à la boucle interne. Ceci est l'exemple d'un phénomène
courant: un tant soit peu de réflexion pendant la conception peut permettre un gain de temps substantiel
pendant l'exécution.
21
La notation exprimant l'itération repeat ... until ... est tout à fait compréhensible puisque c'est une forme
à peine stylisée du langage courant. Malgré tout, il existe de nombreux cas où des boucles repeat ne
conviennent pas pour exprimer l'itération désirée, et ce pour des raisons que nous allons à présent aborder.
Une boucle repeat comporte une condition d'achèvement après le until qui suit le corps de la boucle. Cela
implique que, dans tous les cas, le corps de la boucle est exécuté au moins une fois puisque la condition
d'achèvement ne peut intervenir qu'à la suite de son exécution. L'importance de cette remarque deviendra
évidente à partir de l'exemple suivant.
Supposons que nous ayons besoin d'un algorithme pour déterminer le nombre le plus grand d'une liste.
Un tel algorithme peut se réaliser par un examen de la liste en comparant chaque nombre avec le plus
grand déjà trouvé et en remettant cette opération à jour à chaque occurrence d'un nombre supérieur. On
peut ainsi arriver sans trop d'effort à l'algorithme 2.12.
MAX := le premier nombre de la liste;
repeat
examiner le nombre suivant;
if ce nombre > MAX
then MAX := ce nombre;
until la liste soit entièrement parcourue;
afficher MAX; (2.12)
Cet algorithme semble correct à première vue, pourtant il comporte une erreur monumentale si la liste ne
comporte qu'un seul nombre. Dans ce cas, le processeur atteint le bout de la liste dès qu'il exécute le corps
de la boucle pour la première fois. Même si la condition d'achèvement "fin de liste" est prévue, elle n'est
pas effective dans ce cas puisque le processeur n'effectue aucun test de fin avant qu'il n'ait exécuté le corps
de la boucle au moins une fois. Il faut donc mettre la condition d'achèvement au début de la boucle plutôt
qu'à la fin pour permettre au processeur d'omettre le corps de la boucle si la condition d'achèvement est
vraie. L'algorithme devient (2.13):
MAX := le premier nombre de la liste;
while la liste n'est pas entièrement parcourue do
begin
examiner le nombre suivant;
if ce nombre > MAX
then MAX := ce nombre;
end;
afficher MAX; (2.13)
22
La condition d'achèvement apparaît avant le corps de la boucle entre while et do. Le corps de la boucle
est noté après do. Pour déterminer clairement l'ensemble d'instructions constituant le corps de la boucle,
le PASCAL utilise les mots begin et end qui agissent comme des "super parenthèses" autour des
instructions à considérer et qui définissent ainsi une instruction composée. De cette manière, on constate
sans équivoque que l'instruction afficher MAX ne fait pas partie du corps de la boucle et n'est exécutée
que lorsque la boucle est terminée. Remarque: dans les algorithmes (2.6) et (2.7), des instructions
composées auraient déjà dû être utilisées pour regrouper les instructions qui dépendent des else.
La forme générale de ce type de boucle est la suivante
while condition do corps de la boucle;
avec le corps de la boucle qui est une instruction seule ou une instruction composée.
Elle signifie que le corps de la boucle doit être répété aussi longtemps que la condition est vraie. Du fait
que la condition est testée avant l'exécution du corps de la boucle, ce type de boucle est dit pré-testé. Le
type de la boucle repeat est dit post-testé. En raison des différentes positions de la condition
d'achèvement, le corps d'une boucle post-testée est toujours exécuté au moins une fois, alors que le corps
d'une boucle pré-testée peut ne pas être exécuté du tout. Une boucle pré-testée peut être considérée comme
une boucle de "précaution", alors que la boucle post-testée est une boucle d"'imprudence". Malgré cette
caractérisation peu flatteuse, la boucle post-testée est souvent utilisée et peut être employée de manière
fiable dès qu'il est admis que le corps de la boucle doit être exécuté au moins une fois. C'est le cas des
exemples de 2.8 à 2.11, où toutes des boucles post-testées étaient utilisées.
Pour consolider les notions concernant l'itération qui viennent d'être développées, nous allons étudier
rapidement un très vieil algorithme: l'algorithme d'Euclide, développé aux alentours de 300 av. J.C., pour
déterminer le plus grand commun diviseur (PGCD) de deux entiers positifs. L'algorithme d'Euclide est
fondé sur la découverte de la relation
PGCD (X, Y) = PGCD (Y, MOD (X, Y)) si Y > 0
et
PGCD (X, Y) = X si Y = 0
où X et Y sont des entiers non négatifs et MOD (X, Y), le reste de la division entière de X par Y. Pour
illustrer l'utilisation de cette relation, cherchons à déterminer le PGCD de 24 et 9:
PGCD (24, 9) = PGCD (9, 6) = PGCD (6, 3) = PGCD (3, 0) = 3
En généralisant, pour déterminer le PGCD de deux entiers non négatifs X et Y, tout ce que nous devons
faire est de répéter la division de X par Y puis de remplacer X par Y et Y par le reste. Le processus
23
continue tant que Y n'est pas égal à zéro. Quand Y égale zéro, la réponse est X. Un algorithme approprié
est donc de ce fait
while Y 0 do
begin
MODU := MOD (X, Y);
X := Y;
Y := MODU;
end;
afficher X; (2.14)
Notez que l'utilisation d'une boucle post-testée dans ce cas ne conviendrait pas puisque l'algorithme ne
fonctionnerait pas (division par zéro) si Y était à l'origine égal à zéro.
Avant d'achever cette section, il nous faut encore aborder une autre forme d'itération. C'est une forme
particulièrement simple dans laquelle le nombre de répétitions est connu avant l'exécution de la boucle.
Par exemple, un algorithme pour calculer la puissance N d'un nombre X (c'est-à-dire pour calculer XN )
comportera une boucle dans laquelle X sera multiplié par lui-même, et il est relativement clair que cette
boucle doit être exécutée N fois. Un tel algorithme peut de ce fait être énoncé ainsi (2.15)
obtenir les valeurs de X et de N;
PRODUIT := 1;
for i := 1 to N do PRODUIT := PRODUIT * X;
afficher PRODUIT; (2.15)
Un autre exemple classique est le calcul de la factorielle de N où l'on calcule le produit des N premiers
nombres entiers (2.16)
Obtenir la valeur de N;
PRODUIT := 1; {affecter 1 à produit}
for i := 1 to N do PRODUIT := PRODUIT * i;
afficher PRODUIT; (2.16)
Ces algorithmes illustrent un type d'itération de la forme générale
for i := 1 to N do corps de la boucle; (2.17)
où i est le compteur de boucle qui prend successivement les valeurs de 1 à N, un entier positif quelconque,
et permet ainsi d'accomplir N fois le corps de la boucle. Le nombre de répétitions étant connu à l'avance,
ce type d'itération s'appelle itération définie à l'avance par opposition à l'itération indéfinie dans laquelle
le nombre de répétitions dépend de ce qui arrive quand la boucle est exécutée.
24
L'itération définie peut naturellement être transformée en itération indéfinie (2.18):
NB := 0; {mettre le compteur de répétitions à 0}
while NB < N do
begin
corps de la boucle;
NB := NB + 1;
end (2.18)
La forme 2.16 est néanmoins plus concise et plus adaptée. La durée de l'itération définie est déterminée
au moment de l'entrée dans la boucle et l'achèvement est assuré. L'itération indéfinie dépend de la
réalisation de la condition d'achèvement.
2.7 SEQUENCE, SELECTION ET ITERATION ENSEMBLE
Les trois dernières sections ont décrit trois formes de base de la construction des algorithmes: la séquence,
la sélection et l'itération. Il faut remarquer que ces trois formes sont suffisantes pour concevoir tout
algorithme. Plus précisément, s'il est possible de concevoir un algorithme pour décrire un processus
donné, alors un tel algorithme peut être entièrement conçu à partir de la séquence, de la sélection et de
l'itération seulement. Il existe cependant d'autres formes de construction qui s'ajoutent utilement aux trois
formes que nous avons déjà présentées (nous les décrirons dans les sections suivantes).
Cependant, pour mettre au clair les idées déjà exposées, nous développerons un algorithme permettant de
classer une liste de noms par ordre alphabétique. La nécessité de trier l'information intervient dans de
nombreuses applications informatiques. C'est un fait que certains ordinateurs passent plus de temps à trier
qu'à toute autre opération. Parce que le tri est une activité très banale, il y a de nombreux algorithmes pour
le faire. Celui que nous allons développer ici est particulièrement simple; il est connu sous le nom de tri
à bulles. Ici nous emploierons un algorithme pour le classement de noms, mais il peut être également
utilisé pour classer toute autre sorte d'information dans un ordre déterminé quelconque.
L'idée de base consiste à parcourir la liste des noms en comparant chaque nom avec celui qui lui succède
et en les intervertissant s'ils ne sont pas dans l'ordre. Si, à la fin du parcours, tous les noms sont classés, il
n'est pas nécessaire de faire quoi que ce soit d'autre. Si ce n'est pas le cas, un autre parcours de la liste est
effectué et d'autres noms sont à nouveau changés de place si cela est nécessaire. La procédure est illustrée
par la figure 2.1 qui montre comment un nom donné monte ou descend pour atteindre la position correcte.
Un algorithme schématisant cette procédure est énoncé comme suit:
25
while liste non triée do
begin
parcourir liste;
permuter deux noms si nécessaire;
end;
liste originale liste après 1 passage
(4 permutations)
liste après 2 passages
(3 permutations)
liste après 3 passages
(2 permutations)
Jean Jean Frédéric Bertrand
Katia Frédéric Bertrand Frédéric
Frédéric Bertrand Jean Jacques
Bertrand Katia Jacques Jean
Samuel Jacques Katia Katia
Jacques Marie Marie Marie
Marie Samuel Samuel Samuel
Figure 2.1: Action du tri à bulles
On utilise la boucle pré-testée de préférence à la boucle post-testée parce que le processeur risque de
trouver la liste déjà en ordre et n'a alors plus rien à faire. (Cette décision sera réexaminée quand
l'algorithme aura été affiné.) La deuxième ligne de l'algorithme peut être affinée de la manière suivante:
commencer au début de la liste;
repeat
si le nom suit alphabétiquement le nom qui le suit then permuter nom et suivant;
examiner le nom suivant;
until la fin de la liste soit atteinte;
Si le nombre de noms est connu (soit N) avant le début de la boucle, alors la boucle indéfinie repeat peut
être remplacée par une boucle définie, compte tenu du fait qu'il y a exactement N - 1 paires de noms
adjacents à comparer. De ce fait l'algorithme complet peut être énoncé de la manière suivante:
while liste non triée do
begin
commencer au début de la liste;
for i := 1 to N – 1 do
begin
if le nom suit alphabétiquement le nom qui le suit then permuter noms;
examiner le nom suivant;
end;
end; (2.19)
26
Cet algorithme convient à la condition que le processeur soit en mesure de déterminer (à la ligne 1) si la
liste est triée ou non. S'il ne le peut pas, la condition d'achèvement de la ligne 1 exige un affinement
supplémentaire. Pour savoir si la liste est classée, on peut essayer de se rappeler si, lors du précédent
parcours, il a été nécessaire de permuter deux noms quelconques. Si ce n'a pas été le cas, tous les noms
sont sans doute dans le bon ordre et la liste est par conséquent triée. A noter qu'au moins un parcours
complet de la liste est nécessaire pour savoir si elle est triée dès le départ. Dans ce cas la boucle pré-testée
est impropre et doit être remplacée par la boucle post-testée. On obtient alors l'algorithme suivant:
repeat
commencer au début de la liste;
for i := 1 to N – 1 do
begin
if le nom suit alphabétiquement le nom qui le suit
then
begin
permuter;
se souvenir qu'une permutation a été faite ici;
end;
examiner le nom suivant;
end;
until plus de permutation pendant ce parcours; (2.20)
Remplacer la boucle pré-testée de l'algorithme 2.19 par la boucle post-testée de l'algorithme 2.20 est le
renversement de la première décision. De tels renversements ne sont pas rares pour affiner des
algorithmes. Plus on ajoute de détails, plus les premières décisions prises avant d'avoir eu une
appréhension totale de l'algorithme doivent être reconsidérées. C'est pourquoi il est important de retarder
ces décisions aussi longtemps que possible de manière qu'elles soient prises en toute connaissance de
cause et n'entraînent pas de révisions ultérieures. Cette philosophie prudente peut être résumée par le
proverbe cyniquement renversé: remettre toujours au lendemain ce qui est difficile à faire le jour même.
L'algorithme 2.20 est un algorithme de tri particulièrement simple, mais ce n'est pas toujours le plus rapide.
D'autres algorithmes donnent au processeur moins d'instructions, et de ce fait accroissent sa vitesse
d'exécution. L'algorithme 2.20 est parfait lorsque la liste est presque en ordre au départ, ce qui n'implique
que quelques parcours. Il ne l'est pas du tout si le dernier nom de la liste est le premier dans l'ordre
alphabétique. Dans ce cas, il faut N - 1 parcours de la liste pour placer ce nom en tête. On peut démontrer
que la moyenne des parcours nécessaires au tri de la liste est approximativement proportionnelle à N.
27
Puisque chaque parcours implique N -1 exécutions de la boucle interne, le nombre moyen de pas exécutés
est approximativement proportionnel à N². Le nombre de pas impliqués dans l'exécution d'un algorithme,
et par conséquent le temps nécessaire à son exécution, sont des attributs qui sont regroupés sous le terme
général de complexité.
Nous conclurons en rappelant que séquence, sélection et itération sont des formes de construction
d'algorithmes tout à fait adéquates. Dans les sections suivantes, nous ajouterons à. ces formes la
modularité et la récursivité qui, sans être absolument nécessaires, sont très pratiques.
2.8 MODULARITE
Dans les sections précédentes, nous avons montré comment développer des algorithmes grâce à des
procédures d'affinement des instructions. A chaque étape de cet affinement, l'algorithme est divisé en
composants plus petits qui peuvent être définis à leur tour de manière plus détaillée. L'affinement s'achève
lorsque chaque élément de l'algorithme est exprimé de manière telle que le processeur prévu peut
l'interpréter.
Les composants rencontrés pendant l'affinement sont souvent totalement indépendants de l'algorithme
principal au sens où ils peuvent être conçus extérieurement au contexte dans lequel ils doivent être utilisés.
De tels éléments peuvent être conçus par quelqu'un d'autre que le concepteur de l'algorithme principal et
peuvent également être utilisés comme éléments d'un autre algorithme. Ils peuvent être considérés comme
des éléments multifonctionnels et intégrables à tout algorithme auquel ils seraient nécessaires.
En guise d'illustration nous allons examiner la conception de certains algorithmes destinés à être exécutés
par un simple automate. La fonction de l'automate consiste à dessiner: il est équipé de roulettes qui lui
permettent des déplacements sur la feuille de papier et d'un stylo qui peut s'abaisser dès qu'il veut faire un
trait. L'automate peut interpréter et exécuter des commandes de la forme:
déplace (x) déplace en avant x cm
gauche (x) tourne x degrés a gauche
droite (x) tourne x degrés à droite
lève stylo ôte stylo du papier
pose stylo pose stylo sur papier
28
Supposons que nous voulions que l'automate dessine deux carrés concentriques comme le montre la figure
2.2, sa position initiale étant le point X, centre des carrés, le stylo levé. On peut esquisser l'algorithme
suivant
déplace en A;
dessine un carré de 10 cm de côté;
déplace en B;
dessine un carré de 20 cm de côté; (2.21)
B
Figure 2.2: Carrés concentriques devant être tracés par un automate à partir du point X
La seconde et la quatrième instructions de cet algorithme impliquent le dessin d'un carré, qui est une
procédure en soi indépendante du reste de l'algorithme, ce qui implique que nous pouvons concevoir un
algorithme pour dessiner un carré sans référence au contexte de l'algorithme qui l'utilise. Nous pouvons
même, si nous le désirons, demander à quelqu'un d'autre de le concevoir sans lui dire à quoi nous
l'emploierons. Une fois un tel algorithme conçu, nous pouvons l'intégrer aux endroits prévus dans
l'algorithme 2.21 ou à tout autre algorithme pour lequel le tracé d'un carré serait nécessaire.
Un algorithme qui peut être intégré à un autre algorithme est un module (dans certains langages de
programmation, ce peut être une procédure, une routine, une sous-routine ou une fonction). Un module
est un algorithme en soi et peut être conçu indépendamment du contexte dans lequel il doit être utilisé.
On dit d'un algorithme qui utilise un module qu'il l'appelle.
Pour que le module de conception du carré soit globalement utilisable, il doit être en mesure d'effectuer
un tracé de n'importe quelle taille. Lorsque le module est appelé, la taille spécifique requise doit être
indiquée. Pour l'algorithme 2.21, nous pourrions écrire
dessinercarré (10) et dessinercarré (20)
ce qui signifierait qu'un des carrés doit avoir un côté de 10 cm et l'autre, un côté de 20 cm. Ce module,
lui-même peut être énoncé de la manière suivante (2.22), en utilisant la syntaxe du PASCAL qui annonce
un module par le mot procedure et inclut toutes les instructions du module entre begin et end:
A
X
29
procedure dessinercarré (taille);
{Dessine un carré dont le côté a une longueur taille en cm. Le carré est tracé dans le sens inverse
des aiguilles d'une montre en partant de la position actuelle de l'automate. La première ligne est
tracée selon l'orientation actuelle de l'automate. L'automate revient à sa position et à son
orientation initiales dès que le stylo est levé.}
begin
poser stylo;
for i := 1 to 4 do
begin
déplacer (taille);
gauche (90);
end;
lever stylo;
end; (2.22)
La taille représente un paramètre formel du module: il est utilisé à l'intérieur du module pour définir la
taille du carré. Lorsque le module est appelé, le paramètre actuel 10 (ou 20) donne une valeur spécifique
de la taille, et détermine ainsi la grandeur du carré.
Dans ce syllabus, la notation que nous retiendrons pour les modules sera la suivante:
procedure nommodule (paramètres formels);
{Spécification du traitement que le module décrit}
begin
corps du module;
end;
Le commentaire entre accolades aide le lecteur à comprendre ce que le module fait; le corps du module
explique le détail de ce qu'il effectue. Le corps d'un module est exécuté et le commentaire ne l'est pas.
On peut appeler un module de la manière suivante:
nommodule (paramètres actuels);
C'est ce que le processeur interprète comme une directive pour exécuter le corps du module appelé dont
les paramètres formels ont été remplacés par les paramètres actuels de l'appel. Les paramètres formels
30
d'un module peuvent être considérés comme la représentation de l'information nécessaire au module
lorsqu'il est appelé.
Les paramètres actuels sont des informations pour un appel particulier. Ces informations prennent la place
des paramètres formels lorsque le module est exécuté. Il doit naturellement y avoir le même nombre de
paramètres actuels et formels.
Un algorithme construit autour d'un nombre donné de modules est appelé un algorithme modulaire.
Chaque module est un composant en soi de l'algorithme et agit comme un bloc dans la construction de
l'algorithme. L'interface entre le module et ses appelants est double:
1) l'interface explicitement exprimée dans les paramètres (par exemple la taille du carré à dessiner par
dessinercarré);
2) l'interface implicite dans les présupposés du module et de son appelant sur leur action réciproque (par
exemple que dessinercarré se termine avec le stylo levé).
Les deux formes d'interface doivent être décrites dans la spécification du module. La seconde forme,
devant être implicite, doit faire l'objet d'une description très fine.
En utilisant le module dessinercarré comme nous l'avons précédemment défini, nous pouvons affiner
l'algorithme 2.21 de la manière suivante:
gauche (45);
déplacer (SQRT(50)); {déplacer en A}
gauche (135);
dessinercarré (10); {dessiner carré intérieur}
droite (135);
déplacer (SQRT(50)); {déplacer en B}
gauche (135);
dessinercarré (20); {dessiner carré extérieur} (2.23)
Notez que toutes les instructions de l'algorithme sont des appels à des modules. Nous n'avons pas donné
les algorithmes pour les modules déplacer, gauche et droite puisque nous avons estimé qu'ils étaient
suffisamment simples pour que l'automate soit capable d'interpréter leurs appels. Si ce n'est pas le cas,
chaque module devra être défini dans les termes que l'automate peut interpréter. Ainsi le module déplacer
pourrait par exemple être défini comme (2.24)
31
procedure déplacer (x);
{L'automate se déplace de x cm en avant sans changer d'orientation. Le stylo n'est ni levé ni posé.}
begin
N := x DIV (circonférence d'une roulette); {nombre requis de rotations des roulettes}
for i := 1 to N do faire tourner toutes les roulettes à la fois;
end; (2.24)
Cette définition de déplacer présuppose que l'automate peut faire des divisions et qu'il sait comment faire
réaliser une rotation à ses roulettes. DIV est l'opérateur de division entière.
Il faut bien comprendre que le concepteur de l'algorithme 2.23 n'a pas besoin de savoir comment le module
dessinercarré travaille; tout ce qu'il doit connaître est l'effet de son exécution. En d'autres termes, il n'a
pas besoin de comprendre le corps du module mais uniquement de lire la spécification de son en-tête.
Ainsi peut-il clairement distinguer deux problèmes de conception: celui de l'algorithme 2.23 et la
conception de dessinercarré. Cela diminue la complexité de la procédure de conception tout en lui
assurant une plus grande vitesse et une meilleure fiabilité. dessinercarré peut être conçu après que
l'algorithme 2.23 est fini ou peut l'être par quelqu'un d'autre indépendamment de l'algorithme.
Inversement, si le module existe déjà parce qu'il a été nécessaire à un autre algorithme, il peut simplement
être appelé sans travail supplémentaire. Les possibilités des modules peuvent encore être illustrées par
cette approche du module dessinercarré. Puisqu'un carré n'est qu'un polygone particulier, il peut être
intéressant de concevoir un module pour dessiner des polygones et de l'appeler grâce à des paramètres
actualisés appropriés pour un carré. Un module de tracé de polygone peut s'énoncer (2.25):
procedure dessinerpolygone (taille, N);
{Dessine un polygones de N côtés de taille cm chacun. Le polygone est tracé dans le sens inverse
des aiguilles d'une montre à partir de la position actuelle de l'automate. La première ligne est
dessinée selon l'orientation actuelle de l'automate. L'automate revient à sa position et à son
orientation initiales lorsque le stylo est levé.}
begin
poser stylo;
for i := 1 to N do
begin
déplacer (taille);
gauche (360 DIV N);
end;
lever stylo;
end; (2.25)
32
Le module dessinercarré peut à présent être récrit simplement:
procedure dessinercarré (taille);
{Dessine un carré de côté taille cm,... }
begin
dessinerpolygone (taille,4);
end;
De même, on peut écrire un module pour dessiner un triangle (2.26)
procedure dessinertriangle (taille);
{Dessine un triangle équilatéral de taille cm de côté,...}
begin
dessinerpolygone (taille,3);
end; (2.26)
Les modules pour tracer des pentagones, des hexagones, etc. peuvent être écrits aussi simplement. Notez
que la dernière version de dessinercarré ne nécessite aucune modification de l'algorithme 2.23 ou d'autre
algorithme l'appelant.
Les avantages que comporte l'utilisation de modules peuvent être résumés de la manière suivante:
1) Les modules correspondent naturellement à l'affinement progressif de l'algorithme et l'on obtient ainsi
une conception descendante.
2) Un module est en soi un composant de tout autre algorithme plus important qui l'appelle. Un module
et l'algorithme appelant peuvent être conçus indépendamment l'un de l'autre, ce qui simplifie la
procédure de conception. Puisque l'écriture d'un algorithme est généralement une tâche difficile, toute
simplification est bienvenue. Les avantages de la simplification consistent en une conception plus
rapide et en une moindre probabilité d'erreurs.
3) Pour intégrer un module à un algorithme, il suffit de savoir ce que fait le module et non comment il le
fait. Ce que fait un module peut être expliqué de manière adéquate par un commentaire de début.
4) De même que les modules simplifient la conception des algorithmes, ils simplifient aussi leur
compréhension. Pour comprendre, par exemple, l'algorithme 2.23, il suffit de comprendre l'effet des
modules déplacer, dessinercarré et ainsi de suite, sans pour autant savoir comment ces résultats sont
atteints. La facilité de compréhension est très importante dans le cas fréquent où un algorithme doit
être modifié (particulièrement lorsqu'il doit l'être par d'autres que l'auteur). C'est également un facteur
d'importance pour la démonstration de la validité de l'algorithme.
5) Une fois qu'un module a été conçu, il peut être intégré à tout algorithme qui en a besoin. Il est de ce
fait possible de construire une bibliothèque de modules, tels que des modules de tri, de résolution
d'équations, de calcul des impôts, etc.
33
L'approche modulaire sera généralisée en deuxième bachelier pour conduire à la méthodologie objet qui
est à la base d'une autre méthode de conception d'algorithme: l'approche ascendante.
2.9 RECURSION
Dans la section 2.6, nous présentions un algorithme (2.16) pour calculer le produit des N premiers entiers
(la factorielle de N ). Cet algorithme utilisait une boucle dans laquelle les entiers successifs de 1 à N
étaient multipliés entre eux. Une approche différente consiste à utiliser le fait que la factorielle de N est
le produit de N par la factorielle de N – 1, c'est-à-dire, factorielle (N) = N * factorielle (N - 1).
Cela est vrai pour tout N plus grand que 1. De plus, factorielle (1) = 1. Ainsi un algorithme possible pour
calculer la factorielle de N est écrit par le module suivant:
function factorielle (N);
{Calcule la factorielle N pour tout entier N > 0}
begin
if N = 1
then factorielle := 1
else factorielle := N * factorielle (N-1);
end; (2.27)
Une fonction, notée function en PASCAL, est un module spécial dont le nom nommodule définit une
entité contenant une valeur. Une fonction est un module avec des paramètres formels et actuels (exemple:
factorielle (N – 1)) dont le résultat du calcul est contenu dans son nommodule (factorielle := 1). On utilise
une fonction plutôt qu'une procédure lorsque le calcul du module doit produire un seul résultat. Remarque:
nous avons déjà rencontré une fonction baptisée SQRT qui appliquée au paramètre N fournit la racine
carrée de N. Comme c'est une fonction, nous pouvons écrire
X := SQRT (4); et X contient alors la valeur 2.
L'avant-dernière ligne du module présuppose que le module doit être à nouveau exécuté, mais avec les
paramètres actuels moins un. La figure 2.3 illustre l'exécution du module lorsque N est égal à 3. La figure
montre comment le calcul de factorielle (3) implique le calcul de factorielle (2) qui à son tour implique
celui de factorielle (1). Les boîtes illustrent les trois exécutions requises du module et les nombres à droite
de chaque boîte représentent les résultats cumulatifs après chaque exécution.
L'algorithme 2.27 de calcul de la factorielle de N, est exprimé en termes d'un algorithme de calcul de la
factorielle de N - 1. C'est pourquoi on peut considérer que l'algorithme est exprimé en référence à lui-
34
même, son entrée N devant être remplacée par N - 1. Le terme utilisé pour cette forme d'expression est la
récursion: un algorithme récursif est un algorithme qui s'appelle lui-même.
On évite le mouvement apparent de retour sur soi-même de la récursion en s'assurant que l'entrée des
appels récursifs successifs devient progressivement plus "simple". On doit alors rencontrer un cas limite
dans lequel l'entrée est si "simple" que le traitement peut être effectué sans qu'il n'ait plus à s'appeler lui-
même. Par exemple, l'entrée N de l'algorithme 2.27 devient progressivement plus élémentaire en étant
réduite de 1 à chaque appel successif. A la limite, quand N est réduit à 1, l'exécution est directe et ne
nécessite pas d'autres appels. Le cas limite peut être considéré comme une issue de secours qui assure en
tout état de cause la fin de l'exécution. Tout algorithme récursif doit comporter une issue de secours et
l'entrée doit être simplifiée progressivement jusqu'à pouvoir atteindre cette issue de secours.
factorielle (3):
6
Figure 2.3: Calcul de factorielle (3) par l'algorithme 2.27
Voici un autre exemple de récursion avec le problème de l'inversion de l'ordre des lettres d'un mot (star
en rats). Ce problème peut être résolu en ôtant la première lettre du mot, en inversant le reste du mot et
en ajoutant ensuite la lettre ôtée. La base d'un tel algorithme peut être
ôter la première lettre
inverser le reste du mot
ajouter la lettre ôtée
L'algorithme est nettement récursif puisqu'il décrit comment inverser une séquence de lettres en termes
d'inversion d'une séquence plus courte de lettres. A chaque appel récursif, une seule lettre est ôtée de la
séquence à inverser, ce qui simplifie progressivement l'entrée de l'algorithme. Dans le cas limite, lorsque
la séquence ne comporte plus que la première lettre, l'issue réside dans le fait qu'une seule lettre à inverser
équivaut à l'écrire. D'où cet algorithme complet pour inverser une séquence de lettres.
if 3 = 1
then ... else factorielle := factorielle (2) * 3;
if 2 = 1
then ...
else factorielle := factorielle (l) * 2;
if 1=1
then factorielle := 1
else ...
2
1
6
35
procedure inverser (séquence);
{inverse la séquence donnée de lettres}
begin
if séquence ne contient qu'une lettre
then l'écrire
else
begin
ôter la première lettre de la séquence;
inverser (reste de la séquence);
ajouter la lettre ôtée;
end;
end; (2.28)
La figure 2.4 illustre l'exécution du module ayant comme entrée "star". La sortie cumulative de chaque
appel est inscrite à droite entre parenthèses.
inverser "star"
if "star" contient une lettre
then...
else ôter "s"
inverser "tar"
if "tar" contient une lettre
then...
else ôter "t"
inverser "ar"
if "ar" contient une lettre
then...
else ôter "a"
inverser "r"
if "r" contient une lettre
then l'écrire ( r )
else...
ajouter "a" ( ra )
ajouter "t" ( rat )
ajouter "s" ( rats )
Figure 2.4: Inversion du mot "star" par l'algorithme 2.28
36
Les deux algorithmes 2.27 et 2.28 peuvent être remplacés par des algorithmes itératifs, ce qui sous-entend
que la récursion n'est qu'un cas particulier d'itération. Il peut être démontré que pour tout algorithme
utilisant la récursion, il existe un algorithme équivalent qui utilise l'itération. Malgré tout, un algorithme
récursif décrivant un processus particulier est souvent beaucoup plus concis qu'un itératif, et dans de
nombreux exemples, il est beaucoup plus facile à déterminer et à comprendre. Dans les paragraphes
suivants nous en donnerons deux exemples. Le premier est un algorithme récursif plus concis que son
équivalent itératif. C'est une version récursive de l'algorithme d'Euclide permettant de trouver le plus
grand commun diviseur de deux entiers positifs: la version itérative est l'algorithme 2.14 de la section 2.6.
PGCD (x, y) = PGCD (y, reste de x DIV y) à moins que y = 0, auquel cas PGCD (x, y) = x.. Cette relation
conduit immédiatement à l'algorithme récursif suivant:
function PGCD (X, Y);
{Calcule le PGCD des entiers positifs X et Y}
begin
if Y = 0
then PGCD := X
else PGCD := PGCD (Y, MOD (X, Y);
end; (2.29)
Notez que l'exécution récursive de l'algorithme se termine lorsque Y est réduit à zéro, auquel cas le résultat
requis est X. La figure 2.5 illustre l'exécution de l'algorithme du PGCD de 24 et de 9.
calculer PGCD (24, 9)
if 9 = 0
then...
else calculer PGCD (9, 6) ( 3 )
if 6 = 0
then...
else calculer PGCD (6, 3) ( 3 )
if 3 = 0
then...
else calculer PGCD (3, 0) ( 3 )
if 0 = 0
then résultat est 3 ( 3 )
else...
Figure 2.5: Calcul du PGCD (24,9) par l'algorithme 2.29
37
Pour le second exemple, il est plus facile de dégager un algorithme récursif qu'un algorithme itératif. C'est
un cas célèbre, connu sous le nom de la tour de Hanoï. Selon la légende, des moines bouddhistes de Hanoï
furent chargés pendant plusieurs années de la mission suivante. Les prêtres disposaient de trois barres
verticales et d'un ensemble de 64 disques circulaires de tailles différentes. Chaque disque comportait un
trou central lui permettant de s'emboîter exactement à la barre. Au départ, les disques étaient empilés par
ordre de taille décroissante sur une seule barre, de telle sorte qu'ils formaient une tour comme le montre
la figure 2.6. Les prêtres avaient pour tâche de les transférer sur l'une des autres barres en ne déplaçant
qu'un disque à la fois et en s'assurant qu'aucun disque n'était posé sur un disque plus petit. Ce transfert
devait permettre une élévation spirituelle et les prêtres croyaient que son achèvement coïnciderait avec la
fin du monde !
Puisque la stratégie de déplacement des disques n'est pas évidente et puisqu'une erreur coûterait des années
de travail, les prêtres doivent se conformer scrupuleusement à un algorithme qui décrit comment résoudre
leur problème. Un tel algorithme peut être décrit de la manière suivante.
Figure 2.6: La tour de Hanoï
Appelons a, la barre qui maintient la barre initiale; b, celle sur laquelle la tour doit être transférée et c la
troisième. Etant donné les règles gouvernant le transfert des disques, il apparaît que la seule façon de
déplacer le plus grand disque de la tour initiale afin de former la base de la nouvelle tour est d'ôter les 63
disques supérieurs. La seule place que ces 63 disques puissent occuper est la troisième barre. L'algorithme
pour transférer la tour de la barre a vers b est le suivant:
transférer les 63 disques supérieurs de a à c;
déplacer le disque inférieur de a à b;
transférer les 63 disques de c à a;
L'algorithme décrit le transfert de 64 disques entre deux barres en termes du transfert de 63 disques entre
deux barres. De même, le transfert de 63 disques entre deux barres peut être décrit en termes du transfert
de 62 disques entre deux barres et ainsi de suite. En généralisant ce problème, l'algorithme permettant de
transférer N disques d'un support de départ à un support d'arrivée (étant donné que le troisième support
est appelé intermédiaire ) est
38
transférer N-1 disques du départ sur l'intermédiaire;
déplacer 1 disque du départ sur l'arrivée;
transférer N-1 disques de l'intermédiaire sur l'arrivée;
Cet algorithme est nettement récursif et le nombre de disques à déplacer à chaque appel récursif est
successivement réduit de 1. On peut sortir de ces appels successifs lorsqu'il ne reste plus qu'un seul disque
à transférer entre deux barres. Dans ce cas, il ne reste plus qu'à l'ôter et le déplacer. D'où cet algorithme
complet pour transférer N disques d'une barre de départ sur une barre d'arrivée:
procedure déplacertour (N, départ, arrivée, intermédiaire);
{déplace une tour de N disques du départ à l'arrivée en utilisant l'intermédiaire}
begin
if N = 1
then déplacer un disque du départ sur l'arrivée
else
begin
déplacertour (N - 1, départ, intermédiaire, arrivée);
déplacer un disque du départ sur l'arrivée;
déplacertour (N - 1, intermédiaire, arrivée, départ);
end;
end; (2.30)
L'exécution de l'algorithme lorsque N = 64 mène à deux exécutions avec N = 63, chacune desquelles
menant à deux exécutions avec N = 62 et ainsi de suite. C'est pourquoi le transfert total de la tour nécessite
264 - 1 exécutions de l'algorithme. Puisqu'un seul disque est déplacé à chaque exécution, le nombre total
de déplacements à effectuer est égal à 264 - 1. Si les prêtres peuvent déplacer un disque par seconde sans
jamais faire une erreur, le temps nécessaire au transfert total devra être de l'ordre de 600 000 000 000
d'années ! On peut en outre prouver qu'il n'existe aucun algorithme plus rapide.
Dès à présent, il est clair qu'il existe une stratégie utile permettant d'élaborer des algorithmes récursifs. Le
premier élément de la stratégie est de déterminer comment la procédure à exécuter peut être exprimée de
manière récursive; autrement dit comment la procédure peut être exprimée en termes de procédures
similaires qui diffèrent de la procédure initiale par une entrée simplifiée (par exemple, un nombre plus
petit ou encore une séquence plus courte). Le second élément consiste à assurer un cas limite lorsque
l'entrée est réduite au point que l'appel récursif n'est plus nécessaire. Cette limitation sert ensuite de sortie
hors de la récursion.
39
CHAPITRE 3 : STRUCTURES DE DONNEES
3.1 INTRODUCTION
Nous nous sommes principalement consacrés jusqu'à présent à la structure de contrôle des algorithmes,
c'est-à-dire aux constructions qui peuvent être utilisées pour contrôler l'ordre et les circonstances dans
lesquels les étapes individuelles d'un algorithme sont exécutées. Le choix de constructions de contrôle
appropriées est une partie essentielle du développement d'un algorithme, mais qui ne peut être accomplie
sans considérer l'information (ou les données) que l'algorithme manipule. En général, les données
manipulées par un algorithme ne sont pas simplement un ensemble quelconque d'éléments sans rapport
les uns avec les autres, mais consistent plutôt en informations reliées les unes aux autres.
Comme exemple, considérons un algorithme utilisé pour avoir une information constante sur le personnel
employé dans une entreprise. Les données manipulées par l'algorithme comportent des noms, des adresses,
des âges, des grades hiérarchiques et ainsi de suite. Ces éléments ne sont pas seulement des informations,
mais ont des relations logiques entre eux. Un rapport évident entre un nom, une adresse, un âge et une
position hiérarchique est que ces éléments concernent une même personne. Les données ne sont donc pas
des éléments isolés mais un ensemble d'enregistrements dont chacun contient toute l'information
concernant un employé donné. Ces enregistrements peuvent avoir des rapports logiques entre eux,
reflétant les rapports logiques entre les personnes qu'ils décrivent. Par exemple, certains employés (et les
enregistrements les décrivant) peuvent être associés parce qu'ils travaillent dans le même département
d'une entreprise, ou un employé peut être associé à plusieurs autres parce qu'il est leur supérieur
hiérarchique immédiat. Les données qui sont organisées pour refléter les rapports logiques entre leurs
éléments sont dites structurées. Les éléments de données et leurs relations mutuelles donnent ensemble
ce qu'on appelle une structure de données.
Nous avons déjà utilisé des structures de données précédemment sans les mentionner explicitement. Par
exemple les algorithmes de tri que nous avons développés fonctionnaient tous sur une liste de noms. Une
telle liste est une structure de données dans laquelle les noms individuels sont reliés entre eux par leur
ordre physique: un nom vient soit avant soit après d'autres noms de la liste. Les algorithmes de tri
transforment une liste en une autre en modifiant l'ordre physique des noms afin qu'ils coïncident avec leur
ordre alphabétique. Une liste constitue un exemple d'un type particulièrement commun de structure de
données, connu sous le nom de séquence. Une séquence est un ensemble d'éléments ordonné de telle
manière que tout élément à l'exception d'un seul (le premier) ait un prédécesseur. Quelques exemples:
40
1) Un mot, qui est une séquence de lettres.
2) Un texte, qui est une séquence de mots séparés par des espaces et des symboles de ponctuation.
3) Un nombre, qui est représenté sous forme écrite par une séquence de chiffres.
4) Un train, qui est une séquence de wagons (précédés d'une locomotive).
5) Un annuaire téléphonique, qui est une séquence d'enregistrements, dont chacun contient un nom, une
adresse et un numéro de téléphone.
Une séquence est une structure particulièrement utile pour des éléments devant être traités l'un après
l'autre. Un algorithme de description de tels traitements peut se présenter sous la forme globale
commencer au début de la séquence;
while la fin de la séquence n'est pas atteinte do
traiter l'élément suivant;
Si l'on sait que la séquence contient au moins un élément, la boucle while peut être remplacée par une
boucle repeat. Si le nombre d'éléments est connu, une itération indéfinie peut être remplacée par une
itération définie. Les algorithmes 2.13 et 2.19 sont des exemples d'algorithmes agissant sur des séquences
selon ce schéma général.
En général, les algorithmes décrivent des processus qui transforment une structure de données (l'entrée)
en une autre structure de données (la sortie). Parfois, comme lorsqu'il s'agit d'un tri à bulles (algorithme
2.20), la transformation peut être effectuée par simple manipulation des données à l'intérieur du cadre de
la structure de données initiale. Cependant, dans de nombreux cas, des structures de données
intermédiaires peuvent être nécessaires. Le développement de l'algorithme dans ces cas est intimement lié
au choix d'une structure de données appropriée.
Avant d'aborder la description des structures, il convient de s'intéresser aux éléments d'information qui la
composeront. Ces éléments (ces données) peuvent être de types différents comme des entiers, des réels,
des booléens, des caractères, … Les types constituent une description du format de représentation interne
des données en machine, et ils sont par là-même un outil d’abstraction, puisqu’ils libèrent le programmeur
du souci de la représentation physique des données. Ainsi, il n’est pas nécessaire de savoir comment est
représentée une variable de type char ou boolean, voire string, du moment que l’on sait la manipuler de
la manière convenue. Nous introduirons donc le concept de type de données qui nous conduira à
sélectionner des types de données primitifs grâce auxquels nous pourrons alors construire des structures
de données. Dans ce chapitre 3, nous verrons les structures de données statiques élémentaires. Le chapitre
41
4 présentera les bases des structures dynamiques. Le chapitre 5 abordera des structures de données plus
élaborées implémentées "statiquement" ou "dynamiquement".
3.2 LE CONCEPT DE TYPE DE DONNÉES
En mathématiques, on classe couramment les variables suivant un certain nombre de caractéristiques. On
peut faire une claire distinction entre les variables réelles, complexes ou logiques, ou entre les variables
représentant des valeurs individuelles, des ensembles de valeurs ou des ensembles d'ensembles, ou encore
entre les fonctions, les ensembles de fonctions, etc. Cette notion de classification est au moins aussi
importante dans le domaine du traitement des données. Nous poserons donc en principe que chaque
constante, chaque variable, expression ou fonction est d'un certain type. Ce type caractérise
essentiellement l'ensemble des valeurs auquel la constante appartient, ou qui peuvent être prises par une
variable ou une expression, ou encore qui peuvent être engendrées par une fonction.
Dans les textes mathématiques, on peut souvent déduire le type d'une variable de par la façon dont elle
est écrite, sans avoir besoin de recourir au contexte; ceci n'est pas possible en informatique où on n'utilise
qu'un seul jeu de caractères. Une règle générale est donc d'expliciter le type associé lors de la déclaration
d'une constante, d'une variable ou d'une expression, cette déclaration précédant, dans le texte, toute
manipulation de cette constante, variable ou expression. Cette règle est particulièrement importante si l'on
considère le fait qu'un compilateur doit choisir la représentation de l'objet en mémoire: la quantité de
mémoire réservée à une variable sera calculée en tenant compte de l'ensemble des valeurs que la variable
peut prendre. C'est souvent la clé de la réalisation efficace d'un algorithme. Les principales caractéristiques
du concept de type sont:
1) Un type de donnée détermine l'ensemble des valeurs auquel appartient une constante, ou qui peuvent
être prises par une variable ou une expression, ou qui peuvent être engendrées par un opérateur ou une
fonction.
2) Le type de la valeur d'une constante, d'une variable ou d'une expression peut être déduit de sa forme
ou de sa déclaration sans qu'il soit nécessaire d'exécuter un quelconque traitement.
3) Tout opérateur et toute fonction exige des arguments d'un certain type et produit un résultat d'un type
donné. Si un opérateur admet des arguments de types différents (par exemple + peut admettre des
entiers ou des réels), le type du résultat peut être déterminé à l'aide de règles spécifiques du langage.
En conséquence, un compilateur peut utiliser cette information sur les types pour vérifier la légalité de
certaines constructions. C'est ainsi que l'affectation erronée d'une valeur booléenne à une variable
42
arithmétique peut être détectée avant l'exécution du programme. Cette redondance dans le texte du
programme est extrêmement utile: c'est une aide au développement des programmes et c'est le principal
avantage des bons langages de haut-niveau par rapport au langage machine.
La théorie présentée ici implique certaines méthodes de définition des types de données. Dans la plupart
des cas, on définit de nouveaux types en termes de types déjà définis. Les valeurs de ces nouveaux types
sont souvent des agrégats de valeurs qui appartiennent à des types constituants déjà définis; on dit qu'ils
sont structurés. S'il n'y a qu'un seul type constituant, on a alors affaire à un type de base. Le nombre de
valeurs distinctes appartenant à un type T est son cardinal qu'il est utile de connaître pour calculer la
quantité de mémoire nécessaire à la représentation d'une variable X de type T, ce qu'on note X : T.
Puisque les types constituants peuvent également être structurés, on peut construire une structure
hiérarchique de types, étant entendu que les composants ultimes de la structure sont atomiques. Il est donc
nécessaire d'avoir une notation pour ces types primitifs non structurés. La méthode la plus évidente est
d'énumérer les valeurs constituant le type. Si, par exemple, on a besoin de manipuler des figures
géométriques planes, on peut définir un type primitif forme, dont les valeurs seront rectangle, carré,
ellipse et cercle. Mais en dehors de ces types définis par le programmeur, il en existe d'autres prédéfinis
comme, par exemple, pour représenter les nombres entiers et les valeurs logiques. Si un ordre est défini
sur les valeurs de ces types, on dit que le type est ordonné ou scalaire. Remarque: dans le cas d'une
énumération explicite des valeurs, l'ordre est défini par la position des valeurs dans l'énumération.
Il est donc possible de définir des types primitifs et de construire des types composés, structurés avec un
nombre quelconque d'imbrications. En pratique cependant, il ne suffit pas d'avoir une seule méthode
générale pour combiner des types constituants en une structure. Etant donné les problèmes concrets de
représentation des données, un langage de programmation offre, en général, plusieurs méthodes de
structuration. Au sens mathématique du terme, elles sont équivalentes: elles diffèrent simplement par les
opérateurs disponibles pour sélectionner les composants des structures. Les méthodes de structuration de
base que nous présentons ici sont le tableau, le record, l'ensemble et la suite.
On introduit des variables et des types de données pour faire des calculs; c'est pourquoi on doit leur
associer des opérateurs. Pour chaque type de données standard, un langage de programmation propose un
ensemble d'opérateurs standard, primitifs, de même qu'à chaque méthode de structuration correspondent
une opération spéciale et une notation spéciale de sélection d'un composant. On considère souvent que
l'art de la programmation réside essentiellement dans la composition des opérations; il deviendra vite
évident qu'une bonne composition des données est tout aussi fondamentale et essentielle.
43
Les opérateurs de base les plus importants sont la comparaison et l'affectation, c'est-à-dire le test sur
l'égalité (et sur l'ordre dans le cas de types ordonnés), et l'injonction de mettre à égalité. La différence
fondamentale entre ces deux opérations est soulignée par la distinction claire entre les deux notations
respectées tout au long de ce texte:
Test d'égalité X = Y (expression dont la valeur est Vrai ou Faux)
Affectation à X X := Y (expression qui fait que X devient égal à Y)
Ces opérateurs sont définis pour la plupart des types de données, mais on doit savoir que leur exécution
peut provoquer, dans le cas de données importantes et très structurées, un calcul assez complexe.
Pour ce qui est des types de données primitifs, nous supposerons non seulement l'existence de l'affectation
et de la comparaison, mais encore celle d'un ensemble d'opérateurs pour créer (calculer) de nouvelles
valeurs. Nous introduirons donc les opérations standard de l'arithmétique des types numériques et les
opérateurs élémentaires de la logique des propositions pour les valeurs logiques.
3.3 LES TYPES DE DONNÉES PRIMITIFS
On peut définir un nouveau type de données primitif en énumérant les valeurs distinctes qui le composent.
On a alors un type énuméré dont la définition est de la forme:
Type T = (c1, c2, ..., cn);
T est l'identificateur du nouveau type tandis que les ci sont les nouveaux identificateurs de constantes. Le
cardinal de T est card (T) = n.
Exemples:
Type forme = (rectangle, carré, ellipse, cercle);
Type couleur = (rouge, jaune, vert);
Type sexe = (mâle, femelle);
Type Boolean = (FALSE, TRUE);
Type jourdelasemaine = (lundi, mardi, mercredi, jeudi, vendredi, samedi, dimanche);
La définition de chacun de ces types n'introduit pas seulement un nouvel identificateur de type mais aussi
l'ensemble des identificateurs dénotant les valeurs de ce nouveau type. On peut dès lors utiliser ces
identificateurs comme des constantes dans tout le programme, ce qui améliore grandement la
compréhension du texte. Si, par exemple, nous définissons les variables s, d, r et b par:
44
Var s: sexe;
Var d: jour de la semaine;
Var b: BOOLEAN;
Nous pouvons écrire:
s := mâle;
d := dimanche;
b := TRUE;
ce qui est beaucoup plus compréhensible que
s := 1; d := 7; b := 2;
où l'on suppose que s, d et b sont des entiers et que l'on fait correspondre une constante de la définition à
l'ordre de son apparition dans l'énumération. De plus, un compilateur peut vérifier que l'on ne fait pas un
mauvais usage d'un opérateur. Par exemple, étant donné la définition de s que nous avons vue, l'instruction
s := s + 1 n'a aucun sens.
3.4 TYPES PRIMITIFS STANDARD
Les types primitifs standard sont ceux que l'on trouve tout faits sur la plupart des ordinateurs. Ce sont les
nombres entiers, les valeurs logiques et l'ensemble des caractères imprimables. Sur beaucoup
d'ordinateurs, on trouve aussi les nombres fractionnaires, associés aux opérations arithmétiques standard.
Nous dénoterons ces types par les identificateurs
INTEGER, CARDINAL, REAL, BOOLEAN, CHAR
Le type INTEGER comprend un sous-ensemble des nombres entiers, sous-ensemble dont la taille varie
d'une machine à une autre. Si un ordinateur utilise n bits pour représenter un entier en complément à 2,
les valeurs possibles de x doivent satisfaire -2n-1 x < 2n-1. On suppose que toutes les opérations sur les
données de ce type sont exactes et qu'elles correspondent aux lois ordinaires de l'arithmétique, tout calcul
étant interrompu lorsque le résultat est en dehors du sous-ensemble représentable (c'est ce qu'on appelle
un dépassement de capacité). Les opérateurs standard représentent les quatre opérateurs arithmétiques de
base: l'addition (+), la soustraction (-), la multiplication (*) et la division (/, DIV pour la division modulo).
Le type REAL dénote un sous-ensemble des nombres réels. Alors que l'arithmétique utilisée avec des
opérandes du type INTEGER est supposée conduire à des résultats exacts, celle qui s'applique aux valeurs
du type REAL peut conduire à des résultats légèrement faussés en raison des erreurs d'arrondi dues aux
calculs portant sur un nombre limité de chiffres.
45
Les deux valeurs du type standard BOOLEAN sont notées TRUE (vrai) et FALSE (faux). Les opérateurs
booléens sont la conjonction logique, la disjonction et la négation dont les valeurs sont définies dans la
table 3.1. La conjonction est désignée par le symbole AND, la disjonction par OR et la négation par NOT
(ou -). Notez que les comparaisons sont des opérations produisant un résultat de type BOOLEAN. On
peut donc affecter le résultat d'une comparaison à une variable, ou utiliser ce résultat comme opérande
d'un opérateur logique dans une expression booléenne. Par exemple, étant donné les variables booléennes
p et q et les variables entières x = 5, y = 8, z = 10, les deux affectations
p := x = y;
q := (x < y) AND (y < z);
donnent p = FALSE et q = TRUE.
p q p OR q p AND q NOT p
TRUE TRUE TRUE TRUE FALSE
TRUE FALSE TRUE FALSE FALSE
FALSE TRUE TRUE FALSE TRUE
FALSE FALSE FALSE FALSE TRUE
Table 3.1 Les opérateurs booléens.
Le type standard CHAR comprend l'ensemble des caractères imprimables.
3.5 TYPES INTERVALLE
On constate souvent qu'une variable doit prendre ses valeurs dans un intervalle de valeurs bien déterminé.
Ceci peut être exprimé en écrivant que la variable est d'un type intervalle comme:
Type T = [min .. max];
dans lequel min et max sont des expressions qui spécifient les limites de l'intervalle. Notez que ces
expressions n'admettent comme opérandes que des constantes.
Exemples:
Type an = [1970 .. 2010];
Type lettre = ["A" .. "Z"];
Type indice = [0 .. 2* N-1];
Etant donné les variables
Var Y : an;
Var L : lettre;
46
les affectations Y := 2000 et L := "K" sont correctes, alors que Y := 1291 et L := "9" ne le sont pas. Mais
la légalité d'une affectation ne peut être vérifiée sans exécution du programme que si la valeur affectée est
une constante. Lorsqu'on a des affectations comme Y := N et L := C, dans lesquelles N est du type
INTEGER et C du type CHAR, on ne peut rien déduire du texte du programme. Il faut alors réaliser les
vérifications à l'exécution, ce que font certains systèmes qui utilisent la redondance de l'information pour
détecter d'éventuelles erreurs. Comme nous l'avons vu, ceci est une des principales raisons de l'utilisation
des langages de haut-niveau.
3.6 LA STRUCTURE DE TABLEAU
Le tableau (array) est probablement la structure de données la mieux connue; dans certains langages c'est
même la seule disponible. Un tableau est formé de composants qui sont tous du même type: son type de
base; c'est donc une structure homogène. Le tableau est aussi une structure dite à accès aléatoire: à un
instant donné, on peut sélectionner n'importe quel composant. Pour désigner un composant, on ajoute au
nom de la structure ce qu'on appelle un indice, qui doit être une valeur du type défini comme le type
d'indice du tableau. La définition d'un type de tableau T spécifie donc à la fois un type de base T0 et un
type d'indice TI.
Type T = array [TI] of T0;
Exemples:
Type Ligne = array [1 .. 5] of REAL;
Type Carte = array [1 .. 80] of CHAR;
Type Alfa = array [0 .. 15] of CHAR;
Une valeur particulière de la variable
Var X: Ligne;
dont tous les composants satisfont l'équation Xi =2-i est donnée en figure 3.1.
0.5 0.25 0.125 0.0625 0.03125
Figure 3.1 : Tableau de type Ligne.
On sélectionne un composant individuel d'un tableau à l'aide d'un indice. Etant donné une variable tableau
X, on note un sélecteur de tableau en faisant suivre le nom du tableau par l'indice i du composant: X[i].
47
La façon la plus pratique de travailler sur des tableaux, et surtout sur des grands tableaux, est de modifier
sélectivement certains composants et non de construire des valeurs structurées complètement nouvelles.
On peut mieux exprimer ceci en considérant une variable tableau comme un tableau de variables et en
autorisant des affectations à des composants sélectionnés, comme X[i] := 0.125. Même si une mise à jour
sélective ne modifie la valeur que d'un seul composant, d'un point de vue conceptuel, on doit considérer
que la valeur composite toute entière a été modifiée.
Le fait que les indices de tableau, c'est-à-dire les noms des composants du tableau, doivent être d'un type
(scalaire) défini a une conséquence très importante: on peut calculer des indices. Il est possible de
substituer à un indice de valeur constante une expression générale d'indice, le résultat de l'évaluation de
cette expression permettant d'identifier le composant sélectionné. Cette généralité risque de provoquer
une des erreurs de programmation les plus fréquentes: l'indice ainsi calculé peut être extérieur à l'intervalle
des valeurs du type d'indice du tableau.
Le cardinal d'un type structuré, c'est-à-dire le nombre de valeurs de ce type, est le produit des cardinaux
de ses composants. Puisque tous les composants d'un type tableau T sont du même type de base T0, nous
obtenons, avec un type d'index TI, card (T) = card (T0)card(TI).
Les constituants de types tableau peuvent être eux-mêmes structurés. Une variable tableau dont les
composants sont des tableaux est appelée une matrice. C'est ainsi que
Var M : array [1 .. 10] of Ligne;
est un tableau de dix composants (lignes), chacun composé de cinq valeurs de type REAL; c'est donc une
matrice 10 x 5 de composants réels. On peut concaténer les sélecteurs, de sorte que M[i][j] désigne le
jème composant de la ligne M[i], qui est le ième composant de M. On abrège souvent cette notation en
M[i, j], et dans le même esprit la déclaration
Var M : array [l..10] of array [l..51 of REAL;
peut s'écrire de façon plus concise
Var M : array [l .. 10, 1 .. 5] of REAL;
Si l'on doit exécuter la même opération sur tous les composants d'un tableau ou sur plusieurs composants
consécutifs, on peut le souligner en utilisant l'instruction for, comme le montre l'exemple suivant dans
lequel on calcule d'abord la somme des éléments d'un tableau pour rechercher ensuite l'élément maximum
de ce tableau déclaré comme:
48
Var A : array [0 .. N - 1] of INTEGER;
begin
SOMME := 0;
for i := 0 to N-1 do SOMME := A [i] + SOMME;
K := 0;
MAX := A [0];
for i := 1 to N-1 do
if MAX < A [i] then begin K := i;
MAX := A [K];
end;
end.
Remarque: en PASCAL, un programme commence avec les définitions de types suivies des déclarations
de variables, suivies du corps de programme encadré par les mots begin et end. On note la fin du
programme avec un point (.) derrière le dernier end.
3.7 LA STRUCTURE DE RECORD
La façon la plus générale d'obtenir des types structurés est de juxtaposer des éléments de types arbitraires,
qui peuvent eux-mêmes être structurés. En mathématiques, par exemple, les nombres complexes sont
composés de 2 nombres réels, tandis que les coordonnées d'un point sont formées de deux nombres ou
plus, suivant le nombre de dimensions de l'espace considéré. En informatique, on doit souvent décrire un
individu à l'aide de certaines caractéristiques comme son nom, son prénom, sa date de naissance, …
En mathématiques, on dit d'un type composé qu'il est le produit cartésien des types de ses composants;
ceci provient du fait que l'ensemble des valeurs définies par ce type composé est formé de toutes les
combinaisons possibles des valeurs prises dans chacun des ensembles définis par chaque constituant. Le
nombre de ces combinaisons est le produit du nombre des éléments de chaque ensemble constituant, le
cardinal du type composé est donc le produit des cardinaux des types constituants.
En informatique, les types composés, comme ceux correspondant à la description de personnes ou d'objets,
se trouvent souvent dans les fichiers ou les banques de données et permettent d'enregistrer les
caractéristiques d'une personne ou d'un objet. C'est pourquoi le terme anglais record (enregistrement) s'est
imposé plutôt que produit cartésien. En général, un type record T dont les composants sont des types TI,
T2,.... Tn est défini par:
49
Type T = record
s1 : T1;
s2 : T2;
...
sn : Tn;
end;
card (T) = card (T1) * card (T2) * card (…) * card (Tn)
Exemples:
Type Complexe = record
re : REAL;
im: REAL;
end;
Type Date = record
jour : [1 .. 31];
mois : [1 .. 12];
an : [1950 .. 2050];
end;
Type Individu = record
nom, prénom : Alfa;
naissance : Date;
sexe : (homme, femme);
statutmar : (célibataire, marié, veuf);
end;
On peut alors définir, par exemple, les variables:
Var Z : Complexe;
D : Date;
P : Individu;
Les identificateurs s1, s2, ..., sn introduits dans la définition du type record sont les noms que l'on donne
aux composants individuels des variables de ce type. Comme les composants des records s'appellent des
champs, ces noms sont appelés identificateurs de champs. On les utilise dans les sélecteurs de records
appliqués aux variables structurées en records. Etant donné une variable X : T, son ième champ est noté
X.si. La modification sélective de X est réalisée en utilisant la même notation de sélecteur pour la partie
gauche d'une affectation: X.si := e;
50
dans laquelle e est une valeur (une expression) de type Ti. Si l'on a, par exemple, les variables records Z,
D et P déclarées ci-dessus, voici quelques sélecteurs de composants :
Z.im (de type REAL)
D.mois (de type [l .. 12])
P.nom (de type Alfa)
P.naissance (de type Date)
P.naissance. jour (de type [l .. 31])
L'exemple du type Individu montre qu'un composant de record peut être lui-même structuré. On peut donc
concaténer les sélecteurs. On peut aussi utiliser une imbrication de types structurés suivant différentes
méthodes. Par exemple le ième composant d'un tableau A, composant d'une variable record R est noté
R.A[i], et le composant de nom de sélecteur S du ième composant (à structure de record) du tableau A est
noté A[i].S
C'est une des caractéristiques du produit cartésien que de contenir toutes les combinaisons des éléments
des types constituants. En pratique, certaines de ces combinaisons n'ont aucun sens. C'est ainsi que le type
date comprend aussi bien le 31 avril que le 29 février 2015, deux dates qui n'existent pas.
Le programme suivant indique l'utilisation qu'on peut faire de variables de type record. On compte le
nombre de personnes représentées dans le tableau FAMILLE qui sont à la fois femme et célibataire:
Var COMPTEUR : WORD;
FAMILLE : array [1 .. N] of Individu;
begin
COMPTEUR := 0;
for i := 1 to N do
if (FAMILLE [i].sexe = femme) AND (FAMILLE [i].statutmar = célibataire) then
COMPTEUR := COMPTEUR + 1;
end.
La structure de record et la structure de tableau sont toutes les deux à accès aléatoire. Le record est plus
général puisqu'il n'implique pas que tous les types des composants soient identiques, mais le tableau est
plus souple puisque les sélecteurs de composants peuvent être des valeurs calculées, alors que les
sélecteurs des composants de record sont les identificateurs de champ.
51
3.8 LA STRUCTURE DE SUITE
La quatrième méthode élémentaire de structuration est la suite. Un type suite pourrait être déclaré par:
Type T = SEQUENCE of T0;
En PASCAL, on remplace le mot SEQUENCE par file. La forme de cette expression montre que tous les
éléments de la suite sont de même type, le type de base T0 de la suite. Nous noterons une suite S de n
éléments: S = < s0, s1, ..., sn > n étant la longueur de la suite. Cette structure paraît proche du tableau.
La différence réside dans ce que le nombre d'éléments d'un tableau est fixé lors de sa déclaration, alors
que le nombre d'éléments d'une suite est quelconque et peut varier pendant l'exécution du programme.
Bien que chaque suite ait, à tout instant, une longueur fixe et déterminée, on doit considérer que le cardinal
du type suite est infini puisqu'il n'y a pas de limite fixée à la longueur des variables de type suite. Une
conséquence de ce cardinal infini est qu'il est impossible d'allouer une quantité de mémoire donnée à ces
variables. Le stockage devra être géré pendant l'exécution du programme, au fur et à mesure que la suite
grandit, en récupérant éventuellement de l'espace mémoire lorsque la suite diminue. En tout cas, on doit
utiliser un schéma d'allocation dynamique de mémoire.
La contrainte que nous avons mentionnée consiste à n'utiliser que l'accès séquentiel. Le parcours d'une
suite se fait en passant d'un élément à son successeur immédiat, et une suite est engendrée en ajoutant
répétitivement un élément à la fin. Conséquence immédiate de cet accès séquentiel: il n'est pas possible
d'accéder directement à un élément sauf si c'est celui qui est prêt à être examiné. C'est cette discipline
d'accès qui distingue fondamentalement les suites des tableaux. Si la restriction est sérieuse, les avantages
sont grands: simplicité de la gestion de la mémoire, mais surtout possibilité d'utiliser des tampons
lorsqu'on fait passer des données de ou vers la mémoire secondaire. L'accès séquentiel nous permet
d'alimenter un flot de données dans un tube, appelé tampon (buffer), placé entre les deux différents médias
puis envoyer le contenu de ce tampon lorsqu'il est plein. Ceci permet une utilisation bien plus efficace de
la mémoire secondaire. Si l'on n'utilise que l'accès séquentiel, le tampon convient pour toutes les suites et
tous les médias. Il peut donc être construit au niveau du système pour un usage général et le programmeur
n'a pas besoin de l'incorporer dans son programme. Un tel système est souvent appelé système de fichiers
parce qu'en raison de la masse de données, les unités à accès séquentiel sont généralement utilisées pour
un stockage permanent et qu'elles conservent donc les données même lorsque l'ordinateur est éteint.
Nous résumerons ce qui précède de la manière suivante: les tableaux, les records et les ensembles sont
des structures à accès aléatoire. On les stocke dans la mémoire principale, à accès aléatoire. Les suites
sont utilisées dans les accès séquentiels à la mémoire secondaire (disques).
52
La discipline de l'accès séquentiel est renforcée par le biais d'opérateurs dont l'utilisation est obligatoire
pour accéder aux variables de type suite. Ainsi, bien que nous puissions nous référer ici au jème élément
d'une suite en écrivant sj, ce ne sera pas possible dans un programme. L'ensemble des opérateurs doit
comporter au moins un opérateur pour engendrer la suite et un autre pour l'inspecter. Une suite étant
engendrée en ajoutant des éléments à la fin et inspectée en passant à l'élément suivant, il y a donc toujours
une certaine position qui est associée à chaque suite. Voyons un ensemble d'opérateurs de base:
1) Rewrite (S) définit S comme étant la suite vide, donc la suite de longueur 0.
2) Write (S, X) ajoute un élément de valeur X à la suite S.
3) Reset (S) place la position courante au début de S.
4) Read (S, X) affecte l'élément désigné à la variable X et avance la position à l'élément suivant.
Etant donné cet ensemble d'opérateurs sur les suites, on peut faire apparaître les schémas de programmes
suivants pour l'écriture et la lecture d'un fichier séquentiel S:
Type FICHIER = file of REAL;
Var S: FICHIER;
X: REAL;
begin
Rewrite (S);
while B do
begin
P (X);
Write (S, X);
end;
Reset (S);
while not eof (S) do
begin
Read (S, X);
Q (X);
end;
end.
B est la condition qui doit être vérifiée avant que l'instruction P de calcul du prochain élément et celle de
l'ajout de cet élément en fin de fichier soient exécutées. A la lecture, Q est l'instruction que l'on applique
à chaque élément de la suite. La condition ;not eof (S) garantit qu'il y a un prochain élément à lire dans S.
53
CHAPITRE 4 : STRUCTURES DE DONNÉES DYNAMIQUES
4.1 TYPES DE DONNEES RECURSIFS
Au chapitre 3, nous avons introduit les structures de données fondamentales que sont le tableau et le
record. On dit qu'elles sont fondamentales car elles constituent les briques de base avec lesquelles on
formera des structures plus complexes et aussi parce qu'elles sont les plus fréquentes en pratique. Le but
de la définition d'un type de données et de son utilisation pour spécifier le type de variables par la suite,
est de fixer une fois pour toutes le domaine des valeurs possibles que peuvent prendre ces variables et par
conséquent leur format en mémoire. Des variables déclarées de cette façon sont dites statiques. Il existe
toutefois de nombreux problèmes qui impliquent l'usage de structures de données bien plus complexes.
Une des caractéristiques de cette classe de problèmes est que non seulement les valeurs, mais aussi les
structures des variables changent pendant le calcul. Elles sont par conséquent dites dynamiques. Bien
entendu, les composants de telles structures sont - à un niveau de résolution donné - statiques, c'est-à-dire
d'un des types de données fondamentaux. Le présent chapitre est consacré à la construction, l'analyse et
la gestion des structures de données dynamiques.
Il est intéressant de noter qu'il existe des analogies entre les méthodes utilisées pour structurer les
algorithmes et celles utilisées pour structurer les données. Comme dans toute analogie, il y a certes des
différences, mais une comparaison entre les méthodes de structuration des programmes et de structuration
des données reste néanmoins instructive. L'instruction élémentaire, non structurée, est l'affectation de la
valeur d'une expression à une variable. L'entité correspondante dans la famille des structures de données
est le type scalaire, non structuré. Tous les deux constituent les briques de base, l'un pour les instructions
structurées, l'autre pour des types de données composites. Les structures les plus simples, obtenues par
énumération ou juxtaposition, sont l'instruction composée et la structure de record. Toutes les deux sont
formées d'un nombre fini (et habituellement petit) de composants explicitement énumérés, qui peuvent
être de natures différentes les uns des autres. Si tous les composants étaient identiques, il ne serait pas
nécessaire de les écrire chacun individuellement: on utiliserait l'instruction for ou la structure de tableau
pour indiquer la répétition en un nombre de fois connu et fini. Un choix parmi deux ou plusieurs
composants est exprimé respectivement par l'instruction conditionnelle if (ou son extension, l'instruction
case), et par la structure de record avec variante présentée ci-après. Enfin une répétition en un nombre de
fois initialement inconnu (et potentiellement infini) est exprimé par l'instruction while ou repeat. La
structure de données correspondante est la suite ou fichier, qui est la forme la plus simple qui permette de
construire des types de cardinalité infinie.
54
On peut se demander s'il existe une structure de données qui corresponde de cette manière à l'instruction
d'appel de module (procedure). La plus intéressante et la plus novatrice des propriétés de la procédure
est naturellement la récursivité. Des valeurs de tels types de données récursifs contiendraient un ou
plusieurs composants appartenant au même type que lui-même, de la même manière qu'une procédure
récursive contient un ou plusieurs appels à elle-même. Tout comme les procédures, les définitions de ces
types de données pourraient être directement ou indirectement récursifs.
Un exemple simple d'un objet bien représenté par un type de données défini récursivement est l'expression
arithmétique, telle qu'on la rencontre dans les langages de programmation. La récursivité est utilisée pour
indiquer la possibilité d'imbrication, c'est-à-dire l'utilisation des sous-expressions entre parenthèses
comme opérandes des expressions. On peut définir une expression de manière informelle de la façon
suivante:
Une expression consiste en un terme, suivi par un opérateur, suivi par un terme. (Les deux termes
constituent les opérandes de l'opérateur.) Un terme est soit une variable - représentée par un
identificateur - soit une expression entre parenthèses.
Un type de données dont les valeurs représenteraient de telles expressions peut être décrit aisément avec
les outils dont nous disposons déjà, en leur ajoutant la récursivité:
Type expression = record op : opérateur;
opd1, opd2: terme;
end;
Type terme = record (4.1)
case T : BOOLEAN of
TRUE : (id: Alfa);
FALSE : (subex : expression);
end;
Toute variable du type terme consiste donc en deux composants: le sélecteur de champ T et, si T est vrai,
le champ id, sinon le champ subex qui est lui-même une expression. Un rôle important de la partie variante
devient évident: c'est le seul moyen par lequel on peut limiter la structure de donnée récursive, et c'est
donc le compagnon indispensable de toute définition récursive. L'analogie entre les concepts de
structuration de programme et de structuration de données est très forte dans ce cas; il doit nécessairement
y avoir une instruction conditionnelle ou sélective dans toute procédure récursive afin de pouvoir terminer
l'exécution de la procédure. Et la fin de l'exécution correspond évidemment à une cardinalité finie.
55
4.2 POINTEURS
La propriété caractéristique des structures récursives qui les distingue nettement des structures
fondamentales (tableaux, records, ensembles) est leur faculté de varier de taille. Il est donc impossible
d'affecter une quantité fixe de mémoire à une structure définie récursivement, et par conséquent, il est
impossible à un compilateur d'associer une adresse spécifique aux composants de telles variables. La
technique la plus utilisée pour résoudre ce problème met en œuvre l'allocation dynamique de mémoire,
c'est-à-dire l'allocation de mémoire individuellement à chaque composant au moment où il commence à
exister lors de l'exécution du programme, plutôt qu'au moment de sa traduction. Le compilateur n'alloue
qu'une quantité fixe de mémoire, juste assez pour contenir l'adresse du composant dynamiquement alloué,
à la place du composant lui-même. Par exemple, un arbre généalogique peut être représenté par des records
isolés - et peut-être non contigus -, un par personne. Ces personnes sont alors reliées par leurs adresses
affectées respectivement aux champs associés à père et mère. Graphiquement, cette situation s'exprime le
mieux au moyen de flèches ou de pointeurs (figure 4.1)
Figure 4.1: Structures reliées par des pointeurs
Pour mettre en œuvre cette possibilité, de nombreux langages de programmation ont introduit un type de
variable appelé pointeur dont le nom signifie que l'on fait référence au composant et non à la valeur du
composant.
Insistons bien sur le fait que l'usage de pointeurs n'est qu'une technique utilisée pour réaliser des structures
de données récursives. Le programmeur n'a nullement besoin d'être conscient de leur existence. La
mémoire pourrait être allouée automatiquement lors de la première référence à un nouveau composant.
Toutefois, si la technique d'utilisation de références ou de pointeurs est rendue explicite, elle ouvre la
porte à la définition de structures de données plus générales encore que celles que l'on peut obtenir par
des définitions récursives. Il est possible en particulier de définir des structures circulaires ou
56
potentiellement infinies, ainsi que d'imposer le partage de certaines structures. Il est donc devenu courant
dans les langages de programmation avancés d'offrir la possibilité de manipuler explicitement des
références aux données en plus des données elles-mêmes. Ceci impose qu'il y ait une nette distinction de
notation entre les données et les références aux données, et donc qu'on introduise des types de données
dont les valeurs soient des pointeurs (références) vers d'autres données. La notation que nous utiliserons
pour ce faire est la suivante:
Type T = ^ T0; (4.2)
La déclaration de type (4.2) exprime le fait que les valeurs du type T sont des pointeurs vers des données
du type T0. Il est extrêmement important que le type des éléments pointés ressorte clairement de la
définition de T. Nous dirons que T est lié à T0. Ce lien distingue les pointeurs des langages de haut-niveau
des adresses des langages machine et, en accroissant la redondance de la notation, joue un point important
dans la sécurité des programmes.
Les valeurs des types pointeurs sont générées chaque fois qu'un élément de donnée est alloué
dynamiquement. Nous prendrons comme convention qu'une telle circonstance est toujours explicitement
mentionnée, ceci en opposition à la technique où l'élément est alloué la première fois qu'on y fait référence.
Pour ce faire, nous introduisons une procédure new. Etant donnée une variable pointeur P de type T,
l'instruction new (P) alloue effectivement une variable de type T0 et affecte le pointeur désignant cette
variable à P (voir Figure 4.2). On fait référence à la valeur pointeur elle-même par P (c'est-à-dire comme
valeur de la variable pointeur P). Par contre, la variable à laquelle P fait référence est désignée par P^.
P : ^ T
P^ : T
Figure 4.2: Allocation de variable dynamique
Nous avons mentionné plus haut qu'il est essentiel que tout type récursif comporte un composant sous
variante de façon à garantir une cardinalité finie. Ceci s'exprime par le schéma de déclaration (4.3).
Type T = record (4.3)
case TERMINAL : BOOLEAN of
FALSE : (S (T));
TRUE : ; {vide}
end;
57
S (T) désigne une suite de définitions de champs qui contient un ou plusieurs champs de type T, assurant
ainsi la récursivité. Toutes les structures d'un type basé sur ce modèle ont une structure d'arbre ou de liste.
Une de leurs propriétés est de contenir des pointeurs vers des composants qui ne contiennent que le
sélecteur de champ, c'est-à-dire sans aucune autre information utile. La technique de réalisation au moyen
de pointeurs suggère une manière aisée d'économiser de l'espace mémoire en incluant l'information portée
par le sélecteur dans la valeur de type pointeur elle-même. La solution la plus commode est d'étendre le
domaine des valeurs de tous les types pointeurs par une valeur unique qui ne pointe sur aucun élément.
Nous désignerons cette valeur par le symbole spécial nil, et nous supposerons acquis que nil fait
automatiquement partie de tout type pointeur déclaré.
La nouvelle formulation du type de données (4.1), basée sur des pointeurs explicites, est donnée en (4.4)
Type termePtr = ^ terme; (4.4)
Type expPtr = ^ expression;
Type expression = record op : opérateur;
opdl, opd2 : termePtr;
end;
Type terme = record
case T : BOOLEAN of
TRUE : (id : Alfa);
FALSE : (subex: expPtr);
end
La section suivante est consacrée à la génération et à la manipulation d'une structure de données dont les
composants sont reliés par des pointeurs explicites: la liste linéaire (ou suite chaînée). On pourra en dériver
des règles pour la manipulation de structures plus complexes que nous aborderons dans le chapitre suivant.
4.3 LISTES LINEAIRES
La façon la plus simple de relier un ensemble d'éléments entre eux est de les aligner pour former une liste.
Dans ce cas, il n'est besoin que d'un seul lien dans chaque élément pour désigner son successeur.
Supposons que les types Nœud et Ptr soient définis comme montré en (4.5). Toute variable de ce type est
constituée de trois éléments, à savoir une clé d'identification, un pointeur vers le successeur, et
éventuellement des informations associées, omises en (4.5).
58
Type Ptr = ^ Noeud; (4.5)
Type Noeud = record cle : INTEGER;
suivant : Ptr;
info : ...;
end
Var P, Q : Ptr;
La figure 4.3 montre une liste de nœuds, avec un pointeur vers son premier élément affecté à une variable
P. L'opération la plus simple que l'on puisse effectuer sur une liste comme celle-ci est d'insérer un élément
en tête. Il faut tout d'abord allouer un élément de type Nœud, sa référence (ou pointeur) étant
temporairement affectée à une variable pointeur auxiliaire Q. Puis une simple réaffectation des pointeurs
termine l'opération, dont le programme est donné en (4.6). Notez que l'ordre de ces trois instructions est
absolument essentiel.
new (Q); (4.6)
Q^.suivant := P;
P := Q;
Figure 4.3: Exemple de liste
L'opération d'insertion d'un élément en tête de liste suggère immédiatement le moyen de générer une telle
liste: en partant d'une liste vide, on ajoute répétitivement un élément en tête. Ce processus de génération
de liste est exprimé en (4.7); ici le nombre d'éléments à relier est N.
P := nil; {liste vide au début} (4.7)
while N > 0 do
begin
new (Q);
Q^.suivant := P;
P := Q;
Q^.cle := N;
N := N - 1;
end;
59
Ceci est la manière la plus simple de former une liste. Toutefois l'ordre des éléments qui en résulte est
l'ordre inverse de leur insertion. Dans certaines applications, ceci n'est pas souhaitable et il est par
conséquent nécessaire de savoir ajouter des éléments à la queue de la liste plutôt qu'en tête. Quoiqu'on
pourrait facilement trouver la queue de la liste en la parcourant, cette façon de faire naïve impose un effort
qu'on peut s'épargner en utilisant un second pointeur, QUEUE, par exemple, qui désigne en permanence
le dernier élément. Elle a toutefois pour inconvénient que le premier élément à insérer doit être traité
différemment des autres.
L'accès explicite aux pointeurs rend certaines opérations assez simples, qui eussent été fort compliquées
autrement; parmi ces opérations portant sur une liste, on trouve les opérations d'insertion et de suppression
(ou de mise à jour sélective d'une liste), et bien sûr l'opération de parcours d'une liste.
Etudions pour commencer l'insertion dans une liste. Supposons qu'un élément désigné par une variable
pointeur Q soit à insérer dans une liste après l'élément désigné par le pointeur P. Les réaffectations de
pointeurs sont données en (4.8) et leur effet visualisé sur la figure 4.4.
Q^.suivant := P^.suivant;
P^.suivant := Q; (4.8)
Figure 4.4: Insertion en liste après P^
Si l'insertion doit avoir lieu avant l'élément désigné par P plutôt qu'après, la nature unidirectionnelle de la
chaîne de liens semble poser problème, car elle n'offre pas de moyen d'accéder au prédécesseur d'un
élément. Cependant il existe une astuce simple qui permet de s'en sortir: elle est donnée en (4.9) et illustrée
par la figure 4.5. Supposons que la clé du nouvel élément soit 8.
new (Q);
Q^ := P^; (4.9)
P^.cle := 8;
P^.suivant := Q;
60
L'astuce consiste bien évidemment à insérer le nouvel élément après P^ et à échanger ensuite les valeurs
du nouvel élément et de P^.
Figure 4.5: Insertion en liste avant P^
Considérons ensuite le processus de suppression dans une liste. Supprimer le successeur de P^ est évident.
En (4.10), on montre ceci combiné à la réinsertion de l'élément supprimé en tête d'une autre liste (désignée
par Q). La figure 4.6 illustre l'effet des instructions (4.10) et montre qu'il s'agit d'un échange cyclique de
trois pointeurs.
R := P^.suivant;
P^.suivant := R^.suivant; (4.10)
R^.suivant := Q;
Q := R;
L'élimination de l'élément désigné lui-même (plutôt que de son successeur) est plus difficile, car nous
sommes à nouveau confronté au problème rencontré lors de l'insertion: revenir au prédécesseur de
l'élément désigné est impossible. Mais supprimer le successeur après avoir déplacé sa valeur vers l'avant
est une solution simple et assez immédiate. Elle ne s'applique toutefois que lorsqu'il a un successeur, c'est-
à-dire lorsqu'il n'est pas le dernier élément de la liste.
Figure 4.6: Effacement et réinsertion en liste
61
Nous allons maintenant nous occuper de l'opération fondamentale de parcours d'une liste. Supposons qu'il
faille appliquer une opération OP à chaque élément d'une liste dont le premier élément est P^. On peut
exprimer cette tâche de la façon suivante:
while la liste désignée par P n'est pas vide do
begin
effectuer l'opération OP;
passer au successeur;
end;
Cette opération est décrite en détail par l'instruction (4.11).
while P <> nil do (4.11)
begin
OP (P^);
P := P^.suivant;
end;
Il découle des définitions de l'instruction while et de la structure du chaînage que OP sera appliqué à tous
les éléments de la liste et à aucun autre.
Une opération très fréquemment effectuée sur une liste est la recherche dans la liste d'un élément d'une
clé donnée X. A la différence d'un tableau, la recherche ne peut être ici que purement séquentielle. La
recherche se termine soit lorsqu'un élément est trouvé, soit lorsqu'on atteint la fin de la liste. Ceci est
reflété par la conjonction logique de deux termes. Nous supposerons à nouveau que la tête de la liste est
désignée par un pointeur P.
while (P <> nil) AND (P^.cle <> X) do
P := P^.suivant;
P = nil implique que P^ n'existe pas et que par conséquent l'expression P^.cle <> X est indéfinie. L'ordre
des deux termes est donc essentiel.
62
CHAPITRE 5 : STRUCTURES DE DONNEES ELABOREES
Dans ce chapitre, nous passons en revue les structures de données élaborées, à savoir les listes, les piles,
les files ainsi que les arbres binaires et les arbres binaires de recherche. Nous décrivons ensuite les files
de priorité et leur implémentation au moyen de tas.
5.1 TYPE ABSTRAIT ET STRUCTURE DE DONNEES
Une structure de données est l’implémentation explicite d’un ensemble organisé d’objets, avec la
réalisation des opérations d’accès, de construction et de modification afférentes. Un type de données
abstrait est la description d’un ensemble organisé d’objets et des opérations de manipulation sur cet
ensemble. Ces opérations comprennent les moyens d’accéder aux éléments de l’ensemble, et aussi,
lorsque l’objet est dynamique, les possibilités de le modifier. Plus formellement, on peut donner une
définition mathématique d’un type abstrait: c’est une structure algébrique, formée d’un ou de plusieurs
ensembles, munis d’opérations vérifiant un ensemble d’axiomes.
Avec ces définitions, une structure de données est la réalisation, l’implémentation explicite d’un type de
données. Décrire un type de données, le spécifier comme on dit, c’est décrire les opérations possibles et
licites, et leur effet. Décrire une structure de données, c’est expliciter comment les objets sont représentés
et comment les opérations sont implémentées. Pour l’évaluation d’algorithmes, il importe de plus de
connaître leur coût en temps et en place.
Du point de vue des opérations, un type abstrait est à un type de base d’un langage de programmation ce
que l’en-tête de procédure est à un opérateur. La procédure réalise une opération qui n’est pas élémentaire
au sens du langage de programmation; de la même manière, un type de données abstrait propose une
organisation qui n’est pas offerte par le langage. Une réalisation du type abstrait, c’est-à-dire une
implémentation par une structure de données, correspond alors à l’écriture du corps d’une procédure.
Le concept de type abstrait ne dépend pas du langage de programmation considéré, et on peut se livrer à
l’exercice (un peu stérile) de définir abstraitement les booléens, les réels, etc. En revanche, l’éventail des
types concrets varie d’un langage de programmation à un autre. Ainsi, les piles existent dans certains
langages de programmation, les tableaux ou les chaînes de caractères dans d’autres.
On peut également considérer un type abstrait comme une boîte noire qui réalise certaines opérations
selon des conventions explicites. Cette vision correspond à un style de programmation que l’on pourrait
63
appeler la programmation disciplinée. Le programmeur convient d’accéder à la réalisation d’un type de
données uniquement à travers un ensemble limité de procédures et de fonctions, et s’interdit notamment
tout accès direct à la structure qui serait rendue possible par une connaissance précise de l’implémentation
particulière. De nombreux langages de programmation facilitent ce comportement par la possibilité de
créer des modules ou unités séparés. Lorsqu’un type de données est implémenté, on peut se servir de ses
opérations comme opérations élémentaires, et en particulier les utiliser dans l’implémentation de types de
données plus complexes. Ceci conduit à une hiérarchie de types, où l’on trouve, tout en bas de l’échelle,
des types élémentaires comme les booléens, entiers, réels, tableaux, à un deuxième niveau les piles, files,
listes, arbres, puis les files de priorités, dictionnaires, graphes.
La réalisation efficace de types de données par des structures de données qui implémentent les opérations
de manière optimale en temps et en place constitue l’une des préoccupations de l’algorithmique. Le temps
requis par une opération de manipulation d’un type s’exprime en fonction du temps requis par les
opérations intervenant dans sa réalisation. Ces opérations elles-mêmes sont peut-être complexes, et
implémentées dans une autre structure de données. En descendant la hiérarchie, on arrive à des opérations
élémentaires (opérations arithmétiques ou tests sur des types élémentaires, affectation de scalaires) dont
le temps d’exécution est considéré, par convention, comme constant, et ceci quel que soit le langage de
programmation utilisé.
Pour les types de données abstraits les plus simples, plusieurs réalisations efficaces sont faciles à obtenir
et à décrire. Il en est ainsi des piles, des files, des listes, et dans une moindre mesure des dictionnaires et
des files de priorités, qui sont des ensembles munis de fonctions d’accès spécifiques. La réalisation
d’arbres ayant de bons comportements requiert en revanche un soin certain.
5.2 STRUCTURES LINEAIRES
Les structures linéaires tirent leur nom du fait que les données y sont organisées sous forme d‘une liste
dans laquelle elles sont mises les unes derrière les autres. On peut représenter une telle liste à l‘aide d‘un
tableau unidimensionnel ou sous la forme d‘une liste chaînée. Selon la nature des opérations autorisées,
on obtient différents types de listes, en particulier les piles et les files.
5.2.1 Listes
Une liste linéaire sur un ensemble E est une suite finie (e1, ..., en) d’éléments de E. Les éléments de la
suite sont soit accessibles directement, par leur indice, soit indirectement, quand la liste est représentée
64
par une suite d’objets chaînés. Dans les implémentations, un indice est représenté par une place, et on
accède à l’élément de E qui figure à cette place par une fonction particulière appelée contenu (ou parfois
clé). Cette représentation sépare proprement la position d’un élément dans la liste de l’élément lui-même.
De plus, elle permet de définir, sur une place, d’autres fonctions, comme la fonction successeur qui donne
la place suivante.
Une liste est une liste linéaire où les insertions et suppressions se font non seulement aux extrémités, mais
aussi à l’intérieur de la liste. Les listes constituent un type de données très souple et efficace. Ainsi, on
peut parcourir des listes (on ne parcourt ni les files ni les piles) sans les détruire, on peut rechercher un
élément donné, on peut concaténer des listes, les scinder, etc. La distinction entre les places et leur contenu
est importante. Une place est propre à une liste, c’est-à-dire ne peut pas être partagée entre plusieurs listes;
en revanche, un élément peut figurer dans plusieurs listes, ou plusieurs fois dans une même liste.
Une liste peut contenir zéro, un ou plusieurs éléments. La longueur d‘une liste est son nombre d‘éléments.
Une liste vide est une liste de longueur nulle. La tête de la liste est son premier élément. La définition de
la queue d‘une liste n‘est pas universelle; certains la définissent comme étant le dernier élément de la liste
et d‘autres comme la liste obtenue en enlevant la tête.
On s‘intéresse souvent à des listes d‘éléments (entiers, chaînes de caractères, objets identifiés par un
entier…) appartenant à un ensemble sur lequel existe une relation d‘ordre total. C‘est le cas quand on
cherche à trier les éléments de la liste, c'est-à-dire à permuter les éléments de la liste pour qu‘ils deviennent
placés par ordre croissant (ou décroissant).
Opérations sur les listes
Les opérations habituelles sur les listes sont les suivantes.
• Insertion d‘un élément au début, à la fin, ou entre deux éléments de la liste. En particulier, on
pourra chercher à insérer un élément dans une liste triée à une bonne place, c'est-à-dire en conservant le
fait que la liste est triée.
• Suppression d‘un élément quelconque.
• Recherche: cette opération peut renvoyer vrai ou faux selon qu‘un élément donné figure ou non
dans la liste; elle peut aussi renvoyer l‘adresse de l‘élément recherché sous forme, selon les cas, d‘un
indice d‘un tableau ou d‘un pointeur.
• Concaténation de deux listes L1 et L2 contenant des éléments d‘un même type: cette opération
donne la liste obtenue en mettant d‘abord les éléments de L1 puis ceux de L2.
65
Nous commençons par décrire les opérations de base sur les listes, et exprimons ensuite d’autres
opérations à l’aide des opérations de base. Les 5 opérations d’accès sont les suivantes:
Les 4 opérations de construction et de modification sont:
Avec ces 9 opérations primitives, on peut en réaliser d’autres; ainsi, tête(L) = contenu(premier(L), L)
donne le premier élément d’une liste L. En voici d’autres:
Cette fonction s’écrit comme suit:
On programme la fonction chercher de la même manière.
66
Plusieurs implémentations des listes sont possibles; le choix de l’implémentation dépend des opérations
effectivement utilisées. Si seules les opérations de base sont utilisées, on peut employer une
implémentation simple; pour plus de souplesse, on utilisera une implémentation par liste doublement
chaînée. C’est elle qui permet notamment de concaténer deux listes, ou de scinder une liste en temps
constant.
Implémentation d‘une liste par un tableau
On peut représenter une liste par un tableau. L‘indice du début de la liste sera alors fixé (en général, ce
sera l‘indice 0 ou l‘indice 1). Il faudra connaître et actualiser le cas échéant le nombre n d‘éléments de la
liste pour savoir d‘où à où les éléments se trouvent dans le tableau.
Si on veut insérer un nouvel élément dans la liste:
• s‘il s‘agit d‘insérer un élément à sa place dans une liste triée, il faudra décaler tous les éléments
suivants d‘une case, auquel cas la complexité dans le pire des cas est de l‘ordre de la longueur de la liste;
• si l‘ordre des éléments n‘importe pas, on insérera en général l‘élément nouveau à la fin du tableau,
la complexité étant alors de l‘ordre de 1.
Si on veut supprimer un élément de la liste:
• s‘il s‘agit de supprimer un élément d‘une liste triée, il faudra décaler tous les éléments suivants,
d‘où une complexité au pire de l‘ordre de la longueur de la liste;
• si l‘ordre des éléments n‘importe pas, le plus rapide sera de mettre à la place de l‘élément à
supprimer le dernier élément de la liste.
Si maintenant on veut concaténer deux listes L1 et L2, soit on recopie L1 puis L2 dans un nouveau tableau,
soit on recopie les éléments de L2 à la suite de ceux de L1 dans le tableau qui contenait L1; dans les deux
cas, il faut évidemment que les tableaux soient suffisamment grands. La complexité est soit de l‘ordre du
nombre total d‘éléments de L1 et L2, soit de l‘ordre du nombre d‘éléments de L2.
Un inconvénient d‘un tableau, par rapport à la liste chaînée que nous développons ci-dessous, est qu‘il
faut prendre garde à ne pas déborder du tableau. Quand le tableau est plein, il faut soit refuser les
insertions, soit prendre un tableau plus grand et y recopier la liste.
67
Certaines des fonctions sont particulièrement simples à réaliser, comme suivant ou contenu. L’insertion
et la suppression prennent un temps linéaire en fonction de la taille de la liste, puisqu’il faut déplacer toute
la partie de la liste à droite de la position considérée.
Implémentation d‘une liste par une liste chaînée
Une liste chaînée est constituée de "maillons"; les maillons peuvent contenir des données et l‘adresse d‘un
autre maillon. Les données contenues par les maillons sont du même type d‘un maillon à l‘autre. Une liste
chaînée composée des entiers 5, 2 et 7 pourra être représentée comme ci-dessous:
où début est l‘adresse d‘un maillon. Le maillon qui se trouve à l‘adresse début contient l‘élément qui
constitue la tête de la liste. Pour accéder à l‘ensemble des éléments de la liste, on part de l‘adresse début.
On peut alors accéder au premier maillon où on lit l‘adresse contenue dans celui-ci, qui est celle du
deuxième maillon. On accède ainsi au deuxième maillon pour connaître le deuxième élément de la liste
et ainsi de suite. Il est nécessaire qu‘une adresse spéciale soit mise dans le dernier maillon pour qu‘on
puisse savoir que la fin de la liste est atteinte. Cette adresse spéciale est prévue par les langages de
programmation qui permettent de manipuler les listes chaînées; elle s‘appelle en général nil, ou NULL,
ou null; c‘est toujours en quelque sorte l‘adresse qui vaut zéro, notée adresse nulle sur notre schéma.
À condition de connaître certaines adresses appropriées, on constate que l‘insertion, la suppression, la
concaténation se font avec une complexité de l‘ordre de 1. En revanche, nous verrons dans le chapitre
suivant que la recherche d‘un élément dans une liste triée de n éléments peut se faire avec une complexité
de l‘ordre de ln(n) lorsqu‘on utilise un tableau, alors que la complexité est toujours dans le pire des cas et
en moyenne de l‘ordre de n lorsque la liste est codée avec une liste chaînée.
La gestion d‘une liste chaînée se fait généralement en employant une allocation dynamique de mémoire
chaque fois qu‘un nouveau maillon est nécessaire; les adresses sont alors des adresses dans la mémoire
principale de l‘ordinateur. Néanmoins, on peut gérer une structure de liste chaînée avec un tableau de
maillons, les adresses de maillons devenant des indices du tableau; on retrouve alors l‘inconvénient de la
limitation du nombre de données au nombre de cases du tableau. Dans la suite, nous supposerons
implicitement qu‘on utilise une allocation dynamique de mémoire pour chaque nouveau maillon.
L’implémentation par une liste chaînée est plus souple. Elle permet la réalisation de chacune des 9
opérations de base en un temps constant. En revanche, d’autres opérations, comme la concaténation de
deux listes, prennent un temps non constant.
68
Implémentation d‘une liste par une liste doublement chaînée
L’implémentation par une liste doublement chaînée circulaire est la plus souple, et permet aussi la
réalisation efficace d’opérations supplémentaires sur les listes. Détaillons cette structure. Une place est un
pointeur vers un triplet formé de l’élément et de deux pointeurs, l’un vers la place précédente, l’autre vers
la place suivante. La liste est circulaire, de sorte que la première place est la place qui suit la dernière. Une
liste est un pointeur vers le premier élément de la liste de valeur nil quand la liste est vide.
En Pascal, les déclarations de type sont:
où élément est un type défini par ailleurs. Les en-têtes de procédures et fonctions se déclarent comme suit:
Voici l’implémentation des cinq fonctions d’accès:
69
Remarquons que, dans l’implémentation par une liste simplement chaînée, chaque place pointe en fait sur
une liste, à savoir sur le reste de la liste commençant à cette place. Naturellement, la place suivant la
dernière est alors la liste vide, en général représentée par nil. On peut donc parcourir une telle liste par
l’instruction while p = nil do begin I; p:=suivant(p) end.
5.2.2 Piles
Une pile (stack en anglais) est une liste dans laquelle l‘insertion ou la suppression d‘un élément s‘effectue
toujours à partir de la même extrémité de la liste, extrémité appelée le sommet de la pile. L‘action
consistant à ajouter un nouvel élément au sommet de la pile s‘appelle empiler; celle consistant à retirer
l‘élément situé au sommet de la pile s‘appelle dépiler. Une pile permet de modéliser un système régi par
la discipline "dernier arrivé - premier sorti"; on dit souvent qu‘il s‘agit d‘un traitement LIFO (last in, first
out). La hauteur de la pile est son nombre d‘éléments.
Opérations sur une pile
Les fonctions souvent définies dans l‘implémentation d‘une pile sont :
1. répondre à la question: la pile est-elle vide ?
2. éventuellement, selon l‘implémentation, répondre à la question: la pile est-elle pleine ?
3. empiler un élément, en traitant éventuellement le cas où la pile serait pleine (push en anglais),
4. dépiler un élément, en traitant le cas où la pile serait vide (pop en anglais),
5. donner la valeur de l‘élément qui se trouve au sommet de la pile, sans dépiler celui-ci,
6. vider la pile.
Implémentation d‘une pile par un tableau
Si la pile est représentée par un tableau p, on doit gérer une variable pour le sommet de la pile, variable
que nous notons sp. Supposons que les éléments de la pile soient stockés à partir de l‘indice 0 du tableau;
l‘empilement d‘un nouvel élément x consiste alors à introduire x dans la case p(sp) et à remplacer sp par
sp + 1; le dépilement consiste à supprimer l‘élément p(sp - 1) de p puis à remplacer hauteur par sp - 1. La
pile est vide si la variable sp vaut zéro. La pile est pleine si sp est égal à la dimension du tableau.
70
En toute rigueur, un test de débordement est nécessaire dans la procédure empiler, pour éviter de dépasser
les bornes du tableau p.
Implémentation d‘une pile par une liste chaînée
Si la pile est représentée par une liste chaînée, L, (Figure 5.3) à laquelle on accède par un pointeur sommet,
on ajoute un nouvel élément x de la manière suivante. On crée un nouveau maillon M destiné à contenir
x et on y insère x dans le champ de M prévu à cet effet. Dans le champ de M destiné à contenir l‘adresse
du maillon suivant de la liste après insertion de x, on met la valeur du pointeur sommet. Enfin, pour
accéder à la nouvelle liste à l‘aide du pointeur sommet, on attribue à sommet l‘adresse de M. De la même
façon, pour dépiler un élément, on extrait l‘élément contenu dans le premier maillon de L (celui auquel
on accède grâce à sommet) puis on décale sommet en le faisant pointer sur le maillon qui suit le premier
maillon; on peut alors en général libérer l‘espace en mémoire alloué au maillon contenant x.
Figure 5.3: Un pile représentée par une liste chaînée.
La pile est vide si l‘adresse sommet est égale à l‘adresse nulle. La pile n‘est jamais pleine (il faut
néanmoins ne pas dépasser la capacité en mémoire de la machine sur laquelle on travaille, ce qui peut se
produire en particulier si on empile et qu‘on dépile fréquemment et qu‘on oublie de désallouer l‘espace
en mémoire quand on dépile un élément).
La propriété fondamentale d’une pile est que la suppression annule l’effet d’une insertion: si on empile
un élément, puis on dépile, on retrouve la pile dans l’état de départ. Les opérations sur une pile dont les
éléments sont de type élément sont les suivantes:
71
5.2.3 Files
Une file est une liste dans laquelle toutes les insertions de nouveaux éléments s‘effectuent d‘un même
côté de la liste appelé fin et toutes les suppressions d‘éléments s‘effectuent toujours à partir de l‘autre
extrémité, appelée début. L‘action consistant à ajouter un nouvel élément à la fin de la file s‘appelle
enfiler; celle consistant à retirer l‘élément situé au début de la file s‘appelle défiler. Une file permet de
modéliser un système régi par la discipline "premier arrivé - premier sorti" (FIFO : first in, first out).
Opérations sur une file
Implémentation d‘une file par un tableau
Si la file est représentée par un tableau f, on doit gérer deux indices tête et queue indiquant les cases de f
entre lesquelles se trouvent toutes les données; la donnée devant sortir en premier figure dans la case
d‘indice tête, tandis que la première case libre, c'est-à-dire la case dans laquelle on placera la prochaine
donnée enfilée, est d‘indice queue + 1. Enfiler un nouvel élément x consiste donc à introduire x dans la
case f(queue + 1) et à remplacer queue par queue + 1. Défiler un élément consiste d‘autre part à remplacer
tête par tête + 1, après avoir traité l‘élément f(tête). En pratique, la dimension de f est une constante dim:
le nombre d‘éléments présents dans f ne peut donc pas excéder dim. Si d‘autre part le nombre d‘entrées
et de sorties est grand devant dim, on a intérêt à gérer f de manière cyclique pour éviter un débordement:
quand il n‘y a plus de place à la fin du tableau pour ajouter un élément, on recommence à remplir f à partir
de ses premières cases (dans ce cas, queue devient plus petit que tête).
Implémentation d‘une file par une liste chaînée
Il est commode alors de maintenir à jour deux pointeurs, tête et queue, la liste étant chaînée de tête vers
queue. Pour défiler, on décale tête en le faisant pointer sur le maillon qui suit celui sur lequel il pointe,
72
après avoir traité l‘élément du maillon supprimé. Pour enfiler un nouvel élément x, on crée un nouveau
maillon M dans lequel on place x et dans lequel l‘adresse du maillon suivant est l‘adresse nulle. Puis on
ajoute M à la fin de la liste à l‘aide du pointeur queue que l‘on décale pour le faire pointer sur M.
L’implémentation par liste circulaire est plus souple, mais un peu plus complexe (voir figure 5.4). Dans
cette implémentation, une file est repérée par un pointeur sur sa dernière place (si la file est vide, le
pointeur vaut nil). La tête de la file est donc l’élément suivant, et peut être facilement supprimée; de
même, l’insertion en fin de file se fait facilement.
Figure 5.4: Une file circulaire
5.3 ARBRES
5.3.1 Arbres généraux
Un arbre est une structure composée d‘éléments appelés nœuds; il est constitué d‘un nœud particulier
appelé racine et d‘une suite ordonnée éventuellement vide A1, A2, …, Ap d‘arbres appelés sous-arbres
de la racine. Un arbre contient donc au moins un nœud: sa racine.
Exemple: la figure suivante représente l‘arbre d‘une descendance; la racine contient Yolande; il est
constitué de trois sous-arbres (p = 3): A1, de racine Claire, contient Claire et Hortense; A2, de racine Jean,
contient Jean, Élisabeth, Jacques, Lou et Mandé; A3, de racine Colette, est réduit à Colette.
73
Plusieurs définitions sont à retenir; nous illustrons les définitions avec l‘exemple ci-dessus en identifiant
un nœud avec la chaîne de caractères qu‘il contient:
• les fils d‘un nœud sont les racines de ses sous-arbres : les fils de Jean sont Élisabeth et Jacques;
• le père d‘un nœud x autre que la racine est l‘unique nœud dont x est un fils : Jacques est le père de
Lou et de Mandé; la racine d‘un arbre n‘a pas de père;
• un nœud interne est un nœud qui a au moins un fils : Claire est un nœud interne;
• une feuille d‘un arbre est un nœud sans fils : Mandé est une feuille;
• les ancêtres d‘un nœud a sont les nœuds qui sont sur le chemin entre la racine (incluse) et a (inclus);
les ancêtres de a différents de a sont les ancêtres propres de a : les ancêtres de Jacques sont Jacques, Jean
et Yolande;
• les descendants d‘un nœud a sont les nœuds qui appartiennent au sous-arbre de racine a; les
descendants de a différents de a sont les descendants propres de a : les descendants de Jean sont Jean,
Élisabeth, Jacques, Lou et Mandé.
• la profondeur d‘un nœud est la longueur du chemin allant de la racine à ce nœud; la profondeur de
la racine est donc nulle et la profondeur d‘un nœud autre que la racine vaut un de plus que la profondeur
de son père; la profondeur d‘un nœud peut aussi être appelée niveau ou hauteur du nœud : la profondeur
d‘Élisabeth vaut 2;
• la hauteur d‘un arbre est la profondeur maximum de ses nœuds (dans l'exemple: 3).
Pour connaître un arbre, on procède généralement en mémorisant la racine (ou plus précisément son
adresse); il suffit alors que chaque nœud connaisse ses nœuds fils pour pouvoir retrouver tout l‘arbre.
5.3.2 Parcours d‘un arbre général
Parcourir un arbre, c‘est examiner une fois et une seule chacun de ses nœuds, l‘ordre des examens
dépendant d‘une certaine règle. On distingue les deux types suivants. Diverses opérations peuvent être
effectuées quand on examine un nœud (par exemple, lui attribuer un numéro).
Le parcours en préordre
Parcourir un arbre en préordre, c‘est:
• examiner la racine;
• parcourir en préordre le premier sous-arbre;
• …
• parcourir en préordre le dernier sous-arbre. Ce parcours est aussi dit parcours en ordre préfixe.
74
La complexité de ce parcours est du même ordre que le nombre de nœuds de l‘arbre.
Exemple: le parcours en préordre de l‘arbre donné en exemple considère successivement les nœuds
Yolande, Claire, Hortense, Jean, Élisabeth, Jacques, Lou, Mandé, Colette.
Le parcours en postordre
Parcourir un arbre en postordre, c‘est:
• parcourir en postordre le premier sous-arbre;
• …
• parcourir en postordre le dernier sous-arbre;
• examiner la racine.
Ce parcours est aussi dit parcours en ordre postfixe ou suffixe. Le parcours en ordre postfixe a clairement
la même complexité que le parcours en préordre, c'est-à-dire de l‘ordre du nombre de nœuds de l‘arbre.
Exemple: le parcours en postordre de l‘arbre donné en exemple considère successivement les nœuds
Hortense, Claire, Élisabeth, Lou, Mandé, Jacques, Jean, Colette, Yolande.
Remarque: on peut voir les ordres obtenus par les parcours en préordre et en postordre sur l‘ensemble des
nœuds d‘une autre façon en considérant ce qu‘on appelle "un parcours à main gauche" de l‘arbre. On part
de la racine et on suit le tracé de l‘arbre comme l‘indique la figure ci-dessous. On s‘aperçoit que l‘examen
en préordre est obtenu en examinant les nœuds à la première rencontre alors que l‘examen en postordre
est obtenu en examinant les nœuds à la dernière rencontre.
5.3.3 Arbres binaires
Un arbre binaire est soit vide, soit constitué d‘un nœud particulier appelé racine et de deux sous-arbres
binaires disjoints appelés sous-arbre gauche et sous-arbre droit. On notera donc que, formellement, un
arbre binaire n‘est pas un arbre, au sens donné ci-dessus (un arbre n‘est pas vide et n‘utilise pas la notion
de droite et de gauche). Cependant, la forte parenté qui existe entre ces deux concepts fait que l‘on est
75
souvent amené à étendre aux arbres binaires certaines définitions valables en principe seulement pour les
arbres généraux. Ce sera par exemple le cas plus bas pour les parcours en préordre ou en postordre.
La terminologie est la même que celle des arbres généraux; néanmoins, si on considère les fils d‘un nœud,
on parlera, s‘ils existent, du fils gauche et du fils droit. Sur l‘exemple, on remarque que certains nœuds
ont seulement un fils droit ou seulement un fils gauche; par exemple, le nœud e (i.e. contenant la donnée
e) admet uniquement un fils gauche, le nœud i, et pas de fils droit; si on considérait l‘exemple comme un
arbre général, on dirait que e a un seul fils, le nœud i, et le lien entre e et i serait dessiné verticalement.
Pour coder un arbre binaire, on fait correspondre à chaque nœud une structure contenant la donnée et deux
adresses, une adresse pour chacun des deux fils, avec la convention qu‘une adresse nulle indique un arbre
binaire vide. Il suffit alors de mémoriser l‘adresse de la racine pour pouvoir reconstituer tout l‘arbre.
Remarque: on code souvent un arbre général en utilisant un arbre binaire; pour cela on associe à chaque
nœud de l‘arbre initial un nœud de l‘arbre binaire; le fils gauche d‘un nœud dans l‘arbre binaire correspond
au premier fils du nœud correspondant de l‘arbre initial (on met une adresse nulle s‘il n‘y a aucun fils)
alors que le fils droit de ce nœud correspond au premier "frère cadet", c'est-à-dire au nœud de l‘arbre
initial qui a même père que le nœud considéré et qui se trouve immédiatement à sa droite (on met une
adresse nulle s‘il n‘y a aucun frère cadet). Ainsi, l‘arbre général donné en exemple précédemment et
retracé ci-dessous à gauche peut être codé avec l‘arbre binaire représenté à droite, en changeant bien
entendu l‘interprétation des liens.
76
Le parcours en ordre symétrique
Les deux parcours définis pour les arbres généraux sont aussi définis pour les arbres binaires. Pour
l‘exemple ci-dessus, le parcours en préordre donne l‘ordre: c, b, d, e, i, f, a, g, h et le parcours en postordre
donne l‘ordre: d, i, e, b, a, h, g, f, c.
On considère pour les arbres binaires un troisième ordre: l‘ordre symétrique. Parcourir un arbre binaire
en ordre symétrique, c‘est, si l‘arbre binaire est non vide, alors
• parcourir en ordre symétrique le sous-arbre gauche;
• examiner la racine;
• parcourir en ordre symétrique le sous-arbre droit.
Ce parcours est aussi dit parcours en ordre infixe ou milieu. La complexité du parcours en ordre
symétrique est, de même que pour les autres parcours, de l‘ordre du nombre de nœuds de l‘arbre. Exemple:
le parcours en ordre symétrique donné en exemple conduit à l‘ordre: d, b, i, e, c, a, f, g, h.
Remarque: on peut illustrer les trois parcours des arbres binaires à l‘aide du parcours à main gauche; il est
plus agréable pour cela de faire figurer sur le tracé de l‘arbre les sous-arbres vides comme il est fait ci-
dessous; le préordre correspond à la première fois que l‘on rencontre les nœuds, l‘ordre symétrique à la
deuxième fois et le postordre à la troisième fois.
Exemple d‘application: on peut utiliser un arbre binaire pour représenter une expression arithmétique
composée à partir des entiers et des quatre opérateurs binaires: +, -, ×, /. L‘arbre ci-dessous représente
l‘expression: (14 + (8 / 2)) × (5 - 3)
77
Par construction, dans cet arbre, tout nœud interne a un fils gauche et un fils droit.
Les trois parcours de cet arbre donnent:
• parcours en préordre: × + 14 / 8 2 - 5 3; on reconnaît la forme polonaise de l‘expression;
• parcours en ordre infixe: 14 + 8 / 2 × 5 - 3; il faudrait ajouter les parenthèses pour retrouver
l‘expression initiale;
• parcours en postordre: 14 8 2 / + 5 3 - ×; on reconnaît la forme polonaise inverse de l‘expression.
Quelques arbres binaires particuliers
Un arbre binaire est dit complet si tout nœud interne a exactement deux fils.
Un arbre binaire est dit parfait si, en appelant h la hauteur de l‘arbre, les niveaux de profondeur 0, 1, …,
h - 1 sont complètement remplis alors que le niveau de profondeur h est rempli en partant de la gauche; la
structure d‘un arbre binaire parfait est complètement déterminée par son nombre de nœuds; nous donnons
ci-après les arbres binaires parfaits à 5 nœuds et à 12 nœuds. On rencontre aussi quelquefois le qualificatif
de presque-complet pour un tel arbre.
En revanche, l‘arbre ci-dessous n‘est pas parfait.
Un arbre binaire est dit équilibré si, pour tout nœud de l‘arbre, les sous-arbres gauche et droit ont des
hauteurs qui diffèrent au plus de 1. L‘arbre ci-après est équilibré.
78
Un arbre binaire parfait est équilibré. On pourrait démontrer que la hauteur h d‘un arbre binaire équilibré
ayant n nœuds vérifie: log2(n + 1) ≤ h ≤ 1,44 log2(n + 2), d‘où on peut déduire facilement que la profondeur
moyenne des nœuds d‘un arbre binaire équilibré est du même ordre que ln n.
En ce qui concerne un arbre binaire quelconque de n nœuds, on établirait facilement que la profondeur
ainsi que la hauteur moyenne des feuilles ont toujours un ordre de grandeur compris entre ln n et n. La
hauteur de l‘ordre de n est atteinte pour des arbres qui sont "tout en hauteur" comme on peut en voir ci-
après; ces arbres seront dits dégénérés.
Des arbres binaires complets peuvent aussi avoir une hauteur de l‘ordre du nombre de nœuds comme
l‘illustrent les deux arbres ci-dessous, qualifiés aussi de dégénérés.
5.3.4 Dictionnaires et arbres binaires de recherche
Un dictionnaire est un type de données opérant sur les éléments d’un ensemble totalement ordonné,
appelés les clés et doté des opérations suivantes:
79
Les arbres binaires de recherche se prêtent particulièrement bien à l’implémentation des dictionnaires. Il
suffit ici de savoir qu’un arbre binaire de recherche est un arbre binaire dont chaque sommet est muni
d’une clé prise dans un ensemble totalement ordonné. De plus, pour chaque sommet de l’arbre, les clés
contenues dans son sous-arbre gauche sont strictement inférieures à la clé du sommet considéré et cette
clé est elle-même strictement inférieure aux clés contenues dans le sous-arbre droit. En d’autres termes,
un parcours symétrique de l’arbre donne une liste des clés en ordre croissant. Donnons d’abord les en-
têtes des opérations, qui sont les mêmes que dans un arbre :
Voici la réalisation de la recherche dans un arbre:
Pour l’insertion, on procède de manière similaire:
La suppression est plus difficile à réaliser parce qu’il faut conserver l’ordre sur l’arbre résultat. Soit x la
clé à supprimer, et soit s le sommet dont x est le contenu. Si s est une feuille, il suffit de la supprimer. Si
s n’a qu’un seul fils, on le remplace par son fils unique. Si s a deux fils, on cherche son descendant t dont
le contenu le précède dans l’ordre infixe: c’est le sommet le plus à droite dans son sous-arbre gauche. On
supprime ce sommet (qui n’a pas de fils droit), après avoir remplacé le contenu de s par le contenu de t.
(On pourrait aussi bien, symétriquement, remplacer le contenu de s par celui du sommet qui lui succède
dans l’ordre infixe.)
80
Voici une réalisation de cet algorithme:
L’appel à la fonction SUPPRIMER-MAX se fait donc dans le cas où l’arbre a deux sous-arbres non vides,
et où le contenu de la racine de a est à supprimer. La fonction SUPPRIMER-MAX réalise la suppression
du sommet de plus grande clé parmi les descendants, et retourne le contenu de ce sommet.
Plusieurs implémentations des arbres sont possibles; la plus souple utilise des pointeurs. A chaque
sommet, on associe deux pointeurs, l’un vers le sous-arbre gauche, l’autre vers le sous-arbre droit. Un
arbre est donné par un pointeur vers sa racine. Un sommet comporte en plus un champ qui contient la clé
associée. On est donc conduit à définir les types suivants:
5.3.5 Files de priorité
Les files de priorité constituent un type de données intéressant qui illustre bien comment une hiérarchie
de structures peut permettre d’implémenter un type de données. Une file de priorité est un type de données
opérant sur des clés, donc sur les éléments d’un ensemble totalement ordonné, et muni des opérations:
81
Il est commode de disposer de la combinaison de MINIMUM et de SUPPRIMER-MIN sous la forme:
Fréquemment, on convient qu’une même clé peut figurer plusieurs fois dans une file.
Si les clés sont toutes distinctes, on peut réaliser une file de priorité à l’aide d’un arbre binaire de
recherche. L’efficacité des opérations dépend alors de l’efficacité de l’insertion et de la suppression de la
plus petite clé dans un arbre binaire de recherche. On verra au chapitre 6 comment ces opérations peuvent
être réalisées en temps logarithmique, moyennant un rééquilibrage de l’arbre binaire. Nous présentons ici
une autre implémentation, au moyen d’un tas.
Un tas est un arbre tournoi parfait. Un arbre tournoi est un arbre binaire dont les sommets sont munis
d’une clé et tel que, pour tout sommet autre que la racine, la clé du sommet est plus grande que celle de
son père. En d’autres termes, les clés sur un chemin croissent de la racine vers une feuille. (La définition
avec plus petit est équivalente et, dans ce cas, les clés décroissent de la racine vers une feuille.)
Figure 5.7: Un arbre tournoi.
La figure 5.7 montre un arbre tournoi, et la figure 5.8 un tas (arbre tournoi parfait).
Figure 5.8: Un tas (tournoi parfait).
Sur les arbres parfaits, on utilise certaines des opérations des arbres binaires: EST-ARBREVIDE,
ARBREVIDE, RACINE, PERE, FILS-GAUCHE, FILS-DROIT. Par ailleurs, on définit les opérations
spécifiques suivantes:
82
Ces opérations conservent donc la perfection d’un arbre. Pour les arbres tournoi, la fonction CONTENU
donne le contenu (la clé) d’un sommet, et on fait appel à une procédure supplémentaire, ECHANGER-
CONTENU(p, q) qui échange les clés des sommets p et q.
Implémente les opérations des files de priorités au moyen des opérations des tas. Le minimum est évident:
c’est le contenu de la racine. Elle se fait donc en temps constant. Pour l’insertion d’une clé x, on crée une
feuille contenant cet élément (dernier niveau du tas); on compare son contenu à celui de son père; s’il est
plus petit, on l’échange, et on continue en progressant vers la racine du tas. Voici la procédure :
L’extraction de la plus petite clé se fait sur un canevas similaire:
On remplace donc le contenu de la racine par le contenu de la dernière feuille. Cette feuille est supprimée.
Puis, on descend de la racine vers les feuilles pour mettre la clé à une place convenable si elle ne l’est pas,
c’est-à-dire si elle est plus grande que l’une des clés des fils. Si le sommet en question a deux fils, on
échange la clé du père avec la plus petite des clés de ses fils. On obtient ainsi une correction locale; on
poursuit l’opération tant que nécessaire. Revenons à l’exemple de la figure 5.8. La suppression de la clé
1 amène la clé 7 à la racine. La descente qui s’ensuit est illustrée sur la figure 5.9. La fonction FILS-
MIN(p, a) retourne le fils de p dont le contenu est le plus petit. Elle s’écrit:
83
Figure 5.9: Mise en place de la clé 7 par comparaison aux fils.
Il est clair que la hauteur d’un tas est logarithmique en fonction du nombre de ses sommets, donc que
l’insertion et l’extraction d’une clé prennent un temps logarithmique, sous réserve que les opérations
élémentaires s’implémentent en temps constant.
Comme nous l’avons annoncé plus haut, il existe une implémentation très efficace des tas à l’aide d’un
couple formé d’un tableau a et d’un entier n donnant le nombre de clés présentes dans le tas. Les sommets
du tas étant numérotés niveau par niveau de la gauche vers la droite, chaque sommet est représenté par
l’indice d’une clé d’un tableau a. Le contenu d’un sommet p est rangé dans a[p], et est donc accessible en
temps constant. Passons en revue les opérations:
Les autres opérations se réalisent aussi simplement:
Seule la procédure ECHANGER-CONTENU(p, q) qui échange les clés des sommets p et q, demande trois
instructions. L’efficacité pratique de la réalisation des files de priorités est évidemment améliorée si l’on
travaille directement sur le tableau, et si l’on remplace les appels de procédures par les instructions
correspondantes.
84
CHAPITRE 6 : RECHERCHE ET TRI
6.1 INTRODUCTION
On considère des données appartenant à un ensemble totalement ordonné. Les trier consiste alors à les
ranger en ordre croissant ou décroissant. Quant à rechercher une donnée, c‘est soit simplement déterminer
si la donnée figure ou non, soit, dans le cas où la donnée figure, trouver l‘endroit où cette donnée est
stockée.
Les opérations de recherche et de tri consomment un pourcentage important du temps total de calcul des
ordinateurs. C‘est pourquoi les gains sur la complexité des algorithmes de tri et de recherche ont une
importance considérable: aussi ont-ils été très étudiés et perfectionnés. Dans tout ce chapitre, les données
que nous considérerons seront des entiers. Néanmoins, remarquons qu‘il est rare de trier simplement des
entiers; on rencontre plus fréquemment des tris de structures selon un champ de cette structure. On peut
trier des structures comportant un nom d‘élève et une note de cet élève par liste alphabétique des noms
des élèves ou par notes croissantes; on peut trier des factures par dates croissantes; on peut trier des cartes
à jouer par couleurs et à l‘intérieur de chaque couleur par niveaux et ainsi de suite. Il faudra considérer
que le type des données considérées est un type quelconque sur lequel est définie une relation d‘ordre total
notée avec les symboles habituels <, >, ≤, ≥.
6.2 RECHERCHE DICHOTOMIQUE DANS UN TABLEAU TRIE
On suppose ici que l‘on dispose d‘un tableau trié par ordre croissant et qu‘on souhaite savoir si un élément
fixé (i.e. une donnée) figure ou non dans la liste. On peut bien sûr utiliser une recherche séquentielle qui
consiste à regarder successivement, en partant de la gauche du tableau, tous les éléments. Néanmoins, il
sera plus astucieux d‘utiliser une recherche dichotomique.
La recherche dichotomique consiste à comparer l‘élément, ou un des deux éléments, qui se trouve au
centre de la liste avec l‘élément recherché; si cet élément central est égal à l‘élément recherché, c‘est
terminé; s‘il est supérieur à l‘élément recherché, on abandonne la moitié droite de la liste (correspondant
aux éléments plus grands que l‘élément central) et on recommence avec la liste formée par la moitié
gauche (correspondant aux éléments plus petits que l‘élément central) de la liste initiale; s‘il est inférieur
à l‘élément recherché, on abandonne la moitié gauche de la liste (correspondant aux éléments plus petits
que l‘élément central) et on recommence avec la liste formée par la moitié droite (correspondant aux
85
éléments plus grands que l‘élément central) de la liste initiale. Et ainsi de suite jusqu‘à ce que la liste
restante soit vide (recherche infructueuse) ou bien avoir trouvé l‘élément cherché (recherche fructueuse).
Écrivons le pseudo-code de cet algorithme qui renvoie vrai ou faux selon que l‘élément recherché est
trouvé ou non. Si on recherche l‘indice de l‘élément dans le cas où il figure, il faut adapter l‘algorithme.
Nous allons établir la complexité de cet algorithme. Pour chaque passage dans la boucle tant que, on fait
un nombre d‘opérations élémentaires majoré par une constante; à chaque passage dans la boucle, la
longueur de la liste est divisée par 2 (même un peu plus), ce qui fait que si on note p le nombre total de
passages dans la boucle, au bout de p passages, la longueur de la liste est majorée par n / 2p, et au moins
égale à 1: n / 2p ≥ 1, et donc: 2p ≤ n; d‘où p ≤ log2(n). La complexité est au pire de l‘ordre de log2(n) ou,
ce qui revient au même, de ln(n).
6.3 COMPLEXITE D‘UN ALGORITHME DE TRI
Comme pour tout algorithme, la complexité d‘un algorithme de recherche ou de tri peut s‘évaluer soit
dans le "pire des cas", c'est-à-dire pour un ordre initial des données spécialement défavorable pour cet
algorithme, soit dans le "meilleur des cas", soit "en moyenne". Par "en moyenne", on entend ici la
moyenne arithmétique des complexités sur toutes les permutations possibles des données, que l‘on
suppose, pour ce calcul, deux à deux distinctes.
Si un algorithme de tri doit souvent être exécuté mais qu‘il n‘est pas impératif d‘avoir un temps
d‘exécution maximum très petit, on pourra utiliser un algorithme de bonne complexité en moyenne mais
dont la complexité au pire peut être médiocre. C‘est le cas d‘un certain nombre de transactions que l‘on
peut exécuter en temps différé; le fait que, dans le "pire des cas", de tels algorithmes ne soient pas très
86
performants n‘est pas pénalisant, le pire étant peu probable en principe. En revanche, lorsqu‘on travaille
en temps réel, on s‘intéresse souvent à améliorer la complexité dans le pire des cas. En effet, même si
elles sont rares, des attentes très longues peuvent être inacceptables.
La plupart des algorithmes de tri sont fondés sur des comparaisons successives entre les données pour
déterminer la permutation correspondant à l‘ordre croissant des données. Nous appellerons tri comparatif
un tel tri. La complexité de l‘algorithme a alors le même ordre de grandeur que le nombre de comparaisons
entre les données faites par l‘algorithme. Nous ne verrons que des tris comparatifs.
Nous allons voir plus loin le tri sélection et le tri insertion de complexité en O(n2), qui seront simples à
écrire mais peu efficaces; en effet, nous verrons aussi le tri rapide et le tri par arbre binaire de recherche
qui sont en moyenne en O(n ln (n)), mais dans le pire des cas en O(n2); nous verrons enfin le tri tas qui
est dans le pire des cas en O(n ln (n)).
6.4 TRI SELECTION
Le tri sélection consiste à chercher la plus petite donnée de la liste, à mettre celle-ci en première position,
puis à chercher la plus petite donnée parmi les données autres que la première, la mettre en deuxième
position, et ainsi de suite. Dans le pseudo-code donné ci-dessous, on suppose qu‘on dispose d‘une fonction
échanger telle que, si T est un tableau et i et j deux indices de ce tableau, échanger(T, i, j) échange les
données du tableau T qui se trouvent aux indices i et j.
La complexité de ce tri est aussi bien dans le pire des cas que dans le meilleur des cas (et donc qu‘en
moyenne) en O(n2). Ce n‘est donc pas un tri très efficace, mais en revanche c‘est un tri très simple.
87
6.5 TRI INSERTION
Le principe du tri par insertion est le suivant. On souhaite trier une liste de n données; on procède par
étape; à la ie étape (i variant de 1 à n - 1), on suppose que les i premières données sont déjà triées; on
considère alors la (i + 1)e donnée que l‘on appelle clé; on la compare successivement aux données
précédentes, en commençant par la ie puis en remontant dans la liste jusqu‘à trouver la bonne place de clé
(c'est-à-dire entre deux données successives, l‘une étant plus petite et l‘autre plus grande que clé), ou bien
en tout premier si clé est plus petite que les i premières données; au fur et à mesure, on décale "d‘une case
vers la droite" les données plus grandes que clé de façon à anticiper la place de ces données après insertion
de clé; on met clé à la bonne place; à l‘issue de cette étape, les i + 1 premières données sont donc triées.
Ce tri est en O(n2) dans le pire des cas (cas où la liste est triée dans l‘ordre inverse) et en O(n) dans le
meilleur des cas (cas où la liste serait déjà triée avant application de l‘algorithme); si on considère que
toutes les permutations des données sont équiprobables, on vérifie facilement que le tri est en moyenne
en O(n2). C‘est donc encore un tri peu efficace mais qui a aussi le mérite de la simplicité. Le tri insertion
a une complexité en moyenne du même ordre que celle du tri sélection; néanmoins, si les données à trier
sont souvent presque triées (dans le sens souhaité), il vaudra mieux choisir le tri insertion.
6.6 TRI RAPIDE
Le principe du tri rapide est le suivant. On utilise une fonction nommée partition qui s‘applique à une
liste; cette fonction extrait une donnée, nommée clé, de la liste, par exemple la première (c‘est ce que nous
choisirons plus bas) puis elle réorganise la liste de sorte qu‘on trouve d‘abord les données ne dépassant
pas la valeur de clé (on appellera sous-liste gauche cette partie de la liste), puis la donnée clé, puis les
données supérieures à clé (on appellera sous-liste droite cette partie de la liste). Le tri rapide peut être
défini récursivement. Pour appliquer le tri rapide à une liste ayant au moins deux données, on commence
88
par appliquer la fonction partition, puis on applique le tri rapide à la sous-liste gauche, puis on applique
le tri rapide à la sous-liste droite.
La fonction partition peut être implémentée de différentes façons; il importe simplement que sa
complexité pour une liste de longueur n soit en O(n), pour que le tri rapide ait une bonne complexité (voir
plus bas). Nous supposons que les données sont dans un tableau T et que ce tableau contient une case
supplémentaire à la droite des données, qui contient une donnée strictement supérieure à toutes les
données de la liste; cette condition est nécessaire pour que, dans le pseudo-code donné ci-dessous, la
variable i ne risque pas de croître "indéfiniment"; il ne faudra pas l‘oublier au moment d‘une
programmation (ou bien il faudra modifier légèrement le pseudo-code ci-dessous pour éviter le
débordement sur la droite du tableau). Dans le pseudo-code suivant, partition renvoie l‘indice du tableau
où clé est rangée. La procédure échanger est définie comme plus haut.
Prenons un exemple. Les données sont les valeurs qui figurent dans la seconde ligne du tableau T suivant,
la première précisant les indices des cases de T:
On suppose qu‘on applique la fonction partition avec g = 1 et d = 12. La variable clé vaut T[1] = 9. Au
premier passage dans la boucle externe, i s‘arrête à 3, j s‘arrête à 12. On procède à l‘échange et on obtient:
89
Après quoi i passe à 4 et j à 11. Au deuxième passage dans la boucle, i s‘arrête à 4 et j s‘arrête à 10. On
procède à l‘échange et on obtient:
avec i = 5 et j = 9. Au troisième passage dans la boucle, i s‘arrête à 5 et j s‘arrête à 8. On procède à
l‘échange et on obtient:
avec i = 6 et j = 7. Au quatrième passage dans la boucle, i s‘arrête à 7 et j s‘arrête à 6. Le test "i < j ?" est
négatif car on a i ≥ j. On sort de la boucle externe "tant que i ≤ j" car on a i > j; on échange T[1] avec T[j],
i.e. T[6]; on obtient:
On retourne l‘indice 6. On remarque que la donnée de valeur 9 est à sa place définitive et qu‘avant elle,
se trouvent des données inférieures à 9 et, après, des données supérieures à 9.
On peut maintenant écrire le pseudo-code du tri rapide pour un tableau compris entre les indices g et d.
On appellera tri_rapide(1, n) pour trier des données se trouvant entre les indices 1 et n d‘un tableau.
Sur notre exemple, il reste à appliquer le tri rapide entre les indices 1 et 5 puis entre les indices 7 et 12.
L‘application de tri_rapide(1, 5) appelle partition(1, 5) qui conduit au tableau:
et renvoie la valeur 3. On applique alors tri_rapide(1, 2), qui appelle partition(1, 2) qui ne change pas le
tableau et retourne la valeur 1, puis tri_rapide(1, 0) qui ne fait rien, puis tri_rapide(4, 5) qui appelle
partition(4, 5) qui conduit au tableau:
90
et retourne l‘indice 4. Puis, tri_rapide(4, 3) ne fait rien ainsi que tri_rapide (5, 5). Le tri rapide entre les
indices 1 et 5 est terminé.
L‘application de tri_rapide(7, 12) fait appel à partition(7, 12) qui conduit au tableau:
et retourne l‘indice 11. Alors, tri_rapide(7, 10) appelle partition(7, 10) qui conduit à:
et retourne l‘indice 9. Puis, tri_rapide(7, 8) fait appel à partition(7, 8) qui ne change pas le tableau et
retourne l‘indice 7, puis tri_rapide(7, 6) ainsi que tri_rapide(8, 8) qui ne font rien. On "remonte" avec
tri_rapide(12, 12) qui ne fait rien. L‘algorithme est terminé.
On remarque que la complexité de la fonction partition est bien linéaire en la longueur de la liste
considérée. Le "gros" du travail consiste en l‘application des fonctions partition.
Le pire des cas pour cet algorithme est celui où la clé vient toujours à une extrémité du sous-tableau allant
de l‘indice g à l‘indice d pour chaque appel à la fonction partition. Ce sera par exemple le cas si on trie un
tableau déjà trié. Il sera alors fait appel à la fonction partition pour des listes de longueur n, puis n - 1, puis
n - 2, …, puis 2; la somme des complexités de ces fonctions donne un algorithme en O(n2).
Le meilleur des cas est celui où la liste est toujours partagée en deux sous-listes de même longueur. On
aura en tout:
• un appel à la fonction partition sur une liste de longueur n,
• deux appels à la fonction partition sur des listes de longueurs environ n/2,
• quatre appels à la fonction partition sur des listes de longueurs environ n/4,
• …
D‘où une complexité de l‘ordre de n pour la liste de longueur n, une complexité totale de l‘ordre de n pour
les deux sous-listes de longueur n/2, une complexité totale de l‘ordre de n pour les quatre sous-listes de
91
longueur n/4, … Comme la longueur est divisée par deux quand on passe de n à n/2, puis de n/2 à n/4, on
a en tout une complexité de l‘ordre de n ln (n).
On peut montrer sans trop de difficulté, par une formule de récurrence, que la complexité en moyenne est
aussi de l‘ordre de n ln (n). Remarquons que pour éviter d‘avoir une complexité en n2 lorsqu‘on trie une
liste déjà triée, on prend souvent, au tout début de la fonction partition, une donnée au hasard dans la liste
traitée et on l‘échange avec la donnée qui se trouve en première position, puis on continue de la façon
indiquée précédemment.
6.7 ARBRE BINAIRE DE RECHERCHE
Un arbre binaire de recherche est un arbre dont les nœuds appartiennent à un ensemble totalement ordonné
et tel que, pour tout nœud interne a, les données contenues dans le sous-arbre gauche de a sont inférieures
ou égales à la donnée contenue dans le nœud a, qui est elle-même inférieure ou égale aux données
contenues dans le sous-arbre droit de a. Exemple:
Par définition d‘un arbre binaire de recherche, un parcours en ordre symétrique de l‘arbre donne la liste
triée des données que contient l‘arbre.
Ci-dessous, on supposera que la racine de l‘arbre ainsi que les fils gauche et droit d‘un nœud sont des
adresses de nœuds. Si on a l‘adresse adr d‘un nœud, adr.donnée sera la donnée contenue par le nœud (cela
serait noté adr→donnée s‘il s‘agissait d‘un codage en langage C), adr.fils_gauche sera l‘adresse du fils
gauche et adr.fils_droit sera l‘adresse du fils droit.
Pour insérer une donnée nommée clé dans un arbre binaire de recherche, on compare clé à la donnée
contenue dans la racine; si clé est plus petite, on l‘insère dans le sous-arbre gauche; si elle est plus grande,
on l‘insère dans le sous-arbre droit. Ceci est décrit plus précisément par la fonction récursive insérer dont
on donne ci-dessous le pseudo-code.
92
La complexité d‘une insertion ou d‘une recherche dans un arbre binaire de recherche est:
• dans le pire des cas égale à la profondeur de l‘arbre binaire dans lequel se fait l‘insertion;
• en moyenne égale à la profondeur moyenne des feuilles de l‘arbre binaire.
Considérons un arbre binaire de recherche obtenu par insertions successives de n données formant une
permutation quelconque, toutes les permutations étant équiprobables. On sait qu‘en moyenne la hauteur
ainsi que la profondeur moyenne des feuilles de cet arbre sont de l‘ordre de ln(n); le pire néanmoins
correspond à un arbre dégénéré, où on obtient une hauteur de l‘arbre et une profondeur moyenne des
feuilles de l‘ordre de n. La recherche d‘une donnée dans un arbre binaire de recherche contenant n données
est donc au pire en O(n) et en moyenne en O(ln (n)).
Si on veut trier n des données en utilisant un arbre binaire de recherche, il faut:
• construire l‘arbre binaire de recherche en partant de l‘arbre vide et en insérant les données les unes après
les autres; la complexité pour l‘ensemble des insertions est de l‘ordre de la somme des profondeurs des
nœuds de l‘arbre obtenu; celle-ci a un ordre de grandeur compris entre n ln (n) et n2, et est en moyenne
sur les jeux de données possibles de l‘ordre de n ln (n);
• on lit en ordre symétrique l‘arbre binaire obtenu, opération dont la complexité est du même ordre que le
nombre de nœuds de l‘arbre, et donc inférieure à celle de la construction de l‘arbre.
Le tri par arbre binaire de recherche est donc au pire en O(n2) et en moyenne en O(n ln (n)).
6.8 STRUCTURE DE TAS ET TRI TAS
6.8.1 Tas en tableau
Pour rappel, on appelle tas un arbre binaire parfait, c'est-à-dire où tous les niveaux sont remplis sauf
éventuellement le dernier, celui-ci étant rempli de la gauche vers la droite, et dans les sommets duquel
93
figurent des éléments d‘un ensemble totalement ordonné, l‘élément stocké en un nœud quelconque étant
plus grand (la définition avec plus petit est équivalente) que les éléments stockés dans ses deux nœuds fils
s‘il a deux fils, dans son fils s‘il a un seul fils. Nous avons vu, dans la section Files de priorité, qu'un tas
pouvait être implémenté très efficacement dans un tableau. C‘est ce codage avec un tableau qui sera en
général retenu dans le traitement d‘un tas. Nous appellerons nœud d‘indice i le nœud qui est numéroté par
i, et donc qui est rangé dans la ie case du tableau.
On donne ci-dessous la représentation d'un tas dans un tableau.
6.8.2 Insertion d‘un nouvel élément dans un tas
Pour structurer une liste donnée de valeurs à partir d‘un tas vide, on insère les éléments les uns après les
autres en veillant à conserver la structure de tas. Le nouvel élément est mis à la première place disponible
dans la dernière rangée du tas si celle-ci n‘est pas encore pleine; si la dernière rangée est pleine, on en
crée une nouvelle et on insère le nouvel élément à la première place de la nouvelle rangée. C’est la
procédure INSERERTAS que nous avons vue dans la section des Files de priorité et que nous réécrivons
comme suit :
Imaginons que, partant du tas représenté ci-dessus, on veuille introduire la valeur 28. On place la valeur
28 à droite de la dernière feuille introduite, c'est-à-dire dans la case d‘indice 9 du tableau.
94
On compare 28, la nouvelle donnée insérée, avec la donnée contenue dans le nœud père, autrement dit on
compare la donnée de la case d‘indice 9 du tableau avec la donnée de la case d‘indice [9/2] = 4. Puisque
28 est plus grand que 21, on échange le 21 et le 28. En observant cet échange, on remarque qu‘en toute
généralité la seule relation définissant un tas qui peut ne pas être vérifiée est maintenant celle qui existe
entre la donnée (28) contenue par le nœud d‘indice 4 et la donnée (25) contenue par le nœud père de celui-
ci, d‘indice [4/2] = 2.
On compare la donnée 28 du nœud d‘indice 4 avec la donnée 25 contenue dans son nœud père, d‘indice
2. Puisque 28 est plus grand que 25, on échange le 25 et le 28. On remarque que la seule relation définissant
un tas qui peut ne pas être vérifiée est maintenant celle qui existe entre la donnée (28) contenue par le
nœud d‘indice 2 et la donnée (56) contenue par le nœud d‘indice [2/2] = 1.
On compare la donnée 28 de la case d‘indice 2 avec la donnée contenue dans le nœud père d‘indice 1.
Puisque 28 est plus petit que 56, l‘insertion est terminée. On a bien ainsi restauré la structure de tas.
Lorsqu‘on insère une pe donnée dans un tas, celle-ci est insérée initialement en dernier dans le tableau,
c'est-à-dire dans le niveau de profondeur h = [log2 p]; on fait alors au plus h comparaisons et échanges
d‘éléments. La complexité d’une insertion est donc logarithmique et la complexité de la création d’un tas
de p valeurs est égale à p ln (p).
95
6.8.3 Principe du tri tas
Dans un tas, le plus grand élément est à la racine. Tirons parti de cette indication pour trier des données
de façon très efficace. On échange la donnée contenue par la racine avec la donnée contenue dans la
dernière feuille du tas, c'est-à-dire avec la donnée contenue dans la dernière case du tableau représentant
le tas. La donnée contenue dans la racine avant l‘échange étant la plus grande, après l‘échange la donnée
contenue dans la dernière case du tableau est la plus grande et est donc à sa place dans un tri par ordre
croissant; on ne va plus y toucher. On va alors reconstruire un tas avec les données d‘indices compris
entre 1 et n - 1 (en notant n le nombre initial de données); la seule condition définissant un tas qui peut
être violée est la supériorité de la donnée de la racine par rapport à ses fils. Pour cela, dans une démarche
symétrique de celle de la construction du tas, on "fait descendre" la donnée mise à la racine: tant qu‘on
n‘a pas atteint une feuille du tas et que la donnée qui descend est plus petite que la plus grande des données
de ses deux fils, on l‘échange avec cette plus grande donnée.
Nous utilisons en fait la même démarche que celle suivie dans les Files de priorité avec les fonctions
EXTRAIREMIN et FILS-MIN qui sont réécrites comme suit:
Reprenons l'exemple précédent. On échange la donnée de la racine avec la dernière donnée du tas.
96
On cherche à reconstituer un tas sur les 8 premières cases du tableau. Pour cela, on cherche la plus grande
des deux données contenues dans les fils de la racine, c'est-à-dire les nœuds d‘indice 2 × 1 = 2 et 2 × 1 +
1 = 3; la plus grande de ces données vaut 28; on échange donc le contenu de la case 1 avec le contenu de
la case 2.
On cherche la plus grande des données entres les données contenues par les nœuds d‘indice 2 × 2 = 4 et
2 × 2 + 1 = 5; la plus grande de ces données vaut 25 et est plus grande que 21; on échange donc le contenu
de la case 2 avec le contenu de la case 4.
Comme on ne considère qu‘un tas sur les 8 premières cases, le nœud d‘indice 4 a un seul fils dans le tas,
qui contient la donnée 5. Comme 21 est plus grand que 5, la descente est terminée.
La complexité de la descente est au pire de l‘ordre de la hauteur de l‘arbre binaire, puisque, pour chaque
niveau de l‘arbre, on fait un nombre d‘opérations majoré par une constante (au plus deux comparaisons
et quelques affectations); la descente est donc en O(ln (n)) pour un tas de n données.
6.8.4 Pseudo-code du tri tas
Pour trier un tableau T, d'indices de 1 à n, contenant n données, on utilise la procédure tri_tas suivante:
La complexité se calcule à partir de celle des procédures montée et descente; elle est en O(n ln (n)). On
constate donc que ce tri a la complexité optimum d‘un tri comparatif.
97
CHAPITRE 7 : TIRER PARTI DE LA REPETITION
7.1 LE DRAPEAU TRICOLORE DE DIJKSTRA
Soit un tableau T [0 .. m-1] contenant NB boules bleues (B), Nb boules blanches (b) et NR boules rouges
(R) disposées aléatoirement. Nous avons donc NB + Nb +NR = m. On veut classer ces boules en
regroupant successivement les bleues, les blanches et les rouges pour reconstituer le drapeau hollandais
de E.W. DIJKSTRA. On impose que les déplacements des boules ne peuvent se faire que par des
permutations au sein du tableau.
Un solution immédiate est obtenue avec le tri à bulles dont la complexité est en O(n2). Pouvons-nous
construire un algorithme de complexité O(n) en ne regardant chaque boule qu'une et une seule fois?
Pour cela, il faut parcourir le tableau et, pour chaque boule rencontrée, compléter le drapeau
précédemment construit avec les boules rencontrées jusqu'alors, le drapeau étant délimité par les
séparations entre les couleurs. De cette manière, lorsque nous aurons analysé toutes les boules, le drapeau
sera constitué complètement.
Supposons que nous ayons déjà analysé une partie du tableau et qu'un drapeau ait été constitué avec les
boules déjà analysées. Ceci est représenté par la figure suivante:
i est l'indice de la zone des blanches;
j est l'indice de la zone des rouges;
k est l'indice de la zone à classer (partie du tableau non encore organisée en drapeau);
Si la boule rencontrée est une blanche (b)
if T[k] = b then
begin
PERMUTER (T[k] et T[j]);
j := j + 1;
k := k + 1;
end;
La boule blanche est dans sa zone et il suffit de redéfinir le début de la zone rouge et de réduire la zone à
classer.
i j k
B B B B b b b R R R b R R B b R B R B b b R B b R B b R b B
98
Si la boule rencontrée est une rouge (R)
if T[k] = R then k := k + 1 end;
La boule rouge est dans sa zone et il suffit de réduire la zone à classer.
Si la boule rencontrée est une bleue (B)
if T[k] = B then
begin
PERMUTER (T[k] et T[j]);
PERMUTER (T[j] et T[i]);
i := i + 1;
j := j + 1;
k := k + 1;
end;
La boule bleue est dans sa zone et il suffit de redéfinir le début des zones blanche et rouge et de réduire la
zone à classer.
La complexité de l'algorithme est bien en O(n) puisque chaque boule n'est regardée qu'une seule fois.
Qu'en est-il si nous nous intéressons plus précisément au nombre d'opérations plus complexes, en
l'occurrence l'opération PERMUTER?
Avec NB bleues, nous accomplissons 2 * NB permutations, avec Nb blanches, Nb permutations et avec
les rouges, aucune permutation. Le nombre total de permutation est donc:
2 * NB + Nb. Si les boules sont en nombres égaux, nous avons 2 * m/3 + m/3 = m permutations.
Est-il possible d'améliorer l'algorithme? Les boules bleues posent problème car elles doivent subir un long
"déplacement" depuis la zone à classer jusqu'à leur zone propre. Comment réduire ce "déplacement"?
Tout naturellement en positionnant la zone de départ "au milieu" des autres zones. Ceci est représenté à
la figure suivante:
Il vient alors:
Si la boule rencontrée est une blanche (b)
if T[k] = b then k := k + 1 end;
La boule blanche est dans sa zone et il suffit de réduire la zone à classer.
i k j
B B B B b b b b B b R B R B b b R B b R B b R b B R R R R R
99
Si la boule rencontrée est une rouge (R)
if T[k] = R then
begin
PERMUTER (T[k] et T[j-1]);
j := j - 1;
end;
La boule rouge est devant sa zone qu'il convient alors de redéfinir. La zone à classer commence toujours
au même endroit.
Si la boule rencontrée est une bleue (B)
if T[k] = B then
begin
PERMUTER (T[k] et T[i]);
i := i + 1;
k := k + 1;
end;
La boule bleue est dans sa zone et il suffit de redéfinir le début des zones blanche et rouge.
Avons-nous amélioré l'algorithme? Le nombre de permutations est égal à NR + NB. Si les boules sont en
nombres égaux, nous avons m/3 + m/3 = 2*m/3 permutations. Ce second algorithme est meilleur.
Toutefois, ceci n'est vrai qu'en moyenne.
Le premier algorithme est meilleur si
2 * NB + Nb < NR + NB soit si
NB + Nb (= m – NR) < NR soit si m/2 < NR. Si le tableau initial est rempli à plus de 50% de rouges, le
premier algorithme est meilleur.
100
7.2 PROBLEME DU PLUS GRAND CARRE DE 1
Soit le tableau T[0 .. m-1, 0 .. n-1] avec m > 0 et n > 0, dont les T[i, j] sont égaux à 0 ou 1. Il importe de
trouver un sous-ensemble de T dont tous les éléments sont égaux à 1 et forment un carré.
Essayer tous les carrés de dimension inférieure ou égale au Min (m, n) présenterait une complexité de
calcul beaucoup trop grande. Recherchons une solution "idéale" c'est-à-dire qui ne nécessiterait qu'une
seule lecture de toutes les valeurs de T. Il faut par exemple parcourir T, ligne par ligne et dans chaque
ligne, regarder les colonnes successivement avant de passer à la ligne suivante. L'analyse de chaque
élément doit permettre de donner la taille du plus grand carré rencontré jusqu'alors. De la sorte, lorsque le
dernier élément aura été analysé, nous connaîtrons la taille du plus grand carré de 1 dans T.
Supposons que nous ayons déjà analysé une partie de T et que nous ayons à traiter T [i, j] et qu'à ce
moment la taille du plus grand carré soit égale à dmax. La situation est illustrée par la figure suivante:
Si T [i, j] = 0, il n'y a aucune possibilité d'agrandir le plus grand carré.
Si T [i, j] = 1, trois cas sont possibles, illustrés par les figures suivantes:
a est la taille du plus grand carré dont le coin inférieur droit est T[i, j-1]
b est la taille du plus grand carré dont le coin inférieur droit est T[i-1, j]
y est la taille du plus grand carré dont le coin inférieur droit est T[i, j]
1) Si a = b
Si ? = 1 alors y := a + 1 (= b + 1)
Si ? = 0 alors y := a
0 j n-1
0 1 0 0 1 1 1 0 1 0 0
1 1 0 1 0 1 1 1 1 1
1 0 0 1 1 0 1 1 1 1
0 1 1 1 0 1 1 1 1 1
0 1 1 0 1 1 1 1 0 1
1 0 0 1 1 1 1 0 0 0
i 1 0 1 1 1 1 0 1 0 0
0 1 1 0 1 1 0 1 1 0
0 1 1 1 1 1 0 1 0 1
0 1 1 0 1 1 1 0 1 1
1 1 1 1 1 1 1 0 0 1
1 0 1 0 1 1 1 1 1 0
0 1 1 1 1 1 0 1 1 0
m-1 1 1 1 1 1 1 0 1 1 1
?
b
a
1
101
2) Si a < b alors y := a + 1
3) Si a > b alors y := b + 1
La taille du plus grand carré de 1 rencontré jusqu'alors est: dmax := max (dmax, y)
Nous pouvons simplifier ces tests comme suit
if T [i, j] = 0 then y := 0
else
begin
c := min (a, b);
if T [i - c, j - c] = 0 then y := c
else
begin
y := c + 1;
dmax := max (dmax, y)
end;
end;
Pour disposer des valeurs a et b, il suffit de mémoriser dans un tableau TC [0 .. n-1] les y obtenus pour
les éléments de la ligne i dont les indices varient de 0 à j – 1 et les y obtenus pour les éléments de la ligne
i – 1 dont les indices varient de j à n – 1. Nous ajoutons alors une place supplémentaire en TC[-1],
initialisée à 0 pour traiter le cas j = 0 comme tous les autres j.
A l'initialisation, tous les éléments de TC sont bien évidemment égaux à 0.
L'algorithme est alors le suivant:
b
1
a
b
1
a
102
i := 0;
j := 0;
dmax := 0;
k := -1;
while i < m do
begin
if T [i, j] = 0 then TC [j] := 0
else
begin
c := min (TC [j - 1], TC [j]);
if T [i - c, j - c] = 0 then TC [j] := c (1)
else
begin
TC [j] := c + 1;
dmax := max (dmax, TC [j])
end;
end;
if j < n then j := j + 1
else
begin
j := 0;
i := i + 1
end;
end;
La complexité de cet algorithme est en O(n) puisque chaque élément du tableau est regardé une seule fois
et parfois deux fois (dans le cas (1)).
103
CHAPITRE 8 : L'ARCHITECTURE DES ORDINATEURS
Dans les chapitres précédents, nous nous sommes préoccupés de la conception des algorithmes. Pour qu'un
algorithme soit utile, on doit disposer d'un processeur capable de lire, comprendre et exécuter les
instructions que contient l'algorithme. Un ordinateur est un processeur à même d'exécuter de nombreux
types différents d'algorithmes. Ce chapitre présente la conception des ordinateurs.
8.1 STRUCTURE DES ORDINATEURS
Une fois les algorithmes élaborés, les programmeurs les transcrivent dans un langage de programmation
pour qu'ils puissent être exécutés par l'ordinateur. Malheureusement, les langages de programmation
évolués, bien qu'ils soient commodes pour l'utilisateur, ne se prêtent pas à une utilisation directe par les
ordinateurs en raison du coût prohibitif que de tels ordinateurs impliquent. Les constructeurs ont donc
fabriqué des ordinateurs pour exécuter des programmes écrits dans des langages beaucoup plus simples,
appelés langages machine.
A l'aube de l'informatique, les ordinateurs étaient construits afin d'exécuter directement des programmes
en langage machine. Cependant on s'est très vite rendu compte que les différentes instructions d'un langage
machine quel qu'il soit présentaient des ressemblances les unes avec les autres. Il est possible d'isoler un
nombre restreint d'opérations fondamentales, appelées micro-instructions, et d'exprimer toute instruction
de langage machine comme un ensemble restreint de ces micro-instructions. Pour des raisons d'économie,
les ordinateurs modernes sont conçus pour exécuter les micro-instructions plutôt que les programmes
directement en langage machine. Les constructeurs fournissent également un programme appelé
interpréteur (écrit en termes de micro-instructions) qui indique à l'ordinateur comment lire, comprendre
et exécuter chaque instruction du langage machine. Par conséquent, l'ensemble ordinateur / interpréteur
est en mesure d'exécuter des programmes écrits en langage machine. Ces ordinateurs sont appelés
ordinateurs microprogrammés.
L'équipement électronique d'un ordinateur est décrit dans les sections suivantes, en partant des principes
de physique et en aboutissant aux composants de base qui le constituent et qui permettent la manipulation
des micro-instructions. L'accent est mis surtout sur la conception de la mémoire et de l'UCT. De par leur
nature, les dispositifs d'entrée et de sortie comportent parfois des composants mécaniques puisqu'ils
doivent communiquer avec le monde extérieur (par exemple, fermer une soupape dans une usine de
produits chimiques). Les dispositifs d'entrée et de sortie sont décrits dans la dernière section.
104
8.2 PHYSIQUE ET ELECTRONIQUE
8.2.1 LES SEMI-CONDUCTEURS
Lorsqu'on ouvre un ordinateur, on voit un ensemble de plaquettes rectangulaires enfichées ensemble sur
un panneau d'assemblage. Chaque plaquette contient des boîtiers en plastique reliés les uns aux autres. A
l'intérieur de chaque boîtier se trouve une fine puce de silicium dont la taille n'excède généralement pas
le quart de celle d'un ongle. Afin de comprendre ce qui se passe dans une puce il faut examiner de très
près l'une de ses infimes parties. La puce est presque exclusivement composée de monocristal de silicium,
constituant principal du sable. Près de la surface, certaines zones de la structure cristalline contiennent des
traces de phosphore et d'autres des traces de bore. Il y a également quelques fines couches de bioxyde de
silicium ainsi que de minces lamelles d'aluminium.
Pour comprendre ce qu'est une puce, il faut savoir que ce sont ses caractéristiques électriques qui
comptent. L'aluminium, comme la plupart des métaux, est un bon conducteur d'électricité parce que ses
électrons peuvent se déplacer librement. D'autre part, le silicium pur est un mauvais conducteur parce que
tous ses électrons sont étroitement liés à l'intérieur de la structure cristalline. Le silicium comportant des
traces de phosphore a quelques électrons plus mobiles et il est appelé semi-conducteur de type n. Il possède
une capacité limitée de conduire une charge électrique négative. Inversement, le silicium comportant des
traces de bore manque d'électrons dans sa structure cristalline, et c'est pourquoi il a une capacité limitée
de conduire une charge électrique positive. C'est ce qu'on appelle un semi-conducteur de type p. Enfin, le
bioxyde de silicium est un mauvais conducteur (donc un bon isolant).
8.2.2 LES TRANSISTORS
Les différents matériaux des semi-conducteurs occupent toute la puce suivant une structure régulière. La
plus petite unité de la structure est appelée transistor. Il peut y avoir plus de 1000000 transistors sur une
seule puce.
Collecteur Base Emetteur
Silicium
n
n p
Isolant en
bioxyde de silicium
Conducteur en aluminium
Collecteur
Emetteur
Base
105
Comme le montre la figure ci-dessus, il y a trois emplacements dans chaque transistor où les conducteurs
d'aluminium sont en contact avec la surface du silicium. Ce sont le collecteur, la base et l'émetteur du
transistor. Les caractéristiques électriques des semi-conducteurs permettent au transistor d'agir comme un
commutateur (un interrupteur). Lorsque la tension correcte est appliquée à la base, un courant électrique
peut circuler entre le collecteur et l'émetteur. En l'absence d'une telle tension sur la base, aucun courant
ne peut passer. Le symbole du transistor est donné avec la figure précédente.
8.2.3 LES PORTES
Des transistors peuvent être interconnectés pour former ce qui est appelé une porte.
La figure ci-dessus montre deux transistors interconnectés de telle manière qu'un courant puisse passer du
collecteur de l'un à l'émetteur de l'autre uniquement lorsque la base des deux transistors est soumise à la
tension adéquate. Une telle configuration peut être utilisée comme la base d'une porte ET, réalisant la
fonction logique AND. On conçoit alors aisément qu'il est possible de construire des portes qui réaliseront
les autres fonctions logiques OR et NOT.
Une des caractéristiques importantes des portes est qu'elles ne réagissent qu'à une tension d'entrée basse
ou haute (autrement dit, l'état 0 ou l'état 1). Une porte a des entrées, dont chacune peut avoir une tension
correspondant soit à 0 soit à 1, et une sortie qui peut correspondre à 0 ou à 1 selon la valeur des entrées.
8.3 LES COMPOSANTS
Une puce peut comporter quelques milliers de portes et un ordinateur peut être constitué de nombreuses
puces, il est donc extrêmement difficile de comprendre les ordinateurs uniquement en termes de portes.
Leur nombre considérable et la complexité de leurs interconnexions rendent impossible la visualisation
de toutes les portes d'un ordinateur en une seule fois. Pour permettre cette visualisation, les ingénieurs ont
rassemblé des groupes de portes en des composants plus grands. Ce sont ces composants qui, associés les
uns aux autres, constituent un ordinateur complet. Les composants essentiels comprennent les mémoires,
les additionneurs, les bus, les horloges et l'unité de commande.
E
n
t
r
é
e
s Sortie
106
8.3.1 LES MEMOIRES
Il est essentiel que les ordinateurs soient en mesure de se souvenir des données, que ce soit pour un court
laps de temps (lorsqu'il s'agit par exemple de résultats intermédiaires obtenus pendant des calculs) ou que
ce soit pour des périodes plus longues. On appelle bascule (ou flip-flop) un composant qui peut stocker
soit 1 soit 0. Tout ce qui peut indifféremment prendre 0 ou 1 comme valeur est dit contenir un bit (un
élément d'information binaire, binary digit en anglais). Ainsi une bascule peut stocker un bit d'information.
Huit bits sont souvent appelés un octet.
Il va de soi que les ordinateurs doivent mémoriser plus d'un bit d'information. Par exemple, un nombre
peut comporter de nombreux chiffres qui tous doivent être conservés. Les ordinateurs manipulent
généralement les données par tranches de format fixe appelées mots, bien que la taille d'un mot puisse
varier d'un ordinateur à un autre. Actuellement, la taille d'un mot est souvent égale à 64 bits. Si la taille
du mot est de N bits, N bascules sont nécessaires pour conserver un mot de données. Un ensemble de
bascules est appelé registre.
De nombreux types différents de données peuvent tenir en un seul mot. Si seuls des entiers non négatifs
sont nécessaires, ils peuvent être représentés par le système de numérotation binaire. Si la taille d'un mot
est de N bits, ce système permet à tout nombre compris entre 0 et 2N - 1 d'être représenté. En général, le
bit le plus à droite (appelé bit le moins significatif) est la colonne des unités, et plus on s'éloigne vers la
gauche plus les colonnes augmentent en importance jusqu'au bit le plus à gauche (ou le plus significatif),
dont la valeur est de 2N-1.
Les nombres négatifs peuvent être représentés de la même manière. La seule modification consiste à
attribuer au bit le plus significatif le poids –2N - 1. On déduit assez facilement que tout nombre compris
entre –2N-1 et 2N-l - l peut être représenté par cette méthode, appelée représentation en complément à deux.
Une des caractéristiques de cette représentation est que les nombres négatifs et non négatifs peuvent
facilement être distingués en consultant le bit le plus significatif. Lorsque ce bit est à 1 le nombre est
négatif; lorsqu'il est à 0 le nombre est soit zéro soit positif.
Il est souhaitable de représenter non seulement des nombres mais aussi des caractères dans un ordinateur.
Plusieurs méthodes standard de représentation ont été établies; l'une d'entre elles est la représentation
ASCII. Cette convention utilise 7 bits pour représenter un caractère, de telle sorte que 27 caractères sont
possibles dans ce codage. Actuellement, on utilise 16 bits pour les caractères (code Unicode) afin de
pouvoir représenter les caractères de la plupart des langues du monde.
107
Il existe également d'autres méthodes normalisées pour représenter des nombres réels et des nombres à
grande précision contenant plus de chiffres que ne peut en contenir un seul mot. Ces méthodes utilisent
quelques mots pour représenter chaque nombre.
Les registres, qui peuvent contenir un mot de données, sont généralement construits à partir de la
technologie la plus rapide. Ceci les rend très coûteux et ils servent essentiellement à conserver des
informations fréquemment utilisées. Cependant, les ordinateurs ont aussi besoin de stocker de grandes
quantités d'information telles que les instructions d'un algorithme en cours d'exécution et la masse des
données sur lequel l'algorithme travaille. C'est pourquoi les ordinateurs ont une mémoire très importante
dont le fonctionnement est légèrement plus lent mais moins onéreux. C'est ce qu'on appelle la mémoire
centrale dont chaque cellule a une capacité égale à la taille du mot du processeur. Pour des raisons
pratiques, ces cellules sont numérotées consécutivement à partir de zéro. Autrement dit, elles sont
numérotées 0,1,2,3... Ces numéros sont appelés adresses, et chaque cellule a une adresse unique.
Pour stocker une information dans la mémoire centrale, il est nécessaire de fournir à la mémoire une
adresse, ainsi que l'information à stocker. La mémoire conserve alors l'information dans la cellule
mémoire correspondant à l'adresse donnée. Inversement, l'information peut être retrouvée en donnant une
adresse à la mémoire centrale. La mémoire restitue alors l'information contenue à l'adresse donnée.
Une distinction très importante, car déterminante dans le fonctionnement, l'architecture et le prix des
ordinateurs, doit se faire au sein des différentes sortes de mémoire, en fonction de leur temps d'accès,
immédiat ou plus ou moins différé, en fonction de leur vitesse de transmission et de leur capacité de
stockage. Cette distinction permet de hiérarchiser les mémoires en classant en premier les mémoires les
plus rapides mais, du coup, les plus chères: registres du CPU, mémoire cache, mémoire centrale, disque
dur, mémoire d'archivage.
En dehors de mémoires spécialisées ultrarapides comme celles contenant des microprogrammes, les
mémoires les plus rapides mais aux capacités extrêmement limitées sont les registres qui forment des
mémoires de quelques octets au plus, dont les temps de réponse s'inscrivent dans les étapes atomiques du
processeur et dont la rapidité conditionne étroitement la vitesse de son fonctionnement. Elles sont
talonnées par les mémoires cache ou antémémoires du processeur, avec une capacité de l'ordre de quelques
centaines de kilooctets au plus et des temps d'accès voisins de la nanoseconde, alimentant le processeur à
la cadence de ses instructions. Suit la mémoire centrale, de plusieurs centaines de mégaoctets, avec des
temps d'accès décuplés. Arrivent ensuite, après des millisecondes de temps d'accès, les disques
magnétiques, dont la capacité s'exprime cette fois en gigaoctets. Enfin existent les mémoires d'archivage,
108
aux capacités illimitées, ou exprimées en téraoctets, parfois gérées par des serveurs d'archivage et qui
combinent stockage au moindre coût et sauvegarde permettant la remise d'un fichier dans son état antérieur
(backup).
8.3.2 LES ADDITIONNEURS
Dans le système décimal, la table d'addition est la suivante:
0+0=0, retenue 0
0+1=1, retenue 0
0+2=2, retenue 0
0+3=3, retenue 0
...
4+5=9, retenue 0
4+6=0, retenue 1
4+7=1, retenue 1
4+8=2, retenue 1
...
9+9=8, retenue 1
De la même façon, le système binaire comporte sa table d'addition:
0+0=0, retenue 0
0+1=1, retenue 0
1+0=1, retenue 0
1+1=0, retenue 1
Il faut remarquer que la retenue n'est nécessaire que lorsque les deux chiffres sont 1. C'est le cas précis où
la sortie de la porte ET est 1. Par conséquent, la porte ET est idéale pour calculer la retenue. La table
d'addition binaire montre également que la somme de deux chiffres est égale à 1 si et seulement si un
chiffre est 1 et l'autre 0. Par conséquent, la somme peut être obtenue par (premier chiffre AND NOT
second chiffre) OR (second chiffre AND NOT premier chiffre). Nous venons de construire un composant
appelé demi-additionneur qui additionne deux chiffres et produit une somme et une retenue et qui est
entièrement composé de portes.
Un ordinateur doit naturellement être capable d'additionner de grands nombres comportant de nombreux
chiffres. Si la taille du mot est de N chiffres, un additionneur de N chiffres est nécessaire. On l'obtient en
connectant judicieusement des demi-additionneurs prenant en charge les bits de chaque colonne des
chiffres à additionner et la retenue de la colonne précédente. On peut alors admettre que toutes les
opérations mathématiques et logiques peuvent être accomplies à l'aide de portes et de nombres ou de
caractères codés dans le système binaire.
109
8.3.3 LES BUS DE DONNEES
Parce qu'un ordinateur est construit autour d'un certain nombre de composants, il est essentiel qu'il soit en
mesure de transmettre les informations dans les deux sens entre la mémoire et l'additionneur. Ce
mouvement des informations est obtenu grâce aux bus de données. Un bus de données est à la base un
assemblage de fils qui connectent les différents composants entre eux. Le nombre de fils dans un bus de
données correspond généralement à la taille du mot du processeur. Ainsi les données seront transférées
par lots de dimension égale à celle que les composants peuvent manipuler. Par exemple, si l'additionneur
peut additionner des nombres de 64 bits et que la taille de la cellule mémoire est de 64 bits, il est
souhaitable que le bus de données puisse transférer 64 bits de données dans les deux sens entre
l'additionneur et la mémoire. Puisqu'un bus de données ne peut transférer qu'un mot de données à la fois,
il faut nécessairement déterminer quels sont les composants autorisés à utiliser les bus à tout moment.
Cela peut être effectué en connectant chaque composant au bus par l'intermédiaire d'une porte ET dont
l'autre entrée est un signal de contrôle qui ne libère le mot de données que si le bus est libre.
8.3.4 LES HORLOGES ET L'UNITE DE COMMANDE
Nous avons vu qu'un ordinateur consiste en divers composants interconnectés par des bus de données.
Ces composants requièrent souvent des signaux de contrôle pour régulariser leur activité. Un signal de
contrôle détermine par exemple le moment où une bascule stocke son entrée de données. Il en va de même
lorsqu'il faut déterminer le composant qui doit transférer ses données sur un bus. Les signaux de contrôle
émanent d'un composant informatique connu sous le nom d'unité de commande qui a pour fonction de
réaliser le transfert de composant à composant des données qui conviennent au moment voulu, et de
s'assurer que les opérations correctes sur les données sont effectuées.
L'horloge représente un élément important de l'unité de commande; elle produit des signaux à intervalles
réguliers. Ces signaux sont utilisés par l'unité de commande pour s'assurer que tous les composants de
l'ordinateur fonctionnent en synchronisation les uns avec les autres, et que chaque composant dispose d'un
temps suffisant pour mener son opération à terme.
8.4 COMMUNIQUER AVEC LE MONDE EXTERIEUR
Notre discussion a porté jusqu'à présent dans ce chapitre sur l'unité centrale de traitement (UCT) et sur la
mémoire centrale des ordinateurs. Naturellement, les ordinateurs peuvent aussi échanger de l'information
avec le monde extérieur.
110
8.4.1. CONNEXION DES PERIPHERIQUES
Pour réaliser leur fonction d'acquisition ou de restitution des données, les périphériques doivent être
raccordés à l'unité centrale de telle sorte qu'ils puissent recevoir des commandes, transférer les données
depuis ou vers la mémoire centrale, et annoncer la fin d'une opération ou tout autre changement dans leur
état. Le raccordement se définit en termes de câblage, de tensions électriques, de signaux de commande
et d'horloge, le tout formant l'interface E/S. Les modes de raccordement des périphériques aux ordinateurs
varient, non seulement en fonction de la nature des périphériques, mais aussi de l'époque de leur
développement.
Port: un port relie un seul périphérique au travers d'une interface généralement spécialisée pour ce type
particulier de périphérique.
Port parallèle: Le port parallèle effectue des transmissions entre unité centrale et périphérique par
envois de 8 bits en parallèle. Le port parallèle est encore présent dans la plupart des configurations de
PC, mais on tend à lui préférer le bus série USB.
Port sériel: Présents dans les ordinateurs en nombre variable (de 1 à 4) et désignés par le terme COM
suivi de leur numéro de 1 à 4, ils sont destinés principalement à la connexion de modems ou d'autres
dispositifs de télécommunication au débit limité.
Port clavier et port souris: Destinés chacun au raccordement de ces deux périphériques à faible
vitesse.
LAN: Ce port est destiné à la connexion aux réseaux locaux.
Port AGP: Le port AGP (Accelerated Graphics Port) est un port spécialisé, dédié à l'affichage
graphique, pour former une voie rapide acheminant directement la masse importante de données
nécessaires pour afficher les images animées.
Bus: à l'instar du bus interne, intégré dans l'unité centrale, les différents bus externes sont prévus pour
accueillir plusieurs périphériques pouvant être de nature différente, mais utilisant la même interface. Un
bus ne possède qu'une logique limitée, la gestion des opérations d'entrées-sorties devant être assumée pour
sa plus grande part par le périphérique lui-même. Il est dès lors capital, tant pour les constructeurs
informatiques que pour ceux des périphériques, de se mettre d'accord sur une technologie de bus destinée
à devenir le standard.
USB: Le bus USB a été conçu de manière à simplifier et à standardiser l'interface avec les multiples
périphériques. Il est utilisé indifféremment pour la connexion d'imprimantes, de modems ADSL, de
graveurs de CD, d'appareils photo numériques, de Webcams, de disques externes, pour autant que ces
périphériques présentent l'interface USB. Cela permet de limiter le nombre de connecteurs sur
111
l'ordinateur et ne subsisteront bientôt, en sortie de celui-ci, que les ports USB et ceux exigeant un débit
très important.
Firewire: Le bus Firewire trouve son origine dans le monde Apple et est le concurrent direct de l'USB.
Ces deux technologies de bus ont en commun qu'elles peuvent supporter un grand nombre de
périphériques pour un même port, qu'elles peuvent fonctionner en mode isochrone (à débit constant
comme la voix, la musique ou la vidéo) ou asynchrone, et qu'elles sont plug and play, le périphérique
étant reconnu et les pilotes associés automatiquement installés que ce soit pendant le fonctionnement ou
lors de l'allumage de l'ordinateur.
Contrôleur: un contrôleur regroupe plusieurs appareils périphériques de même nature, en économisant
ainsi le nombre de liaisons avec l'unité centrale et en gérant des fonctions communes. Doté de plus en plus
souvent d'un processeur, il s'occupe également de la gestion algorithmique de ce type de périphérique.
Contrôleur IDE: Le contrôleur IDE se présente actuellement sous le nom de EIDE (Enhanced
Integrated Drive Electronics). Il gère les unités à disques magnétiques, les disquettes, les périphériques
CD et DVD.
PCMCIA ou PC Card: Les cartes PCMCIA (Personal Computer Memory Card International
Association) sont destinées à être insérées dans un emplacement prévu à cet effet et caractéristique des
PC portables. Les PC Cards ont le format d'une carte de crédit et se présentent sous différents types
correspondant à des épaisseurs différentes. Les PC Cards peuvent contenir des mémoires flash, des
disques magnétiques miniaturisés, des connexions aux réseaux locaux ou au GSM. Leur compatibilité
de fonctionnement avec un ordinateur particulier et son système d'exploitation demande une vérification
préalable à l'achat.
Contrôleur SCSI: Sur les PC, les contrôleurs SCSI sont plutôt réservés aux configurations haut de
gamme, telles que les serveurs. Il faut considérer le contrôleur SCSI comme un super-contrôleur,
régulant à travers un bus qui lui est propre, les échanges entre des contrôleurs de périphériques et le bus
du PC. Les contrôleurs SCSI se présentent sous la forme d'une carte à enficher sur le bus du PC. Ils
offrent leurs avantages propres, particulièrement la simultanéité dans l'exécution des opérations
d'entrée-sortie et la connexion à haut débit de périphériques externes au boîtier du PC.
8.4.2 PERIPHERIQUES
8.4.2.1 Mémoires externes
Les mémoires externes ou secondaires permettent le stockage de volumes importants de données sous une
forme directement exploitable par les programmes. L'enregistrement des données repose sur les lois du
112
magnétisme dans le cas des disques durs ou sur des variations dans la réflexion de la lumière, dans le cas
du CD. Qu'elles soient de nature magnétique ou optique, les données emplissent un plateau mis en rotation
afin que chacun de ses points enregistrés soit présenté à tour de rôle devant un organe de lecture doublé
selon le cas d'un organe d'écriture et nommé tête. Les têtes elles-mêmes se déplacent radialement afin de
pouvoir balayer l'entièreté du plateau. Un autre type de mémoire de masse (mémoire flash), avec une
capacité relativement limitée, est basé sur des circuits électroniques de type statique.
Disques magnétiques
Les disques magnétiques dits aussi disques durs sont constitués d'un ou plusieurs plateaux rigides tournant
à vitesse élevée et constante. Les faces du plateau sont couvertes d'une mince couche d'un matériau
magnétisable, dont les qualités permettent une densité d'enregistrement très élevée. L'état magnétique d'un
point du plateau peut être modifié par un électro-aimant situé sur la tête de lecture-écriture. Les têtes de
lecture-écriture sont montées au bout d'un bras actionné par un servomécanisme qui leur permet de balayer
transversalement le plateau, s'immobilisant en des positions séparées par des distances infimes, de l'ordre
du micromètre. Les différentes positions transversales d'arrêt du bras déterminent sur chaque face du
plateau autant de pistes concentriques dont l'empilement sur deux faces ou plus est considéré comme un
cylindre. Le temps de déplacement du bras y compris la phase de stabilisation est au minimum de quelques
millisecondes. La longueur de ce temps de latence pour se rendre d'une piste à l'autre explique en partie
la lenteur de celui-ci et pourquoi on préfère n'y faire appel que pour d'importants transferts de données.
Chaque piste est à son tour divisée en secteurs, chaque secteur pouvant généralement contenir 512 octets.
Par exemple, un disque pourrait contenir 1024 pistes, chacune comprenant 64 secteurs. La capacité des
disques durs est en augmentation constante et aujourd'hui autour des centaines de Gigaoctets (GB ou
Gigabytes). Le compartimentage des surfaces du disque en cylindres, pistes et secteurs est une opération
nommée formatage. Elle consiste à écrire sur le disque des informations qui serviront de balises et entre
lesquelles les données pourront être écrites et retrouvées. Grâce à ces balises, le bras pourra retrouver
l'aplomb de la piste et pourra lire les secteurs qu'elles encadrent.
En cas de détérioration accidentelle de la structure physique ou logique du disque, il peut être nécessaire
de procéder à un nouveau formatage, mais il faut savoir qu'il en résultera l'effacement total de toutes les
données se trouvant sur le disque, et leur perte irrémédiable si elles n'ont pas pu être sauvegardées par
copie préalable sur un autre support.
113
CD et DVD
Le Compact Disk est un support avec une seule face contenant les données enregistrées. L'enregistrement
des données se fait par l'entremise de déformations ponctuelles de la couche du support, déformations
entravant la réflexion d'un rayon laser. Soit la lumière est réfléchie par l'absence de déformations et le bit
est à 1, soit elle est plutôt dispersée par celle-ci et le bit est à 0. La lecture d'un CD se fait par la mise en
rotation du CD et le déplacement transversal d'un dispositif optique projetant un rayon laser vers le CD et
d'un capteur qui mesure la quantité de lumière réfléchie.
Le CD-ROM (Read Only Memory) comporte une couche de données constituée par un matériau
réfléchissant dans lequel sont gravées des micro-cuvettes qui provoquent la dispersion de la lumière
incidente. Cette couche de données est pressée une fois pour toutes lors de sa création par un appareillage
spécialisé en production de masse. Le CD-ROM constitue un support bien adapté à la diffusion à grande
échelle de gros volumes d'informations telles que des musiques et des images.
Le CD-R (Recordable) est un CD inscriptible dont la couche de données peut être modifiée une seule fois
par un appareil nommé graveur de CD. Il est possible d'écrire à plusieurs reprises (sessions) sur un CD-
R, mais à des endroits différents. Une partie écrite ne peut plus être modifiée. Le CD-RW (ReWritable)
est un CD semblable au CD-R, mais dont la couche de données peut être remise dans son état original de
transparence avant d'être à nouveau modifiée. Ce processus peut être répété un grand nombre de fois par
un graveur de CD.
Le DVD (pour Digital Video Disk, et ultérieurement Digital Versatile Disk pour exprimer sa polyvalence)
reprend les principes de fonctionnement du CD en les optimisant considérablement suite aux progrès de
la technique.
Mémoires flash
Outre leurs usages pour des mémoires spécialisées au sein des ordinateurs, les mémoires flash sont
utilisées pour le stockage de données externes de deux manières différentes, qui se distinguent par la
capacité et la connectivité. Ce type de mémoire de masse est basé sur des circuits électroniques de type
statique. Le Stick USB, dont la capacité de mémorisation est sans cesse croissante, en est une application
remarquable connectable à l'ordinateur via le port USB. De plus, avec l'arrivée massive des appareils
électroniques (appareils photo, caméras vidéo, etc.) sont arrivés des supports de stockage inhérents à ces
derniers, afin de conserver en mémoire des films photo et des CD, des fichiers d'images, des fichiers de
musique, etc.
114
8.4.2.2 Autres périphériques
Le clavier
L'enfoncement et le relâchement d'une touche du clavier se traduit par la modification d'un niveau résistif
ou capacitif. Un composant électronique interne au clavier analyse des centaines de fois par seconde l'état
de chaque touche. A chaque variation d'état, et pour autant qu'elle soit significative dans le temps, il génère
un code touche qui décrit l'emplacement sur le clavier de la touche. Ensuite, il place ce code dans un
registre d'interface E/S qui est alors prélevé par un programme de l'unité centrale.
Le clavier informatique demeure le moyen le plus utilisé pour saisir et stocker des documents écrits. Une
grande variété d'appareils de lecture ou de senseurs automatiques assure de leur côté l'acquisition de
données dans des domaines allant de la médecine à l'industrie, pour des applications bien définies et au
contenu documentaire très spécifique. La reconnaissance de la voix fait d'immense progrès et la dictée de
texte ou de commandes est une réalité. La lecture par scanner d'une page imprimée, suivie de l'analyse de
chaque élément de l'image obtenue et de la transposition des caractères reconnus en codes de l'alphabet
informatique (OCR ou Optical Character Recognition), permet d'éviter la recopie de textes imprimés. La
reconnaissance de l'écriture manuscrite peut aussi, dans certains cas, supplanter le clavier.
La souris
Avec une interface graphique, les déplacements du curseur sur l'écran se font en fonction des mouvements
de la souris, et les objets sur l'écran peuvent être activés par des simples ou doubles clicks sur les boutons
de la souris. Le concept de la souris comme outil de dialogue a pris naissance dans les laboratoires de
recherche de Xerox. Apple a été le premier à mettre sur le marché des micro-ordinateurs exploitant ce
concept, Microsoft s'y ralliant ultérieurement avec l'interface Windows. Des outils de pointage plus précis
et beaucoup plus coûteux que la souris, comme les tablettes graphiques, sont utilisés pour réaliser des
dessins et des plans. D'autres outils de pointage tels les manettes de jeux sont apparentés à la souris.
L'écran
Bien que presque disparu, voyons comment fonctionne un écran à tube cathodique (Cathodic Ray Tube
ou CRT) monochrome. Sous l'effet de champs magnétiques qui provoquent sa déflection, un mince
faisceau d'électrons émis depuis le fond du tube, puis accéléré et orienté par des plaques de déflection,
balaie en une succession de lignes horizontales, composées de points appelés pixels, la surface de l'écran.
Celle-ci est couverte sur sa face interne d'un matériau phosphorescent qui émet de la lumière sous l'effet
115
de l'impact du faisceau d'électrons, l'intensité de l'émission étant fonction de celle du faisceau d'électrons.
Le matériau doit continuer à émettre de la lumière (effet de rémanence) pendant une durée égale à celle
du balayage total de l'écran. Pour obtenir une image en couleurs, il est fait usage de trois faisceaux, chacun
correspondant à chacune des trois couleurs fondamentales utilisées en mode additif. rouge, vert, bleu
(signaux Red, Green, Blue ou RGB). A chaque pixel sont associées trois taches ou sous-pixels, dont la
composition des intensités individuelles reconstitue pour l'œil humain la couleur du pixel vu comme un
ensemble. La proximité (pitch) des sous-pixels au sein d'un pixel est un des critères de qualité d'un écran.
La dimension de l'écran est exprimée par sa diagonale exprimée en pouces et détermine la quantité
d'informations qui peuvent être affichées avec une lisibilité suffisante. La résolution représente le nombre
de pixels affichés par ligne ainsi que le nombre de lignes, par exemple 640x480 pour l'ancien mode VGA,
mais aujourd'hui des résolutions de l600xl200 sont possibles.
Les écrans à cristaux liquides (Liquid crystal display ou LCD) sont aussi dits écrans plats car constitués
d'une superposition de plaques minces et ne présentant pas l'embonpoint caractéristique du tube
cathodique. Leur principe de fonctionnement repose sur la propagation de la lumière polarisée et sur la
propriété qu'ont certains cristaux de modifier, en fonction d'une charge électrique qui leur est appliquée,
le sens de la polarisation de la lumière qui les traverse.
Les imprimantes
Les imprimantes peuvent être classées en deux catégories principales: laser et jet d'encre. La résolution
linéaire des imprimantes est exprimée en points ou dots par pouce (dpi). Le point ou dot constitue la plus
petite partie imprimable et, à ce titre, correspond au pixel des écrans.
L'imprimante laser est essentiellement constituée d'un tambour dont la surface reçoit une charge électrique
en fonction de l'éclairement fourni par un rayon laser ou une source lumineuse équivalente. L'éclairement
du tambour est modulé en fonction des dots de l'image à imprimer. Le tambour est mis en rotation et se
charge de fines particules d'encre (toner) pour former l'image de la page. Les particules de toner sont
ensuite attirées vers la surface de la feuille de papier qui défile de manière synchrone au tambour. Le toner
est enfin fixé sur la feuille de papier par la chaleur d'un four.
L'imprimante à jet d'encre est composée essentiellement d'une tête d'impression se déplaçant sur un axe
transversalement par rapport à la feuille de papier. Au cours de ce déplacement, la tête d'impression
projette sur le papier de minuscules gouttelettes d'encres de différentes couleurs. Lorsque la tête arrive au
bord de la feuille, cette dernière est avancée d'un pas et la tête reprend sa course.
116
CHAPITRE 9 : L'EXECUTION DES ALGORITHMES
9.1 INTRODUCTION
L'ordinateur, en tant que machine, n'est pas très pratique, et ce pour plusieurs raisons.
1) Il n'existe pas de méthode simple pour entrer un programme dans la mémoire de l'ordinateur.
2) Les possibilités d'entrée/sortie (E/S) sont difficiles à utiliser puisque le programmeur doit connaître
les particularités de chaque périphérique. Il doit également s'assurer que son programme examine les
registres d'état des périphériques pour voir à quel moment le processus d'entrée ou de sortie s'achève;
il doit fournir des modules de traitement des interruptions. L'organisation détaillée des transactions
E/S détourne une partie importante de l'effort de programmation de la tâche la plus importante, qui est
celle de l'implantation de l'algorithme.
3) Il n'existe pas de méthode simple pour qu'un programme ou ses données dépasse la capacité de la
mémoire centrale de l'ordinateur.
4) Toutes les ressources informatiques sont consacrées à exécuter un seul programme. Le programme
pourrait n'occuper qu'une fraction de la mémoire centrale et n'utiliser qu'un ou deux périphériques,
mais pourtant le reste de la mémoire et les autres périphériques sont inactifs jusqu'à la fin de l'exécution
du programme. Si le prix de l'ordinateur est élevé, la sous-utilisation de ses ressources coûte cher.
5) L'ordinateur doit être programmé en langage machine. Pour des raisons expliquées plus loin, le
langage machine est tout à fait inapproprié pour la plupart des tâches de programmation.
Le matériel de l'ordinateur a donc besoin de possibilités supplémentaires pour rendre son exploitation plus
aisée et plus économique. Ces possibilités sont données par une série de programmes généralement fournis
par le constructeur. Les programmes font partie du système informatique au même titre que le matériel
lui-même, et sont souvent appelés logiciels de base ou programmes système. Dans ce chapitre, nous allons
décrire les composants essentiels du logiciel système, en insistant particulièrement sur deux de ses aspects.
(1) Le système d exploitation
Un ordinateur est équipé d'un seul système d'exploitation (bien qu'un constructeur puisse en offrir
plusieurs au choix), qui a trois fonctions essentielles:
1) il permet à l'utilisateur de ne plus se préoccuper de quelques-unes des caractéristiques ingrates de
l'ordinateur, telles que la capacité mémoire et les idiosyncrasies de ses possibilités E/S;
117
2) il offre une grande souplesse dans la manipulation des programmes et des données, de telle sorte qu'un
utilisateur peut, par exemple, demander qu'un programme particulier soit exécuté avec un ensemble
particulier de données en entrée, et solliciter une sortie imprimée;
3) il permet le partage des possibilités de l'ordinateur entre plusieurs utilisateurs, de manière simultanée.
Les systèmes d'exploitation seront décrits en détail dans la section 9.3.
(2) Les traducteurs de langage (compilateurs, interpréteurs, ... )
Les traducteurs de langage traduisent des programmes écrits en langages évolués (PASCAL, C, C++, ...)
dans le langage machine de l'ordinateur concerné. Un traducteur différent est nécessaire pour chaque
langage évolué utilisé. Les traducteurs sont divisés en deux catégories: les interpréteurs et les
compilateurs. Elles seront toutes deux décrites dans la section 9.2.
(3) Les éditeurs
Pendant la mise au point d'un programme, il est généralement nécessaire d'apporter des modifications
fréquentes (corrections d'erreurs, ajouts de modules, et ainsi de suite). Pour éviter une saisie trop
importante, il est d'usage de conserver le programme dans une mémoire auxiliaire et d'accomplir les
modifications in situ. Le programme système utilisé pour apporter ces modifications est appelé un éditeur.
En fait, un éditeur peut être non seulement utilisé pour modifier des programmes mais encore pour
modifier tout autre élément d'information textuelle susceptible d'être conservé en mémoire auxiliaire. La
nature de cette information varie selon les applications informatiques: une documentation de programme,
des manuels d'utilisateurs, des lettres types, des bibliographies, des catalogues et le texte de ce syllabus.
Les possibilités offertes par un éditeur permettent à l'utilisateur de localiser, de supprimer ou de remplacer
des parties spécifiques d'un texte et d'en insérer là où c'est nécessaire. La plupart des éditeurs sont utilisés
interactivement: l'utilisateur donne des commandes à l'éditeur à partir d'un terminal et examine les
modifications apportées.
(4) Les chargeurs
Certains traducteurs de langage stockent les programmes traduits dans une mémoire auxiliaire jusqu'à ce
qu'ils soient appelés pour être exécutés. Le programme système chargé du transfert des programmes à
partir de la mémoire est appelé chargeur. La plupart des chargeurs sont également capables d'associer des
modules de programmes traduits en différentes occasions à l'intérieur d'un seul programme en langage
118
machine. Cette caractéristique est particulièrement utile pour incorporer des modules "bibliothèque",
souvent utilisés dans un programme, sans avoir à les traduire à plusieurs reprises.
9.2 TRADUCTEURS DE LANGAGE DE PROGRAMMATION
La fonction d'un traducteur de langage est, comme nous venons de l'indiquer, de traduire en langage
machine des programmes écrits en langage évolué. Les programmes peuvent ensuite être exécutés par un
interpréteur microprogrammé qui transforme les instructions en langage machine en signaux de
commande pour l'exécution.
Il y a deux sortes d'entités dans un programme en langage évolué pour lesquelles une traduction est
nécessaire: les instructions et les structures de données. Les instructions d'un langage évolué sont
généralement plus puissantes que celles d'un langage machine, ainsi, un processus représenté par une seule
instruction en langage évolué en nécessitera plusieurs en langage machine. C'est pourquoi chaque
instruction en langage évolué est généralement traduite par plusieurs instructions en langage machine,
processus pouvant être considéré comme un affinement supplémentaire de l'instruction en langage évolué.
Les structures de données pouvant être manipulées par un langage évolué (par exemple des listes, des
séquences de caractères, des arbres) ne sont pas directement exploitables en langage machine. De telles
structures doivent, au contraire, être représentées sous forme de bits, de nombres et d'adresses; le
traducteur doit transformer les structures de données évoluées en une représentation au niveau machine.
Généralement parlant, deux stratégies différentes peuvent être adoptées pour la traduction de programmes
évolués: il s'agit de l'interprétation et de la compilation.
9.2.1 L'INTERPRETATION
L'interprétation consiste à traduire et à exécuter un programme évolué, instruction par instruction,
l'exécution de chaque instruction précédant la traduction de la suivante. L'interprétation est accomplie par
l'interpréteur. Dans la plupart des cas, l'interpréteur est équipé d'un ensemble de modules de série. Chacun
d'entre eux consiste en une séquence d'instructions en langage machine correspondant à un type particulier
d'instructions en langage évolué. De ce fait, pour traduire chaque instruction évoluée, l'interpréteur
l'examine simplement afin de savoir à quel type elle appartient et de choisir le module devant être appelé.
Les éléments de données manipulés par une instruction évoluée (c'est-à-dire les opérandes de l'instruction)
sont entrés dans le module comme paramètres. Lorsque le module a été exécuté, le contrôle est rendu à
119
l'interpréteur qui répète ensuite le cycle pour l'instruction suivante. L'interpréteur détermine le type de
chaque instruction évoluée en utilisant les règles syntaxiques du langage concerné. Si une instruction
comporte une erreur de syntaxe, l'interpréteur la détecte et la signale; mais puisque l'erreur rend souvent
l'instruction ambiguë, aucune tentative ne sera faite pour l'exécuter.
La vitesse de traduction dépend en grande partie de la syntaxe du langage traduit: plus complexe est la
syntaxe, plus lente est la traduction. Puisqu'un interpréteur traduit chaque instruction évoluée à chaque
fois qu'elle est exécutée, il est avantageux de conserver une syntaxe aussi simple que possible, et c'est un
des principaux objectifs de conception de la plupart des langages évolués normalement traduits par
l'interprétation. En Basic, par exemple, langage conçu dans l'esprit d'une traduction interprétative, le type
de chaque instruction n'est déterminé que par son premier mot. L'interpréteur microprogrammé gagne
également en rapidité à partir de la syntaxe très simple du langage machine qu'il interprète. Le type d'une
instruction en langage machine est déterminé par son code opération, et son unique opérande est constituée
par les données stockées dans la cellule mémoire indiquée par son adresse.
9.2.2 LA COMPILATION
Lorsqu'un programme évolué est traduit par un interpréteur, la traduction s'effectue en fonction de
l'exécution. Par conséquent, si une instruction doit être exécutée plusieurs fois (dans une boucle, par
exemple), elle doit également être traduite plusieurs fois, puisque l'exécution et la traduction de chaque
instruction sont inextricablement liées. Ceci peut constituer une source de coût inutile, puisque la
retraduction est nettement redondante. Le coût dû à une nouvelle traduction est inacceptable, en particulier
dans l'une des circonstances suivantes:
1) le temps de traduction d'une instruction dépasse celui de son exécution;
2) le programme est fréquemment exécuté sans aucune modification (par exemple, un programme de
bulletins de salaire);
3) la vitesse d'exécution est prioritaire (par exemple, quand les réponses doivent être rapides comme dans
le cas de réservations auprès de compagnies aériennes).
Pour éviter un tel coût, il faut adopter une stratégie différente de traduction et d'exécution de programmes.
Cette stratégie sépare la traduction de l'exécution en insistant sur le fait que tout le programme doit être
traduit avant son exécution. La traduction d'un programme évolué est appelée compilation. Elle est
exécutée par un programme système, le compilateur. L'exécution ne commence que lorsque le programme
évolué a été entièrement compilé. Le programme évolué initial est le programme source, et celui résultant
de la compilation est le programme objet. C'est ce dernier qui est exécuté.
120
Puisque la compilation et l'exécution constituent des processus distincts, un programme objet, lorsqu'il a
été produit par un compilateur, peut être exécuté plusieurs fois sans que soit nécessaire une autre
compilation du programme source. Il suffit de trouver un moyen de stocker le programme objet jusqu'à
ce que son exécution soit à nouveau requise. La mémoire auxiliaire d'un ordinateur est généralement
utilisée à cette fin, et le programme objet est transféré par un chargeur en mémoire lorsque l'exécution est
requise.
9.3 LES SYSTEMES D'EXPLOITATION
9.3.1 GENERALITES
Le système d'exploitation est sans doute la partie la plus importante et la plus complexe des logiciels de
base accompagnant un ordinateur. Il est chargé de fournir les dispositifs qui rendent l'utilisation de
l'ordinateur plus simple et plus rentable. Tous les ordinateurs (à l'exception de quelques microordinateurs
très rudimentaires) ont un système d'exploitation généralement fourni par le constructeur, et souvent, le
système d'exploitation est le produit d'un effort de conception et de développement comparable à celui
fourni pour l'équipement de l'ordinateur. Les raisons pour lesquelles les systèmes d'exploitation sont si
complexes apparaîtront progressivement au long de cette section.
Un système d'exploitation accomplit de multiples tâches minutieuses qui peuvent en gros être classées de
la manière suivante :
1) Il permet à l'utilisateur où à d'autres logiciels de base de ne plus se préoccuper de certaines
caractéristiques de l'équipement de l'ordinateur. Certaines des caractéristiques les plus difficiles
concernent la manipulation des dispositifs d'entrée et de sortie (E/S), et le système d'exploitation joue
un rôle fondamental en simplifiant l'utilisation de ces dispositifs.
2) Il permet de manipuler les programmes et les données avec une plus grande aisance. Le système
d'exploitation gère l'interprétation des commandes requises et organise l'ensemble complexe des
actions nécessaires pour son exécution.
3) Il permet également de partager les ressources informatiques entre plusieurs utilisateurs simultanés.
L'objectif recherché est l'augmentation de la disponibilité de l'ordinateur pour ses utilisateurs, et en
même temps l'optimisation de l'utilisation de ressources telles que le processeur, la mémoire et les
périphériques.
Pour apprécier les fonctions du système d'exploitation, il suffit de se demander comment fonctionnerait
un ordinateur qui n'en posséderait pas. Supposons, par exemple, que l'ordinateur doive exécuter différents
121
travaux pour un nombre donné d'utilisateurs. (Un travail peut consister en une série d'actions nécessaires
pour exécuter le programme d'un utilisateur. Dans un cas élémentaire, il peut impliquer une compilation
du programme source, suivie du chargement et de l'exécution du programme objet.) Si l'ordinateur n'a pas
de système d'exploitation, l'utilisateur doit passer, pour que son travail soit exécuté, par toute une série
d'étapes telles que:
1) présenter le programme source au dispositif d'entrée correspondant;
2) apprendre au compilateur à lire le programme source à partir du dispositif d'entrée, le compiler et
ranger le programme objet obtenu dans une mémoire auxiliaire;
3) apprendre au chargeur comment transférer le programme objet de la mémoire auxiliaire vers la
mémoire centrale;
4) placer les données nécessaires au programme dans le dispositif d'entrée approprié;
5) lancer l'exécution du programme objet;
6) recueillir les données en sortie sur le dispositif que le programme utilise (exemple une imprimante).
Avec cette procédure, le rendement de l'ordinateur (c'est-à-dire le nombre de tâches qu'il accomplit en un
temps donné) est limité par la rapidité à laquelle chaque utilisateur peut presser les touches appropriées et
manipuler les dispositifs E/S employés par son programme. De telles activités humaines sont d'une lenteur
fastidieuse si on les compare à la vitesse d'exécution du processeur, aussi est-il clair que l'ordinateur n'est
pas utilisé de manière rentable.
Une des premières choses à faire pour augmenter le rendement est de confier la manipulation des touches
et des dispositifs E/S à un opérateur spécialisé, mais si l'on considère la grande disparité entre l'homme et
les vitesses d'exécution de l'ordinateur, l'amélioration est encore marginale. Une mesure plus efficace
consiste à automatiser la séquence d'opérations nécessaires à l'exécution d'un travail, de telle sorte que
l'intervention humaine soit réduite au minimum. Cela peut être fait en introduisant un petit programme de
contrôle dont la fonction est de lancer le compilateur, le chargeur et le programme objet aux moments
adéquats. Il ne reste plus à l'opérateur qu'à manipuler les dispositifs E/S.
Grâce à la réduction maximale de l'intervention humaine, le rendement de l'ordinateur est maintenant
limité par la vitesse à laquelle il peut accomplir les E/S. Une augmentation du rendement ne peut être
accomplie que lorsqu'on supprime la limitation des E/S: il faut pour ce faire utiliser les interruptions de
programme, signaux envoyés par les dispositifs qui indiquent au processeur central qu'un transfert de
données est achevé. Un dispositif d'interruption permet au processeur de lancer un transfert E/S, de
poursuivre le traitement pendant que le transfert s'effectue et de recevoir une notification par le moyen
d'une interruption lorsque le transfert est achevé.
122
La capacité de faire se chevaucher des transferts E/S avec le traitement ne peut être exploitée que si le
processeur peut accomplir une autre tâche pendant chaque transfert. Ce que permet la
multiprogrammation qui est le fait de pouvoir stocker et traiter les programmes et les données de plusieurs
tâches en même temps en mémoire centrale. Pendant qu'un travail attend une opération d'entrée ou de
sortie, le processeur peut exécuter une autre tâche. La fin du transfert E/S est signalée par une interruption,
et le travail en attente peut être repris soit immédiatement soit quand le second travail sollicite à son tour
une entrée ou une sortie. C'est ce qu'illustre la figure 9.1 qui montre l'exécution de trois tâches dans un
système multiprogrammé. Pour simplifier, les trois tâches de notre exemple sont identiques, chacune
requérant un temps d'exécution d'une ms avant et après un transfert E/S qui dure aussi 1 ms. La figure
9.1(a) montre l'exécution de trois tâches en séquence, dans un système non multiprogrammé. La figure
9.1(b) montre l'effet de la multiprogrammation. Il faut remarquer que, dans ce cas, le processeur est
constamment occupé et que les trois tâches sont accomplies en 6 ms. Dans la figure 9.1(a), le processeur
est inactif pendant 3 ms, et les trois tâches prennent 9 ms. Dans ce cas, la multiprogrammation fait passer
le rendement d'un taux moyen de 333 tâches par seconde à 500 tâches par seconde, soit une augmentation
de 50%. Naturellement, on ne peut s'attendre à ce que le traitement et les exigences E/S des différentes
tâches se complètent toujours aussi facilement que dans notre exemple. Cependant, plus il y a de tâches
en mémoire, plus grande est la possibilité que l'une d'entre elles soit prête à être exécutée.
Figure 9.1: Effets de la multiprogrammation
La multiprogrammation a d'autres avantages. Elle améliore l'utilisation de certaines ressources, comme
les périphériques, puisque les tâches stockées en mémoire peuvent être choisies à tout moment, de sorte
123
que leurs besoins en ressources se complètent et utilisent toutes (ou presque) les ressources disponibles.
La multiprogrammation permet également un accès simultané à l'ordinateur par plusieurs utilisateurs.
Chaque utilisateur peut lancer des tâches à partir de son terminal et celles-ci peuvent être exécutées en
même temps que des tâches lancées par d'autres utilisateurs à partir d'autres terminaux. La progression de
chaque tâche, ainsi que les résultats qu'elle produit, peuvent être immédiatement renvoyés au terminal
d'origine. Ce mode d'opération est dit à multi-accès ou en temps partagé (ce dernier terme provient du
partage de temps processeur réparti entre les utilisateurs). L'implantation de la multiprogrammation
nécessite des ajouts importants au système d'exploitation embryonnaire décrit précédemment, en
particulier des modules pour accomplir les fonctions suivantes:
1) La distribution. Faire passer le processeur d'une tâche à une autre lorsqu'il le faut.
2) La gestion des interruptions. Interpréter chaque interruption comme un signal de terminaison du
transfert E/S, et de ce fait reprendre l'exécution de la tâche qui requérait ce transfert.
3) L'affectation des ressources. L'affectation des ressources informatiques aux tâches selon les besoins.
Les ressources comportent la mémoire, les dispositifs E/S et le processeur lui-même. Ce dernier est
cependant suffisamment important pour être étudié séparément.
4) La protection des ressources. Il faut s'assurer qu'aucune tâche ne peut accéder à une ressource qui ne
lui a pas été affectée. C'est un point essentiel si les tâches doivent être protégées des erreurs
accidentelles ou dues à la malveillance.
5) L'ordonnancement. Il s'agit de décider de la priorité de la tâche à exécuter lorsqu'une autre vient de se
terminer. Les programmes et les données en attente sont normalement stockés en mémoire auxiliaire
et transférés en mémoire centrale avant le début de l'exécution. La décision de la priorité des tâches à
effectuer est basée sur des facteurs tels que la priorité de chaque tâche, les ressources actuellement
disponibles et les ressources dont chaque tâche a besoin.
L'optimisation du rendement et de l'utilisation de ressources par la multiprogrammation n'est obtenu qu'au
prix d'une augmentation considérable de la complexité du système d'exploitation. En résumé, notre désir
d'augmenter le rendement de la partie matérielle d'un ordinateur de base nous a conduit à introduire un
système d'exploitation comportant de nombreuses fonctions. Certaines de ces fonctions facilitent
également l'utilisation de l'ordinateur. Par exemple, la gestion des interruptions décharge le programmeur
des tâches d'écriture des parties de programme destinées à détecter le moment où les transactions E/S sont
terminées. Dans les sections suivantes, nous verrons comment certaines de ces fonctions peuvent être
implantées et quels sont les algorithmes utilisés à cet effet.
124
9.3.2 LE DISTRIBUTEUR
Nous avons vu précédemment que l'exécution d'une tâche pouvait impliquer l'exécution d'un certain
nombre de programmes différents, tels qu'un compilateur, un chargeur et un programme-objet compilé.
Les fonctions proposées par le système d'exploitation comportent aussi l'exécution de programmes
différents qui font partie du système d'exploitation. L'exécution d'un programme est un processus et le
système d'exploitation est chargé de lancer et de coordonner les différents processus devant être exécutés.
Certains de ces processus exécutent des fonctions du système d'exploitation (comme l'ordonnancement et
la gestion des E/S), alors que d'autres (comme la compilation) sont lancés sur l'ordre des utilisateurs.
L'existence simultanée de plusieurs processus implique qu'ils se partagent l'UCT (Unité Centrale de
Traitement). C'est le cas même lorsque l'ordinateur n'a qu'un seul utilisateur, puisque les processus lancés
à la demande de l'utilisateur doivent partager l'UCT avec des processus qui font partie du système
d'exploitation. Lorsque la multiprogrammation est en vigueur, le degré de répartition est augmenté de
manière équivalente. Le partage est effectué en faisant passer à plusieurs reprises l'UCT d'un processus à
un autre, de sorte que chaque processus soit exécuté juste avant de perdre l'UCT au profit d'un autre
processus. Le changement est généralement si rapide (tous les cinquantièmes de seconde, par exemple)
que tous les processus semblent être exécutés simultanément, alors que naturellement l'UCT ne peut être
affectée qu'à un seul processus à la fois.
Si plusieurs UCT sont disponibles, certains processus peuvent réellement être exécutés simultanément.
Pourtant, il y a généralement moins d'UCT que de processus, et de ce fait les UCT doivent continuer à
passer d'une tâche à une autre. Les ordinateurs qui ont assez d'UCT pour en affecter une à chaque
processus sont encore assez rares sur le marché mais certains laboratoires de recherche travaillent déjà
avec des ordinateurs comptant plusieurs milliers d'UCT. Dans les sections suivantes, nous supposerons
que le partage de l'UCT est nécessaire; toutefois nous ne nous en tiendrons pas aux machines comportant
une seule UCT.
Dès qu'un processus est lancé, il peut être dans l'un des trois états suivants (voir la figure 9.2):
1) En cours d'exécution: le processus est exécuté par une UCT.
2) Prêt: le processus est exécutable et attend qu'une UCT lui soit affectée. Tous les processus prêts sont
candidats à l'affectation d'une UCT.
3) Bloqué: le processus ne peut être traité tant qu'un résultat, comme la fin d'un transfert E/S, n'apparaît
pas. Les processus bloqués ne sont pas candidats à l'affectation d'une UCT.
125
Un processus en cours d'exécution est bloqué lorsqu'il requiert un transfert E/S, et il le reste jusqu'à la fin
du transfert. A ce point, le processus est prêt et son exécution peut être reprise dès qu'une UCT lui a été
affectée. C'est pourquoi les processus qui alternent le calcul avec les E/S de manière répétitive alternent
entre les états d'exécution, de blocage et de disponibilité.
Figure 9.2: Transitions entre les trois états possibles d'un processus
Dans certains systèmes d'exploitation, le lancement d'un transfert E/S est la seule occasion qu'a l'UCT
d'être déconnectée d'un processus. Ce type de situation peut conduire à la monopolisation d'une UCT par
un seul processus qui n'accomplit des E/S que très rarement. Pour un partage plus équitable des UCT, il
est indispensable de limiter la période pendant laquelle un processus peut se dérouler de manière continue,
et de déconnecter l'UCT de tout processus atteignant la limite qui lui est impartie. Le temps alloué à un
processus pour une exécution continue est appelé quantum (ou tranche de temps). Un processus utilisant
plus que son quantum change d'état. Il passe de l'exécution à la disponibilité, libérant son UCT pour un
autre processus en attente. Le processus reçoit un nouveau quantum lorsqu'il est de nouveau sélectionné
pour être exécuté. Le choix de la taille du quantum dépend de nombreux facteurs complexes, tels que le
temps qu'a déjà utilisé le processus, celui de la distribution par le transfert et les contraintes d'équité.
La responsabilité de commutation des UCT entre les processus appartient à un module du système
d'exploitation, le distributeur. Le distributeur est normalement appelé dans les circonstances suivantes:
1) un processus en cours d'exécution demande un transfert E/S ou une ressource; il est donc bloqué;
2) le quantum d'un processus en cours d'exécution expire, indiquant que l'UCT devra être réaffectée
3) l'exécution d'un processus se termine.
Dans chacun de ces cas, le distributeur doit choisir un des processus prêts pour une prochaine exécution.
Les critères de sélection visent généralement à assurer un partage équitable des UCT entre tous les
processus, mais dans certains cas, la sélection peut se faire en faveur des processus dont la priorité a été
126
reconnue (peut-être parce qu'ils accomplissent des fonctions importantes du système ou sont associés à
des tâches urgentes). La sélection par le distributeur provoque le changement d'état du processus (de "prêt
" à en "cours d'exécution"). La figure 9.2 montre les trois états d'un processus et les transitions entre eux.
9.3.3 LA GESTION DE LA MEMOIRE
Une des fonctions les plus importantes du système d'exploitation est la gestion des ressources de mémoire
de l'ordinateur. La gestion de la mémoire a trois aspects fondamentaux:
1) Affectation: pour qu'un processus soit exécuté il doit lui être affecté une mémoire suffisante pour
stocker son programme et ses données.
2) Protection: il est important qu'aucun processus ne puisse avoir accès à une partie quelconque de
mémoire qui ne lui soit pas affectée. La protection est essentielle pour éviter que des erreurs de
programmation affectent d'autres processus et pour éviter une consultation non autorisée des données
d'autres processus, ou des interférences malveillantes dans l'exécution d'un autre processus.
3) Utilisation: la mémoire est une ressource précieuse puisque c'est le seul endroit où les programmes
d'exécution du processus peuvent résider. C'est pourquoi il est important de l'utiliser au mieux, en
l'affectant autant que possible à tout moment et en essayant de s'assurer que la mémoire comporte en
permanence des processus prêts à être exécutés.
Pour atteindre une utilisation maximale, le système d'exploitation doit être libre d'affecter à un processus
n'importe quelle partie de la mémoire disponible. Il peut d'ailleurs avoir besoin de déplacer un programme
et des données d'un processus d'une zone mémoire à une autre, de sorte que, par exemple, plusieurs zones
non affectées puissent être fusionnées à l'intérieur d'une zone plus importante et utilisable. Ceci signifie
que lorsqu'un programme est écrit et compilé, ni le programmeur ni le compilateur ne peuvent savoir où
le programme va résider en mémoire lors de l'exécution. Comment un compilateur peut-il générer des
adresses exactes alors qu'il ignore quelle zone mémoire le programme objet occupera durant l'exécution?
La réponse tient en une distinction nette entre les adresses du programme générées par un traducteur de
langage et les adresses mémoire dans lesquelles le programme objet doit par la suite résider. Le traducteur
de langage suppose que toute la mémoire est disponible et génère des adresses de programme partant de
zéro: ces adresses doivent ensuite être transformées en adresses mémoire correspondantes pour la zone de
mémoire affectée au programme objet par le système d'exploitation. La transformation des adresses du
programme en adresses mémoire est généralement accomplie par l'UCT au moment où le programme
objet est exécuté. Voyons deux méthodes couramment utilisées pour cela et le type de gestion de la
mémoire qui en résulte.
127
Les registres de base et de limite
La première méthode nécessite un registre supplémentaire dans l'UCT. Ce registre, le registre de base,
contient l'adresse de base du processus en cours d'exécution, c'est-à-dire l'adresse de la première cellule
mémoire affectée au processus. L'UCT transforme chaque adresse de programme utilisée par le processus
en l'adresse mémoire correspondante, en y ajoutant simplement le contenu du registre de base.
Soient deux processus A et B disposant de zones mémoire (figure 9.3). Les adresses programme du
processus A sont comprises entre 0 et 1199 et les cellules mémoire qui lui sont affectées sont comprises
entre 1500 et 2699. Les adresses programme du processus B sont comprises entre 0 et 799 et les cellules
mémoire entre 2800 et 3599. Lorsque le distributeur choisit de lancer l'exécution du processus A, il charge
l'adresse de base 1500 dans le registre de base (figure 9.3(a)). L'UCT calcule les adresses mémoire
correspondantes en ajoutant le contenu du registre de base à chaque adresse programme utilisée pendant
l'exécution. Chaque adresse mémoire est par conséquent supérieure de 1500 à l'adresse programme
correspondante, reflétant la position du processus A en mémoire. De même lorsque le processus B est
lancé, le registre de base est chargé avec l'adresse de base 2800 (figure 9.3(b)) et à chaque adresse
programme utilisée pendant l'exécution de B est ajouté 2800 pour produire l'adresse mémoire adéquate.
Figure 9.3: Transformation d'adresse par un registre de base
128
Nous pouvons remarquer au passage que les processus A et B peuvent utiliser les mêmes adresses de
programme, mais que celles-ci doivent être transformées de manière appropriée en adresses mémoire
différentes. L'adresse programme 135 doit être par exemple transformée en l'adresse mémoire 1635
lorsque A est exécuté et en adresse mémoire 2935 lorsque B est exécuté.
L'utilisation d'un registre de base permet de stocker le programme et les données dans une partie
disponible de la mémoire; elles peuvent être déplacées par le système d'exploitation. La seule obligation
du système d'exploitation est de se souvenir de l'adresse de base de chaque processus et de charger le
registre de base en conséquence lorsque le processus a été sélectionné pour être exécuté. Le registre de
base n'est cependant pas suffisant pour protéger un processus contre des intrusions d'autres processus dans
la partie affectée de la mémoire, qu'elles soient délibérées ou dues à des erreurs. Par exemple, si le
processus A de la figure 9.3 utilise l'adresse programme 2000, celle-ci sera transformée par l'UCT en
adresse mémoire 3500. La cellule mémoire 3500 est pourtant affectée au processus B et ne devrait par
conséquent pas être accessible au processus A. Il est indispensable d'interdire ce type d'accès.
Pour une protection plus efficace, il faut ajouter un registre supplémentaire à l'UCT, le registre de limite
ou registre de longueur. Cette limite est fixée par le système d'exploitation et correspond au nombre de
cellules mémoire affectées au processus en cours d'exécution. C'est pourquoi, par exemple, lorsque le
processus A de la figure 9.3 est lancé, le registre de limite est fixé à 1200; pour le processus B, le registre
de limite est fixé à 800. La transformation d'une adresse programme en adresse mémoire reste presque la
même, mais des vérifications sont ajoutées pour s'assurer qu'il n'est possible d'accéder qu'aux cellules
mémoire affectées.Cet algorithme est exécuté par le microprogramme de l'UCT pour transformer toute
adresse programme en adresse mémoire correspondante. Si une erreur d'adressage se produit, le contrôle
est rendu au système d'exploitation qui interrompt le processus.
Les paragraphes précédents ont présenté les mécanismes utilisés par les registres de base et de limite pour
donner au matériel le support nécessaire à la gestion de la mémoire. Nous pouvons maintenant concentrer
notre attention sur les algorithmes que le système d'exploitation utilise pour exploiter ces mécanismes.
L'objectif principal d'un système d'exploitation est de stocker en mémoire autant de processus que
possible. Si un processus est bloqué, la zone mémoire qu'il occupe est provisoirement inutilisable: cela
n'a aucune importance si la mémoire est suffisamment importante pour contenir un nombre tel de
processus que certains d'entre eux soient toujours prêts à être exécutés; mais si la capacité de mémoire est
peu importante elle risque d'être entièrement occupée par les processus bloqués ce qui entraîne un blocage
complet de l'ordinateur. Le danger peut être réduit par un processus de transfert (swapping), c'est-à-dire
par déplacement du programme et des données d'un processus bloqué vers une mémoire auxiliaire, afin
129
de faire de la place pour d'autres processus prêts pour l'exécution. Le processus déplacé de la mémoire
centrale devient postulant d'un nouveau déplacement en sens inverse dès qu'il change d'état (de bloqué à
disponible). Remarquez que lorsqu'un processus est replacé en mémoire, il n'est pas nécessaire qu'il
occupe les mêmes cellules que celles qu'il occupait avant son déplacement. Le système d'exploitation
charge simplement le registre de base avec la nouvelle adresse de base lorsque le processus doit être
exécuté. Le choix des processus à déplacer dépend de critères comme le degré de priorité du processus,
l'espace mémoire qu'il occupe, le temps dont il dispose avant d'être bloqué et le temps mémoire qu'il a
déjà utilisé. Le transfert peut augmenter considérablement l'utilisation effective de la mémoire, mais
uniquement au prix du temps pris pour déplacer et replacer les programmes et les données de la mémoire
centrale à une mémoire auxiliaire et vice versa.
A la fin d'un processus, la zone mémoire qu'il occupe peut être affectée à un nouveau processus. Comme
il est peu probable que le nouveau processus ait exactement besoin de la même taille en mémoire, une
petite zone peut être inutilisée, comme le montre la figure 9.4.
Figure 9.4. Fragmentation de la mémoire
Au terme d'un certain nombre d'échanges, la mémoire peut être fragmentée, c'est-à-dire qu'une proportion
substantielle la composant peut être composée de plusieurs zones non affectées, chacune étant trop
restreinte en elle-même pour stocker un processus. Une fragmentation excessive implique une faible
utilisation de la mémoire et le système d'exploitation doit, par conséquent, s'efforcer de réduire la
fragmentation au minimum. On peut obtenir ce résultat par une affectation prudente (plusieurs algorithmes
existent pour cela, mais ils ne font pas l'objet de cet enseignement) et par une fusion des zones adjacentes
de la mémoire qui sont inutilisées afin de constituer des zones plus importantes et donc utilisables. Ce
processus, qui est le compactage, est illustré par la figure 9.5. L'accumulation de nombreux déplacements
à l'intérieur de la mémoire et la remise en place de toutes les adresses de base constitue un travail
considérable, et le compactage se justifie donc en dernier ressort.
130
Figure 9.5: L'effet de compactage
Un inconvénient des schémas de gestion de la mémoire qui se basent sur les registres de base ou de limite
est que le programme complet ainsi que les données d'un processus doivent être simultanément présents
en mémoire lorsqu'un processus est exécuté. Cela signifie que:
1) un espace doit être trouvé pour le programme et ses données, même si le processus n'utilise qu'une
petite partie de cet espace pendant une période particulière de l'exécution; et
2) la taille du programme et des données est limitée par la capacité mémoire de l'ordinateur.
Le mécanisme suivant de gestion de la mémoire permet d'éviter cet inconvénient.
La pagination
La pagination est une technique de gestion de la mémoire qui permet à un processus d'être exécuté quand
seul un segment du programme et des données réside en mémoire centrale. Elle permet donc l'exécution
d'un processus même lorsque la totalité du programme et de ses données ne peuvent tenir à la fois en
mémoire. (Une autre technique, appelée segmentation, est aussi régulièrement utilisée)
Lorsque la pagination est employée, le programme et les données de chaque processus sont considérés
comme étant divisés en un certain nombre de pages de taille identique, et la mémoire est elle-même divisée
en un nombre de structures de page d'égale grandeur. Chaque structure de page peut contenir une page
d'un processus. Les structures de page sont affectées par le système d'exploitation, de sorte qu'à tout
moment chaque processus ait quelques pages occupant des structures de page de la mémoire, pendant que
le reste est conservé en mémoire auxiliaire.
131
La division en pages d'un programme et de ses données est très simple. Si par exemple la taille de la page
est 1000, alors la page 0 contient la partie de programme et les données dont les adresses programme sont
comprises entre 0 et 999, la page 1 contient la partie de programme et les données aux adresses programme
de 1000 à 1999, et ainsi de suite. Ce sont uniquement la partie matérielle de l'ordinateur et le système
d'exploitation qui considèrent un processus divisé de cette façon: les mécanismes de pagination sont
transparents au programmeur et aux traducteurs de langage.
L'UCT transforme une adresse programme en une adresse mémoire
1) en calculant, à partir de l'adresse programme, quelle page et quelle cellule de la page sont visées; et
2) en utilisant les informations gardées par le système d'exploitation pour déterminer quelle structure la
page occupe actuellement.
La première de ces étapes est évidente, ne nécessitant que la division de l'adresse programme par la taille
de la page. Si l'adresse du programme est 2764 et que la taille de la page est 1000, la référence est faite à
la cellule 764 de la page 2. En pratique, la taille de la page est choisie en fonction d'une puissance de 2
(généralement 512, 1024 ou 2048), ce qui rend la division (en binaire) triviale.
La seconde étape de transformation d'adresses est accomplie par l'intermédiaire d'une table de pages qui
indique quelle structure, s'il y en a une, est occupée par chacune des pages du processus. Le système
d'exploitation gère une table de pages pour chaque processus et la met à jour pour refléter l'occupation
actuelle des structures par page. Il n'y a qu'une entrée dans une table de pages d'un processus pour chacune
de ses pages. L'entrée comporte
1) une indication concernant la page actuellement en mémoire; et
2) l'adresse de la structure de page contenant la page si celle-ci est en mémoire, sinon la position de la
page en mémoire auxiliaire.
Si la page est stockée en mémoire, l'adresse de sa structure est une information suffisante pour achever la
transformation d'une adresse de programme en adresse mémoire. Il se peut, cependant, qu'un processus
renvoie à une page qui ne réside pas actuellement en mémoire. Dans ce cas (appelé un défaut de page) la
transformation d'adresse ne peut pas être faite tant que la page référencée n'a pas été transférée de la
mémoire auxiliaire à la mémoire centrale, et que la table des pages n'a pas été mise à jour. Le processus
est alors bloqué et un autre processus est activé pendant ce temps. Lorsque le transfert de page est effectué,
le processus est de nouveau prêt et il est à nouveau sélectionné afin d'être exécuté. Le processus de
transformation d'adresse en entier est alors répété avec succès. La transformation d'adresse exécutée par
l'UCT est illustrée par la figure 9.6.
132
Figure 9.6: Transformation d'adresses en pagination
Puisque la vitesse de transformation est un point crucial pour la vitesse de l'ordinateur, il est habituel de
garder un segment de la table des pages, pour le processus en cours d'exécution, dans un ensemble de
registres spéciaux de l'UCT, aussi bien qu'en mémoire.
Il faut noter que la pagination permet à un programme d'être plus grand que la mémoire de l'ordinateur,
puisqu'il ne doit pas être stocké entièrement en mémoire pour être exécuté. C'est pourquoi la pagination
donne l'illusion d'une mémoire virtuelle plus grande que la mémoire effectivement disponible. C'est cette
mémoire virtuelle qui est "vue" par le programmeur et le traducteur de langage. Ils n'ont plus à se
préoccuper des mécanismes sous-jacents qui lui permettent de fonctionner.
La protection de la mémoire contre des accès non autorisés est automatiquement garantie par l'utilisation
d'une table de pages séparée pour chaque processus. Toutes les adresses mémoire utilisées par un
processus sont interprétées en fonction de la table de pages propre au processus: il est donc impossible à
un processus d'accéder à des structures qui ne lui ont pas été affectées.
Les décisions fondamentales prises par le système d'exploitation dans un contexte de pagination se
rapportent au choix des pages du processus qui devraient être stockées en mémoire et de celles qui
devraient être renvoyées en mémoire auxiliaire. Nous avons déjà vu qu'une page doit être placée en
mémoire lorsqu'elle est référencée et, à moins qu'il existe une structure de page vide, une autre page doit
être déplacée. La question se posant au système d'exploitation est de savoir quelle page déplacer. Cette
question est importante puisque le déplacement peu judicieux d'une page peut provoquer son retour
presque immédiat. Si l'échange des pages entre la mémoire auxiliaire et la mémoire centrale est trop élevé,
on court le risque de surcharger les mécanismes d'E/S et de bloquer en mémoire la majeure partie des
processus attendant les transferts de pages. L'effet sur le fonctionnement de l'ordinateur est alors
désastreux.
133
Idéalement, le système d'exploitation devrait déplacer une page qui n'aurait pas à être référencée dans
l'immédiat. Malheureusement, il n'est pas possible d'anticiper le futur: le mieux que puisse faire le système
d'exploitation est d'anticiper en fonction du passé. Cette inférence est plus facile à réaliser, étant donné le
caractère entièrement prévisible de la plupart des processus qui, habituellement, obtiennent leurs
instructions de cellules mémoire consécutives et qui accèdent souvent à des éléments d'information
stockés de manière adjacente.
Avant de passer au paragraphe suivant, il faut noter que puisque toutes les pages et les structures sont de
même taille, la fragmentation de la mémoire ne peut se produire, et l'utilisation de la mémoire peut par
conséquent être très élevée. Contre cet avantage, il faut considérer l'espace occupé par les tables de pages
elles-mêmes et la complexité supplémentaire du microprogramme de l'UCT.
9.3.4 L'ORDONNANCEMENT ET L'AFFECTATION DE RESSOURCES
Comme nous l'avons indiqué dans la section 9.3.1, les travaux en attente de traitement sont généralement
stockés en mémoire auxiliaire jusqu'à ce que le système d'exploitation lance leur exécution. L'exécution
d'une tâche simple requiert normalement le lancement et la coordination de plusieurs processus, soit
simultanément soit en séquence (voir section 9.3.2). La responsabilité du lancement des processus revient
à un module du système d'exploitation appelé ordonnanceur.
En décidant à quel moment lancer un processus, l'ordonnanceur tient compte des facteurs suivants:
1) le nombre de ressources (par exemple: la mémoire, le temps de traitement, les dispositifs E/S) dont a
besoin le processus;
2) le nombre de ressources disponibles;
3) la priorité du travail auquel le processus est associé;
4) la longueur de l'attente du travail associé.
Le poids donné à ces facteurs varie d'un système d'exploitation à un autre, selon que l'objectif majeur est
le rendement maximal ou l'offre de services rapides à une certaine classe d'utilisateurs. Les informations
concernant les besoins en ressources d'un processus peuvent être recueillies pendant l'exécution du
processus, ou fournies par l'utilisateur en tant que partie des informations de contrôle du travail associé.
Les informations concernant les ressources disponibles sont gérées par l'ordonnanceur et mises à jour
quand les ressources sont affectées et reprises.
134
L'affectation de ressources peut être soit
1) statique, ce qui signifie que toutes les ressources nécessaires à un processus sont affectées lors de son
lancement et reprises à la fin de son exécution; soit
2) dynamique, ce qui signifie que les ressources ne sont affectées à un processus que lorsqu'elles sont
nécessaires et reprises quand le processus n'en a plus besoin.
En mode d'allocation statique, un processus ne peut être lancé que lorsque toutes les ressources nécessaires
sont disponibles; en mode d'allocation dynamique, un processus peut être lancé à tout moment, mais peut
être bloqué si une ressource est indisponible au moment voulu. L'allocation dynamique peut entraîner une
meilleure utilisation des ressources mais est plus difficile à gérer. En particulier, des mesures doivent être
prises pour en finir avec l'interblocage, situation dans laquelle chacun de deux (ou plusieurs) processus
utilise une ressource nécessaire à l'autre. Si aucun des deux ne peut rendre la ressource qu'il bloque, aucun
ne peut être exécuté et tous deux resteront bloqués indéfiniment. De nombreuses mesures peuvent être
prises pour éviter ou maîtriser l'interblocage: toutes ont des inconvénients et certaines d'entre elles peuvent
être complexes et prendre un temps considérable.
9.3.5 LA MANIPULATION DES E/S
Une des fonctions du système d'exploitation est de manipuler toutes les opérations d’E/S sur ordre des
processus de l'utilisateur et ce pour différentes raisons:
1) Les caractéristiques opérationnelles des dispositifs E/S liés à un ordinateur varient considérablement,
en particulier par leur vitesse, la quantité de données qu'ils transfèrent en une seule opération et la
manière dont les données sont représentées sur les dispositifs d'entrée et de sortie. Il est très ennuyeux
pour l'utilisateur d'avoir à s'occuper de ces détails; il est pour lui beaucoup plus pratique de s'en
remettre aux modules du système d'exploitation qui gèrent à sa place les opérations E/S.
2) Pour rendre efficace une allocation de processeur (section 9.3.2), le système d'exploitation doit savoir
à quel moment un processus est lancé et à quel moment il s'achève: ceci est beaucoup plus facile si le
système d'exploitation se charge lui-même de tous ces transferts.
3) Certains dispositifs E/S sont partageables, en ce sens qu'ils peuvent gérer des transferts successifs
d'E/S qui proviennent de processus différents. Un disque, par exemple, peut être partageable parce que
des transferts différents peuvent être dirigés vers (ou provenir de) différentes zones du disque sans
risque de confusion. D'autres dispositifs ne sont pas partageables: la façon dont ils travaillent fait que
135
les transferts successifs des différents processus conduisent à un inextricable mélange des données.
Une imprimante, par exemple, est un dispositif qu'on ne peut partager, puisque son utilisation par
différents processus au même moment provoquerait des impressions de lignes de différents processus
sur la même feuille de papier. Des dispositifs qui ne peuvent être partagés ne doivent être alloués qu'à
un seul processus à la fois et le système d'exploitation doit veiller à ce qu'un processus n'utilise que
les dispositifs qui lui ont été alloués. Ceci est beaucoup plus facile si c'est le système d'exploitation
qui gère les échanges E/S.
Un processus demande un transfert E/S en appelant le module du système d'exploitation approprié dont
les paramètres spécifient la nature du transfert requis. Ce module
1) vérifie la légitimité de la demande (par exemple, que le dispositif E/S est alloué au processus qui le
demande);
2) lance le transfert en exécutant des instructions appropriées au dispositif E/S concerné;
3) bloque le processus demandeur;
4) appelle le distributeur pour sélectionner un autre processus.
La fin du transfert est signalée par une interruption qui force l'UCT à se brancher à un endroit fixe de la
mémoire. Cet emplacement contient la première instruction d'un gestionnaire d'interruption qui est un
module du système d'exploitation chargé de la gestion des interruptions.
Le gestionnaire d'interruption
1) identifie l'origine de l'interruption (c'est-à-dire quel dispositif E/S l'a provoquée) et par conséquent le
processus qui est à l'origine du transfert;
2) change l'état du processus incriminé, du mode bloqué au mode prêt, et rend donc acceptable la reprise
du processus;
3) reprend le processus qui était en cours d'exécution lorsque l'interruption s'est produite. (Il arrive que
l'interruption permette de réallouer l'UCT, auquel cas le gestionnaire d'interruption appelle le
distributeur pour sélectionner un autre processus.)
Les détails de l'opération E/S dans son intégralité sont transparents au processus demandeur, qui doit
uniquement appeler le module E/S correspondant.
9.3.6 LE SYSTEME DE FICHIERS
Dans la plupart des systèmes informatiques, il est nécessaire de conserver les informations sous une forme
facilement accessible pendant longtemps. Le type d'informations stockées varie naturellement selon ce
136
que le système se propose d'en faire, mais il comprend généralement des programmes et des données qui
doivent être utilisés à plusieurs reprises. Ce sont des programmes système, des données qui sont le fruit
d'expérimentations scientifiques ou d'études, des programmes écrits par des utilisateurs ou des bases de
données d'applications variées. Pour accéder facilement à ces informations, il faut les stocker dans le
système. Pour des raisons techniques et économiques, le stockage à long terme de grandes quantités
d'informations est effectué sur des supports de mémoires auxiliaires comme les disques magnétiques. C'est
le rôle du système d'exploitation de gérer cette mémoire auxiliaire de manière que les informations soient
localisées et rappelées facilement.
L'information en mémoire auxiliaire est habituellement conservée sous la forme de fichiers qui peuvent
être de tailles différentes. Chaque fichier est un ensemble d'informations considéré comme une entité par
ses utilisateurs. Il peut s'agir par exemple d'un programme, des observations d'une expérimentation ou
d'une liste d'employés. Le fichier est l'unité logique qui est stockée et gérée par le système d'exploitation.
Le système de fichiers est la partie du système d'exploitation qui est responsable des fichiers. Les fonctions
spécifiques d'un système de fichiers varient selon l'application informatique, mais comportent
1) la création et la destruction de fichiers;
2) la possibilité d'accéder aux fichiers;
3) la gestion de l'espace de la mémoire auxiliaire;
4) la protection des fichiers contre des accès non autorisés (bien qu'un accès légal puisse être autorisé
entre les membres d'une même équipe);
5) la protection des fichiers contre les pertes ou les détériorations dues aux pannes matérielles.
Puisque l'emplacement physique d'un fichier ne concerne pas l'utilisateur, il est courant que son créateur
donne un nom à chacun de ses fichiers, ce qui permet au système d'y accéder simplement par leurs noms.
Le système de fichiers comporte donc un répertoire de noms de fichiers et de leurs emplacements sur le
support mémoire. Dans un contexte où plusieurs utilisateurs sont autorisés à créer et à manipuler leurs
propres fichiers, le répertoire présente généralement une structure arborescente à deux niveaux. La racine
de l'arbre est le répertoire principal avec une entrée pour chaque utilisateur. Les feuilles sont les
répertoires des utilisateurs, avec une entrée pour chacun des fichiers de l'utilisateur. Cette structure permet
à différents utilisateurs d'appeler leurs fichiers par les mêmes noms sans risque de confusion. Les
répertoires sont stockés en mémoire auxiliaire (comme les fichiers eux-mêmes) et sont transférés en
mémoire lorsque cela est nécessaire.
137
Chaque entrée du répertoire principal comporte l'information suivante au sujet de l'utilisateur:
1) le nom par lequel l'utilisateur est connu du système;
2) l'emplacement du répertoire de l'utilisateur correspondant.
Chaque entrée d'un répertoire utilisateur comporte les informations suivantes au sujet d'un fichier de
l'utilisateur:
1) le nom du fichier;
2) l'emplacement du fichier en mémoire auxiliaire;
3) la taille du fichier;
4) l'information de contrôle d'accès fournie par l'utilisateur et qui spécifie qui peut utiliser le fichier et
quel type d'accès est autorisé (l'accès peut, par exemple, être autorisé pour une consultation mais pas
pour une modification);
5) différentes informations administratives telles que la date de création du fichier, ainsi que celle de sa
dernière modification.
La structure de répertoire peut être étendue à plusieurs niveaux (figure 9.7). Cela permet à un utilisateur
de regrouper les fichiers logiquement connexes et d'accéder à chaque groupe par un répertoire différent.
Il permet aussi à une équipe de mettre au point un répertoire de jonction, avec leurs répertoires individuels
aux niveaux inférieurs de l'arbre. Certains fichiers du répertoire de jonction (par exemple les fichiers I et
J de la figure 9.8) peuvent être librement accessibles à tous les membres de l'équipe, alors que le contrôle
d'accès de ceux contenus dans les répertoires individuels (par exemple, G et K ) est plus sélectif.
Figure 9.7: Structure d'un répertoire à multi-niveaux
138
L'espace en mémoire auxiliaire est alloué par unités de taille fixe, appelées blocs (la taille d'un bloc est
par exemple équivalente à 500 cellules mémoire). Chaque fichier occupe un certain nombre de blocs,
pouvant se situer n'importe où dans la mémoire auxiliaire (il n'est pas nécessaire qu'ils soient contigus).
Le système de fichiers doit gérer les informations concernant ceux des blocs qui sont libres et ceux qui
sont alloués à des fichiers particuliers. Les algorithmes et les structures de données utilisés pour
l'allocation dépendent de la manière dont les fichiers doivent être utilisés. Ils dépendent en particulier du
mode d'accès (soit séquentiel du début à la fin, soit aléatoire à n'importe quel point) d'un fichier.
Puisque le contenu d'un fichier peut représenter plusieurs mois de travail ou des données irremplaçables,
il est important que le système dispose des mécanismes adéquats de sauvegarde et de recours en cas de
défaillance du logiciel ou du matériel. Le système doit donc conserver des copies de tous les fichiers de
façon à pouvoir les restituer après un accident malencontreux.
Il y a deux méthodes principales pour sauvegarder des fichiers:
1) Périodiquement: Le contenu total du support mémoire est copié à intervalles réguliers. La copie peut
être faite d'un disque sur un autre ou d'un disque sur une bande magnétique. Les principaux
inconvénients de cette technique sont le grand volume d'informations devant être copié et 1'éventualité
des pertes de fichiers créés ou modifiés depuis la dernière copie.
2) Au fur et à mesure: Un fichier n'est copié que lors de sa création ou d'une modification. Cette technique
réduit la quantité de copies tout en permettant une mise à jour plus fréquente. La copie au fur et à
mesure est cependant plus difficile à gérer, puisque les précédentes copies doivent être localisées et
détruites (ou reconnues et ignorées pendant la récupération succédant à une panne). Une variante de
ce type de copie consiste à ne copier que les modifications apportées à un fichier. La récupération
après une panne peut être très complexe mais la technique est pratique lorsque les modifications sont
si fréquentes que la copie du fichier en entier est irréalisable (par exemple les fichiers de réservations
d'une compagnie aérienne).
9.3.7 LE CONTROLE DES TRAVAUX
Nous conclurons notre discussion sur les systèmes d'exploitation en décrivant brièvement comment
l'utilisateur indique au système d'exploitation ce qu'il désire qu'il fasse. Généralement parlant, toutes les
opérations que demande l'utilisateur concernent la manipulation des programmes et des données pouvant
être stockées en tant que fichiers ou présentées par les dispositifs E/S. Les formes de manipulation varient
considérablement: plus courantes sont l'entrée, la sortie, la copie de données ainsi que la compilation et
l'exécution des programmes.
139
Les instructions que donne l'utilisateur au système d'exploitation sont exprimées en un langage de
commande. Les langages de commande permettent la transmission des types d'informations suivants
1) Informations opérationnelles, spécifiant quelles opérations l'utilisateur désire accomplir (par exemple
copier un fichier ou exécuter un programme).
2) Informations EIS, spécifiant d'où proviennent les programmes et/ou les données nécessaires à une
opération, et l'emplacement auquel les résultats devront être affectés (par exemple, le programme
réside dans un fichier particulier, la sortie doit se faire sur le terminal de l'utilisateur).
3) Informations ressources, donnant une estimation des ressources nécessaires pour effectuer une
opération (par exemple, la capacité de mémoire, le temps de traitement). Les informations concernant
les ressources sont utilisées par l'ordonnanceur lors du lancement des processus (section 9.3.4). Dans
les cas où l'utilisateur ne connaît pas ou ne spécifie pas quelles ressources sont nécessaires, le système
d'exploitation attribue lui-même des valeurs par défaut.
4) L'identification de l'utilisateur, spécifiant qui est l'utilisateur et établissant s'il est de bonne foi (par
son numéro et un mot de passe). Ces informations sont utilisées pour contrôler l'accès à l'ordinateur,
et peuvent également l'être pour un abonnement ou une facture.
L'interprétation des instructions de contrôle des travaux est accomplie par une partie du système
d'exploitation connue sous le nom d'interpréteur du contrôle des travaux (ou interpréteur de commande).
Il analyse chaque instruction (ou séquence d'instructions) et l'interprète. Dans certains cas, comme la
compilation d'un programme utilisateur, l'interpréteur n'est pas en mesure d'interpréter lui-même
l'instruction. Il construit cependant un fichier qui spécifie ce qui est en train d'être fait. Le fichier indique
quel processus doit être lancé et peut contenir des informations relatives aux E/S ou aux ressources
extraites de l'instruction ou données par défaut. L'ordonnanceur examine périodiquement une liste de ces
fichiers pour décider s'il doit lancer un autre processus (voir section 9.3.4).
La syntaxe de la plupart des langages de contrôle des travaux est de plus en plus simple comme l'illustre
les évolutions constantes des interfaces graphiques des systèmes d'exploitation modernes.
