Algorithme Et Programmation
Algorithme Et Programmation
Algorithme Et Programmation
INF411
Les bases de la programmation
et de l'algorithmique
Jean-Christophe Fillitre
dition 2014
ii
Avant-propos
Ce polycopi est utilis pour le cours INF411 intitul Les bases de la programmation
et de l'algorithmique. Ce cours fait suite au cours INF311 intitul Introduction l'informatique et prcde le cours INF421 intitul Design and Analysis of Algorithms.
Ce polycopi reprend, dans sa premire partie, quelques lments d'un prcdent polycopi crit, en plusieurs itrations, par Jean Berstel, Jean-ric Pin, Philippe Baptiste,
Luc Maranget et Olivier Bournez. Je les remercie sincrement pour m'avoir donn accs
http://www.enseignement.polytechnique.fr/informatique/INF411/
L'auteur peut tre contact par courrier lectronique l'adresse suivante :
Historique
Version 1 : samedi 3 aot 2013
Version 2 : mercredi 30 juillet 2014
iv
1 Le langage Java
1.1
1.2
. . . . . . . . . . . . . . . . . . . . . . . .
1.1.1
Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.2
1.1.3
Surcharge
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.4
Hritage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.5
Classes abstraites . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
1.1.6
Classes gnriques
10
1.1.7
Interfaces
1.1.8
Rgles de visibilit
. . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
Modle d'excution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
1.2.1
. . . . . . . . . . . . . . . . . . . . .
13
1.2.2
Mmoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
1.2.3
Valeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2 Notions de complexit
2.1
2.2
2.3
12
. . . . . . . . . . . . . . . . . . . . . . . . . . .
23
23
2.1.1
La notion d'algorithme . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.1.2
. . . . . . . . . . . . . . . . . .
24
2.1.3
24
2.1.4
25
2.1.5
26
Complexits asymptotiques
. . . . . . . . . . . . . . . . . . . . . . . . . .
27
2.2.1
Ordres de grandeur . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
2.2.2
Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
2.2.3
Notation de Landau
. . . . . . . . . . . . . . . . . . . . . . . . . .
28
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
2.3.1
Factorielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
2.3.2
Tours de Hanoi
29
Quelques exemples
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
31
3 Tableaux
33
3.1
3.2
3.3
3.4
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
35
3.2.1
35
3.2.2
36
38
Tableaux redimensionnables
. . . . . . . . . . . . . . . . . . . . . . . . . .
39
3.4.1
Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
3.4.2
41
3.4.3
44
3.4.4
44
3.4.5
Code gnrique
47
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 Listes chanes
49
4.1
49
4.2
54
4.3
54
4.4
. . . . . . . . . . . . . . . . . . . . . . . .
59
4.4.1
Listes cycliques
59
4.4.2
Listes persistantes
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .
60
4.5
61
4.6
Code gnrique
66
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 Tables de hachage
69
5.1
Ralisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
5.2
Redimensionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73
5.3
Code gnrique
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
5.4
75
6 Arbres
77
6.1
. . . . . . . . . . . . . . . . . . . . . . . . . . .
77
6.2
78
6.3
79
6.3.1
Oprations lmentaires
. . . . . . . . . . . . . . . . . . . . . . . .
80
6.3.2
quilibrage
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84
6.3.3
Structure d'ensemble . . . . . . . . . . . . . . . . . . . . . . . . . .
90
6.3.4
Code gnrique
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
6.4
Arbres de prxes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
6.5
Cordes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
96
7 Files de priorit
101
7.1
7.2
7.3
7.4
Code gnrique
. . . . . . . . . . . . . . . . . . . . . . . . 102
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
vii
8 Classes disjointes
111
8.1
Principe
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
8.2
Ralisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
117
9 Arithmtique
119
9.1
9.2
Exponentiation rapide
9.3
Crible d'ratosthne
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
125
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
11 Rebroussement (backtracking )
131
12 Tri
137
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
. . . . . . . . . . . . . . . . . . . . . . . . . . . 149
13 Compression de donnes
151
IV Graphes
161
14 Dnition et reprsentation
163
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
169
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
Annexes
185
A Lexique Franais-Anglais
185
viii
Bibliographie
187
Index
189
Premire partie
Prliminaires
Le langage Java
On rappelle ici certains points importants du langage de programmation Java. Ce chapitre n'est nullement exhaustif et suppose que le lecteur est dj familier du langage Java,
notamment grce au cours INF311. On pourra aussi lire l'excellent ouvrage
to Programming in Java
Introduction
type. En toute premire approximation, une classe peut tre vue comme un enregistrement.
class Polar {
double rho;
double theta;
}
rho et theta sont les deux champs de la classe Polar, de type double. On cre
instance particulire d'une classe, appele un objet , avec la construction new. Ainsi
Ici
une
Polar.
p,
de type
Polar,
p,
p.x.
0.0).
p.rho = 2;
p.theta = 3.14159265;
double x = p.rho * Math.cos(p.theta);
p.theta = p.theta / 2;
Pour allouer de nouveaux objets en initialisant leurs champs avec des valeurs particulires,
constructeurs . Un
champs rho et theta en
Polar
Polar)
n'est pas
ngatif. Dans le cas contraire, on lve une exception. Ce constructeur nous permet d'crire
maintenant
Attention
Nous avions pu crire plus haut
new Polar()
En eet, toute classe possde un constructeur par dfaut, sans argument. Mais
une fois qu'un constructeur est ajout la classe
Polar,
le constructeur im-
troduire un constructeur sans argument. Une classe peut en eet avoir plusieurs
constructeurs, avec des arguments en nombre ou en nature dirents. On parle de
surcharge.
1.1.1 Encapsulation
Supposons maintenant que l'on veuille maintenir l'invariant suivant pour tous les
objets de la classe
Polar
0 rho
Pour cela on dclare les champs
l'extrieur de la classe
Polar.
rho
0 theta < 2
theta privs,
et
class Polar {
private double rho, theta;
Polar(double r, double t) { /* garantit l'invariant */ }
}
Si on cherche accder au champ
p.rho
rho
de la classe
Polar,
compilateur :
Polar
class Polar {
private double rho, theta;
...
double norm() { return rho; }
}
rho
de type
Polar,
on appelle la mthode
norm
ainsi :
p.norm()
Navement, on peut voir cet appel de mthode comme un appel
norm
norm(p)
une
fonction
qui recevrait l'objet comme premier argument. Dans une mthode, cet argument
implicite, qui est l'objet sur lequel on appelle une mthode, est dsign par le mot-cl
this.
norm
rho
Polar(double r, double t) {
this.rho = r;
this.theta = t;
}
car, dans le constructeur,
this
mme donner aux paramtres du constructeur les mmes noms que les champs :
rho
dsigne le paramtre et
this.rho
le champ. On
vite ainsi d'avoir trouver un nom dirent pour l'argument quand on programme,
le plus dicile est souvent de trouver des noms judicieux.
Attention
rho
et
theta
aux paramtres
rho
et
theta
eux-mmes.
statique
aux instances de cette classe ; dit autrement, il s'apparente une variable globale.
class Polar {
double rho, theta;
static double two_pi = 6.283185307179586;
De mme, une
mthode
peut tre
statique
tionnelle.
this
dynamique.
n'est pas autoris. En eet, il n'existe pas ncessairement d'objet particulier ayant
t utilis pour appeler cette mthode. Pour la mme raison, une mthode statique ne peut
pas appeler une mthode dynamique. l'inverse, en revanche, une mthode dynamique
peut parfaitement appeler une mthode statique. Enn, on note que le point d'entre d'un
programme Java, savoir sa mthode
main,
1.1.3 Surcharge
Plusieurs mthodes d'une mme classe peuvent porter le mme nom, pourvu qu'elles
aient des arguments en nombre et/ou en nature dirents ; c'est ce que l'on appelle la
surcharge (en anglais overloading ). Ainsi on peut crire dans la classe Polar deux mthodes mult pour multiplier respectivement par un autre nombre complexe en coordonnes
polaires ou par un simple ottant.
class Polar {
...
void mult(Polar p) {
this.rho *= p.rho; this.theta = normalize(this.theta + p.theta);
}
void mult(double f) {
this.rho *= f;
}
}
On peut alors crire des expressions comme
p.mult(p)
ou encore
p.mult(2.5).
La sur-
charge est rsolue par le compilateur, au moment du typage. Tout se passe comme si on
avait crit en fait deux mthodes avec des noms dirents
class Polar {
...
void mult_Polar(Polar p) {
this.rho *= p.rho; this.theta = normalize(this.theta + p.theta);
}
void mult_double(double f) {
this.rho *= f;
}
}
qu'une facilit fournie par le langage pour ne pas avoir introduire des noms dirents. On
peut surcharger autant les mthodes statiques que dynamiques, ainsi que les constructeurs
(voir notamment l'encadr page 4).
1.1.4 Hritage
B
Le concept central de la programmation oriente objet est celui d'hritage : une classe
peut tre dnie comme hritant d'une classe
A,
ce qui se note
A,
simple
A.
sous-typage
peut tre
langage orients objets, comme C++). La relation d'hritage forme donc un arbre
class
class
class
class
A
B
C
D
{ ... }
extends A { ... }
extends A { ... }
extends C { ... }
A
B C
D
Prenons comme exemple un ensemble de classes pour reprsenter des objets graphiques
(cercles, rectangles, etc.). On introduit en premier lieu une classe
Graphical reprsentant
class Graphical {
int x, y;
/* centre */
int width, height;
move pour dplacer l'objet et draw pour le dessiner. Pour reprsenter un rectangle,
hrite de la classe Graphical.
thodes,
on
exemple
rednir
la mthode
draw
dans la classe
Rectangle
p.draw();
new C(...)
type statique
a le type
radius
des-
pour le
Graphical.
On utilise pour
La classe
nus
aprs le nom de la classe gnrique. (La notion de classe gnrique est explique en dtail
un peu plus loin.) Initialement la liste est vide. On dnit une mthode
void add(Graphical g) {
this.group.add(g);
// + mise jour de x,y,width,height
}
Il reste rednir les mthodes
draw
et
move.
tous les lments qui le composent, c'est--dire tous les lments de la liste
chaque lment
liste
this.group,
Pour parcourir la
void draw() {
for (Graphical g : this.group)
g.draw();
}
Cette construction aecte successivement la variable
this.group
et, pour chacun, excute le corps de la boucle. Ici le corps de la boucle est
move
dans la classe
Group
en appelant la
draw
(ou
move)
sur un objet
de type statique
Graphical,
sans sa-
voir s'il s'agit d'un rectangle, d'un cercle, ou mme d'un autre groupe. En fonction de la
nature de cet objet, le code correspondant sera appel. cet endroit du programme, le
compilateur ne peut pas le connatre. C'est pourquoi on parle d'appel
dynamique
de m-
thode. (D'une manire gnrale, statique dsigne ce qui est connu/fait au moment de
la compilation, et dynamique dsigne ce qui est connu/fait au moment de l'excution.)
10
La classe Object
Une classe qui n'est pas dclare comme hritant d'une autre classe hrite de la classe
Object. Il s'agit d'une classe prdnie dans la bibliothque Java, de son vrai nom
java.lang.Object. Par consquent, toute classe hrite, directement ou indirectement,
de la classe Object. Parmi les mthodes de la classe Object, dont toute classe hrite
donc, on peut citer notamment les trois mthodes
Graphical.
Elle nous
sert de type commun tous les objets graphiques, mais elle ne reprsente pas un objet
particulier. C'est ce que l'on appelle une
mot-cl
abstract.
classe abstraite
Graphical,
gnrique. L'exemple le plus simple est srement celui d'une classe Pair pour reprsenter
1
une paire forme d'un objet d'une classe A et d'un autre d'une classe B . Il s'agit donc
d'une classe paramtre par les classes A et B. On la dclare ainsi :
Pair, on utilise
fst et snd avec
1. D'une faon assez surprenante, une telle classe n'existe pas dans la bibliothque standard Java.
11
A fst;
B snd;
et le constructeur naturel avec
Pair(A a, B b) {
this.fst = a;
this.snd = b;
}
(On note qu'on ne rpte pas les paramtres dans le nom du constructeur, car ils sont
identiques ceux de la classe.) De la mme manire, les paramtres peuvent tre utiliss
dans les dclarations et dnitions de mthodes. Ainsi on peut crire ainsi une mthode
renvoyant la premire composante d'une paire, c'est--dire une valeur de type
A et B par des paramtres eectifs, c'est--dire par deux expressions de type. Ainsi on peut
crire
p0
caractres. Une telle dclaration peut tre faite aussi bien dans la classe
rieur, dans une autre classe. Comme on le voit, la syntaxe pour raliser l'instanciation est,
sans surprise, la mme que pour la dclaration. Comme on le voit galement, l'instancia-
static,
car ils ne concident pas ncessairement avec ceux de la classe. Ainsi, une
Pair
qu' l'ext-
rieur, dans une autre classe. Les paramtres d'un code statique ne sont pas ncessairement
les mmes que ceux de la classe gnrique. Par exemple on peut crire
12
pour renvoyer une paire forme de deux fois le mme objet. Lorsqu'on utilise une mthode
statique gnrique, l'instanciation est infre par le compilateur. Ainsi on crit seulement
1.1.7 Interfaces
contrat entre une fournisseur de
interface. Une interface est un ensemble de
mthodes. Voici par exemple une interface minimale pour une structure de pile contenant
des entiers.
interface
boolean
void
int
}
Stack {
isEmpty()
push(int x)
pop()
isEmpty, push
et
pop.
peut tre utilise comme un type. On peut ainsi crire une mthode
isEmpty, push
et
pop. On peut
Stack.
Stack
plmenter l'interface
implements,
de la manire suivante :
Stack
MyIntStack
Stack.
Stack
13
MyIntStack
par
interface Comparable<K> {
int compareTo(K k);
}
On l'utilise pour exiger que les objets d'une classe donne soient comparables entre eux.
Des exemples d'utilisation se trouvent dans les sections 6.3.4, 7.4 12.5 ou encore 13.2.
la visibilit d'un champ. Plus gnralement, il existe quatre niveaux de visibilit dirents
en Java :
et ses sous-classes ;
public
: visibilit illimite.
Ces qualicatifs de visibilit s'appliquent aussi bien aux champs qu'aux mthodes et aux
constructeurs. Pour des raisons de simplicit, ce polycopi omet le qualicatif
public
la
double).
short, char, int et long) et deux types de nombres virgule ottante (float
14
Entiers.
bn1
b0 est
n vaut
bn2
b1
...
et le bit
b0
bn1
Le bit
appel le
le
Java,
Selon le type
pour dnoter
non sign
en base 2,
n1
X
bi 2i .
i=0
Les valeurs possibles vont de 0, c'est--dire
le cas du type
00...002 ,
2n 1,
c'est--dire
11...112 .
C'est
vont donc de 0
Pour
bn1
comme un bit
n1
complment
ngatif. Plutt que de simplement mettre un signe devant un entier reprsent par les
bits restants, les ordinateurs utilisent une reprsentation plus subtile appele
deux .
n1
bn1 2
n2
X
bi 2i .
i=0
Les valeurs possibles s'tendent donc de
-dire
011...1112 .
2n1 ,
c'est--dire
100...0002 ,
2n1 1,
c'est-
00...002 .
et
long
sur respectivement 8, 16, 32 et 64 bits. Les plages de valeurs de ces types sont donc
7
7
15
15
31
31
63
63
respectivement 2 ..2 1, 2 ..2 1, 2 ..2 1 et 2 ..2 1.
Outre les oprations arithmtiques lmentaires, le langage Java fournit galement
des oprations permettant de manipuler directement la reprsentation binaire d'un entier,
et le OU exclusif appliqus bit bit aux bits de deux entiers. Il existe galement des
oprations de
dcalage
<< k
k zros de poids faible. De mme, l'opration >>> k est un dcalage logique droite,
k zros de poids fort. Enn, l'opration >> k est un dcalage arithmtique
droite, qui rplique le bit de signe k fois. Ces oprations sont utilises dans le chapitre 11
insre
qui insre
de capacit
et que ce dernier n'est pas signal, ni par le compilateur (qui ne pourrait pas
dbordement
100000 * 100000
15
double
float
long
int
char short
byte
Ce cours n'entre pas dans les dtails de cette reprsentation, qui est complexe, mais
plusieurs choses importantes se doivent d'tre signales. En premier lieu, il faut avoir
conscience que la plupart des nombres rels, et mme la plupart des nombres dcimaux,
ne sont pas reprsentables par un ottant. En consquence, les rsultats des calculs sont
arrondis et il faut en tenir compte dans les programmes que l'on crit. Ainsi, le nombre
n'est pas reprsentable et un simple calcul comme
qui n'est pas gal
173,2.
1732 0,1
0,1
pas tester en gnral qu'un nombre ottant est nul, mais plutt qu'il est infrieur une
9
borne donne, par exemple 10 . En revanche, si les calculs sont arrondis, ils le sont d'une
manire qui est spcie par un standard, savoir le standard IEEE 754 [ ]. En particulier,
ce standard spcie que le rsultat d'une opration, par exemple la multiplication
0,1
1732
Conversions automatiques.
bissent des conversions automatiques d'un type vers un autre dans certaines circonstances.
Ainsi, si une mthode doit renvoyer un entier de type
est de type
type
int.
char.
int,
return c o c
long un entier de
on peut crire
trait de bas en haut tant vu comme une conversion et la conversion tant transitive. Les
conversions entre les types entiers se font sans perte. En revanche, les conversions vers les
types ottants peuvent impliquer un arrondi (on peut s'en convaincre par un argument
combinatoire, par exemple en constatant que le type
type
float).
long
Lorsque la conversion n'est pas possible, le compilateur Java indique une erreur. Ainsi,
on ne peut pas aecter une valeur de type
renvoyer une valeur de type
float
int
char
ou encore
16
int.
char
char
et d'un
short
int,
le rsultat sera de
sera de type
int.
1.2.2 Mmoire
Cette section explique comment la mmoire est structure et notamment comment les
objets y sont reprsents. Reprenons l'exemple de la classe
class Polar {
double rho, theta;
}
et construisons un nouvel objet de la classe
Polar
Polar
rho 0.0
theta 0.0
Les petites botes correspondent des zones de la mmoire. Les noms ct de ces botes
(p,
rho, theta) n'ont pas de relle incarnation en mmoire. En tant que noms, ils n'existent
que dans le programme source. Une fois celui-ci compil et excut, ces noms sont devenus
des
adresses
dsignant des zones de la mmoire, qui ne sont rien d'autre que des entiers.
Ainsi la bote
trouve les petites botes dessines droite. Dans une est mentionne la classe de l'objet,
Polar. L encore, il ne s'agit pas en mmoire d'un nom, mais d'une reprsentation plus
bas niveau (en ralit une autre adresse mmoire vers une description de la classe Polar).
Dans d'autres botes on trouve les valeurs des deux champs rho et theta. L encore on a
ici
explicit le nom ct de chaque champ mais ce nom n'est pas reprsent en mmoire. Le
compilateur sait qu'il a rang le champ
Notre schma est donc une simplication de l'tat de la mmoire, les zones mmoires
apparaissent comme des cases (les variables portent un nom) et les adresses apparaissent
comme des ches qui pointent vers les cases, alors qu'en ralit il n'y a rien d'autre que
des entiers rangs dans la mmoire des adresses qui sont elles-mmes des entiers. Par
ailleurs, notre schma est aussi une simplication car la reprsentation en mmoire d'un
objet Java est plus complexe : elle contient aussi des informations sur l'tat de l'objet.
Mais ceci ne nous intresse pas ici. Dans ce polycopi, on s'autorisera parfois mme ne
pas crire la classe dans la reprsentation d'un objet quand celle-ci est claire d'aprs le
contexte.
Tableaux
Un tableau est un objet un peu particulier, puisque ses direntes composantes ne
sont pas dsignes par des noms de champs mais par des indices entiers. Nanmoins l'ide
17
reste la mme : un tableau occupe une zone contigu de mmoire, dont une petite partie
dcrit le type du tableau et sa longueur et le reste contient les dirents lments. Dans
la suite, on reprsentera un tableau de manire simplie, avec uniquement ses lments
prsents horizontalement. Ainsi un tableau contient les trois entiers 1, 2 et 3 sera tout
simplement reprsent par
1 2 3
Allocation et libration
Comme expliqu ci-dessus, l'utilisation de la construction
allocation
new
tas
l'autre tant la pile, dcrite dans le paragraphe suivant. Si la mmoire vient s'puiser,
l'exception
de la mmoire peut tre rcupre, lorsque les objets correspondants ne sont plus utiliss. Cette libration de mmoire n'est pas la charge du programmeur (contrairement
d'autres langages comme C++) : elle est ralise automatiquement par le
lector
Garbage Col-
(ou GC). Celui-ci libre la mmoire alloue pour un objet lorsque cet objet ne peut
plus tre rfrenc partir des variables du programme ou d'autres objets pouvant encore
tre rfrencs. La libration de mmoire est eectue incrmentalement, c'est--dire par
petites tapes, au fur et mesure de l'excution du programme. En premire approximation, on peut considrer que le cot de la libration de mmoire est uniformment rparti
sur l'ensemble de l'excution. En particulier, on peut s'autoriser penser que le cot
d'une expression
Pile d'appels
Dans la plupart des langages de programmation, et en Java en particulier, les appels de
fonctions/mthodes obissent une logique dernier appel, premier sorti , c'est--dire
que, si une mthode
calculant la factorielle de
n.
fact(4),
fact
fact(3).
4.
fact sera
de fact(4)
de la mthode
Puis l'valuation
n de la mthode
3. On comprend qu'on ne peut pas
fact(4), sinon la valeur 4 sera perdue,
alors mme qu'il nous reste eectuer une multiplication par cette valeur l'issue de
suivante :
3. La pile d'appels n'est pas lie la rcursivit mais la notion d'appels imbriqus, mais une fonction
rcursive conduit naturellement des appels imbriqus.
18
fact(3) n
fact(2) n
.
.
.
On visualise bien une structure de pile (qui crot ici vers le bas). Lorsqu'on parvient
fact(0).
La variable
est leve. Par dfaut, la taille de pile est relativement petite, de l'ordre de 1 Mo, ce qui
correspond environ 10 000 appels imbriqus (bien entendu, cela dpend de l'occupation
sur la pile de chaque appel de fonction). On peut modier la taille de la pile avec l'option
-Xss
Test
1.2.3 Valeurs
Il y a en Java deux grandes catgories de valeurs : les
valeurs primitives
et les
objets.
La distinction est en fait technique, elle tient la faon dont ces valeurs sont traites par
la machine, ou plus exactement sont ranges dans la mmoire. Une valeur primitive se
sut elle-mme ; il s'agit d'un entier, d'un caractre, ou encore d'un boolen. La valeur
d'un objet est une
int x = 1 ;
int[] t = {1, 2, 3} ;
Les variables
et
x 1
t
1 2 3
et
construction
variable
int y = x ;
int[] u = t ;
19
y 1
x 1
1 2 3
En particulier, les deux variables
alias .
sont des
et
t.
et en vriant que
u[1] = 42;
alors
on obtient
x 1
y 1
1 42 3
ce que l'on peut observer facilement, par exemple en achant la valeur de
dant,
avec
x 1
y 1
Cepen-
t
4 5
t[1].
1 42 3
null
d'aller voir o il pointe. Toute tentative se traduit par une erreur l'excution, savoir
le dclenchement de l'exception
NullPointerException.
Toute valeur qui n'est pas initialise (variable, champ, lment de tableau) reoit une
valeur par dfaut. Le langage spcie qu'il s'agit de 0 dans le cas d'un entier, d'un caractre
ou d'un ottant,
false
null
tableau).
==
teur != teste leur dirence. Pour des valeurs primitives, cela concide avec l'galit mathmatique. En revanche, pour deux objets, c'est--dire deux valeurs qui sont des pointeurs,
il s'agit tout simplement de l'galit de ces deux pointeurs. Autrement dit, le programme
int[] t = {1, 2, 3} ;
int[] u = t ;
int[] v = {1, 2, 3} ;
System.out.println("t==u : " + (t == u) + ", t==v : " + (t == v)) ;
t==u : true, t==v : false. Les pointeurs t et u sont gaux parce qu'ils pointent
le mme objet. Les pointeurs t et v, qui pointent vers des objets distincts, sont
ache
vers
20
1 2 3
On dit parfois que
1 2 3
String t = "coucou" ;
String u = "coucou" ;
String v = "cou" ;
String w = v + v ;
System.out.println("t==u : " + (t == u) + ", t==w : " + (t == w)) ;
t==u : true, t==w : false, ce qui rvle que les chanes (objets) rfrencs par
u sont exactement les mmes (le compilateur les a partages), tandis que w est une
ache
et
autre chane.
"coucou"
w
"coucou"
==. Dans le cas des chanes, il existe une mthode equals spcialise qui
equals est l'galit
structurelle
d'crire une mthode pour raliser l'galit structurelle, si besoin est. Un exemple d'galit
structurelle est donn dans la section 5.3.
par valeur.
copies
vers de nouveaux
emplacements mmoire. Mais il faut bien garder l'esprit qu'une telle valeur est soit une
valeur primitive, soit un pointeur vers une zone de la mmoire, comme expliqu ci-dessus.
En particulier, dans ce second cas, seul le
mthode
pointeur
suivante
int x = 1;
int[] y = {1, 2, 3};
f(x, y);
Juste avant l'appel
on a la situation suivante :
21
y
x 1
Juste aprs l'appel
x 1
a 1
a = 2
Aprs l'appel
f,
et
b[2] = 7
et
et
et
1 2 3
x 1
a 2
1 2 7
la
la
x 1
1 2 7
f),
les variables
1 2 3
f.
tait un objet et si
b[2] = 7
dans
par
x 1
1 2 3
a 2
4 5 6
b = new
f:
x 1
En particulier, le tableau
{4, 5, 6}
1 2 3
par le GC.
Un objet allou dans une mthode n'est pas systmatiquement perdu pour autant. En
eet, il peut tre renvoy comme rsultat (ou stock dans une autre structure de donnes).
Si on considre par exemple la mthode suivante
b,
alors l'appel
g(1)
va conduire la
situation suivante
a 1
et c'est la
variables
1 1 1
valeur de b qui est renvoye, c'est--dire le pointeur vers le tableau. Bien que les
a et b sont dtruites, le tableau survivra (si la valeur renvoye par g est utilise
22
Exercice 1.1.
que
1,
int x = 1;
f(x);
System.out.println(x);
Notions de complexit
calculabilit,
ore des outils pour formaliser la notion d'algorithme de faon trs gnrale.
Elle s'intresse en fait essentiellement discuter les problmes qui sont rsolubles
informatiquement, c'est--dire distinguer les problmes
rsolus informatiquement) des problmes
indcidables
dcidables
complexit
ressources (temps, mmoire, etc.) ncessaires la rsolution de ces problmes. C'est typiquement ce dont on a besoin pour mesurer l'ecacit des algorithmes considrs dans
ce cours : on considre des problmes qui admettent une solution, mais pour lesquels on
cherche une solution ecace.
Ces thories permettent de formaliser proprement la notion d'algorithme, en complte
gnralit, en faisant abstraction du langage utilis, mais cela dpasserait compltement
l'ambition de ce polycopi. Dans ce polycopi, on va prendre la notion suivante d'algorithme : un algorithme
et
24
d, on sache clairement associer l'alA sur l'entre d, la valeur de cette mesure, note (A,d) : par exemple, pour un
algorithme de tri, si la mesure lmentaire est le nombre de comparaisons eectues,
(A,d) est le nombre de comparaisons eectues sur l'entre d (une liste d'entiers) par
l'algorithme de tri A pour produire le rsultat A(d) (cette liste d'entiers trie).
Il est clair que (A,d) est une fonction de l'entre d. La qualit d'un algorithme A n'est
donc pas un critre absolu, mais une fonction quantitative (A,.) des donnes d'entre
Il faut simplement qu'tant donne une entre
gorithme
naturel. Par exemple, cette fonction peut tre celle qui compte le nombre d'lments dans
la liste pour un algorithme de tri, la taille d'une matrice pour le calcul du dterminant,
la somme des longueurs des listes pour un algorithme de concatnation.
Pour passer d'une fonction des donnes vers les entiers, une fonction des entiers (les
tailles) vers les entiers, on considre alors la complexit
de l'algorithme
(A,n) =
au pire cas
: la complexit
(A,n)
max
d | taille(d)=n
(A,d).
n.
Exemple.
M = max1in ei ,
e1 ,e2 , ,en ,
avec
n 1,
T,
25
n1. Nous avons donc (A,d) = n1 pour cet algorithme A. Ce nombre est indpendant
d de taille n, et donc (A,n) = n 1.
de la donne
en moyenne
(A,n) = E[(A,d) | d
o
: la complexit moyenne
taille(d) = n],
(A,n) =
(d)(A,d),
d | taille(d)=n
o
(d)
n.
En pratique, le pire cas est rarement atteint et l'analyse en moyenne peut sembler plus
sduisante. Mais il est important de comprendre que l'on ne peut pas parler de moyenne
sans loi de probabilit (sans distribution) sur les entres, ce qui est souvent trs dlicat
estimer en pratique. Comment anticiper par exemple les matrices qui seront donnes
un algorithme de calcul de dterminant ? On fait parfois l'hypothse que les donnes
sont quiprobables (lorsque cela a un sens, comme lorsqu'on trie
nombres entre
et
et o l'on peut supposer que les permutations en entre sont quiprobables), mais cela
est bien souvent totalement arbitraire, et pas rellement justiable. Enn, les calculs de
complexit en moyenne sont plus dlicats mettre en uvre.
Exemple.
n, puisque
T sont des
(k 1)i1
.
ki
26
de
X (k 1)i1
(k 1)n
C=
n
+
i.
kn
ki
i=1
Or
x,
n
X
ixi1 =
i=1
1 + xn (nx n 1)
(1 x)2
Pn
i=0
xi =
1xn+1
) et donc
1x
n
(k 1)n
1
(k 1)n
n
C=n
.
+k 1
(1 + ) = k 1 1
kn
kn
k
k
k est trs grand devant n (on eectue par exemple une recherche dans un tableau
n = 1000 lments dont les valeurs sont parmi les k = 232 valeurs possibles de type
int), alors C n. La complexit moyenne est donc linaire en la taille du tableau, ce qui
ne nous surprend pas. Lorsqu'en revanche k est petit devant n (on eectue par exemple
une recherche parmi peu de valeurs possibles), alors C k . La complexit moyenne est
Lorsque
de
donc linaire en le nombre de valeurs, ce qui ne nous surprend pas non plus.
timalit ou non d'un algorithme pour rsoudre un problme donn. On xe un problme
(P,n) =
inf
max
n,
(A,d).
mais aussi l'algo-
rithme. On considre le meilleur algorithme qui rsout le problme, le meilleur tant celui
avec la meilleure complexit au sens de la dnition prcdente, c'est--dire au pire cas.
C'est donc la complexit du meilleur algorithme au pire cas.
L'intrt de cette dnition est le suivant : si un algorithme
(P,n), i.e.
(A,n) = (P,n)
pour tout
n,
possde la complexit
optimal. Tout autre algorithme est moins performant, par dnition. Cela permet donc
de prouver qu'un algorithme est optimal.
Il y a une subtilit cache dans la dnition ci-dessus. Elle considre la complexit
du problme
un algorithme pour une taille d'entres xe, mais plutt un algorithme qui fonctionne
quelle que soit la taille des entres. Plus subtilement encore, cet algorithme peut ou non
procder diremment selon la valeur de
n.
d'un problme se doit de faire cette distinction ; on parle alors de complexit uniforme et
non-uniforme. Mais ceci dpasse largement le cadre de ce cours.
27
max
n1
comparaisons. La rponse
est non ; dit autrement, cet algorithme est optimal en nombre de comparaisons. En effet, considrons la classe
maximum de
de
est tel
que tout lment autre que le maximum est compar au moins une fois avec un lment
sur un tableau
n1
lments en moins de
du problme
n1
est
(P,n) = n 1.
n, n log2 n,
croissantes, sur un processeur capable
n2 , n3 , ( 32 )n , 2n
et
n!
n
n = 10
<1
n = 30
<1
n = 50
<1
n = 100
<1
n = 1000
<1
n = 10000
<1
n = 100000 < 1
n = 1000000 1s
Complexit
s
s
s
s
s
s
s
n log2 n
<1s
<1s
<1s
<1s
<1s
<1s
2s
20s
n2
<1s
<1s
<1s
<1s
1s
2 min
3 heures
12 jours
n3
<1s
<1s
<1s
1s
18 min
12 jours
32 ans
31 710 ans
( 32 )n
<1s
<1s
11 min
12,9 ans
2n
<1s
18 min
36 ans
1017 ans
n!
4s
1025
ans
28
2.2.2 Conventions
Ce type d'exprience invite considrer qu'une complexit en
( 32 )n , 2n
ou
n!
ne peut
pas tre considre comme raisonnable. On peut discuter de savoir si une complexit en
n158 est en pratique raisonnable, mais depuis les annes 1960 environ, la convention en
informatique est que oui : toute complexit borne par un polynme en
est considre
comme raisonnable. Si on prfre, cela revient dire qu'une complexit est raisonnable
d
ds qu'il existe des constantes c, d, et n0 telles que la complexit est borne par cn , pour
n > n0 . Des complexits non raisonnables sont par exemple nlog n , ( 23 )n , 2n et n!.
Cela ore beaucoup d'avantages : on peut raisonner un temps (ou un espace
mmoire, ou un nombre de comparaisons) polynomial prs. Cela vite par exemple de
prciser de faon trop ne le codage, par exemple comment sont codes les matrices pour
un algorithme de calcul de dterminant : passer du codage d'une matrice par des listes
un codage par tableau se fait en temps polynomial et rciproquement.
D'autre part, on raisonne souvent une constante multiplicative prs. On considre que
deux complexits qui ne dirent que par une constante multiplicative sont quivalentes :
3
3
par exemple 9n et 67n sont considrs comme quivalents. Ces conventions expliquent
que l'on parle souvent de complexit en temps de l'algorithme sans prciser nement la
mesure de ressource lmentaire
RAM.
et
de Landau.
deux fonctions dnies des entiers naturels vers les entiers naturels (comme
f (n) = O(g(n))
si et seulement si il existe deux constantes positives
n0
et
telles que
n n0 ,f (n) Bg(n).
Ceci signie que
g.
En particulier
O(1)
O(1)
signie constant(e).
temps d'excution est constant et ne dpend pas de la taille des donnes. C'est donc un
ensemble constant d'oprations lmentaires (exemple : l'addition de deux entiers avec les
conventions donnes plus haut).
On dit d'un algorithme qu'il est linaire s'il utilise
polynomial s'il existe une constante a telle que le nombre total d'oprations lmentaires
a
est O(n ) : c'est la notion de raisonnable introduite plus haut.
29
2.3.1 Factorielle
Prenons l'exemple archi-classique de la fonction factorielle, et intressons-nous au
nombre d'oprations arithmtiques (comparaisons, additions, soustractions, multiplications) ncessaires son calcul. Considrons un premier programme calculant
n!
l'aide
d'une boucle.
n1
(une comparaison, une multiplication et une addition), plus une dernire comparaison
pour sortir de la boucle. La complexit est donc
plexit de
fact
La com-
n!,
cette
fois rcursivement.
static int
if (n ==
return
else
return
}
Soit
C(n)
fact(int n) {
0)
1;
n * fact(n-1);
C(n) = 3 + C(n 1)
et
i.
appels
fact,
O(n).
En eet, la pile
page 17.
temp,
dest.
n+1
de
un disque de
30
C(n) le nombre d'instructions lmentaires pour calculer hanoi(n, ini, temp, dest).
C(n + 1) 2C(n) + , o est une constante, et C(0) = 0. On en dduit
Nous avons
hanoi
Exercice * 2.1.
O(2n ).
n-ime
Deuxime partie
Structures de donnes lmentaires
Tableaux
De manire simple, un tableau n'est rien d'autre qu'une suite de valeurs stockes dans
des cases mmoire contigus. Ainsi on reprsentera graphiquement le tableau contenant
la suite de valeurs entires
3,7,42,1,4,8,12
de la manire suivante :
42
12
i-ime
en temps constant.
En Java, on peut construire un tel tableau en numrant ses lments entre accolades,
spars par des virgules :
a[0],
la seconde avec
a[1],
a[-1],
a,
on crira
a[1] = 0;
Si l'indice ne dsigne pas une position valide dans le tableau, l'aectation provoque la
mme exception que pour l'accs.
On peut obtenir la longueur du tableau
vaut 7 sur l'exemple prcdent. L'accs la longueur se fait en temps constant. Un tableau
peut avoir la longueur 0.
Il existe d'autres procds pour construire un tableau que d'numrer explicitement ses
lments. On peut notamment construire un tableau de taille donne avec la construction
new
34
Chapitre 3. Tableaux
a.
s 0 et parcourir tous
les lments du tableau pour les ajouter un par un cette variable. La mthode naturelle
les valeurs
0, 1,
. . .,
de la manire suivante :
lments
du tableau
avec la construction
le programme se simplie en
int s = 0;
for (int x : a)
s += x;
return s;
Ce programme eectue exactement
a.length
A(X) =
ai X i
0i<n
Une mthode simple, mais nave, consiste crire une boucle qui ralise exactement la
somme ci-dessus.
mthode de Horner.
X.
X i,
en factorisant intelligemment, et en
35
a[i].
Si la variable
a.length
additions et
Exercice 3.1.
Exercice 3.2.
en argument et
premires
F0 = 0
F1 = 1
Fn = Fn2 + Fn1
n 2.
pour
Exercice 3.3.
les lments d'un tableau en utilisant l'algorithme suivant appel mlange de Knuth
(Knuth
shue ),
pour
soit
de
n1
i (inclus)
i et j
k1
avec
(int)(Math.random() * k ).
tous
v.
interrompre le parcours ds que l'lment est trouv. Une solution consiste utiliser
return
36
Chapitre 3. Tableaux
Exercice 3.4.
valeur de
apparat dans
Exercice 3.5.
a,
o la
crire une mthode qui renvoie l'lment maximal d'un tableau d'entiers.
On discutera des diverses solutions pour traiter le cas d'un tableau de longueur 0.
comparaisons, o
cependant, la recherche d'un lment dans un tableau peut tre ralise de manire plus
ecace. C'est le cas par exemple lorsque le tableau est tri. On peut alors exploiter l'ide
suivante : on coupe le tableau en deux par le milieu et on dtermine si la valeur
doit
tre recherche dans la moiti gauche ou droite. En eet, il sut pour cela de la comparer
avec la valeur centrale. Puis on rpte le processus sur la portion slectionne.
x=9
on cherche dans
on compare
x=9
on cherche dans
on compare
x=9
a[0:7]
avec
a[3]=6
12
14
12
14
12
14
12
14
a[4:7]
avec
a[5]=12
a[4:4]
avec
a[4]=9
On note que seulement trois comparaisons ont t ncessaires pour trouver la valeur. C'est
une application du principe
suprieures
v,
et
d.
sont infrieures
<v
d
?
et
>v
avec 0 et
n
a.length-1,
respectivement.
37
while (g <= d) {
on calcule l'indice de l'lment central, en faisant la moyenne de
et
d.
int m = (g + d) / 2;
Il est important de noter qu'on eectue ici une division
entire.
g et d, ce qui
a[m] existe et qu'il est bien situ entre g et d. Si l'lment a[m] est
if (a[m] == v)
return true;
Sinon, on dtermine si la recherche doit tre poursuivie gauche ou droite. Si
a[m] < v,
on poursuit droite :
if (a[m] < v)
g = m + 1;
Sinon, on poursuit gauche :
else
d = m - 1;
Si on sort de la boucle
while,
d).
On renvoie alors
false
g)
ou strictement plus
return false;
Le code complet est donn programme 1 page 38.
Java fournit une telle mthode
binarySearch
java.util.Arrays.
algorithme est au pire O(log n)
dans la classe
dg<
itrations de la boucle,
2k
k . Initialement, on a g = 0 et d = n 1 et
k = 0, donc l'ingalit est tablie. Supposons maintenant l'ingalit vraie au rang k et
g d. la n de la k + 1-ime itration, on a soit g = m+1, soit d = m-1. Dans le premier
La dmonstration se fait par rcurrence sur
cas, on a donc
g+d
g+d dg
n
n
+1 d
=
< k
= k+1
2
2
2
2 2
2
38
Chapitre 3. Tableaux
d g 0.
k log2 (n),
on a
d g < 1,
O(n).
O(log n),
pas dans les mmes conditions : une recherche dichotomique est exclue si les donnes ne
sont pas tries.
Exercice 3.6.
Exercice 3.7.
forme
(g+d)/2
binarySearch
230
termine toujours.
int.
sous la
Comment y
remdier ?
et le modie
et le passe la mthode
a.
f,
f,
on a
la variable
0 1 2 3
b
et, aprs l'excution de l'instruction
39
b[2] = 42;,
on a
0 1 42 3
b
En particulier, aprs l'appel la mthode
tableau
en anglais).
On suppose, pour simplier, qu'on ne s'intresse ici qu' des tableaux contenant des
lments de type
int.
ResizableArray
fournissant
un constructeur
ResizableArray(int len)
pour construire un nouveau tableau redimensionnable de taille
len,
mthodes suivantes :
int size()
void setSize(int len)
int get(int i)
void set(int i, int v)
La mthode
size
a posteriori
avec la mthode
setSize.
Les mthodes
get
et
set
sont les oprations de lecture et d'criture dans le tableau. Comme pour un tableau usuel,
elles lveront une exception si on cherche accder en dehors des bornes du tableau.
40
Chapitre 3. Tableaux
3.4.1 Principe
L'ide de la ralisation est trs simple : on utilise un tableau usuel pour stocker les
lments et lorsqu'il devient trop petit, on en alloue un plus grand dans lequel on recopie
les lments du premier. Pour viter de passer notre temps en allocations et en copies,
on s'autorise ce que le tableau de stockage soit trop grand, les lments au-del d'un
certain indice n'tant plus signicatifs. La classe
class ResizableArray {
private int length;
private int[] data;
o le champ
this.data
this.length
. . . lments . . .
. . . inutilis . . .
this.data.length
0 length data.length
On note le caractre priv des champs
l'invariant ci-dessus.
Pour crer un nouveau tableau redimensionnable de taille
il sut d'allouer un
length
length.
data,
len,
ga-
lement :
ResizableArray(int len) {
this.length = len;
this.data = new int[len];
}
int size() {
return this.length;
}
Pour accder au
i-ime
int get(int i) {
if (i < 0 || i >= this.length)
throw new ArrayIndexOutOfBoundsException(i);
return this.data[i];
}
L'aectation est analogue (voir page 42). Toute la subtilit est dans la mthode
qui redimensionne un tableau pour lui donner une nouvelle taille
il n'y a rien faire, si ce n'est mettre le champ
this.data,
il va
setSize
Plusieurs cas de
len.
41
this.data
this.data
this.data
this.data = a;
L'ancien tableau sera ramass par le GC. Enn on met jour la valeur de
quel que soit le rsultat du test
len > n
this.length,
this.length = len;
Exercice 3.8.
exemple si elle devient grande par rapport au nombre d'lments eectifs et que le tableau
occupe beaucoup de mmoire. Modier la mthode
setSize
tableau.
Exercice 3.9.
int[] toArray()
numbers.txt,
42
Chapitre 3. Tableaux
43
Puis on alloue un nouveau tableau redimensionnable destin recevoir les entiers que l'on
va lire. Initialement, il ne contient aucun lment :
readLine
du
BufferedReader
while (true) {
String s = f.readLine();
La valeur
null
break
if (s == null) break;
Dans le cas contraire, on tend la taille du tableau redimensionnable d'une unit, et on
stocke l'entier lu dans la dernire case du tableau :
Ceci conclut la lecture du chier. Pour tre complet, il faudrait aussi grer les exceptions
Exercice 3.10.
d'autre part,
Complexit.
mensionnable de taille 0 et nous avons augment sa taille d'une unit chaque lecture
d'une nouvelle ligne. Si la mthode
setSize
cation d'un nouveau tableau et une recopie des lments dans ce tableau, la complexit
aurait t quadratique, puisque la lecture de la
cot
i,
i-ime
1 + 2 + + n =
pour un chier de
n(n + 1)
= O(n2 )
2
setSize
elle consiste doubler (au minimum) la taille du tableau lorsqu'il doit tre agrandi.
Montrons que le cot total est alors linaire. Supposons, sans perte de gnralit, que
n 2 et posons k = blog2 (n)c c'est--dire 2k n < 2k+1 . Au total, on aura eectu
k + 2 redimensionnements pour arriver un tableau data de taille nale 2k+1 . Aprs le
i-ime redimensionnement, pour i = 0, . . . ,k + 1, le tableau a une taille 2i et le i-ime
i
redimensionnement a donc cot 2 . Le cot total est alors
k+1
X
i=0
2i = 2k+2 1 = O(n).
44
Chapitre 3. Tableaux
setSize
sionnement n'est pas ncessaire) et d'autres au contraire un cot non constant, mais
la complexit totale reste linaire. Ramen l'ensemble des
comme si chaque opration d'ajout d'un lment avait eu un cot constant. On parle
O(1).
sous
Si on crit navement
String s = "0";
for (int i = 1; i <= n; i++)
s += ", " + i;
alors la complexit est quadratique, car chaque concatnation de chanes, pour construire
s + ", " + i, a un cot proportionnel la longueur de s, c'est--dire proportionnel i. L encore, on peut avantageusement exploiter le principe du tableau redimensionnable pour construire la chane s. Il sut d'adapter le code de ResizableArray
le rsultat de
pour des caractres plutt que des entiers (ou encore en faire une classe gnrique voir
section 3.4.5 plus loin).
Plus simplement encore, la bibliothque Java fournit une classe
StringBuilder
pour
construire des chanes de caractres incrmentalement sur le principe du tableau redimensionnable. Une mthode
StringBuilder,
append
d'o le code
buf.toString().
Exercice 3.11.
qui renvoie le contenu d'un tableau redimensionnable sous la forme d'une chane de caractres telle que
"[3, 7, 2]".
On se servira d'un
StringBuilder
chane.
structure de pile.
ou d'assiettes pose sur une table. En particulier, on ne peut accder qu'au dernier lment
ajout, qu'on appelle le
B,
puis
sommet
A,
puis
45
C
B
A
B,
qu'on dpile
A.
une pile est donc dernier arriv, premier sorti (en anglais, on parle de LIFO pour
tions suivantes :
s.push(B);
s.push(C);
C
B
A
int x = s.pop();
// x vaut C
B
A
n1
sut d'augmenter la taille du tableau d'une unit. Pour dpiler, il sut de rcuprer le
dernier lment du tableau puis de diminuer sa taille d'une unit.
Pour bien faire les choses, cependant, il convient d'encapsuler le tableau redimensionnable dans la classe
class Stack {
private ResizableArray elts;
...
}
Ainsi, seules les mthodes fournies pourront en modier le contenu. Le code complet est
donn programme 3 page 46. Note : La bibliothque Java fournit une version gnrique
de la structure de pile, dans
java.util.Stack<E>.
46
class Stack {
private ResizableArray elts;
Stack() {
this.elts = new ResizableArray(0);
}
boolean isEmpty() {
return this.elts.size() == 0;
}
int size() {
return this.elts.size();
}
void push(int x) {
int n = this.elts.size();
this.elts.setSize(n + 1);
this.elts.set(n, x);
}
int pop() {
int n = this.elts.size();
if (n == 0)
throw new NoSuchElementException();
int e = this.elts.get(n - 1);
this.elts.setSize(n - 1);
return e;
}
int top() {
int n = this.elts.size();
if (n == 0)
throw new NoSuchElementException();
return this.elts.get(n - 1);
}
}
Chapitre 3. Tableaux
47
swap qui change les deux lments au sommet
Stack, puis comme une nouvelle mthode de
Stack.
des lments.
class ResizableArray<T> {
private int length;
private T[] data;
Le code reste essentiellement le mme, au remplacement du type
int
par le type
aux
T[].
new T[len]
mais
il n'y a pas de risque ici car il s'agit d'un champ priv que nous ne pourrons jamais
confondre avec un tableau d'un autre type.
La seconde subtilit concerne la mthode
setSize,
est diminue. Jusqu' prsent, on ne faisait rien, si ce n'est mettre jour le champ
length.
Mais dans la version gnrique, il faut prendre soin de ne pas conserver tord des pointeurs
vers des objets qui pourraient tre rcuprs par le GC car inutiliss par ailleurs. Il faut
donc eacer les lments partir de l'indice
valeur
null.
length.
48
Chapitre 3. Tableaux
Listes chanes
Ce chapitre introduit une structure de donne fondamentale en informatique, la
liste
Singly
simple que
class Singly {
int element;
Singly next;
}
La valeur
null nous sert reprsenter la liste vide i.e. la liste ne contenant aucun lment.
Le constructeur naturel de cette classe prend en arguments les valeurs des deux champs :
x,
1, 2
et
3,
de la faon suivante :
Singly
1
Singly
2
Singly
3
50
tte
Singly x = null;
ce qui correspond une situation o
aucun
Singly, une telle valeur n'en est pas pour autant un objet de la classe
Singly, avec un champ element et un champ next. Par consquent, il faudra pendre soin
Bien que de type
dans la suite de toujours bien traiter le cas de la liste vide, de manire viter l'exception
NullPointerException.
null.
x = x.next.
Le parcours s'arrte
while (x != null) {
...
x = x.next;
}
Comme premier exemple, considrons une mthode statique
un entier
cessivement la valeur
contains.
s = s.next;
false
return false;
Il est important de noter que ce code fonctionne correctement sur une liste vide, c'est--
dire lorsque
ce qui est
page 51.
51
Complexit.
contient
cot
n.
Si en revanche la valeur
la position
i,
apparat avec quiprobabilit toutes les positions possibles dans la liste, le cot moyen
de sa recherche est donc
n+1
1X
i=
n i=1
2
ce qui est galement linaire. La structure de liste chane n'est donc pas particulirement
adapte la recherche d'un lment ; elle a d'autres applications, qui sont dcrites dans
les prochaines sections.
Exercice 4.1.
int length(Singly s)
gueur de la liste
s.
Exercice 4.2.
l'lment d'indice
exception si
de la liste
s,
qui renvoie
Achage
listToString qui conver"[1 -> 2 -> 3]". Comme
nous l'avons expliqu plus haut (section 3.4.3), la faon ecace de construire une telle
52
s.element,
au
StringBuilder, puis
c'est--dire si s.next
la chane
n'est pas
while (s != null) {
sb.append(s.element);
if (s.next != null) sb.append(" -> ");
s = s.next;
}
Une fois sorti de la boucle, on ajoute le crochet fermant et on renvoie la chane contenue
dans le
StringBuilder.
return sb.append("]").toString();
L encore, ce code fonctionne correctement sur une liste vide, renvoyant la chane
Exercice 4.3.
"[]".
seul
de la liste
exclus, et enn
imaginer une situation o les lments ne peuvent tre tous stocks en mmoire car trop
nombreux, par exemple.
L'ide est la suivante. On parcourt la liste en maintenant un lment candidat
la victoire dans le tirage. l'examen du
i-ime
randomElement
qui ralise ce tirage. On commence par vacuer le cas d'une liste vide,
index.
53
1/index.
while (s != null) {
if ((int)(index * Math.random()) == 0) candidate = s.element;
Pour cela, on tire un entier alatoirement entre 0 inclus et
index
exclus et on le compare
index++;
s = s.next;
candidate.
return candidate;
On note qu'au tout premier tour de boucle qui existe car la liste est non vide
l'lment de la liste est ncessairement slectionn car
Math.random() < 1
et donc
(int)(1 * Math.random()) = 0. La valeur arbitraire que nous avions utilise pour initialiser la variable candidate ne sera donc jamais renvoye. On en dduit galement que
le programme fonctionne correctement sur une liste rduite un lment. Le code complet
est donn programme 5 page 53.
Exercice 4.4.
lments avec
n 1,
chaque lment
54
push
et
pop
constant. Exactement comme nous l'avions fait avec le tableau redimensionnable dans
la section 3.4.4, on va
encapsuler
Stack,
de manire
class Stack {
private Singly head;
...
}
Le code complet de la structure de pile est donn programme 6 page 55. Si on construit
une pile avec
Stack
head
Singly
3
Singly
2
Singly
1
Comme nous l'avons dj dit, la bibliothque Java fournit une version gnrique de la
structure de pile dans
Exercice 4.5.
java.util.Stack<E>.
int size la classe Stack, contenant le nombre
int size() pour renvoyer sa valeur. Expliquer
priv.
Exercice 4.6.
size
doit tre
String toString()
pour la
Stack, qui renvoie le contenu d'une pile sous la forme d'une chane de caractres
"[1, 2, 3]" o 1 est le sommet de la pile. On pourra s'inspirer de la mthode
listToString donne plus haut.
classe
telle que
le.
push et pop, mais o les lments sont renvoys par pop dans
insrs avec push, c'est--dire suivant une logique premier arriv,
class Stack {
private Singly head;
Stack() {
this.head = null;
}
boolean isEmpty() {
return this.head == null;
}
void push(int x) {
this.head = new Singly(x, this.head);
}
int top() {
if (this.head == null)
throw new NoSuchElementException();
return this.head.element;
}
int pop() {
if (this.head == null)
throw new NoSuchElementException();
int e = this.head.element;
this.head = this.head.next;
return e;
}
}
55
56
Dit autrement, il
pop
push
Queue.
head
et
tail,
class Queue {
private Singly head, tail;
...
}
Ainsi, si on construit une le avec
Queue
head
tail
Singly
1
Singly
2
Singly
3
o les insertions se font droite et les retraits gauche. Les lments apparaissent donc
chans dans le mauvais sens . Le code est plus subtil que pour une pile et mrite qu'on
s'y attarde. Le constructeur se contente d'initialiser les deux champs
null
Queue() {
this.head = this.tail = null;
}
this.head vaut null si et
this.tail vaut null. En particulier, la le est vide si et seulement this.head
null
boolean isEmpty() {
return this.head == null;
}
Considrons maintenant l'insertion d'un nouvel lment, c'est--dire la mthode
commence par allouer un nouvel lment de liste
e,
push. On
la liste chane.
void push(int x) {
Singly e = new Singly(x, null);
Il faut alors distinguer deux cas, selon que la le est vide ou non. Si elle est vide, alors
this.head et this.tail pointent dsormais tous les deux sur cet unique lment de liste :
57
if (this.head == null)
this.head = this.tail = e;
e la n de la liste existante, dont le dernier lment est
oublier de mettre ensuite jour le pointeur this.tail :
this.tail,
sans
else {
this.tail.next = e;
this.tail = e;
}
push. Pour le retrait d'un lment, on procde l'autre extrmit
de la liste, c'est--dire du ct de this.head. On commence par vacuer le cas d'une liste
Ceci conclut le code de
vide :
int pop() {
if (this.head == null)
throw new NoSuchElementException();
Si en revanche la liste n'est pas vide, on peut accder son premier lment, qui nous
donne la valeur renvoyer :
int e = this.head.element;
Avant de la renvoyer, il faut supprimer le premier lment de la liste, ce qui est aussi
simple que
this.head = this.head.next;
this.head
null :
this.tail
null
si
this.head
est devenu
et
this.tail,
on va mettre
push teste la
this.tail null
this.head
et non celle de
this.tail.
valeur de
Cependant, mettre
liste devenue maintenant inutile. Enn, il n'y a plus qu' renvoyer la valeur
return e;
Le code complet de la structure de le est donn programme 7 page 58. Note : La bibliothque Java fournit une version gnrique de la structure de le dans
Exercice 4.7.
java.util.Queue<E>.
58
class Queue {
private Singly head, tail;
Queue() {
this.head = this.tail = null;
}
boolean isEmpty() {
return this.head == null;
}
void push(int x) {
Singly e = new Singly(x, null);
if (this.head == null)
this.head = this.tail = e;
else {
this.tail.next = e;
this.tail = e;
}
}
int top() {
if (this.head == null)
throw new NoSuchElementException();
return this.head.element;
}
int pop() {
if (this.head == null)
throw new NoSuchElementException();
int e = this.head.element;
this.head = this.head.next;
if (this.head == null) this.tail = null;
return e;
}
59
liste cyclique .
0
Si on modie le champ
l'lment
s2,
next
s4
(4.1)
c'est--dire
s4.next = s2;
alors on se retrouve dans la situation suivante :
null,
(4.2)
d'autres lments de la liste. D'une manire gnrale, on peut montrer que toute liste
simplement chane est soit de la forme (4.1), c'est--dire une liste linaire se terminant
par
null,
0
= 3).
longueur nie
=2
et
Il est important de comprendre que les programmes que nous avons crits plus haut, qui
sont construits autour d'un parcours de liste, ne fonctionnent plus sur une liste cyclique,
car ils ne terminent plus dans certains cas. En eet, le critre d'arrt
s == null
ne sera
jamais vri. Si on voulait les adapter pour qu'ils fonctionnent galement sur des listes
cycliques, il faudrait tre mme de dtecter la prsence d'un cycle. Si on y rchit un
instant, on comprend que le problme n'est pas trivial.
On prsente ici un algorithme de dtection de cycle, d Floyd, et connu sous le nom
d'algorithme du livre et de la tortue. Comme son nom le suggre, il consiste parcourir
la liste deux vitesses direntes : la tortue parcourt la liste la vitesse 1 et le livre
parcourt la mme liste la vitesse 2. Si un quelconque moment, le livre atteint la n
60
de la liste, elle est dclare sans cycle. Et si un quelconque moment, le livre et la tortue
se retrouvent la mme position, c'est que la liste contient un cycle. Le code est donn
programme 8 page 60. La seule dicult dans ce code consiste correctement traiter les
dirents cas o le livre (la variable
un
NullPointerException
hare)
dans le calcul de
hare.next.
false.
null
et que
dlicate. Tant que la tortue est l'extrieur du cycle, elle s'en approche chaque tape
de l'algorithme, ce qui assure la terminaison de cette premire phase (en au plus
tapes
avec la notation ci-dessus). Et une fois la tortue prsente dans le cycle, on note qu'elle ne
peut tre dpasse par le livre. Ainsi la distance qui les spare diminue chaque tape
de l'algorithme, ce qui assure la terminaison de cette seconde phase (en au plus
tapes).
n o
est le nombre d'lments de la liste. Cet algorithme est donc tonnamment ecace. Et
x0
et une fonction
telle que
f (x)
est
de telle fonction. L'algorithme de Floyd permet alors de calculer partir de quel rang ce
gnrateur entre dans un cycle et la longueur de ce cycle.
61
1
17, ou encore d'en modier la structure, pour faire reboucler l'lment 4 vers l'lment 2,
alors ce changement aectera la liste
d'alias que nous avons dj voque avec les tableaux (voir page 19).
Il existe de nombreuses situations dans lesquelles on sait pertinemment qu'une liste
ne sera pas modie aprs sa cration. On peut donc chercher le garantir, comme un
invariant du programme. Une solution consisterait faire des champs
element
et
next
des champs privs et n'exporter que des mthodes qui ne modient pas les listes. Une
solution encore meilleure consiste dclarer les champs
element
et
next
comme
final.
Ceci implique qu'ils ne peuvent plus tre modis au-del du constructeur (le compilateur
le vrie), ce qui est exactement ce que nous recherchons.
class Singly {
final int element;
final Singly next;
...
}
Ds lors, une situation de partage telle que celle illustre ci-dessus n'est plus problmatique. En eet, la portion de liste partage ne peut tre modie ni par le dtenteur de
ni par celui de
y,
persistante
ou
immuable .
Un style de pro-
grammation qui ne fait usage que de structures de donnes persistantes est dit
purement
applicatif. L'un des intrts de ce style de programmation est une diminution signicative
du risque d'erreurs dans les programmes. En particulier, il devient beaucoup plus facile
de raisonner sur le code, en utilisant le raisonnement mathmatique usuel, sans avoir
se soucier constamment de l'tat des structures de donnes. Un autre avantage est la
possibilit d'un
partage
62
class Doubly {
int element;
Doubly next, prev;
...
o
et
next est le pointeur vers l'lment suivant, comme pour les listes simplement chanes,
prev le pointeur vers l'lment prcdent. Une liste rduite un unique lment peut
Doubly(int element) {
this.element = element;
this.next = this.prev = null;
}
Bien entendu, on pourrait aussi crire un constructeur naturel qui prend en arguments les
valeurs des trois champs. On ne le fait pas ici, et on choisit plutt un style de construction
de listes o de nouveaux lments seront insrs avant ou aprs des lments existants.
insertAfter(int v) qui ajoute un nouvel ldsign par this. On commence par construire le
ci-dessus.
void insertAfter(int v) {
Doubly e = new Doubly(v);
Il faut maintenant mettre jour les dirents pointeurs
this
et
e.
next
et
prev
est
this.
e.prev = this;
this est e. Cependant, il y avait
this.next, et il convient alors
e et this.next.
this,
if (this.next != null) {
e.next = this.next;
e.next.prev = e;
}
Enn, on peut mettre jour
this.next = e;
nant les entiers 1, 2, 3, dans cet ordre, en commenant par construire l'lment de valeur
1, puis en insrant successivement 3 et 2 aprs 1.
63
Doubly
1
Doubly
2
Doubly
3
next
vaut
Exercice 4.8.
null.
prev
lment de valeur
juste avant
this.
vaut
null
insertBefore(v)
void remove() {
if (this.prev !=
this.prev.next
if (this.next !=
this.next.prev
}
null)
= this.next;
null)
= this.prev;
this
(voire les deux la fois). Pour eectuer une telle suppression dans une liste simplement
chane, il nous faudrait galement un pointeur sur l'lment qui prcde
Il est important de noter que la mthode
remove
dans la liste.
x.remove()
Pour y remdier, plusieurs solutions peuvent tre utilises. On peut par exemple placer
aux deux extrmits de la liste deux lments ctifs, qui ne seront pas considrs comme
faisant partie de la liste et qui ne seront jamais supprims. On parle de
sentinelles . Mieux
encore, on peut encapsuler la liste doublement chane dans un objet qui maintient des
pointeurs vers son premier et son dernier lment, exactement comme nous l'avons fait
pour raliser des piles et des les avec des listes simplement chanes page 54.
64
null)
= this.next;
null)
= this.prev;
Le code complet des listes doublement chanes est donn programme 9 page 64.
La bibliothque Java fournit une classe gnrique de listes doublement chanes dans
java.util.LinkedList<E>.
chane pour rsoudre le problme suivant, dit problme de Josephus. Des joueurs sont
placs en cercle. Ils choisissent un entier
et liminent le
J(n,p)
dsigne le nombre de
n=7
et
p=5
on
i.e.
J(7,5) = 6.
crivons une mthode statique
josephus(int n, int p)
65
J(n,p) en utilisant une liste doublement chane cyclique, reprsentant le cercle des joueurs.
La mthode remove ci-dessus pourra alors tre utilise directement pour liminer un
joueur. On commence par crire une mthode statique circle(int n) qui construit une
liste doublement chane cyclique de longueur n. Elle commence par crer le premier
lment, de valeur 1 (on suppose ici n 1).
n, . . . ,2
procdant dans cet ordre, on aura bien au nal l'lment 2 juste aprs l'lment 1.
n. l'issue
dans la boucle,
n.
On le fait donc
de la boucle, il ne sera
lorsque
vaut
n.
En ralit, ce test est positif ds le premier tour de boucle (et seulement au premier). Mais
le traiter l'extrieur de la boucle nous obligerait faire un cas particulier pour
n = 1.
return l1;
circle
josephus.
des joueurs.
et
c.next.
while (c != c.next) {
Il s'agit ici d'une comparaison
physique
(avec
!=),
pointeurs. chaque tour de boucle, on procde l'limination d'un joueur. Pour cela, on
p 1 fois dans le cercle, avec c = c.next, puis on limine le joueur c ainsi obtenu
c.remove.
avance
avec
next
66
c = c.next;
while.
return c.element;
Le code complet est donn programme 10 page 66. Pour plus de dtails concernant ce
problme, et notamment une solution analytique, on pourra consulter
matics
Concrete Mathe-
Exercice 4.9.
Rcrire la mthode
chane. Indication : dans la boucle interne, conserver un pointeur sur l'lment prcdent,
de manire pouvoir supprimer facilement le
Exercice 4.10.
Rcrire la mthode
p-ime
josephus
Singly
on crit donc
et
Doubly
par le type
67
class Singly<E> {
E element;
Singly<E> next;
et pour les listes doublement chanes
class Doubly<E> {
E element;
Doubly<E> next, prev;
Le reste du code est le mme, au remplacement prs de
68
Tables de hachage
Supposons qu'un programme ait besoin de manipuler un
ensemble
de chanes de ca-
ractres (des noms de personnes, des mot-cls, des URL, etc.) de telle manire que l'on
puisse, ecacement, d'une part ajouter une nouvelle chane dans l'ensemble, et d'autre
part chercher si une chane appartient l'ensemble. Avec les structures de donnes vues
jusqu' prsent, c'est--dire les tableaux et les listes, ce n'est pas facile. L'ajout peut
certes se faire en temps constant par exemple au dbut ou la n d'une liste ou la
n d'un tableau redimensionnable mais la recherche prendra un temps
semble contient
O(n)
si l'en-
les chanes dans un tableau tri, mais c'est alors l'ajout qui prendra un temps
O(n)
dans
le pire des cas. Dans ce chapitre, nous prsentons une solution simple et ecace ce
problme : les tables de hachage.
L'ide est trs simple. Si les lments taient des entiers entre 0 et
directement un tableau de taille
m.
m 1, on utiliserait
situation en utilisant une fonction f associant aux direntes chanes un entier dans
0..m 1. Bien entendu, il est impossible de trouver une telle fonction injective en gnral.
Il va donc falloir grer les collisions, c'est--dire les cas o deux ou plusieurs chanes
ont la mme valeur par f . Dans ce cas, on va les stocker dans un mme paquet . Si
la rpartition entre les dirents paquets est quilibre, alors chaque paquet ne contient
qu'un petit nombre de chanes. On peut alors retrouver rapidement un lment car il ne
reste plus qu' le chercher dans son paquet. Si on ralise chaque paquet par une simple
liste chane, ce qui convient parfaitement, une table de hachage n'est au nal rien d'autre
qu'un tableau de listes.
Considrons par exemple une table de hachage constitue de
m=7
paquets et conte-
hachage,
f,
h,
fonction de
la fonction f
appele
comme
f (s) = h(s)
Ainsi, l'opration
modulo
mod
h(s)
m.
f
la longueur de la chane
s.
0..m 1.
Supposons
Alors on obtient la
70
""
"we like"
"the codes"
"in"
"Java."
"in", respectivement de
longueurs 9 et 2, car ces deux chanes ont pour image 2 par la fonction f . (Mais l'ordre dans
Ainsi le paquet 2 contient les deux chanes
"the codes"
et
lequel ces deux chanes apparaissent dans la liste peut varier suivant l'ordre d'insertion
des lments dans la table.)
5.1 Ralisation
HashTable. On commence par
Bucket, pour reprsenter les paquets
class Bucket {
String element;
Bucket next;
Bucket(String element, Bucket next) {
this.element = element;
this.next = next;
}
}
La classe
HashTable
paquets :
class HashTable {
private Bucket[] buckets;
Pour crire le constructeur, il faut se donner une valeur pour
m, c'est--dire un nombre de
paquets. Idalement, cette taille devrait tre du mme ordre de grandeur que le nombre
d'lments qui seront stocks dans la table. L'utilisateur pourrait ventuellement fournir
cette information, par exemple sous la forme d'un argument du constructeur, mais ce n'est
pas toujours possible. Considrons donc pour l'instant une situation simplie o cette
taille est une constante compltement arbitrairement, savoir
m = 17.
5.1. Ralisation
71
ici 19. Quoique l'on fasse, le plus important rside dans la dernire ligne, qui assure que
la valeur nale est bien un indice lgal dans le tableau
soin de masquer le bit de signe (avec
& 0x7fffffff)
buckets.
En particulier, on a pris
donne un rsultat
du mme signe que son premier argument, qui peut tre ngatif ici en cas de dbordement
de la capacit du type
int.
void add(String s) {
int i = hash(s);
this.buckets[i] = new Bucket(s, this.buckets[i]);
}
Une variante consisterait vrier que
tamment l'exercice 5.2). Mais la version ci-dessus a l'avantage de garantir une complexit
O(1)
dans tous les cas. Et on peut parfaitement tre dans une situation o on sait que
ne fait pas partie de la table par exemple parce qu'on a eectu le test d'appartenance
au pralable.
Pour raliser le test d'appartenance, justement, on procde de la mme faon, en
utilisant la mthode
hash
se trouver, si elle est prsente. Pour chercher dans la liste correspondante, on ajoute par
exemple une mthode statique
contains
la classe
Bucket
contains
de la classe
HashTable
boolean contains(String s) {
return Bucket.contains(this.buckets[hash(s)], s);
}
Le code complet est donn programme 11 page 72.
1. En revanche, il ne serait pas correct d'crire Math.abs(h) % M car si h est gal au plus petit entier,
c'est--dire 231 = 2147483648, alors Math.abs(h) vaudra 2147483648 et le rsultat de hash sera
ngatif.
72
boolean contains(String s) {
return Bucket.contains(this.buckets[hash(s)], s);
}
5.2. Redimensionnement
Exercice 5.1.
73
size
quoi le champ
Exercice 5.2.
void remove(String s)
pour supprimer un l-
ment
de
5.2 Redimensionnement
Le code que nous venons de prsenter est en pratique trop naf. Le nombre d'lments
contenus dans la table peut devenir grand par rapport la taille du tableau. Cette
charge
implique de gros paquets, qui dgradent les performances des oprations (ici seulement
contains).
de l'opration
quement,
mthode
dulo
dynami-
hash
this.buckets.length
doubler la taille
pour cela que
total d'lments (voir l'exercice 5.1 ci-dessus). Il sut alors d'ajouter une ligne au dbut
(ou la n) de la mthode
si ncessaire.
void add(String s) {
if (this.size > this.buckets.length/2) resize();
...
Tout le travail se fait dans cette nouvelle mthode
resize.
this.buckets,
sans oublier de
le nouveau tableau
une boucle
for
et,
74
Complexit.
bleau par hasard. Exactement comme nous l'avons fait pour les tableaux redimensionnables (voir page 43), on peut montrer que l'insertion successive de
table de hachage aura un cot total
O(n).
Certains appels
add
lments dans la
complexit amortie
de
add
reste
O(1).
La complexit de la recherche est plus dicile valuer, car elle dpend de la qualit
de la fonction de hachage. Si la fonction de hachage envoie tous les lments dans le
mme paquet c'est le cas par exemple si elle est constante alors la complexit de
contains
sera clairement
O(n).
lments dans les dirents paquets, alors la taille de chaque paquet peut tre borne
par une constante et la complexit de
contains
sera alors
O(1).
La bibliothque Java propose justement une version gnrique des tables de hachage, sous
et d'une classe
class Pair {
String fst, snd;
...
}
alors il conviendra de l'quiper d'une fonction de hachage d'une part, par exemple en
faisant la somme des valeurs de hachage des deux chanes
fst
et
snd
75
et d'une galit structurelle d'autre part en comparant les deux paires membre membre.
Il y a l une subtilit : la mthode
argument de type
Object
equals
Object
avec un
En eet, la mthode
i-ime
lment (get) et la
recherche d'un lment (contains). Les direntes complexits sont les suivantes :
tableau
tableau tri
liste
table de hachage
add
O(1) amorti
O(n)
O(1)
O(1) amorti
get
O(1)
O(1)
O(i)
contains
O(n)
O(log n)
O(n)
O(1)
76
i-ime
possible de combiner les structures de table de hachage et de liste chane pour conserver,
ct d'une table de hachage, l'ordre d'insertion des lments. Les bibliothques Java
java.util.LinkedHashSet<E>
et
java.util.LinkedHashMap<E>
font cela.
Arbres
La notion d'arbre est dnie rcursivement. Un arbre est un ensemble ni de
tiquets par des valeurs, o un nud particulier
nuds,
racine de l'arbre et
sous-arbres ) de r. En
est appel la
ls
(ou
A
B
C
E
D
F
reprsente un arbre de racine A ayant trois ls. Un nud qui ne possde aucun ls est
appel une
feuille .
hauteur
d'un
arbre est dnie comme le nombre de nuds le long du plus long chemin de la racine
une feuille (ou, de manire quivalente, comme la longueur de ce chemin, plus un). La
hauteur de l'arbre ci-dessus est donc trois.
La notion d'arbre
binaire
soit vide, soit un nud possdant exactement deux ls appels ls gauche et ls droit. Un
arbre binaire n'est pas un cas particulier d'arbre, car on distingue les sous-arbres gauche
et droit (on parle d'arbre positionnel). Ainsi, les deux arbres suivants sont distincts :
A
B
A
B
h.
Pour
h = 0,
possde au plus
2h 1
nuds,
Tree
78
Chapitre 6. Arbres
class Tree {
int value;
Tree left, right;
}
o les champs
left
et
right
null.
la reprsentation d'une liste doublement chane (voir page 64), aux noms des champs
prs. Ce qui change, c'est l'invariant de structure. Pour une liste doublement chane, la
structure impose par construction tait linaire : tout lment suivait son prcdent et
prcdait son suivant. Ici la structure impose par construction sera celle d'un arbre. En
sans expliciter les objets comme des petites botes avec des champs ; cela prendrait trop
de place.
E
D
Comme nous l'avons expliqu plus haut avec les listes (voir section 4.4.2), on peut garantir
le caractre immuable d'un arbre, c'est--dire en faire une structure de donnes persistante,
en ajoutant simplement le qualicatif
final
class Tree {
final int value;
final Tree left, right;
}
Plus loin dans ce chapitre, nous montrerons d'autres faons de construire des arbres, dans
les sections 6.4 et 6.5.
StackOverflowError,
si la hauteur de l'arbre est trs grande. (Les exercices 6.1 et 6.2 proposent de le vrier.)
79
size
rence d'une liste chane pour laquelle nous aurions pu calculer la longueur l'aide d'une
boucle, on ne voit pas ici comment faire cela facilement. C'est en fait possible
mais nous
allons ignorer ce problme pour l'instant. Dans de nombreuses situations o les arbres
sont utiliss, leur hauteur est limite (voir par exemple la section 6.3.2 ci-dessous) il n'y
a donc pas lieu de se soucier d'un ventuel
Exercice 6.1.
un arbre
StackOverflowError.
linaire gauche
contenant
Tree leftDeepTree(int n)
qui construit
Exercice 6.2.
Exercice 6.3.
d'un arbre.
Parcours.
De mme que nous avions crit des mthodes parcourant les lments d'une
liste chane, on peut chercher parcourir les lments d'un arbre, par exemple pour les
acher tous. Supposons par exemple que l'on veuille acher les lments de la gauche
vers la droite , c'est--dire d'abord les lments du ls gauche, puis la racine, puis les
lments du ls droit. L encore, il est naturel de procder rcursivement, et le parcours
est aussi simple que
parcours inxe
de l'arbre (inorder
traversal
en anglais). Si
on ache la valeur de la racine avant le parcours du ls gauche (resp. aprs le parcours
du ls droit) on parle de
parcours prxe
(resp.
postxe )
de l'arbre.
x,
1. Il est mme toujours possible de remplacer une fonction rcursive par une boucle.
x.
80
Chapitre 6. Arbres
arbre binaire de recherche. En particulier, on en dduit que les lments
On appelle cela un
apparaissent dans l'ordre croissant lorsque l'arbre est parcouru dans l'ordre inxe. Nous
allons exploiter cette structure pour crire des oprations de recherche et de modication
ecaces. Par exemple, chercher un lment dans un arbre binaire de recherche ne requiert
pas de parcourir tout l'arbre : il sut de descendre gauche ou droite selon la comparaison entre l'lment recherch et la racine de l'arbre. Dans ce qui suit, on considre
des arbres binaires de recherche
persistants
class BST {
final int value;
final BST left, right;
}
d'obtenir facilement son plus petit lment. Il sut en eet de descendre le long de la
branche gauche, tant que cela est possible. La mthode
une boucle
while
getMin
n'est pas
null
sera rutilise plus loin pour crire la mthode de suppression dans un arbre binaire de
recherche. Le cas de
null
x,
x,
soit
null.
Lorsque
ct poursuivre la descente. L encore, on peut crire cette descente sous la forme d'une
boucle
while.
Exercice 6.4.
Rcrire la mthode
contains
rcursivement.
81
x dans un arbre binaire de reb, en suivant le mme principe
immuables, on crit une mthode add qui
dans
x.
if (b == null)
return new BST(x);
Dans l'autre cas, on compare l'lment
la racine de
b,
et on poursuit rcursivement
if (x < b.value)
return new BST(add(b.left, x), b.value, b.right);
if (x > b.value)
return new BST(b.left, b.value, add(b.right, x));
Il est important de noter que, aprs l'appel rcursif, on reconstruit le nud de l'arbre de
return b;
On fait ici le choix de ne pas construire d'arbre contenant de doublon, mais on aurait trs
bien pu choisir de renvoyer au contraire un arbre contenant une occurrence supplmentaire
de
x.
Le choix que nous faisons ici est cohrent avec l'utilisation des arbres binaires de
recherche que nous allons faire plus loin pour raliser une structure d'ensemble.
Exercice 6.5.
les cas,
i.e.
mme si
Exercice * 6.6.
y apparat dj.
plutt que rcursivement ? Le problme serait-il le mme si l'arbre n'tait pas immuable ?
82
Chapitre 6. Arbres
if (x < b.value)
return new BST(remove(b.left, x), b.value, b.right);
if (x > b.value)
return new BST(b.left, b.value, remove(b.right, x));
Lorsqu'il y a galit, en revanche, on se retrouve confront une dicult : il faut supprimer la racine de l'arbre, c'est--dire renvoyer un arbre contenant exactement les lments
b.left et b.right, mais il n'y a pas de moyen simple de raliser cette union. On souhaite autant que possible conserver b.left ou b.right inchang, pour limiter la quantit
de
if (b.right == null)
return b.left;
getMin(b.right) et o ce dernier est
b.right avec une mthode removeMin que nous allons crire dans un instant.
Exercice 6.7.
add
et
remove
en renvoyant
remove
add ajoute
add et remove en utilisant cette ide. On pourra lever une exception pour signaler
que l'arbre est inchang, en prenant soin de ne pas la rattraper chaque appel rcursif
mais uniquement au sommet de la mthode.
Exercice 6.8.
infrieur ou
83
84
Chapitre 6. Arbres
6.3.2 quilibrage
Telles que nous venons de les crire dans la section prcdente, les direntes oprations
sur les arbres binaires de recherche ont une complexit linaire, c'est--dire
O(n) o n est
le nombre d'lments contenus dans l'arbre. En eet, notre insertion peut tout fait
conduire un peigne c'est--dire un arbre de la forme
A
B
C
D
Il sut en eet d'insrer les lments dans l'ordre A, B, C, D. Une insertion dans l'ordre
inverse donnerait de mme un peigne, dans l'autre sens. Au-del de la dgradation des performances, un tel arbre linaire peut provoquer un dbordement de pile dans les mthodes
nombreuses manires d'quilibrer un arbre binaire de recherche. Nous optons ici pour une
solution connue sous le nom d'AVL (de leurs auteurs Adelson-Velsky et Landis [1]). Elle
consiste maintenir l'invariant suivant :
Pour tout nud, les hauteurs de ses sous-arbres gauche et droit dirent d'au
plus une unit.
crivons une nouvelle classe
class AVL {
final int value;
final AVL left, right;
final int height;
...
Le champ
Pour traiter correctement le cas d'un arbre vide, on se donne la mthode suivante pour
renvoyer la hauteur d'un arbre :
left
et
right.
85
dj construit
de la construction.
d'un arbre
Les mthodes qui ne construisent pas d'arbres, mais ne font que les consulter, sont
sans risquer de violer l'invariant des AVL. On va donc remplacer l'utilisation du constructeur par une mthode
E
F
D
B
(6.1)
et que l'on insre la valeur A avec la mthode d'insertion dans les arbres binaires de
recherche, alors on obtient l'arbre
E
D
B
A
(6.2)
qui n'est pas quilibr, puisque la dirence de hauteurs entre les sous-arbres gauche et
droit du nud E est maintenant de deux. Il est nanmoins facile de rtablir l'quilibre.
En eet, il est possible d'eectuer des transformations locales sur les nuds d'un arbre
qui conservent la proprit d'arbre binaire de recherche. Un exemple de telle opration
est la
rotation droite,
86
Chapitre 6. Arbres
n
rotation droite
x>n
x<k
x<k
k<x<n
k<x<n
par la racine
x>n
et
n.
modie que deux nuds dans la structure de l'arbre. De manire symtrique, on peut
eectuer une rotation gauche. Ainsi l'arbre (6.2) peut tre rquilibr en eectuant une
rotation droite sur le sous-arbre de racine D. On obtient alors l'arbre
E
B
qui est bien un AVL. Une simple rotation, gauche ou droite, ne sut pas ncessairement
rtablir l'quilibre. Si par exemple on insre maintenant C, on obtient l'arbre
E
B
D
C
qui n'est pas un AVL. On peut alors tenter d'eectuer une rotation droite la racine E
ou une rotation gauche au nud B, mais on obtient les deux arbres suivants
B
A
E
E
D
F
qui ne sont toujours pas des AVL. Cependant, celui de droite peut tre facilement rquilibr en eectuant une rotation droite sur la racine E. On obtient alors l'AVL
D
B
A
E
C
87
lv
lv
rotation droite
r
lr
ll
lr
ll
lrv
lv
lv
rotation gauche-droite
lrv
r
ll
lrr
lrr
ll
lrl
lrl
symtrique de rotation droite-gauche. Ces quatre oprations, savoir les deux rotations
simples et les deux rotations doubles, susent rquilibrer les AVL en toute circonstance. crivons maintenant le code de la mthode
commence par calculer les hauteurs
hl
et
hr
considre en premier lieu le cas o le dsquilibre est caus par le sous-arbre gauche
lr
ll
de
On note que
(en haut).
else {
AVL lrl = lr.left, lrr = lr.right;
int lrv = lr.value;
88
Chapitre 6. Arbres
}
return new AVL(new AVL(ll, lv, lrl), lrv, new AVL(lrr, v, r));
L encore,
lr
ne peut tre
null,
car
height(lr) > 0.
garantie, comme le montre la gure 6.1 (en bas). On notera que le dsquilibre peut tre
lrl ou lrr, indiremment, et que dans les deux cas la double rotation gauchel
est plus haut que r), ce qui achve ce premier cas. On traite de manire symtrique le cas
o r est la cause du dsquilibre
caus par
droite rtablit bien l'quilibre. Il n'y a pas d'autre cas possible de dsquilibre (lorsque
et
} else
return new AVL(l, v, r);
ce qui achve le code de la mthode
h1
n?
et un autre de hauteur
h2
on pourrait encore enlever des lments l'un des deux sous-arbres tout en conservant la
h,
on a donc
En prenant le logarithme ( base 2) de cette ingalit, on en dduit la majoration recherche sur la hauteur
n:
1
log2 5
h <
log2 (n + 2) +
2
log2
log2
1,44 log2 (n + 2) 0,328
Un AVL a donc bien une hauteur logarithmique en son nombre d'lments. Comme nous
l'avons dit plus haut, cela garantit une complexit
mais aussi l'absence de
StackOverflowError.
La bibliothque Java propose des arbres binaires de recherche quilibrs (des arbres
89
90
Chapitre 6. Arbres
void remove(int x) {
this.root = AVL.remove(x, this.root);
}
boolean isEmpty();
boolean contains(int x);
void add(int x);
void remove(int x);
Exactement comme nous l'avons fait prcdemment pour construire des structures de pile
et de le au dessus de la structure de liste chane, nous encapsulons un objet de type
AVL
AVLSet
class AVLSet {
private AVL root;
...
}
Le reste du code est immdiat ; il est donn programme 14 page 90.
Ajouter la classe
91
add
et
remove
remove
add
l'exercice 6.7.
Exercice * 6.10.
Ajouter la classe
Exercice 6.11.
O(n + m),
et
sont les
des lments :
class AVL<E> {
final E value;
final AVL<E> left, right;
final int height;
Cela ne sut cependant pas. Le code a besoin de pouvoir comparer les lments entre eux,
contains
ou la mthode
add.
E,
une mthode pour comparer deux lments. Pour cela on utilise l'interface suivante :
interface Comparable<K> {
int compareTo(K k);
}
Le signe de l'entier renvoy par
compareTo
indique comment
de la classe
x.compareTo(y).
AVL,
et
AVL
s'crit
en testant le signe
contains de la classe
92
Chapitre 6. Arbres
mots
(ici du type
String
tiquete par une lettre et chaque nud contient un boolen indiquant si la squence de
lettres menant de la racine de l'arbre ce nud est un mot appartenant l'ensemble.
Par exemple, l'arbre reprsentant l'ensemble de mots {"if",
est le
suivant :
false
false
false
true
true
o
true
n
false
e
true
arbre de prxes ,
trie
en anglais.
L'intrt d'une telle structure de donne est de borner le temps de recherche d'un lment
dans un ensemble la longueur du mot le plus long de cet ensemble, quelque soit le nombre
de mots qu'il contient. Plus prcisment, cette proprit est garantie seulement si toutes
les feuilles d'un arbre de prxes reprsentent bien un mot de l'ensemble, c'est--dire si
elles contiennent toutes une valeur boolenne vrai. Cette
bonne formation
des arbres de
HashMap
Trie
class Trie {
boolean word;
HashMap<Character, Trie> branches;
...
branches de la racine de l'arbre est une table de
hachage contenant deux entres, une associant le caractre 'i' au sous-arbre de gauche,
et une autre associant le caractre 'd' au sous-arbre de droite.
Ainsi, dans l'exemple ci-dessus, le champ
L'arbre de prxes vide est reprsent par un arbre rduit un unique nud o le
champ
word
vaut
false
et
branches
93
Trie() {
this.word = false;
this.branches = new HashMap<Character, Trie>();
}
contains
boolean contains(String s) {
La recherche consiste descendre dans l'arbre en suivant les lettres de
l'aide d'une boucle
for,
s.
On le fait ici
Trie t = this;
for (int i = 0; i < s.length(); i++) { // invariant t != null
t = t.branches.get(s.charAt(i));
t.branches ne contient pas d'entre pour le i-ime caractre de s, alors la mthode
get ci-dessus renverra null. Dans ce cas, on conclut immdiatement que s n'appartient
pas t.
Si
Dans le cas contraire, on passe au caractre suivant. Si on sort de la boucle, c'est qu'on
est parvenu jusqu'au dernier caractre de
s.
return t.word;
s,
de manire similaire
au parcours eectu pour la recherche. C'est cependant lgrement plus subtil, car il faut
ventuellement crer de nouvelles branches dans l'arbre pendant la descente. Comme pour
la recherche, on procde la descente avec une boucle
mot et une variable
for
void add(String s) {
Trie t = this;
for (int i = 0; i < s.length(); i++) { // invariant t != null
char c = s.charAt(i);
Avant de suivre le branchement donn par le caractre
dans une variable locale
b.
94
Chapitre 6. Arbres
null.
get
aura renvoy
Il faut alors ajouter une nouvelle branche. On le fait en crant un nouvel arbre
d'autre part.
if (t == null) {
t = new Trie();
b.put(c, t);
}
On peut alors passer au caractre suivant, car on a assur que
n'est pas
s.
true
null.
Une fois
pour indiquer la
}
t.word = true;
Si le mot
peut tre gnralise toute valeur pouvant tre vue comme une suite de lettres, quelle
que soit la nature de ces lettres. C'est le cas par exemple pour une liste. C'est aussi le
cas d'un entier, si on voit ses bits comme formant un mot avec les lettres
et
1.
Dans ce
Exercice 6.12.
Ajouter la classe
Trie
s,
Exercice * 6.13.
remove
branches vides,
i.e.
La mthode
une mthode
void remove(String s)
qui
si elle existe.
remove
branches
ne contient jamais
une entre vers un arbre ne contenant aucun mot. Indication : on pourra procder rcursivement et se servir de la mthode suivante
boolean isEmpty() {
return !this.word && this.branches.isEmpty();
}
qui teste si un arbre ne contient aucun mot supposer que l'invariant ci-dessus est
Exercice 6.14.
Optimiser la structure de
de l'arbre ne contiennent pas une table de hachage vide, mais plutt la valeur
Exercice 6.15.
La structure
Trie
pourquoi, la dirence des arbres binaires vus plus haut, on ne peut pas en faire facile-
void add(String s) {
Trie t = this;
for (int i = 0; i < s.length(); i++) { // invariant t != null
char c = s.charAt(i);
Map<Character, Trie> b = t.branches;
t = b.get(c);
if (t == null) {
t = new Trie();
b.put(c, t);
}
}
t.word = true;
}
95
96
Chapitre 6. Arbres
6.5 Cordes
On prsente ici une troisime structure d'arbre, les cordes. Il s'agit d'une structure
persistante pour reprsenter de grandes chanes de caractres ecacement, et permettre
notamment des oprations de concatnation et d'extraction de sous-chanes sans impliquer
de copies. La structure de corde s'appuie sur une ide trs simple : une corde n'est rien
d'autre qu'un arbre binaire dont les feuilles sont des chanes (usuelles) de caractres et
dont les nuds internes sont vus comme des concatnations. Ainsi l'arbre
App
"a ver"
App
"y long"
" string"
drations nous poussent raner lgrement l'ide ci-dessus. D'une part, de nombreux
algorithmes auront besoin d'un accs ecace la longueur d'une corde, notamment pour
dcider de descendre dans le sous-arbre gauche ou dans le sous-arbre droit d'un nud
App.
Il est donc souhaitable d'ajouter la taille de la corde comme une dcoration de chaque
nud interne. D'autre part, il est important de pouvoir partager des sous-chanes entre
les cordes elles-mmes et avec les chanes usuelles qui ont t utilises pour les construire.
Ds lors, plutt que d'utiliser une chane complte dans chaque feuille, on va stocker plus
d'information pour dsigner un fragment d'une chane Java, par exemple sous la forme
de deux entiers indiquant un indice et une longueur. Pour reprsenter de tels arbres, on
pourrait imaginer la classe suivante
class Rope {
int length;
String word; int ofs; // feuille
Rope left, right;
// noeud interne
...
}
o le champ
length
feuille uniquement et les deux derniers dans le cas d'un nud interne uniquement. Cette
reprsentation a tout de mme le dfaut d'tre inutilement gourmande : deux champs sont
systmatiquement gchs dans chaque objet. Nous allons adopter une reprsentation plus
subtile, en tirant parti de l'hritage de classes fourni par Java.
On commence par crire une classe
Rope
-dire aussi bien une feuille qu'un nud interne. On y stocke la longueur de la corde,
puisque c'est l l'information commune aux deux types de nuds.
6.5. Cordes
97
App,
calcule
la longueur de la corde
Exercice 6.16.
len
s.
Str
et
exception.
Exercice 6.17.
ofs
Ajouter la classe
Str
chane en argument.
Accs un caractre.
char get(int i) qui renvoie le i-ime caractre d'une corde. On la dclare dans la classe Rope, car on veut pouvoir
accder au i-ime caractre d'une corde sans connatre sa nature. Ainsi, on veut pouvoir
crire r.get(3) avec r de type Rope comme dans l'exemple ci-dessus. Mais on ne peut
pas dnir get dans la classe Rope. Aussi on la dclare comme une mthode abstraite.
crivons maintenant une mthode
98
Chapitre 6. Arbres
get
Str
et
App.
Dans la classe
Str,
char get(int i) {
return this.str.charAt(this.ofs + i);
}
Dans la classe
App,
get
rcursivement.
char get(int i) {
return (i < this.left.length) ?
this.left.get(i) : this.right.get(i - this.left.length);
}
Toute la subtilit de la programmation oriente objet se trouve ici : on ne connat pas la
nature de
this.left
et
this.right
get.
Le bon morceau de code sera appel, par la vertu de l'appel dynamique de mthode.
Exercice 6.18.
une position valide dans la corde. Dans le cas contraire, lever une exception.
Extraction de sous-chane.
sous-corde. Comme pour
Str,
c'est immdiat :
App, c'est plus subtil. En eet, la sous-corde peut se retrouver soit entire-
ment dans la corde de gauche, soit entirement dans la corde de droite, soit cheval sur
les deux. On distingue ces trois cas en calculant la longueur de la portion de
commenant l'indice
ofs
this.left
this.left.
len,
this.right.
6.5. Cordes
99
if (llen <= 0)
return this.right.sub(-llen, len);
Sinon, c'est que le rsultat doit tre la concatnation d'une portion de
portion de
this.right,
sub.
this.left et d'une
Exercice 6.19.
sub
ofs
et
len
dsignent bien une portion valide de la corde. Dans le cas contraire, lever une exception.
Exercice 6.20.
Exercice 6.21.
Rope, Str
et
App.
String toString()
Exercice 6.22.
final)
StringBuilder ?
ds que l'on cherche concatner deux cordes dont la somme des longueurs ne dpasse
pas une constante donne (par exemple 256 caractres) alors on construit directement
un nud de type
r)
Str
mthode
toString
App.
r)
Rope append(Rope
de l'exercice prcdent.
100
Chapitre 6. Arbres
Programme 16 Cordes
abstract class Rope {
int length;
abstract char get(int i);
abstract Rope sub(int ofs, int len);
}
class Str extends Rope {
String str;
int ofs;
Str(String str, int ofs, int len) {
this.str = str;
this.ofs = ofs;
this.length = len;
}
char get(int i) {
return this.str.charAt(this.ofs + i);
}
Rope sub(int ofs, int len) {
return new Str(this.str, this.ofs + ofs, len);
}
}
class App extends Rope {
Rope left, right;
App(Rope left, Rope right) {
this.length = left.length + right.length;
this.left = left;
this.right = right;
}
char get(int i) {
return (i < this.left.length) ?
this.left.get(i) : this.right.get(i - this.left.length);
}
Rope sub(int ofs, int len) {
int llen = this.left.length - ofs;
if (len <= llen) // tout dans left
return this.left.sub(ofs, len);
if (llen <= 0) // tout dans right
return this.right.sub(-llen, len);
return new App(this.left.sub(ofs, llen),
this.right.sub(0, len - llen));
}
}
Files de priorit
les de priorit
(en anglais
priority queue ),
leur priorit et non plus dans l'ordre d'arrive. L'interface que l'on cherche dnir va
donc ressembler quelque chose comme
boolean isEmpty();
int size();
void add(int x);
int getMin();
void removeMin();
Dans cette interface, la notion de minimalit concide avec la notion de plus grande priorit. Contrairement aux les, on prfre distinguer l'accs au premier lment et sa suppression, par deux oprations distinctes, pour des raisons d'ecacit qui seront expliques
plus loin. Ainsi, la mthode
thode
removeMin le supprime. On trouvera des applications des les de priorits plus loin
tas (heap
stock est plus prioritaire que les deux lments situs immdiatement au-dessous. Ainsi,
un tas contenant les lments
suivante :
3
7
21
12
(7.1)
On note qu'il existe d'autres tas contenant ces mmes lments. Par dnition, l'lment
le plus prioritaire est situ la racine et on peut donc y accder en temps constant. Les
102
deux sections suivantes proposent deux faons direntes de reprsenter un tel tas.
7(1)
21(3)
12(2)
9(4)
Cette numrotation permet de reprsenter le tas dans un tableau. Ainsi, le tas ci-dessus
correspond au tableau 5 lments suivant :
12 21
4
9
De manire gnrale, la racine de l'arbre occupe la case d'indice 0 et les racines des deux
sous-arbres du nud stock la case
2i + 2.
aux cases
2i + 1
et
O(log n)
a priori
pour la le de priorit mais une solution plus lgante consiste utiliser un tableau
redimensionnable. De tels tableaux sont prsents dans le chapitre 3 et on va donc rutiliser
ici la classe
ResizableArray
class Heap {
private ResizableArray elts;
elts)
103
Heap() {
this.elts = new ResizableArray(0);
}
Le nombre d'lments contenus dans le tas est exactement celui du tableau redimensionnable, d'o un code immdiat pour les deux mthodes
size
et
isEmpty
int size() {
return this.elts.size();
}
boolean isEmpty() {
return this.elts.size() == 0;
}
La mthode
getMin
int getMin() {
if (this.elts.size() == 0)
throw new NoSuchElementException();
return this.elts.get(0);
}
x,
x jusqu' la bonne
x est plus petit que son pre,
c'est--dire la valeur situe immdiatement au dessus dans l'arbre, on change leurs deux
valeurs et on recommence. Par exemple, l'ajout de 1 dans le tas (7.1) est ralis en trois
tapes :
3
7
21
3
12
1 < 12
7
21
1
1
1<3
12
7
21
3
9
12
moveUp(int x, int i)
qui insre
de racine
fi
du pre de
et la valeur
104
Si
est suprieur
x,
moveUp
partir de
en descendant la valeur
fi.
la place
if (y > x) {
this.elts.set(i, y);
moveUp(x, fi);
Si en revanche
x,
alors
de l'y aecter.
} else
this.elts.set(i, x);
Ceci achve le code de
moveUp.
add
La mthode
mente la taille du tableau d'une unit, en ajoutant une case la n du tableau, puis
appelle la mthode
moveUp
void add(int x) {
int n = this.elts.size();
this.elts.setSize(n + 1);
moveUp(x, n);
}
Comme expliqu plus haut, la mthode
Exercice 7.1.
Rcrire la mthode
moveUp
while.
lgrement plus dlicat que d'insrer un nouvel lment. La raison en est qu'il s'agit de
supprimer la racine de l'arbre et qu'il faut donc trouver par quel lment la remplacer.
L'ide consiste choisir l'lment tout en bas droite du tas, c'est--dire l'lment occupant la dernire case du tableau, comme candidat, puis le faire descendre dans le tas
jusqu' sa place, un peu comme on a fait monter le nouvel lment lors de l'insertion.
Supposons par exemple que l'on veuille supprimer le plus petit lment du tas suivant :
1
4
11
7
5
et
et
descente est termine. Sinon, on change 8 avec le plus petit des deux nuds
a et b, et on
105
4 < 8, 7
4
11
11
5 < 11, 8
7
11
moveDown(int x, int i)
i.
7
8
i.
Il faut
soigneusement tenir compte du fait que ces deux nuds n'existent peut-tre pas.
int j = 2 * i + 1;
if (j + 1 < n && this.elts.get(j + 1) < this.elts.get(j))
j++;
Si le nud
j,
j,
x,
alors
la position
i,
doit descendre.
puis on procde
} else
this.elts.set(i, x);
Ceci achve le code de la mthode
moveDown.
La mthode
removeMin
de suppression du
plus petit lment d'un tas s'en dduit alors facilement. On commence par traiter le cas
pathologique d'un tas vide.
void removeMin() {
int n = this.elts.size() - 1;
if (n < 0) throw new NoSuchElementException();
Puis on extrait la valeur
position du tableau, avant de diminuer la taille du tableau d'une unit, puis d'appeler la
mthode
moveDown
pour placer
de la position 0.
int x = this.elts.get(n);
this.elts.setSize(n);
if (n > 0) moveDown(x, 0);
removeMin
O(log n) o n est
classe Heap est donn
a une complexit
106
107
facilement, appel
(en anglais
heapsort ).
tous les lments trier dans un tas, puis on les ressort successivement avec les mthodes
getMin et removeMin. crire une mthode void sort(int[] a) pour trier un tableau en
utilisant cet algorithme. (Le tri par tas est dcrit en dtail section 12.4.)
auto-quilibrs.
skew heaps.
SkewHeap, qui encapsule un arbre binaire (le tas) et son nombre
la classe Tree de la section 6.1.
class SkewHeap {
private Tree root;
private int size;
On maintiendra l'invariant que le champ
size
SkewHeap.
SkewHeap() {
this.root = null;
this.size = 0;
}
Les mthodes
isEmpty
et
size
en temps constant.
boolean isEmpty() {
return this.size == 0;
}
int size() {
return this.size;
}
isEmpty pourrait tout aussi bien
getMin renvoie le plus petit lment,
this.root
est
null.
La mthode
tester si
mthode
int getMin() {
if (this.isEmpty()) throw new NoSuchElementException();
return this.root.value;
}
Enn la
108
Opration de fusion.
thode
merge
qui fusionne deux tas. On l'crit comme une mthode statique et prive qui
t1
et
t2,
t1
t1
et
t2.
t1.left, t1.right
et
t2
gauche ou droit. Parmi toutes ces possibilits, on choisit celle qui change les deux sousarbres de
t1.left
t1,
t2.
t1.right
prend la place de
else
return new Tree(merge(t2.right, t1), t2.value, t2.left);
Autres oprations.
et
t2
removeMin.
merge.
De cette opration
merge
x,
add
size.
void add(int x) {
this.root = merge(this.root, new Tree(null, x, null));
this.size++;
}
Pour supprimer le plus petit lment, c'est--dire la racine du tas, il sut de fusionner
les deux sous-arbres gauche et droit. On commence par tester si le tas est eectivement
non vide.
int removeMin() {
if (this.isEmpty()) throw new NoSuchElementException();
109
res (pour
merge.
la renvoyer comme
size
res.
this.size--;
return res;
Exercice 7.3.
Ajouter la classe
Complexit.
this
le contenu du tas
SkewHeap
log n.
amorti, le pire des cas d'une suppression particulire pouvant tre suprieur.
Vector<E>
de
la bibliothque Java). S'il s'agit d'arbres binaires, on utilise des arbres gnriques, comme
au chapitre 6. Le reste du code est alors facilement adapt. Lorsqu'il s'agit de comparer
deux lments
et
y,
on n'crit plus
x < y
mais
x.compareTo(y) < 0.
La bibliothque Java propose une telle structure de donnes gnrique dans la classe
java.util.Comparator<T>
interface Comparator<T> {
int compare(T x, T y);
}
C'est alors la mthode
lments.
compare
110
int removeMin() {
if (this.isEmpty()) throw new NoSuchElementException();
int res = this.root.value;
this.root = merge(this.root.left, this.root.right);
this.size--;
return res;
}
Classes disjointes
Ce chapitre prsente une structure de donnes pour le problme des classes disjointes,
connue sous le nom de
union-nd.
union-nd.
8.1 Principe
Sans perte de gnralit, on suppose que l'ensemble partitionner est celui des
entiers
{0,1, . . . ,n 1}.
UnionFind
avec l'interface
suivante :
class UnionFind {
UnionFind(int n)
int find(int i)
void union(int i, int j)
}
Le constructeur
UnionFind(n)
i,
find(i)
{0,1, . . . ,n 1}
dtermine la classe
classe. En particulier, on dtermine si deux lments sont dans la mme classe en com-
et
L'ide principale est de lier entre eux les lments d'une mme classe. Dans chaque
classe, ces liaisons forment des chemins qui mnent tous un unique reprsentant, qui est
le seul lment li lui-mme. La gure 8.1 montre un exemple o l'ensemble
{0,1, . . . ,7}
est partitionn en deux classes dont les reprsentants sont respectivement 3 et 4. Il est
possible de reprsenter une telle structure en utilisant des nuds allous en mmoire
individuellement (voir exercice 8.3). Cependant, il est plus simple et souvent plus ecace
d'utiliser un tableau qui lie chaque entier un autre entier de la mme classe. Ces liaisons
mnent toujours au reprsentant de la classe, qui est associ sa propre valeur dans le
tableau. Ainsi, la partition de la gure 8.1 est reprsente par le tableau suivant :
112
7
3
L'opration
L'opration
l'un des deux reprsentants l'autre. An d'atteindre de bonnes performances, on apporte
deux amliorations. La premire consiste
eectue par
find
pendant la recherche
trouvs sur le chemin parcouru pour l'atteindre. La seconde consiste maintenir, pour
chaque reprsentant, une valeur appele
rang
pourrait avoir un chemin dans cette classe. Cette information est stocke dans un second
tableau et est utilise par la fonction
union
possibles d'une union. Cette structure de donnes est attribue McIlroy et Morris [ ] et
8.2 Ralisation
Dcrivons maintenant le code de la structure
union-nd,
UnionFind
dont une instance reprsente une partition. Cette classe contient deux tableaux privs :
link
rank
class UnionFind {
private int[] link;
private int[] rank;
rank n'est signicative que pour des lments i qui sont des
pour lesquels link[i] = i. Initialement, chaque lment forme
une classe lui tout seul, c'est--dire est son propre reprsentant, et le rang de chaque
classe vaut 0.
UnionFind(int n) {
if (n < 0) throw new IllegalArgumentException();
this.link = new int[n];
for (int i = 0; i < n; i++) this.link[i] = i;
this.rank = new int[n];
}
8.2. Ralisation
113
La fonction
int find(int i) {
if (i < 0 || i >= this.link.length)
throw new ArrayIndexOutOfBoundsException(i);
int p = this.link[i];
if (p == i) return i;
Sinon, on calcule rcursivement le reprsentant
de renvoyer
r.
r,
int r = this.find(p);
this.link[i] = r;
return r;
find
i,
sur
tait dj li
on trouvera
directement. Bien
sans eet.
L'opration
union
ri
et
rj.
et
j.
On
rien faire.
rj,
on fait de
rj
le reprsentant de l'union,
ri
rj.
rj
qui est le
else {
this.link[rj] = ri;
Dans le cas o les deux classes ont le mme rang, l'information de rang doit alors tre
mise jour, car la longueur du plus long chemin est susceptible d'augmenter d'une unit.
if (this.rank[ri] == this.rank[rj])
this.rank[ri]++;
114
union
utilise la fonction
Complexit.
n
et
UnionFind
oprations
find
et
qui crot extrmement lentement. Elle crot si lentement qu'on peut la considrer comme
constante pour toute application pratique vues les valeurs de
et
Introduction to Algorithms
Exercice 8.1.
Ajouter la structure
union-nd
une mthode
int numClasses()
don-
Exercice 8.2.
deux tableaux
Si les lments ne sont pas des entiers conscutifs, on peut remplacer les
rank
et
link
Exercice 8.3.
UnionFind
en
union-nd
consiste ne
pas utiliser de tableaux, mais reprsenter directement chaque lment comme un objet
contenant deux champs
rank
et
link.
Si
class Elt<E> {
private E value;
private Elt<E> link;
private int rank;
...
}
Il n'est plus ncessaire de maintenir d'information globale sur la structure
union-nd, car
Elt
Elt<E>
est la suivante :
Elt(E x)
Elt<E> find()
void union(Elt<E> e)
Elt(E x) construit une classe contenant un unique lment, de valeur x.
On pourra choisir la convention qu'un pointeur link est null lorsqu'il s'agit d'un reprsentant. crire ce constructeur ainsi que les mthodes find et union.
Le constructeur
8.2. Ralisation
115
116
Exercice 8.4.
union-nd
union-nd
sont les direntes cases. L'ide est que deux cases sont dans la mme classe si et seulement
si elles sont relies par un chemin. Initialement, toutes les cases du labyrinthe sont spares
les unes des autres par des murs. Puis on considre toutes les paires de cases adjacentes
(verticalement et horizontalement) dans un ordre alatoire. Pour chaque paire
(c1 ,c2 )
on
avec
union.
crire un
mlange de Knuth
Justier que, l'issue de la construction, chaque case est relie toute autre case par
un unique chemin.
Troisime partie
Algorithmes lmentaires
Arithmtique
et
v,
gcd
pour
et
v.
(9.1)
v soit nul, et renvoie alors la valeur de u, qui est le pgcd des valeurs initiales
La terminaison
et le fait que
u,v 0.
reste par
La correction
de l'algorithme repose sur le fait que l'instruction (9.2) prserve le plus grand diviseur
commun. Quand on parvient
le pgcd des valeurs initiales de
itrations pour
u>v>0
alors
u Fs+1
et
v Fs
120
Chapitre 9. Arithmtique
(Fn )
Exercice 9.1.
u
ou
s = O(log u).
Une analyse
u,v 0.
Si
de Java renvoie
une valeur du mme signe que son premier argument). Modier le code de la mthode
gcd
pour qu'elle renvoie toujours un rsultat positif ou nul, quel que soit le signe de ses
Exercice 9.2.
u > v.
Montrer que,
O(log(max(u,v))).
pour qu'il calcule galement les coecients de Bzout, c'est--dire un triplet d'entiers
tels que
r0 u + r1 v = r2 = gcd(u,v).
v , mais avec deux triplets
d'entiers ~
u = (u0 ,u1 ,u2 ) et ~v = (v0 ,v1 ,v2 ). Initialement, on prend ~u = (1,0,u) et ~v = (0,1,v).
et
avec
q = bu2 /v2 c
(9.2)
traduction littrale de cet algorithme en Java, utilisant des tableaux pour reprsenter
les vecteurs
~u
et
~v ,
v2
et
v.
et
v,
u2
gcd
uniquement, on retrouve les mmes calculs que ceux eectus dans la mthode
la seule dirence que
u2 mod v2
u0 u + u1 v = u2
v0 u + v1 v = v2
121
chaque tour de boucle est certes suprieur, mais il reste born et le nombre d'itrations
est exactement le mme. La complexit est donc toujours
Exercice 9.3.
extendedGcd
Modier la mthode
O(log(max(u,v))).
intermdiaire.
Exercice 9.4.
(mod m).
Soient
appelle quotient de
crire une
par
x2k = (x2 )k
x
= x(x2 )k
2k+1
de type
int,
code donn programme 22 page 121. Il existe de multiples variantes. On peut par exemple
(On verra plus loin pourquoi on s'intresse uniquement aux multiplications, et pas aux
que, si
int.
d'tre de
d'un monode
122
Chapitre 9. Arithmtique
ce qui est une amlioration signicative par rapport un calcul direct en temps linaire .
Exercice 9.5.
vantes :
exp
x2k = (xk )2
x
= x(xk )2
2k+1
Exercice 9.6.
Fn
22
int, avec la matrice identit, la multiplication et l'exponentiation rapide.
gorithme d'exponentiation rapide. On crira une classe minimale pour des matrices
coecients dans
n est-il premier ?)
ou le calcul exhaustif des nombres premiers jusqu' un certain rang. Le crible d'ratosthne est un algorithme qui dtermine, pour un certain entier
entiers
N.
n N.
N = 23.
N,
On va liminer progressivement tous les entiers qui ne sont pas premiers d'o le
nom de
crible.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
Puis on dtermine le premier entier non encore limin. Il s'agit de 2. On limine alors
tous ses multiples, savoir ici tous les entiers pairs suprieurs 2.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
Puis on recommence. Le prochain entier non limin est 3. On limine donc leur tour
tous les multiples de 3.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
On note que certains taient dj limins (les multiples de 6, en l'occurrence) mais ce
n'est pas grave. Le prochain entier non limin est 5. Comme
termin. En eet, tout multiple de 5, c'est--dire
au-del de 23 si
k 5.
k 5,
5 5 > 23
le crible est
k < 5,
soit
nombres qui n'ont pas t limins, c'est--dire ici 2, 3, 5, 7, 11, 13, 17, 19 et 23.
crivons une mthode
sieve
1. Attention cependant ne pas conclure htivement qu'on sait calculer Fn pour de grandes valeurs
de n. Les lments de la suite de Fibonacci croissent en eet de manire exponentielle. Si on a recours des
entiers en prcision arbitraire, le cot des oprations arithmtiques elles-mmes doit tre pris en compte,
et la complexit ne sera pas O(log n). Et dans le cas contraire, on aura rapidement un dbordement
arithmtique.
123
prime contient la valeur false dans toutes ses cases (voir page 19).
true dans toutes les cases d'indice i 2.
b maxc,
limit,
et teste chaque
n,
return prime;
124
Chapitre 9. Arithmtique
O(N ).
boucle principale. S'il ne s'agit pas d'un nombre premier, le cot est constant (on ne fait
N
car
rien). Mais lorsqu'il s'agit d'un nombre premier p, alors la boucle interne un cot
p
on considre tous les multiples de p (en fait, un peu moins car on commence l'itration
p2 , mais cela ne change pas l'asymptotique). Le cot total est donc
N+
XN
p
pN
o la somme est faite sur les nombres premiers. Un thorme d'Euler nous dit que
P
1
pN p ln(ln(N )) d'o une complexit N ln(ln(N )) pour le crible d'ratosthne.
Exercice 9.7.
de la mthode
sieve
Exercice 9.8.
Le type
boolean[]
chaque boolen y est en eet reprsent par un octet, soit 8 bits l o un seul surait. La
bibliothque Java y remdie en proposant une classe
BitSet
sont reprsents d'une manire plus compacte. crire une variante de la mthode
renvoyant un rsultat de type
Exercice 9.9.
BitSet
plutt que
boolean[].
sieve
Exercice * 9.10.
10
Programmation dynamique et
mmosation
F0 = 0
F1 = 1
Fn = Fn2 + Fn1
pour
n 2.
crire une mthode rcursive qui ralise ce calcul en suivant cette dnition est immdiat.
(On calcule ici avec le type
grands.)
Fi .
Fn ,
F5 ,
F3
et trois fois
F2 .
F42 , 3 secondes pour F43 , 5 secondes pour F44 , etc. On reconnat l justement
les nombres de la suite de Fibonacci. On extrapole qu'il faudrait 89 secondes pour calculer
F50
10.1 Mmosation
Puisqu'on a compris qu'on calculait plusieurs fois la mme chose, une ide naturelle
consiste stocker les rsultats dj calculs dans une table. Il s'agit donc d'une table
126
mmosation
(en anglais
Michie en 1968).
Mettons en uvre cette ide dans une mthode
fibMemo
F0
et
fib.
En particulier, elle
F1 .
memo
si la valeur de
fib(n)
n2
F0
et
F1
dans la
Long l = memo.get(n);
if (l != null) return l;
On utilise ici le fait que la mthode
get
null
lorsqu'il n'y a pas d'entre pour la cl donne. Dans ce cas, justement, on calcule le rsultat
exactement comme pour la mthode
fib
memo,
avant de le renvoyer.
memo.put(n, l);
return l;
F50 ,
fibMemo.
fib. Le
fib). On
rcursifs.
127
n+1
Fi
i n et donc un
fibMemo ci-dessus
pour
avec cette ide, on pourrait par exemple remplir le tableau initialement avec la valeur
dans chaque case pour signier que la valeur n'a pas encore t calcule. Mais on
Fi
Fj
pour
j < i.
programmation dynamique
ta-
fibMemo,
l'intrieur
de la mthode
fibDP
de bas en
haut, c'est--dire dans le sens des indices croissants, en faisant un cas particulier pour
f[1].
f[1] = 1;
128
Une fois le tableau rempli, il ne reste plus qu' renvoyer la valeur contenue dans sa dernire
case.
return f[n];
fibDP.
Comme pour
fibDP
F50 ,
fibMemo,
10.3 Comparaison
Le code des mthodes
dynamique est plus simple mettre en uvre que la mmosation. Sur cet exemple,
c'est vrai. Mais il faut comprendre que, pour crire
fibDP,
Fi
i n,
et
le fait de savoir qu'on pouvait les calculer dans l'ordre croissant. De manire gnrale, les
entres de la fonction calculer ne sont pas ncessairement des indices conscutifs, ou ne
sont mme pas des entiers, et les dpendances entre les diverses valeurs calculer ne sont
pas ncessairement aussi simples. En pratique, la mmosation est plus simple mettre
en uvre : il sut en eet de rajouter quelques lignes pour consulter et remplir la table
de hachage, sans modier la structure de la fonction.
Il existe cependant quelques rares situations o la programmation dynamique peut
tre prfre la mmosation. Prenons l'exemple du calcul des coecients binomiaux
C(n,k)
C(n,0) = 1
C(n,n) = 1
pour
0 < k < n.
(n,k),
et en espace
en
O(nk).
C(n 1,k).
croissantes, sans qu'il soit utile de conserver toutes les valeurs calcules jusque l.
10.3. Comparaison
129
1
1
1
.
.
.
10
10
1
1
et en expliquant que l'on va le calculer ligne ligne, en ne conservant chaque fois que
la ligne prcdente pour le calcul de la ligne suivante. Mettons cette ide en uvre dans
une mthode
taille
n+1
row
de
k+1 ;
ce tableau ne contient que des valeurs nulles. On initialise sa toute premire case avec 1.
row[0] = 1;
Cette valeur ne bougera plus car la premire colonne du triangle de Pascal ne contient
que des 1. On crit ensuite une boucle pour calculer la ligne
du triangle de Pascal :
row,
i 1.
Pour ne pas se marcher sur les pieds, on va calculer les nouvelles valeurs de la droite vers
la gauche, car elles ne dpendent pas de valeurs situes plus droite. On procde avec
une seconde boucle :
return row[k];
O(nk)
(on notera cependant qu'il provoque un dbordement arithmtique ; voir l'exercice 10.2).
La conclusion de cette petite exprience est que la programmation dynamique peut
parfois tre plus avantageuse que la mmosation, car elle permet un contrle plus n
des ressources mmoire. Mais dans les trs nombreuses situations o ce contrle n'est pas
ncessaire, la mmosation est plus simple mettre en uvre.
Exercice 10.1.
cnkSmartDP
colonne k.
Modier la mthode
130
Exercice 10.2.
plus des oprations atomiques ; leur cot dpend de la taille des oprandes, qui grandit
Exercice 10.3.
Modier la mthode
fibDP
11
Rebroussement (backtracking )
La technique du
rebroussement
(en anglais
backtracking )
N N
de
telle sorte qu'aucune reine ne soit en prise avec une autre. Voici par exemple l'une des 92
solutions pour
N =8
q
q
q
q
q
q
q
q
? ? ? ? ? ? ? ?
Si on en trouve une, alors on place une reine cet endroit et on poursuit l'exploration
avec la ligne suivante. Sinon,
132
crivons une mthode
et renvoie la solution trouve, le cas chant, ou lve une exception pour signaler l'absence
de solution. On commence par allouer un tableau
n,
laquelle on passe le tableau d'une part et un indice indiquant la prochaine ligne de l'chiquier remplir d'autre part. Elle renvoie un boolen signalant le succs de la recherche.
Il sut donc de l'appeler et de traiter correctement sa valeur de retour.
On en vient la mthode
Le cas de base correspond un chiquier o toutes les lignes ont t remplies. On renvoie
alors
true
r.
cols.
check qui fait cette vrication. Si le test est positif, on apfindSolutionRec pour continuer le remplissage partir de la ligne
succs, on renvoie true immdiatement.
c.
Si on nit par
sortir de la boucle, c'est que toutes les colonnes ont t essayes sans succs. On signale
alors une recherche infructueuse.
}
return false;
check
est cohrent avec les choix prcdents. C'est une simple boucle sur les
premires lignes.
133
Programme 25 Le problme des N reines
static boolean check(int[] cols, int r) {
for (int q = 0; q < r; q++)
if (cols[q] == cols[r] || Math.abs(cols[q] - cols[r]) == r - q)
return false;
return true;
}
static boolean findSolutionRec(int[] cols, int r) {
if (r == cols.length)
return true;
for (int c = 0; c < cols.length; c++) {
cols[r] = c;
if (check(cols, r) && findSolutionRec(cols, r + 1))
return true;
}
return false;
}
static int[] findSolution(int n) {
int[] cols = new int[n];
if (findSolutionRec(cols, 0))
return cols;
throw new Error("no solution for n=" + n);
}
static boolean check(int[] cols, int r) {
for (int q = 0; q < r; q++)
Pour chaque ligne
q,
on vrie que les deux reines ne sont sur la mme colonne et ni sur
return true;
Le code complet est donn programme 25 page 133. Il est important de bien comprendre
que ce programme s'interrompt la premire solution trouve. C'est le rle du second
return true
findSolutionRec.
134
Exercice 11.1.
lutions. Les solutions ne seront pas renvoyes, mais seulement leur nombre total. Pour
1 N 9,
Optimisation.
recherche exhaustive que nous venons de prsenter . Nanmoins, cela ne nous empche pas
de chercher optimiser le programme prcdent. Une ide naturelle consiste maintenir,
pour chaque ligne de l'chiquier, les colonnes sur lesquelles on peut encore placer une
reine. Ainsi, plutt que d'essayer systmatiquement les
N = 8.
Supposons qu'on
qqq
en prise avec les reines dj places le long d'une diagonale ascendante. Ces trois positions (ici en rouge)
q
q
(2)
(3)
(1)
q
q
q
q
(4)
Mettons en uvre cette ide dans un programme qui dnombre les solutions du problme des
exclure, qui sont matrialises en rouge dans les gures ci-dessus. Comme il s'agit de
petits ensembles dont les lments sont dans
reprsenter par des valeurs de type
int,
le bit
l'ensemble. Ainsi, dans la gure 1 ci-dessus, les cinq colonnes considrer sur la quatrime
ligne peuvent tre reprsentes par l'entier dont l'criture binaire est
111001012 ,
c'est--
dire 229 (l'usage est d'crire les bits de poids faible droite). De la mme manire, les
trois positions en prise par une diagonale ascendante (gure 2) correspondent l'entier
104 = 011010002 , et les deux positions en prise par une diagonale descendante (gure 3)
l'entier 9 = 000010012 . L'intrt de cette reprsentation est que les oprations sur les
entiers fournies par la machine vont nous permettre de calculer trs ecacement certaines
1. Si en revanche le problme est de trouver une solution, alors il existe un algorithme polynmial.
135
oprations ensemblistes . Ainsi, si
a, b
et
int
contenant
respectivement les entiers 229, 104 et 9, c'est--dire les trois ensembles ci-dessus, alors
on peut calculer l'ensemble correspondant la gure 4 avec l'expression
L'oprateur
&
a\b\c.
a, b
et
c.
countSolutionsRec
qui
a dsigne les colonnes restant pourvoir, l'entier b (resp. c) les colonnes interdites
car en prise sur une diagonale ascendante (resp. descendante). La mthode renvoie le
nombre de solutions qui sont compatibles avec ces arguments. La recherche parvient son
terme lorsque
if (a == 0) return 1;
a & b & c,
comme expliqu ci-dessus, dans une variable e. On initialise galement une variable f pour
e, le plus ecacement possible. Nous allons parcourir les bits de e qui sont 1, et les
supprimer au fur et mesure, jusqu' ce que e devienne nul.
par
while (e != 0) {
Il existe une astuce arithmtique qui nous permet d'extraire exactement un bit d'un entier
non nul. Elle exploite la reprsentation en complment deux des entiers, en combinant
le ET bit bit et la ngation (entire) :
Hacker's Delight
-e
est gal
[9].) Ce bit
e + 1.
e que
de
l'on vient d'extraire reprsente une colonne considrer. Il nous sut donc de procder
un appel rcursif, en mettant jour les valeurs de
a, b
et
en consquence.
a t retir de
a avec une
a), et a t
tait
ncessairement un bit de
a pas de retenue car
e -= d;
ajout
et
ou
136
return f;
f.
reprsentant l'ensemble
countSolutionsRec,
{0, . . . ,N 1}
N = 14,
on
dnombre les 365 596 solutions en un quart de seconde, au lieu de prs de 8 secondes. Plus
intressant que le temps lui-mme est le nombre de dcisions prises. On le donne ici pour
les deux versions du dnombrement, pour quelques valeurs de
N.
10
11
12
13
14
version nave
version optimise
3,5 105
3,6 104
1,8 106
1,7 105
1,0 107
8,6 105
6,0 107
4,7 106
3,8 108
2,7 107
rapport
9,80
10,8
11,8
12,8
13,8
N.
N,
approximativement
12
Tri
int[]),
nous expliquons comment gnraliser des lments d'un type quelconque. On note
le
nombre d'lments trier. Pour chaque tri prsent, on indique sa complexit en nombre
de comparaisons eectues et en nombre d'aectations.
On rappelle que la complexit optimale d'un tri eectuant uniquement des comparaisons d'lments est en
O(N log N ).
un arbre binaire. Chaque nud interne reprsente une comparaison eectue, le sousarbre gauche (resp. droit) reprsentant la suite de l'algorithme lorsque le test est positif
(resp. ngatif ). Chaque feuille reprsente un rsultat possible, c'est--dire une permutation eectue sur la squence initiale. Si on suppose les
permutations possibles, donc au moins
moins gale
log N !.
N!
lments distincts, il y a
N!
grand nombre de comparaisons eectues par l'algorithme sur une entre. Il existe donc
une entre pour laquelle le nombre de comparaisons est au moins
log(N !).
Par la formule
a[i]
a[0..i-1]
i-1
. . . dj tri . . .
On commence par une boucle
for
a[i]
. . . trier . . .
dj trie, ce qui
138
a[i] la bonne place, on utilise une seconde boucle qui dcale vers
a[i].
int v = a[i], j = i;
for (; 0 < j && v < a[j-1]; j--)
a[j] = a[j-1];
Une fois sorti de la boucle, il reste positionner
donne par
a[j] = v;
Complexit.
insertionSort
i,
i k,
elle eectue
k+1
comparaisons. Au mieux
moyenne
pire cas
N
N
N 2 /2
N 2 /2
comparaisons
aectations
N /4
N 2 /4
: on partage les
lments trier en deux sous-ensembles, les lments du premier tant plus petits que
les lments du second, puis on trie rcursivement chaque sous-ensemble. En pratique, on
ralise le partage l'aide d'un lment
pivot.
Les deux sous-ensembles sont alors respectivement les lments plus petits et plus grands
que
p.
Le tri rapide d'un tableau s'eectue en place. On le paramtre par deux indices
a[l]
partition
tant inclus et
et
139
l < r,
a[l].
for.
l
p
L'indice
(inclus) et
(exclus),
<p
r
?
partitionne
la portion dj parcourue.
int m = l;
for (int i = l + 1; i < r; i++)
a[i] est suprieur ou gal v, il n'y a rien faire. Dans le cas contraire, pour conserver
l'invariant de boucle, il sut d'incrmenter m et d'changer a[i] et a[m].
Si
if (a[i] < p)
swap(a, i, ++m);
(Le code de la mthode
swap
m,
swap(a, l, m);
return m;
On peut bien entendu se dispenser de l'appel
swap
lorsque
l = m,
rien fondamentalement. On crit alors la partie rcursive du tri rapide sous la forme
d'une mthode
l r-1,
quickrec
partition.
Si
et
r.
quickrec(a, l, m);
quickrec(a, m + 1, r);
ce qui achve la mthode
quickrec.
quickrec
140
141
Pour la mthode
C(N ) = N 1 +
1
N
2
= N 1+
N
C(K) + C(N 1 K)
0KN 1
C(K).
0KN 1
C(N )
C(N 1)
2
2
=
+
.
N +1
N
N + 1 N (N + 1)
Il s'agit d'une somme tlscopique, qui permet de conclure que
C(N )
2 log N
N +1
et donc que
C(N ) 2N log N .
partition eectue
swap que d'incrmentations de m. Le meilleur des cas est atteint lorsque
le pivot est toujours sa place. Il n'y a alors aucune aectation. Il est important de
noter que ce cas ne correspond pas la meilleure complexit en termes de comparaisons
(qui est alors quadratique). En moyenne, toutes les positions nales pour le pivot tant
quiprobables, on a donc moins de
alors
rsultats suivants :
comparaisons
aectations
Amliorations.
meilleur cas
moyenne
pire cas
N log N
2N log N
2N log N
N 2 /2
N2
a[l..r[
comme pivot n'est pas forcment une bonne ide. Par exemple, si le tableau est dj
tri, on se retrouvera avec une complexit quadratique. Il est prfrable de choisir le pivot
alatoirement parmi les valeurs de
142
tableau
avant
partition
un peu plus
subtile, propose dans l'exercice 12.1 ci-dessous. Avec ces deux amliorations, on peut
considrer en pratique que le tri rapide est toujours en
O(N log N ).
Comme on le voit, raliser un tri rapide en prenant soin d'viter un pire cas quadratique
n'est pas si facile que cela. Dans les sections suivantes, nous prsentons deux autres tris,
le tri par tas et le tri fusion, qui ont tous les deux une complexit
des cas tout en tant plus simples raliser. Nanmoins, le tri rapide est souvent prfr
en pratique, car meilleur en temps que le tri par tas et meilleur en espace que le tri fusion.
Exercice 12.1.
Modier la fonction
partition
tement plus petits que le pivot ( gauche), les lments gaux au pivot (au milieu) et les
lments strictement plus grands que le pivot ( droite). Au lieu de deux indices
et
dcoupant le segment de tableau en trois parties, comme illustr sur la gure page 139, on
utilisera trois indices dcoupant le segment de tableau en quatre parties. (Un tel dcoupage en trois est aussi l'objet de l'exercice 12.8 plus loin.) La nouvelle fonction
doit maintenant renvoyer deux indices. Modier la fonction
quick_rec
partition
en consquence.
Exercice 12.2.
quickrec,
une ide consiste eectuer d'abord l'appel rcursif sur la plus petite des deux portions,
puis remplacer le second appel rcursif par une boucle
ou
while
en modiant la valeur de
en consquence. Montrer que la taille de pile est alors logarithmique dans le pire
des cas.
Exercice 12.3.
tuer un tri par insertion quand le nombre d'lments trier est petit,
une constante xe l'avance (par exemple 5). Modier le tri rapide pour prendre en
lments trier en deux parties de mme taille, sans chercher comparer leurs lments.
Une fois les deux parties tries rcursivement, il les fusionne, d'o le nom de tri fusion.
Ainsi on vite le pire cas du tri rapide o les deux parties sont de tailles disproportionnes.
On va chercher raliser le tri en place, en dlimitant la portion trier par deux indices
l (inclus) et r (exclus). Pour le partage, il sut de calculer l'indice mdian m = l+2 r . On
trie alors rcursivement les deux parties dlimites par l et m d'une part, et m et r d'autre
part. Il reste eectuer la fusion. Il s'avre extrmement dicile de la raliser en place.
143
Le plus simple est d'utiliser un second tableau, allou une et une seule fois au dbut du
tri.
merge
a1
et
a2,
l, m
et
r.
Les portions
a1[l..m[
et
a1[m..r[ sont supposes tries. L'objectif est de les fusionner dans a2[l..r[. Pour cela, on va
parcourir les deux portions de a1 avec deux variables i et j et la portion de a2 remplir
avec une boucle for.
static void merge(int[] a1, int[] a2, int l, int m, int r) {
int i = l, j = m;
for (int k = l; k < r; k++)
chaque tour de boucle, la situation est donc la suivante :
a1
tri
tri
a2
tri
k
Il faut alors dterminer la prochaine valeur placer en
des deux valeurs
a1[i]
et
a1[j].
a2[k].
il n'y a plus d'lment dans l'une des deux moitis. On dtermine si l'lment doit tre
pris dans la moiti gauche avec le test suivant :
a2[k] = a1[i++];
else
a2[k] = a1[j++];
merge. La partie rcursive du tri fusion est matrialise par une
mthode rcursive mergesortrec qui prend en arguments deux tableaux a et tmp et deux
indices l et r dlimitant la portion trier. Elle trie a[l..r[ en se servant du tableau tmp
comme temporaire. Si le segment contient au plus un lment, c'est--dire si l r-1, il
int m = (l + r) / 2;
(Le calcul de
(l + r) / 2
tmp
comme temporaire.
144
merge
Complexit.
par
vers
tmp.
Si on note
mergesortrec
(resp.
C(N ) = 2C(N/2) + f (N )
145
car les deux appels rcursifs se font sur deux listes de mme longueur
meilleur des cas, la mthode
merge
N/2.
Dans le
car ils sont tous plus petits que ceux de l'autre liste. Dans ce cas f (N ) = N/2 et donc
C(N ) 21 N log N . Dans le pire des cas, tous les lments sont examins par merge et
donc f (N ) = N 1, d'o C(N ) N log N . L'analyse en moyenne est plus subtile (voir
f (N ) = N 2 + o(1),
d'o
merge (chaque
mergesortrec. Si on
thode
donc
2N log N
aectations.
meilleur cas
comparaisons
aectations
Exercice 12.4.
1
N
2
log N
2N log N
moyenne
pire cas
N log N
2N log N
N log N
2N log N
tmp vers a comme on le fait dj. Cependant, pour trier les lments de
a vers tmp, il faut, inversement, trier les deux moitis en place puis fusionner vers tmp. On
puis fusionner de
a donc besoin de deux mthodes de tri mutuellement rcursives. On peut cependant n'en
n'crire qu'une seule, en passant un paramtre supplmentaire indiquant si le tri doit tre
fait en place ou vers
tmp.
mergesortrec
et
mergesort
en suivant
cette ide.
Exercice 12.5.
Le tri fusion est une bonne mthode pour trier des listes. Supposons
ces deux listes. Elle peut vider ses deux arguments de leurs lments. crire une mthode
rcursive
mergesort
qui prend une liste en argument et renvoie une nouvelle liste trie
contenant les mmes lments. Elle ne doit pas modier son argument.
Exercice * 12.6.
en place, c'est--dire
sans aucune allocation supplmentaire, ds lors que le contenu et la structure des listes
peuvent tre modis. Considrons par exemple les listes d'entiers du type
Singly
de
146
A priori,
O(N log N ).
O(log N )
donne immdiate-
en place,
2i + 1
et
2i + 2.
relation d'ordre inverse, c'est--dire un tas o le plus grand lment se trouve la racine.
Pour construire le tas, on considre les lments du tableau de la droite vers la gauche.
chaque tour, on a une situation de la forme
k k+1
0
?
tas en construction
o la partie
a[k]
sa
en
a[0]
avec l'lment
n-1
sa place. On rtablit
place dans un tas de
chaque tour
k,
etc.
on a la situation suivante
0
tas
n-1, n-2,
a[k..n[,
n
tri
a[0..k[, dont tous les lments sont plus petits que ceux
Les deux tapes de l'algorithme ci-dessus utilisent la mme opration consistant faire
descendre une valeur jusqu' sa place dans un tas. On la ralise l'aide d'une mthode
rcursive
limite
147
h2
enracin en
int r = 2 * k + 1;
if (r >= n)
a[k] = v;
Sinon, on dtermine dans
traitant avec soin le cas o
r l'indice de la plus
h2 n'existe pas.
h1
et
h2 ,
en
else {
if (r + 1 < n && a[r] < a[r + 1]) r++;
Si la valeur
a[k].
if (a[r] <= v)
a[k] = v;
Sinon, on fait remonter la valeur
rcursif sur la position
r.
a[r]
et on poursuit la descente de
avec un appel
else {
a[k] = a[r];
moveDown(a, r, v, n);
}
Ceci achve la mthode
moveDown.
en argument
moveDown. On vite
b n2 c 1 (en
les appels inutiles sur des tas rduits des feuilles en commenant la boucle
eet, pour tout indice
strictement suprieur, on a
2k+1 n).
en
a[k]
k,
on change
a[0]
avec la
sa place.
148
149
D'autre part,
moveDown. Le nombre
k est double chaque appel.
moveDown
log n,
puisque la valeur de
Pour le tri lui-mme, on peut grossirement majorer le nombre de comparaisons effectues dans chaque appel
3N log N
moveDown
par
2 log N ,
N log N
soit un total
C(N )
au pire gal
l'algorithme, savoir la construction du tas, n'a qu'un cot linaire (voir par exemple [2,
Sec. 7.3]). Ds lors, seule la seconde partie de l'algorithme contribue la complexit
asymptotique et donc
renvoie
moveDown peut
tre rcrite sous forme d'une boucle mme si on ne risque pas ici un dbordement de
pile, la hauteur tant logarithmique.
K pour les lments, et d'exiger que ce type soit muni d'une relation de comparaison, c'est-dire implmente l'interface java.lang.Comparable<T>, comme nous l'avons dj fait
pour les AVL (section 6.3.4) et les les de priorit (section 7.4). Ainsi le tri par insertion
(programme 27 page 138) s'crit dans sa version gnrique de la manire suivante :
Exercice 12.8.
(Le drapeau hollandais de Dijkstra) crire une mthode qui trie en place
un tableau contenant des valeurs reprsentant les trois couleurs du drapeau hollandais,
savoir
150
Exercice 12.9.
k valeurs
0, . . . ,k 1. crire une
O(max(k,N )) o N est la taille du
13
Compression de donnes
La compression de donnes consiste tenter de rduire l'espace occup par une information. On l'utilise quotidiennement, par exemple en tlchargeant des chiers ou encore
sans le savoir en utilisant des logiciels qui compressent des donnes pour conomiser les
ressources. L'exemple typique est celui des formats d'image et de vido qui sont le plus
souvent compresss. Ce chapitre illustre la compression de donnes avec un algorithme
Exercice 13.1.
compresse.
'i'
et
's'
de reprsenter le caractre
caractres
100
'm'
les carac-
'p'
100011110111101011010.
Les squences pour les caractres 'i', 's', 'm' et 'p' n'ont pas t choisies au hasard.
et
101.
et
"mississippi",
Elles ont en eet la proprit qu'aucune n'est un prxe d'une autre, permettant ainsi
un dcodage sans ambigut. On appelle cela un
code prxe .
facile de construire un tel code si les caractres considrs forment les feuilles d'un arbre
binaire. Prenons par exemple l'arbre suivant :
i
s
m
152
Il sut alors d'associer chaque caractre le chemin qui l'atteint depuis la racine, un
dnotant une descente vers la gauche et un
un tel code est un code prxe. On a dj crois une telle reprsentation avec les arbres
prxes dans la section 6.4, mme si le problme n'tait pas pos en ces termes.
L'algorithme de Human permet de construire, tant donn un nombre d'occurrences
pour chacun des caractres, un arbre ayant la proprit d'tre le meilleur possible pour
cette distribution (dans un sens qui sera expliqu plus loin). La frquence des caractres
peut tre calcule avec une premire passe ou donne l'avance s'il s'agit par exemple
d'un texte crit dans un langage pour lequel on connat la distribution statistique des
caractres. Si on reprend l'exemple de la chane
m(1)
p(2)
s(4)
i(4)
L'algorithme de Human procde alors ainsi. Il slectionne les deux caractres avec les
nombres d'occurrences les plus faibles, savoir ici les caractres
'm'
et
'p',
et les runit
en un arbre auquel il donne un nombre d'occurrences gal la somme des nombres d'occurrences des deux caractres. On a donc la situation suivante :
(3)
m(1)
s(4)
i(4)
p(2)
Puis on recommence avec ces trois arbres , c'est--dire qu'on en slectionne deux ayant
les occurrences les plus faibles, ici 3 et 4, et on les runit en un nouvel arbre, ce qui donne
par exemple ceci :
i(4)
(7)
(3)
m(1)
s(4)
p(2)
(11)
i(4)
(7)
(3)
m(1)
s(4)
p(2)
C'est l'arbre que nous avions propos initialement. Il se trouve qu'il est optimal, pour un
sens que nous donnons maintenant.
Optimalit.
ci
fi .
La
proprit de l'arbre construit par l'algorithme de Human est qu'il minimise la quantit
S=
fi di
i
o
di
caractre
ci .
ci
13.2. Ralisation
somme
153
est strictement plus petite que celle obtenue avec l'algorithme de Human. On
perte de gnralit,
supposons que
par l'algorithme de
Human, c'est--dire deux caractres avec les frquences les plus basses. On peut supposer
que ces deux caractres sont des feuilles de
T,
en les
changeant avec des feuilles. De mme, on peut supposer que ce sont deux feuilles d'un
mme nud, car on peut toujours les changer avec d'autres feuilles. Si on remplace alors
ce nud par une feuille de frquence
f0 +f1 , la somme S
diminue de
f0 +f1 . En particulier,
n1
caractres, ce
13.2 Ralisation
On commence par introduire des classes pour reprsenter les arbres de prxes utiliss dans l'algorithme de Human. Qu'il s'agisse d'une feuille dsignant un caractre ou
d'un nud interne, tout arbre contient un nombre d'occurrences qui lui permettra d'tre
compar un autre arbre. On introduit donc une classe abstraite
HuffmanTree
pour
freq.
HuffmanTree,
left
et
right
Node
154
HuffmanTree,
code,
tree
Huffman.
class Huffman {
private HuffmanTree tree;
private Map<Character, String> codes;
On va se contenter ici de construire des messages encods sous la forme de chanes de
caractres
'0'
et
'1' ;
codes
alphabet de
Huffman(Collection<Leaf> alphabet) {
if (alphabet.size() <= 1) throw new IllegalArgumentException();
this.tree = buildTree(alphabet);
this.codes = new HashMap<Character, String>();
this.tree.traverse("", this.codes);
}
buildTree construit l'arbre de prxes partir de l'alphabet donn et la
traverse le parcourt pour remplir la table codes.
Commenons par le code de la mthode buildTree. Pour suivre l'algorithme prsent
La mthode
mthode
dans la section prcdente, qui slectionne chaque fois les deux arbres les plus petits, on
utilise une le de priorit. Ce peut tre la classe
la classe
java.util.PriorityQueue
Heap
de la bibliothque Java.
HuffmanTree.
On commence par la remplir avec toutes les feuilles contenues dans l'alphabet pass en
argument.
13.2. Ralisation
155
return pq.getMin();
l'arbre, en maintenant le chemin depuis la racine, et de remplir la table chaque fois qu'on
atteint une feuille. crivons pour cela une mthode
Elle prend en arguments le chemin
une table
prefix,
remplir.
en associant la chane
prefix
Leaf,
il sut
Encodage et dcodage.
StringBuilder
156
sb.
return sb.toString();
0 et de 1,
StringBuilder pour
de caractres forme de
on utilise un
construire le rsultat.
int i = 0;
while (i < msg.length()) {
Pour dcoder un caractre, il faut descendre dans l'arbre
dsign par les
et les
msg
find
dans la classe
et la position
i,
HuffmanTree
i += this.codes.get(c).length();
Une autre solution aurait t de faire renvoyer cette longueur par la mthode
find mais il
n'est pas ais de renvoyer deux rsultats. Une fois sorti de la boucle, on renvoie la chane
construite.
return sb.toString();
traverse
HuffmanTree
la mthode
find
13.2. Ralisation
157
Leaf,
il sut de
i-ime
Node,
caractre de la chane
vaut
'0'
ou
'1'.
Exercice 13.2.
Collection<Leaf> buildAlphabet(String s)
qui calcule les nombres d'occurrences des dirents caractres d'une chane
s et les renvoie
sous la forme d'une collection de feuilles. Indication : on pourra utiliser une table de
hachage associant des feuilles des caractres. Une fois cette table remplie, sa mthode
values()
158
13.2. Ralisation
159
160
Quatrime partie
Graphes
14
Dnition et reprsentation
sommets
artes .
On a
V de sommets et d'un
paires de sommets. Si {x,y} E , on dit que les sommets
note x y . Cette relation d'adjacence tant symtrique, on
et
sont adjacents et on
parle de
d'artes .
graphe orient
en choisissant pour
un en-
couples de sommets plutt que de paires. On parle alors d'arcs plutt que
Si (x,y) E on dit que y est un successeur de x et on note x y . Voici un
Un arc d'un sommet vers lui-mme, comme sur cet exemple, est appel une
boucle .
Le
degr entrant (resp. sortant) d'un sommet est le nombre d'arcs qui pointent vers ce sommet
(resp. qui sortent de ce sommet).
Les sommets comme les arcs peuvent porter une information ; on parle alors de
tiquet .
graphe
1. Dans la suite, on utilisera systmatiquement le terme d'arc, y compris pour des graphes non orients.
164
Il est important de noter que l'tiquette d'un sommet n'est pas la mme chose que le sommet lui-mme. En particulier, deux sommets peuvent porter la mme tiquette. Formellement, un graphe tiquet est donc la donne supplmentaire de deux fonctions donnant
respectivement l'tiquette d'un sommet de
E.
chemin du sommet u au sommet v est une squence x0 , . . . ,xn de sommets tels que
x0 = u, xn = v et xi xi+1 pour 0 i < n. Un tel chemin est de longueur n (il contient
n arcs).
Un
0, . . . ,N 1.
Dit autrement, on a
V =
{0, . . . ,N 1}. Le plus naturel pour reprsenter un tel graphe est sans doute une matrice
M , de taille N N o chaque lment Mi,j indique la prsence d'un arc entre les sommets
i et j . En supposant des graphes non tiquets, il sut d'utiliser une matrice de boolens :
class AdjMatrix {
int n; // les sommets sont 0,...,n-1
boolean[][] m;
}
(On conserve ici le nombre de sommets dans un champ
n,
n n.
AdjMatrix(int n) {
this.n = n;
this.m = new boolean[n][n];
}
Cette matrice est initialise avec
false,
aucun arc. Les oprations d'ajout, de suppression ou de test de prsence d'un arc sont
immdiates. Pour des graphes orients, elles sont donnes programme 33 page 165. Elles
ont toutes une complexit
O(1)
Exercice 14.1.
Modier les matrices d'adjacence pour des graphes o les arcs sont
165
166
Exercice 14.2.
Le plus simple pour reprsenter des graphes non orients est de conser-
ver la mme structure que pour des graphes orients, mais en maintenant l'invariant que
pour chaque arc
removeEdge
ab
on a galement l'arc
b a.
addEdge
et
listes d'adjacence. Ainsi pour le graphe dessin page 163, ces listes sont [y] pour le
x, [y,t] pour le sommet y , etc. Il nous sut donc d'utiliser un tableau de listes.
sommet
Cependant, tester la prsence d'un lment dans une liste cote un peu cher, et donc
tester la prsence d'un arc dans le graphe le sera galement. Il semble plus opportun
d'utiliser par exemple une table de hachage pour reprsenter les successeurs d'un sommet
donn, par exemple avec la bibliothque
HashSet
l'ide d'utiliser une table de hachage, o les sommets n'ont plus besoin d'tre les entiers
0, . . . ,N 1, autant pousser cette ide jusqu'au bout et reprsenter un graphe par une table
de hachage associant chaque sommet l'ensemble de ses successeurs, lui-mme reprsent
par une table de hachage. On s'aranchit ainsi compltement du fait que les sommets
sont les entiers
des entiers ; voir l'exercice 14.3. On conserve cependant l'appellation de listes d'adjacence,
mme s'il n'y a pas de liste dans cette reprsentation.
Pour des graphes orients, le code est donn programme 34 page 167. On s'y attardera
un instant pour bien comprendre les petites dirences avec les matrices d'adjacence. En
particulier, il convient de traiter correctement les cas de gure o la table d'adjacence d'un
(amorti) car il ne s'agit que d'oprations d'ajout et de suppression dans des tables de
hachage. Concernant le cot en espace, les listes d'adjacence ont une complexit optimale
de
O(N + E).
Exercice 14.3.
classe
AdjList,
Exercice 14.4.
int nbEdges()
Exercice 14.5.
addEdge
et
removeEdge.
Modier les listes d'adjacence pour des graphes o les arcs sont tiquets
(par exemple par des entiers). On pourra remplacer l'ensemble des successeurs du sommet
x par un
x y.
l'tiquette de l'arc
167
168
Exercice 14.6.
Le plus simple pour reprsenter des graphes non orients est de conser-
ver la mme structure que pour des graphes orients, mais en maintenant l'invariant que
pour chaque arc
removeEdge
ab
on a galement l'arc
b a.
addEdge
et
V,
est immdiate. Si on prend l'exemple des listes d'adjacence, une classe gnrique
class Graph<V> {
private Map<V, Set<V>> adj;
Si la ralisation utilise les classes
suppose donc que la classe
Exercice 14.7.
HashMap
et
HashSet
de la bibliothque standard, on
hashCode
et
equals.
Pour les algorithmes sur les graphes que nous allons crire dans le chapitre suivant,
il est ncessaire de pouvoir accder l'ensemble des sommets du graphe d'une part et
l'ensemble des successeurs d'un sommet donn d'autre part. Plutt que d'exposer la table
de hachage qui contient la relation d'adjacence (ci-dessus on l'a d'ailleurs dclare comme
prive), il sut d'exporter les deux mthodes suivantes :
Set<V> vertices() {
return this.adj.keySet();
}
Set<V> successors(V v) {
return this.adj.get(v);
}
Ds lors, pour parcourir tous les sommets d'un graphe
g,
il sut d'crire
de
g,
il sut d'crire
v.
O(V )
et
O(d(v))
d(v)
15
Graph<V>
On note V le
O(V + E).
cycle
que celui d'une liste ou d'un arbre. Prenons l'exemple du graphe non orient suivant
3
(15.1)
Quel que soit son fonctionnement, un parcours qui dmarrerait du sommet 4 parviendra
un moment o un autre au sommet 5 et il ne doit pas entrer alors dans un boucle
innie du fait de la prsence du cycle
5 2 6.
n'est pas possible et nous avons pu crire le parcours inxe d'un arbre assez facilement
(voir page 79). L'arbre vide
null
cas d'une liste chane, nous avons voqu la possibilit de listes cycliques (section 4.4.1).
Nous avons certes donn un algorithme pour dtecter un tel cycle (l'algorithme du livre
et de la tortue, page 59), mais il exploite de faon cruciale le fait que chaque lment de
la liste ne possde qu'au plus un successeur. Dans le cas d'un graphe, ce n'est plus vrai.
170
marquer
ou d'une autre. Nous utiliserons ici une table de hachage. Une autre solution consiste
modier directement les sommets, si le type
le permet.
rst search
breadth-
s appel la source.
s, puis les sommets
et 6, puis le sommet 3, puis enn le sommet 7. On le redessine ici avec les distances la
source (le sommet 1) indiques en exposant.
01
10
22
33
42
51
62
74
Pour mettre en uvre ce parcours, on va utiliser une table de hachage. Elle contiendra les
sommets dj atteints par le parcours, en leur associant de plus la distance la source.
On renverra cette table comme rsultat du parcours. On crit donc une mthode statique
avec le type suivant :
visited,
le,
vont tre insrs au fur et mesure de leur dcouverte. L'ide est que la le contient,
chaque instant, des sommets situs distance
distance
d+1
sommets distance
sommets distance
d+1
LinkedList
171
Un autre invariant important est que tout sommet prsent dans la le est galement
prsent dans la table
visited.
visited.
while (!q.isEmpty()) {
V v = q.poll();
int d = visited.get(v);
On examine alors chaque successeur
de
v.
for (V w : g.successors(v))
visited,
distance d+1
S'il n'avait pas encore t dcouvert, c'est--dire s'il n'tait pas dans la table
alors on l'ajoute dans la le d'une part, et dans la table
visited
avec la
d'autre part.
if (!visited.containsKey(w)) {
q.add(w);
visited.put(w, d+1);
}
Ceci achve la boucle sur les successeurs de
v.
le, et ainsi de suite. Une fois sorti de la boucle principale, le parcours est achev et on
renvoie la table
visited.
}
return visited;
Le code complet est donn programme 35 page 172. Il s'applique aussi bien un graphe non
orient qu' un graphe orient.
est mis dans la le au plus une fois et donc examin au plus une fois. Chaque arc est
donc considr au plus une fois, lorsque son origine est examine. La complexit est donc
O(V + E),
O(V )
table de hachage, peut contenir (presque) tous les sommets dans le pire des cas.
On note qu'il peut rester des sommets non atteints par le parcours en largeur. Ce sont
les sommets
v.
Sur le graphe
01
10
32
41
Dit autrement, le parcours en largeur dtermine l'ensemble des sommets accessibles depuis
la source, et donne mme pour chacun la distance minimale en nombre d'arcs depuis la
source.
Comme on l'a fait remarquer plus haut, la le a une structure bien particulire, avec
des sommets distance
d,
d + 1.
172
structure de le n'est pas vraiment ncessaire. Deux sacs susent, l'un contenant les
sommets distance
exemple par des
sac
d + 1,
qui est lui-mme vid. (On les change, c'est plus simple.) Cela ne change en
rien la complexit.
Exercice 15.1.
Modier la mthode
bfs
chaque sommet atteint par le parcours. Une faon simple de procder consiste stocker,
pour chaque sommet atteint, le sommet qui a permis de l'atteindre, par exemple dans
une table de hachage. Le chemin est donc dcrit l'envers , du sommet atteint vers la
source.
Exercice 15.2.
arbre
en largeur.
depth-rst search
173
au fur et mesure de leur dcouverte, pour viter de tomber dans un cycle. Prenons
l'exemple du graphe suivant
et d'un parcours en profondeur qui dmarre du sommet 2. Deux arcs sortent de ce sommet,
24
et
25
2 5.
On
passe donc au sommet 5. Aucun arc ne sort de 5 ; c'est une impasse. On revient alors
au sommet 2, dont on considre maintenant le second arc sortant,
peut que suivre l'arc
43
1 4.
2 4.
De 4, on ne
10
et
1 4.
3 1.
Du
1 0,
05
14
20
33
42
51
class DFS<V> {
private final Graph<V> g;
private final HashMap<V, Integer> visited;
private int count;
DFS(Graph<V> g) {
this.g = g;
this.visited = new HashMap<V, Integer>();
this.count = 0;
}
Le champ
count
visited,
dfs
prenant un sommet
en argument.
174
void dfs(V v) {
if (this.visited.containsKey(v)) return;
this.visited.put(v, this.count++);
for (V w : this.g.successors(v))
dfs(w);
}
v a dj t atteint, on ne fait rien. Sinon, on le marque comme dj atteint,
donnant le numro count. Puis on considre chaque successeur w, sur lequel on
Si le sommet
en lui
dans la table
visited avant
de considrer
ses successeurs. C'est l ce qui nous empche de tourner indniment dans un cycle.
La complexit est
O(V + E),
Le parcours en profondeur est donc galement optimal. La complexit en espace est lgrement plus subtile, car il faut comprendre que c'est ici la pile des appels rcursifs qui
contient les sommets en cours de visite (et joue le rle de la le dans le parcours en largeur). Dans le pire des cas, tous les sommets peuvent tre prsents sur la pile, d'o une
complexit en espace
O(V ).
v.
03
10
32
41
tous
dfs
v.
void dfs() {
for (V v : this.g.vertices())
dfs(v);
}
(La surcharge nous permet d'appeler galement cette mthode
visit par un prcdent parcours, l'appel
et sera donc sans eet. Le code complet est donn programme 36 page 175. On l'a complt
par une mthode
getNum
visited
(une fois le
parcours eectu).
Comme on vient de l'expliquer, le parcours en profondeur est, comme le parcours en
largeur, un moyen de dterminer l'existence d'un chemin entre un sommet particulier, la
source, et les autres sommets du graphe. Si c'est l le seul objectif (par exemple, la distance minimale ne nous intresse pas), alors le parcours en profondeur est gnralement
plus ecace. En eet, son occupation mmoire (la pile d'appels) sera le plus souvent bien
int getNum(V v) {
return this.visited.get(v);
}
175
176
infrieure celle du parcours en largeur. L'exemple typique est celui d'un arbre, o l'occupation mmoire sera limite par la hauteur de l'arbre pour un parcours en profondeur,
mais pourra tre aussi importante que l'arbre tout entier dans le cas d'un parcours en largeur. Le parcours en profondeur a beaucoup d'autres application, qui dpassent largement
le cadre de ce cours ; voir par exemple
Exercice 15.3.
Modier la classe
Introduction to Algorithms
[2].
sommet atteint par le parcours. Une faon simple de procder consiste stocker, pour
chaque sommet atteint, le sommet qui a permis de l'atteindre, par exemple dans une table
de hachage. Le chemin est donc dcrit l'envers , du sommet atteint vers la source.
Exercice 15.4.
Exercice 15.5.
Rcrire la mthode
dfs
pile
while
plutt qu'une
Exercice 15.6.
Exercice * 15.7.
a priori
dfs
dj atteint par un autre chemin, parallle. Il faut donc modier le marquage des sommets
pour utiliser non pas deux tats (atteint / non atteint) mais trois : non atteint / en cours
de visite / visit. Modier la classe
mthode
boolean hasCycle()
DFS
Question subsidiaire : Dans le cas trs particulier d'une liste simplement chane, en
quoi cela est-il plus/moins ecace que l'algorithme du livre et de la tortue (page 59) ?
Exercice * 15.8.
n m.
177
Puis on eectue un parcours en profondeur partir d'un sommet quelconque (par exemple
celui en haut gauche, mais ce n'est pas important). Quand on parcourt les successeurs
d'un sommet, on le fait dans un ordre alatoire. Une fois le parcours eectu, le labyrinthe
est obtenu en considrant qu'on peut passer d'un sommet un autre si l'arc correspondant
2
1
4
1
2
3
2 4 3 1 0.
2 1 0,
de longueur 6, mme si celui-ci contient moins d'arcs. De mme le plus court chemin du
sommet 2 au sommet 5 est de longueur 2, en passant par le sommet 4.
L'algorithme que nous prsentons ici pour rsoudre ce problme s'appelle l'algorithme
de Dijkstra. C'est une variation du parcours en largeur. Comme pour ce dernier, on se
donne un sommet de dpart, la source, et on procde par cercles concentriques . La
dirence est ici que les rayons de ces cercles reprsentent une distance en terme de poids
total et non en terme du nombre d'arcs. Ainsi dans l'exemple ci-dessus, en partant de
la source 2, on atteint d'abord les sommets distance 1 ( savoir 4), puis distance 2
( savoir 3 et 5), puis distance 3 ( savoir 1), puis enn distance 5 ( savoir 0). La
dicult de mise en uvre vient du fait qu'on peut atteindre un sommet avec une certaine
distance, par exemple le sommet 5 avec l'arc
2 5,
2 4 5.
On ne peut plus se
le de priorit
(voir chapitre 7). Elle contiendra les sommets dj atteints, ordonns par distance la
source. Lorsqu'un meilleur chemin est trouv, le sommet est remis dans la le avec une
3. Une autre solution consisterait utiliser une structure de le de priorit o il est possible de
modier la priorit d'un lment se trouvant dj dans la le. Bien que de telles structures existent, elles
sont complexes mettre en uvre et, bien qu'asymptotiquement meilleure, leur utilisation n'apporte pas
ncessairement un gain en pratique. La solution que nous prsentons ici est un trs bon compromis.
178
de chaque arc. De manire quivalente, on choisit ici de se donner plutt une fonction de
poids, comme un objet qui implmente l'interface suivante
interface Weight<V> {
int weight(V x, V y);
}
c'est--dire qui fournit une mthode
et
de l'arc
x y.
Cette
existe eectivement un
dans le graphe.
(v,d)
est un sommet et
PriorityQueue. Elle va
class Node<V> {
V node;
int dist;
}
Pour que ces paires soient eectivement ordonnes par la distance, et utilises en cons-
l'interface
est imm-
shortestPaths,
qui renvoie une table donnant les sommets atteints et leur distance la source.
visited
distance
lement la source avec la distance 0. Les distances dans cette table ne sont pas forcment
optimales ; elles pourront tre amliores au fur et mesure du parcours.
pq,
while (!pq.isEmpty()) {
179
l'on a dj trouv le plus court chemin jusqu' ce sommet. On l'ignore donc, en passant
directement l'itration suivante de la boucle.
Node<V> n = pq.poll();
if (visited.contains(n.node)) continue;
Cette situation peut eectivement se produire lorsqu'un premier chemin est trouv puis
un autre, plus court, trouv plus tard. Ce dernier passe alors dans la le de priorit devant
le premier. Lorsque le chemin plus long nira par sortir de la le, il faudra l'ignorer. Si le
visited.add(n.node);
v. La distance v en empruntant l'arc correspondant
est la somme de la distance n.node, c'est--dire n.dist, et du poids de l'arc, donn par
la mthode w.weight.
Puis on examine chaque successeur
for (V v: g.successors(n.node)) {
int d = n.dist + w.weight(n.node, v);
v. Soit c'est la premire fois qu'on
distance. Dans ce dernier cas, on peut ou non amliorer
n.node. On regroupe les cas o distance doit tre mise
en passant par
d.
distance et
v dans
Une fois tous les successeurs traits, on ritre la boucle principale. Une fois
qu'on est sorti de celle-ci, tous les sommets atteignables sont dans
distance,
avec leur
return distance;
Le code complet est donn programme 37 page 180. Le rsultat de l'algorithme de Dijkstra
sur le graphe donn en exemple plus haut, partir de la source 2, est ici dessin avec les
distances obtenues au nal pour chaque sommet en exposant :
05
1
32
2
1
1
13
1
41
4
1
1
20
3
52
180
181
Sur cet exemple, tous les sommets ont t atteints par le parcours. Comme pour les
parcours en largeur et en profondeur, ce n'est pas toujours le cas : seuls les sommets pour
lesquels il existe un chemin depuis la source seront atteints.
valuons la complexit de l'algorithme de Dijkstra, dans le pire des cas. La le de
priorit peut contenir jusqu'
fois, et chaque considration d'un arc peut conduire l'insertion d'un lment dans la le.
Exercice 15.9.
Modier la mthode
shortestPaths
source et chaque sommet atteint par le parcours. Une faon simple de procder consiste
stocker, pour chaque sommet atteint, le sommet qui a permis de l'atteindre, par exemple
dans une table de hachage. Le chemin est donc dcrit l'envers , du sommet atteint
vers la source. Attention : lorsqu'un chemin est amlior, il faut mettre jour cette table.
182
Annexes
Lexique Franais-Anglais
franais
anglais
voir pages
aectation
assignment
arbre
tree
77
arbre binaire
binary tree
77
arbre de prxes
trie
92
arc
(directed) edge
163
arte
edge
163
champ
eld
chemin
path
177
corde
rope
96
degr entrant
indegree
163
degr sortant
outdegree
163
feuille
leaf
77
le
queue (FIFO)
54
le de priorit
priority queue
101
ottant
oating-point number
13
graphe
graph
163
(un)directed graph
163
176
graphe tiquet
labeled graph
inxe (parcours)
inorder traversal
79
liste
liste
49
liste d'adjacence
adjacency list
166
matrice d'adjacence
adjacency matrix
164
mmosation
memoization
125
mthode
method
parcours en largeur
170
parcours en profondeur
172
pgcd
gcd
119
pile
stack (LIFO)
54, 44
shortest path
177
programmation
dynamic
186
anglais
programming (DP)
voir pages
127
racine
root
77
rebroussement
backtracking
131
rednition
overriding
seau
bucket
70
sommet
vertex
163
surcharge
overloading
table de hachage
hash table
69
tableau
array
33
tableau
resizable array
39
redimensionnable
tas
heap
101
transtypage
cast
47
tri
sorting
137
tri en place
in-place sort
tri fusion
mergesort
142
insertion sort
137
heapsort
146
tri rapide
quicksort
138
tri topologique
topological sort
176
Bibliographie
[1] G. M. Adel'son-Vel'ski
and E. M. Landis. An algorithm for the organization of information.
Soviet MathematicsDoklady,
[2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliord Stein.
In-
Addison-Wesley, 1989.
Algorithm design.
merical Algorithms.
[6] Donald E. Knuth.
and Searching.
J. ACM,
Wesley, 2008.
[9] Henry S. Warren.
Hackers's Delight.
Addison-Wesley, 2003.
Addison
188
BIBLIOGRAPHIE
Index
!= (oprateur), 19, 65
O, 28
& (oprateur), 14
<< (oprateur), 14
== (oprateur), 19, 75
>> (oprateur), 14
>>> (oprateur), 14
^ (oprateur), 14
(oprateur), 14
binary search,
bit, 14
36
boucle, 163
C++, 7, 17
calculabilit, 23
champ, 3
chemin
dans un graphe, 164
classe, 3
abstract,
10
abstraite, 10
adresse, 18
algorithme, 23
Comparable<T> (java.lang.),
Comparator<T> (java.util.),
de Dijkstra, 177
de Human, 151
alias, 19, 21, 38, 61
complment deux, 14
arbre, 77
complexit, 23
auto-quilibr, 107
amortie, 44, 74
binaire, 77
asymptotique, 27
binaire de recherche, 79
d'un algorithme
de Patricia, 94
au pire cas, 24
en moyenne, 25
de prxes, 92
quilibr, 84
d'un problme, 26
compression, 151
arc, 163
arithmtique, 119
Arrays (java.util.),
constructeur, 3
37
corde, 96
arte, 163
AVL, 84
cycle
backtracking,
Bzout, 120
DAG, 176
BFS, 170
dbordement arithmtique,
14
91, 149
109
190
INDEX
dcalage, 14
Human
algorithme de, 151
dcidable, 23
hritage, 7
DFS, 172
Dijkstra
immuable, 61
implements,
galit, 19
interface, 12
indcidable, 23
physique, 20
Java, 3
structurelle, 20, 75
encapsulation, 4, 45, 54
ensemble, 69, 90, 92
ratosthne, 122
tiquette, 163
Euclide, 119
Euler, 124
exception, 82
exponentiation rapide, 121
feuille, 77
Fibonacci, 30, 35, 88, 120, 121, 125
le, 54
de priorit, 101
final,
61
ottant, 15
Floyd, Robert W., 59
Garbage Collector,
12
java.lang.
Comparable<T>, 91, 149
java.util.
Arrays, 37
Comparator<T>, 109
HashMap<K, V>, 74
HashSet<E>, 74
LinkedHashMap<E>, 76
LinkedHashSet<E>, 76
LinkedList<E>, 64
PriorityQueue, 154
PriorityQueue<E>, 109
Queue<E>, 57
Stack<E>, 45, 54
TreeMap<K, V>, 88
TreeSet<E>, 88
Vector<E>, 41
Josephus, 64
voir GC
Knuth, Donald E.
gnricit, 10
Knuth shue,
gnrique, 74
graphe, 163
35
dense, 164
LinkedHashMap<E> (java.util.),
LinkedHashSet<E> (java.util.),
LinkedList<E> (java.util.), 64
hachage, 69
heap
voir tas, 101
heapsort
voir tri par tas, 107
74
liste
chane, 49
cyclique, 59, 64
d'adjacence, 166
doublement chane, 61
simplement chane, 49
hritage, 96
Math.random,
Horner
matrice
35, 53
d'adjacence, 164
76
76
INDEX
191
sommet, 163
mlange
voir
Knuth shue,
d'une pile, 44
35
mmosation, 125
mesure lmentaire, 24
mthode, 4
null, 19
NullPointerException,
Object,
surcharge, 6, 75
19, 50, 60, 82
table de hachage, 69
10, 74, 75
tableau, 16, 33
objet, 3
OutOfMemoryError,
de gnriques, 47
17
parcours, 34
redimensionnable, 39, 102
paquetage, 13
parcours
d'arbre, 79
this,
de graphe, 169
de liste, 50
en largeur d'un graphe, 170
en profondeur d'un graphe, 172
inxe, 79
transtypage, 47
Pascal, 128
persistance, 61
fusion, 142
pgcd, 119
pile
d'appels, 17
rapide, 138
topologique, 176
pointeur, 18
protected,
public, 13
union nd,
111
valeur, 18
par dfaut, 19
13
Queue<E> (java.util.),
racine
d'un arbre, 77
rebroussement, 131
recherche
dichotomique, 36
rednition, 8
reines
problme des
trie,
N,
131
sentinelle, 63
85
57
Vector<E> (java.util.),
visibilit, rgles de, 13
41
88
84, 88