Cours programmation et algorithmique

Cours programmation et algorithmique, tutoriel & guide de travaux pratiques en pdf.

Listes chaînées, révisions

Les listes chaınées ont déja et vues dans le cours précédent. Nous commencons donc par quelques révisions. Attention, nous profitons de ce que les listes ont (( déja et vues en cours )) pour systématiser les techniques de programmation sur les listes. Il y a sans doute un vrai profit a` lire cette section. Si vous en doutez, essayez tout de suite les exercices de la section 2.4.

Opérations elémentaires sur les listes

Comme révision nous montrons comment réaliser les ensembles (d’entiers) a` partir des listes (d’entiers). Voici la définition des cellules de liste d’entiers.
class
int
L i s t
L i s t {
val ;
next ;
// L’élément
// La suite
L i s t (int val,
this.val = val
L i s t next) {
; this.next = next ;
}
}
Un ensemble est représent par une liste dont tous les eléments sont deux a` deux distincts. Nous ne spécifions aucune autre contrainte, en particulier aucun ordre des eléments d’une liste n’est imposé. Pour la programmation, un premier point très important a` prendre en compte est que null est un ensemble valable. Il est alors naturel d’écrire des méthodes statiques, car null qui ne possède aucune méthode est une valeur légitime pour une variable de type List .
Commencons par calculer le cardinal d’en ensemble. Compte tenu de ce que les eléments des listes sont deux a` deux distincts, il suﬃt de calculer la longueur d’une liste. Employons donc la boucle idiomatique
static int card( L i s t xs) {
int r = 0 ;
for ( ; xs != null ; xs = xs.next)
r++ ; // pour r = r+1 ;
return r ;
}
Ce premier code fait apparaˆıtre qu’il n’est pas toujours utile de réserver une variable locale pour la boucle idiomatique. Ecrire xs = xs.next ne fait que changer la valeur de la variable locale xs (qui appartient en propre a` l’appel de méthode) et n’a pas d’impact sur la liste elle-mˆeme. Ainsi écrire le code suivant ne pose pas de problème particulier.
L i s t xs = new L i s t (1, new L i s t (2, new L i s t (3, new L i s t (4,null)))) l int size = card(xs) ;
A la fin du code, la variable xs existe toujours et référence toujours la première cellule de la liste {1, 2, 3, 4}. En fait, cette variable xs n’a rien `a voir avec le paramètre homonyme de la méthode card et heureusement.
Poursuivons en aﬃchant les ensembles, ou, plus exactement, en fabriquant une représentation aﬃchable des ensembles sous forme de chaˆıne. Voici un premier essai d’écriture d’une méthode statique toString dans la classe List avec la boucle idiomatique.
static String toString(L i s t xs) {
String r = « { » ;
for ( ; xs != null ; xs = xs.next )
r = r + xs.val + « , » ;
ˆ ´ ´ 11
r = r + « } » ;
return r ;
}
Le code est critiquable :
L’aﬃchage est laid, il y a une virgule en trop a` la fin. Par exemple, pour la liste des entiers
1 et 3, on obtient « {1, 3, } ».
Le coˆut de production de la chaˆıne est quadratique en la longueur de la liste. En eﬀet la concaténation de deux chaˆınes (par +) coˆute en proportion de la somme des longueurs des chaˆınes concaténées, car il faut allouer une nouvelle chaˆıne pour y recopier les caractères des chaˆınes concaténées. Pour une liste xs de longueur n on procède donc `a n concaténations de chaˆınes, de tailles supposées régulièrement croissantes ce qui mène au final `a un coˆut quadratique.
n(n + 1) k + 2 × k + n × k = k
Pour remédier au premier problème on peut distinguer le cas du premier elément de la liste. Pour remédier au second problème il faut utiliser un objet StringBuilder de la bibliothèque Java (voir B.6.1.4). Les objets StringBuilder sont des chaˆınes dynamiques, dont on peut changer la taille. En particulier, ils possèdent une méthode append(String str) qui permet de leur ajouter une chaˆıne str `a la fin, pour un coˆut que l’on peut considérer proportionnel `a la longueur de str. Bref on a :
static String toString(L i s t xs) {
StringBuilder r = new StringBuilder () ; // Un StringBuilder `a nous
r.append(« {« ) ;
i f (xs != null) {
r.append(xs.val) ; // ajouter l’écriture décimale du premier entier xs = xs.next ;
et celles des suivants préfixées par « , » for ( ; xs != null ; xs = xs.next )
r.append(« , » + xs.val) ;
}
r.append(« } ») ;
Renvoyer la cha^ıne contenue dans le StringBuilder return r.toString() ;
}
Après cet échauﬀement, écrivons ensuite la méthode mem qui teste l’appartenance d’un entier a` un ensemble.
static boolean mem(int x, L i s t xs) {
for ( ; xs != null ; xs = xs.next) {
i f (x == xs.val) return true ;
}
return false ;
}
On emploie la boucle idiomatique, afin de parcourir la liste et de retourner de la méthode mem dès qu’un entier égal a` x est trouvé. Comme on le sait certainement déj`a une écriture récursive est également possible.
static boolean mem(int x, L i s t xs) {
i f (xs == null) {
return false ;
} else {
return (x == xs.val) || mem(x, xs.next) ;
}
}
La version récursive provient directement de la définition inductive des listes, elle tient en deux équations :
M (x, ∅)
M (x, (x′, X′))
= faux
= (x = x′)
∨ M (x, X′)
Ces deux équations sont le support d’une preuve par induction structurelle évidente de la cor-rection de mem.
Alors, que choisir ? De fa¸con générale le code itératif (le premier, avec une boucle) est plus eﬃcace que le code récursif (le second), ne serait-ce que parce que les appels de méthode sont assez coˆuteux. Mais le code récursif résulte d’une analyse systématique de la structure de données inductive, et il a bien plus de chances d’ˆetre juste du premier coup. Ici, dans un cas aussi simple, le code itératif est préférable (en Java qui favorise ce style).

Programmation sure, style dit fonctionnel

Nous envisageons maintenant des méthodes qui fabriquent de nouveaux ensembles. Commencons par la méthode add qui ajoute un elément a` un ensemble. Le point remarquable est qu’un ensemble contient au plus une fois un elément donné. Une fois disponible la méthode mem, écrire add est très facile.
static L i s t add(int x, L i s t xs) {
i f (mem(x, xs)) {
return xs ;
} else {
return new L i s t (x, xs) ;
}
}
Attaquons ensuite la méthode remove qui enlève un elément x d’un ensemble X. Nous choisissons de suivre le principe des structures de données dites fonctionnelles ou non-mutables ou encore persistantes. Selon ce principe, on ne modifie jamais le contenu des cellules de liste. Cela revient `a considérer les listes comme définies inductivement par L E = { } ∪ (E × L E ), et il est important d’admettre dès maintenant que cette approche rend la programmation bien plus sure.
Pour écrire remove, raisonnons inductivement : dans un ensemble vide, il n’y a rien `a enlever ; tandis que dans un ensemble (une liste) X = (x′, X′) on distingue deux cas :
L’élément x a` enlever est égal a` x′ et alors X moins x est X′, car X est une liste d’éléments
deux a` deux distincts et donc X′ ne contient pas x.
Sinon, il faut enlever x de X′ et ajouter x′ a` la liste obtenue, dont on sait qu’elle ne peut pas contenir x′.
Soit en équations : ∅
R(x, ∅) =
R(x, (x, X′)) = X′
R(x, (x′, X′)) = (x′, R(x, X′)) avec x = x′
Et en Java :
static L i s t remove(int x, L i s t xs) {
i f (xs == null) {
return null ;
} else i f (x == xs.val) { return xs.next ;
} else {
return new L i s t (xs.val, remove(x, xs.next)) ;
}
}
En ce qui concerne l’état mémoire, remove(x,xs) renvoie une nouvelle liste (il y a des new), dont le début est une copie du début de xs, jusqu’`a trouver l’élément x. Plus précisément, si nous écrivons
L i s t xs = new L i s t (1, new
L i s t (2,
new
L i s t
(3,
new
L i s t
(4,
null)))) ;
L i s t ys = remove(3, xs) ;
Alors on a les structures suivantes en mémoire
(Les cellules allouées par remove sont grisées.) On constate que la partie de la liste xs qui précède l’élément supprimé est recopiée, tandis que la partie qui suit l’élément supprimé est partagée entre les deux listes. Dans le style persistant on en vient toujours `a copier les parties des structures qui sont changées.
Au passage, si on écrit plutˆot L i s t xs = new L i s t (1, new L i s t (2, new L i s t (3, new L i s t (4, null)))) ; xs = remove(3, xs) ;
C’est-`a-dire exactement la mˆeme chose, sauf que la variable xs pointe maintenant vers la nouvelle liste et qu’il n’y a plus de référence vers la première cellule de l’ancienne liste. Il en résulte que la mémoire occupée par les trois premières cellules de l’ancienne liste ne peut plus ˆetre accédée par le programme. Ces cellules sont devenues les miettes et le gestionnaire de mémoire de l’environnement d’exécution de Java peut les récupérer. Le ramassage des miettes (garbage collection) est automatique en Java, et c’est un des points forts du langage.
Ecrivons maintenant remove avec une boucle. Voici un premier essai : parcourir la liste xs en la recopiant en évitant de copier tout elément égal a` x.
static L i s t remove(int x, L i s t xs) {
L i s t r = null ;
for ( ; xs != null ; xs = xs.next ) {
i f (x != xs.val)
r = new L i s t (xs.val, r) ;
}
return r ;
}
Et ici apparaˆıt une diﬀérence, alors que la version récursive de remove préserve l’ordre des eléments de la liste, la version itérative inverse cet ordre. Pour s’en convaincre, on peut remarquer que lorsque qu’une nouvelle cellule new List(xs.val, r) est construite, l’élément xs.val est ajouté au début de la liste r, tandis qu’il est extrait de la fin de la liste des eléments déj`a parcourus. On peut aussi schématiser l’état mémoire sur l’exemple déj`a utilisé. Avant la boucle L’inversion n’a pas d’importance ici, puisque les ensembles sont des listes d’éléments deux `a deux distincts sans autre contrainte, le code itératif convient. Il n’en y irait pas de mˆeme si les listes étaient ordonnées.
Il est possible de procéder itérativement et de conserver l’ordre des eléments. Mais c’est un peu plus diﬃcile. On emploie une technique de programmation que faute de mieux nous appellerons initialisation diﬀérée. Jusqu’ici nous avons toujours appel´ le constructeur des listes `a deux arguments, ce qui nous garantit une bonne initialisation des champs val et next des cellules de liste. Nous nous donnons un nouveau constructeur List ( int val) qui initialise seulement le champ val.1 Le champ next sera aﬀect´ une seule fois plus tard, ce qui revient moralement a` une initialisation.
L i s t (int val) { this.val = val ; }
Pour illustrer l’initialisation diﬀérée, nous commenons par un exemple plus facile.
Exercice 2 Copier une liste en respectant l’ordre de ses eléments, sans écrire de méthode récursive.
Solution. L’idée revient a` parcourir la liste xs en copiant ses cellules et en délégant l’initialisation du champ next a` l’itération suivante. Il y a un petit décalage a` gérer au début et a` la fin du parcours.
static L i s t copy(L i s t xs) {
i f (xs == null) return null ;
Ici la copie possède au moins une cellule, que voici
L i s t r = new L i s t (xs.val) ;
last pointe sur la dernière cellule de la liste r
L i s t last = r ;
// Parcourir la suite de xs
for ( xs = xs.next ; xs != null ; xs = xs.next ) {
(( initialiser )) last.next a` une nouvelle cellule last.next = new L i s t (xs.val) ;
/ qui devient donc la dernière cellule du résultat / last = last.next ;
}
(( initialiser )) le next de la toute dernière cellule a` une liste vide last.next = null ; // Inutile, mais c’est plus propre
return r ;
}
On observe que le code construit une liste sur laquelle il maintient deux références, r pointe sur la première cellule, tandis que last pointe sur la dernière cellule — sauf très brièvement au niveau du commentaire /**. . . **/, o`u last pointe sur l’avant-dernière cellule. Plus précisément, la situation en (( régime permanent )) avant la ligne qui précède le commentaire
On con¸coit qu’avec un tel dispositif il est facile d’ajouter de nouvelles cellules de liste `a la fin du résultat et possible de rendre le résultat (avec r qui pointe sur la première cellule). On observe le cas particulier traité au début, il résulte de la nécessité d’identifier le cas o`u il ne faut pas construire la première cellule du résultat.
Enfin, la méthode itérative construit exactement la mˆeme liste que la méthode récursive, mˆeme si les cellules de listes sont allouées en ordre inverse. En eﬀet la méthode récursive al-loue la cellule après que la valeur du champ next est connue, tandis que la méthode itérative l’alloue avant.
La figure 2 donne la nouvelle version itérative de remove, écrite selon le principe de l’ini-tialisation diﬀérée. Par rapport `a la copie de liste, le principal changement est la possibilité d’arrˆet de la copie `a l’intérieur de la boucle. En eﬀet, lorsque l’élément `a supprimer est identifi´ (x == xs.val), nous connaissons la valeur `a ranger dans last.next, puisque par l’hypothèse (( xs est un ensemble )), xs moins l’élément x est exactement xs.next, on peut donc arrˆeter la copie. On observe également les deux cas particuliers traités au début, ils résultent, comme dans la copie de liste, de la nécessit´ d’identifier les cas o`u il ne faut pas construire la première cellule du résultat. Au final le code itératif est quand mˆeme plus complexe que le code récursif. Par conséquent, si l’eﬃcacit´ importe peu, par exemple si les listes sont de petite taille, la programmation récursive est préférable.
Nous pouvons maintenant étendre les opérations elémentaires impliquant un elément et un ensemble et programmer les opérations ensemblistes du test d’inclusion, de l’union et de la diﬀérence. Pour programmer le test d’inclusion xs ⊆ ys, il suﬃt de tester l’appartenance de tous les eléments de xs `a ys.
static boolean included(L i s t xs, L i s t ys) { for ( ; xs != null ; xs = xs.next )
i f (!mem(xs.val, ys)) return false ;
return true ;
}
static L i s t remove(int x, L i s t xs) {
/* Deux cas particuliers */
i f (xs == null) return null ;
/* Ici xs != null, donc xs.val existe */
i f (x == xs.val) return xs.next ;
/* Ici la première cellule du résultat existe et contient xs.val */
L i s t r = new L i s t (xs.val) ;
L i s t last = r ;
/* Cas général : copier xs (dans r), jusqu’`a trouver x */
for ( xs = xs.next ; xs != null ; xs = xs.next ) {
i f (x == xs.val) {
(( initialiser )) last.next a` xs moins xs.val (c-a-d. xs.next) last.next = xs.next ;
return r ;
}
(( initialiser )) last.next a` une nouvelle cellule last.next = new L i s t (xs.val) ;
last = last.next ;
}
(( initialiser )) last.next a` une liste vide last.next = null ; // Inutile mais c’est plus propre. return r ;
}
Exercice 3 Programmer l’union et la diﬀérence ensembliste.
Solution. Pour l’union, il suﬃt d’ajouter tous les elément d’un ensemble a` l’autre.
static L i s t union(L i s t xs, L i s t ys) {
L i s t r = ys ;
for ( ; xs != null ; xs = xs.next )
r = add(xs.val, r) ;
return r ;
}
On aurait mˆeme pu se passer de la variable r pour écrire ys = add(xs.val, ys) return ys. Mais la clarté en aurait souﬀert. et puis Pour la diﬀérence des ensembles, légèrement plus délicate en raison de la non-commutativité, on enlève de xs tous les eléments de ys.
// Renvoie xs \ ys
static L i s t diff(L i s t xs, L i s t ys) {
L i s t r = xs ;
for ( ; ys != null ; ys = ys.next )
r = remove(ys.val, r) ;
return r ;
}

Programmation dangereuse, structures mutables

Les méthodes remove de la section précédente copient tout ou partie des cellules de la liste passée en argument. On peut, par exemple dans un souci (souvent mal venu, disons le tout de suite) d’économie de la mémoire, chercher `a éviter ces copies. C’est parfaitement possible, `a condition de s’autoriser les aﬀectations des champs des cellules de liste. On parle alors de struc-ture de données mutable ou impérative. Ainsi, dans le remove récursif on remplace l’allocation d’une nouvelle cellule par la modification de l’ancienne cellule, et on obtient la méthode nremove
destructive ou en place suivante
static L i s t nremove(int x, L i s t xs) {
i f (xs == null) {
return null ;
} else i f (x == xs.val) { return xs.next ;
} else {
xs.next = nremove(x, xs.next) ;
return xs ;
}
}
On peut adapter la seconde version itérative de remove (figure 2) selon le mˆeme esprit, les références r et last pointant maintenant, non plus sur une copie de la liste passée en argument, mais sur cette liste elle-mˆeme.
static L i s t nremove(int x, L i s t xs) {
/* Deux cas particuliers */
i f (xs == null) return null ;
i f (x == xs.val) return xs.next ;
Ici la première cellule du résultat existe et contient xs.val,
L i s t r = xs ;
L i s t last = r ;
/* Cas général : chercher x dans xs pour enlever sa cellule */ for ( xs = xs.next ; xs != null ; xs = xs.next ) {
/ Ici, on a last.next == xs /
i f (x == xs.val) {
Enlever la cellule pointée par xs last.next = xs.next ;
return r ;
}
last.next = xs ; // Affectation inutile
last = last.next ;
/ Exceptionnellement, on a xs == last
/
}
last.next = null ; // Affectation inutile return r ;
}
On note que la version itérative comporte des aﬀectations de last.next inutiles. En eﬀet, a` l’intérieur de la boucle les références xs et last.next sont toujours égales, car last pointe toujours sur la cellule qui précède xs dans la liste passée en argument, sauf très brièvement au niveau du second commentaire /**. . . **/. En régime permanent, la situation au début d’une itération de boucle (avant le premier commentaire /**. . . **/)
Et on observe qu’alors l’ensemble xs n’a pas changé.
En conclusion, la programmation des structures mutables est tellement délicate qu’il est souvent plus raisonnable de s’abstenir de l’employer. Comme toujours en programmation, la maxime ci-dessus souﬀre des exceptions, dans les quelques cas o`u l’on possède une maˆıtrise complète des structures de données, et en particulier, quand on est absolument sˆur que les structures modifiées ne sont connues d’aucune autre partie du programme.
Un bon exemple de ce type d’exception est la technique d’initialisation diﬀérée employée dans la seconde méthode remove itérative de la figure 2. En eﬀet, le champ next est aﬀect´ une seule fois, et seulement sur des cellules fraˆıches, allouées par la méthode remove elle-mˆeme, et qui ne sont accessible qu’`a partir des variables r et last elles-mˆemes locales `a remove. Par conséquent, les modifications apportées `a certaines cellules sont invisibles de l’extérieur de remove.

Controle de la révision

Nous avons divisé les techniques de programmation sur les listes selon deux fois deux catégories. Les listes peuvent ˆetre fonctionnelles (persistantes) ou mutables (impératives), et la programmation peut ˆetre récursive ou itérative.
Afin d’ˆetre bien sˆur d’avoir tout compris, programmons une opération classique sur les listes des quatre fa¸cons possibles. Concaténer deux listes signifie, comme pour les chaˆınes, ajouter les eléments d’une liste `a la fin de l’autre. Nommons append la méthode qui concatène deux listes. La programmation récursive non-mutable résulte d’une analyse simple de la structure inductive de liste.
static L i s t
i f (xs ==
append( L i s t null) {
xs,
L i s t
ys) {
return ys ; // A(∅, Y ) = Y
} else {
return new L i s t (xs.val, append(xs.next, ys)) ; // A((x, X), Y ) = (x, A(X, Y ))
}
}
Nommons nappend la version mutable de la concaténation. L’écriture récursive de nappend a` partir de la version fonctionnelle est mécanique. Il suﬃt de remplacer les allocations de cellules par des modifications.
static L i s t nappend(L i s t xs, L i s t ys) {
i f (xs == null) {
return ys ;
} else {
xs.next = nappend(xs.next, ys)) ; return xs ;
}
}
Pour la programmation itérative non-mutable, on a recours a` l’initialisation diﬀérée.
static L i s t append( L i s t xs, L i s t i f (xs == null) return ys ; L i s t r = new L i s t (x.val) ;
ys) {
L i s t last = r ;
for ( xs = xs.next ; xs != null ; xs = xs.next ) { last.next = new L i s t (xs.val) ;
last = last.next ;
}
last.next = ys ;
return r ;
}
Pour la programmation mutable et itérative, on supprime les allocations de la version non-mutable et on remplace les initialisations diﬀérées par des aﬀectations des champs next de la liste passée comme premier argument. On n’explicite que la dernière aﬀectation de last.next qui est la seule qui change quelque chose.
static L i s t nappend(L i s t xs, L i s t ys) {
i f (xs == null) return ys ;
L i s t r = xs ;
L i s t last = r ;
for ( xs = xs.next ; xs != null ; xs = xs.next ) {
last = last.next ;
}
last.next = ys ;
return r ;
}
Voici un autre codage plus concis de la mˆeme méthode, qui met en valeur la recherche de la dernière cellule de la liste xs.
static L i s t nappend(L i s t xs, L i s t ys) {
i f (xs == null) return ys ;
L i s t last = xs ;
for ( ; last.next != null ; last = last.next )
// idiome : boucle qui ne fait rien last.next = ys ;
return xs ;
}
Enfin on constate que le coˆut de la concaténation est de l’ordre de n opérations elémentaires, o`u n est la longueur de la première liste.
Exercice 4 Que fait le programme suivant ?
L i s t L i s t
xs = new L i s t (1, new ys = nappend(xs, xs) ;
L i s t
(2,
new
L i s t
(3,
null))) ;
Solution. Le programme aﬀecte la référence xs au champ next de la dernière cellule de la liste xs. Il en résulte une liste (( bouclée )).

I Listes
1 Structure dynamique, structure s´equentielle
2 Listes chaınees, revisions
3 Tri des listes
4 Programmation objet
5 Compl´ement : listes boucl´ees
II Piles et files
1 `A quoi ¸ca sert ?
2 Impl´ementation des piles
3 Impl´ementation des files
4 Type abstrait, choix de l’impl´ementation
IIIAssociations — Tables de hachage
1 Statistique des mots
2 Table de hachage
3 Choix des fonctions de hachage
IVArbres
1 D´efinitions
2 Union-Find, ou gestion des partitions
3 Arbres binaires
4 Arbres de syntaxe abstraite
5 Files de priorit´e
6 Codage de Huffman
V Arbres binaires
1 Implantation des arbres binaires
2 Arbres binaires de recherche
3 Arbres ´equilibr´es
VI Expressions r´eguli`eres
1 Langages r´eguliers
2 Notations suppl´ementaires
3 Programmation avec les expressions r´eguli`eres
4 Impl´ementation des expressions r´eguli`eres
5 Une autre approche du filtrage
VIILes automates
1 Pourquoi ´etudier les automates
2 Rappel : alphabets, mots, langages et probl`emes
3 Automates finis d´eterministes
4 Automates finis non-d´eterministes
5 Automates finis et expressions r´eguli`eres
6 Un peu de Java
References