Conception D Algorithmes Ed3 v1
Conception D Algorithmes Ed3 v1
3e é
3e é
Conception
3e édition
dit
dit
ion
ion
d’algorithmes
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Patrick Bosc - Marc Guyomard
Conception d’algorithmes
Laurent Miclet
Préface de Colin de la Higuera
Conception
La conception des algorithmes : une science !
Patrick Bosc L’algorithmique est l’art et la science de concevoir des algorithmes
était professeur corrects et efficaces. Pour beaucoup d’informaticiens, c’est l’aspect
d’informatique à l’Enssat, artistique qui prédomine : on cherche l’idée lumineuse, la structure
école d’ingénieurs de cachée, la réponse astucieuse. Mais la conception des algorithmes
l’université de Rennes 1 est d’abord une science dont il faut posséder les bases et les tech-
située à Lannion, où il a niques avant d’exprimer sa créativité. Ce livre invite le lecteur à une
enseigné une vingtaine approche rigoureuse de la construction d’algorithmes. Il explique
d’algorithmes
d’années la plupart des comment la même idée peut se retrouver dans plusieurs algorithmes
méthodes traitées dans correspondant à des problèmes différents. Il donne les outils pour
cet ouvrage. Son activité analyser rationnellement un problème, le classer dans une famille
de recherche a concerné de méthodes et produire une solution exacte.
la prise en compte de
la flexibilité dans les Un manuel de référence sur la construction raisonnée des
systèmes d’information. algorithmes
Marc Guyomard était Dans chaque chapitre de ce livre, les bases théoriques et techniques
professeur d’informatique sont rappelées et illustrées par des exemples. On y trouve ensuite un
grand nombre d’exercices, accompagnés d’une correction minutieuse
150 exercices corrigés
à l’Enssat. Il s’est plus
particulièrement intéressé et complète. De la sorte, on y voit comment une démarche rationnelle
M. Guyomard
• Aux étudiants et enseignants en science informatique
• Aux ingénieurs, enseignants-chercheurs,
informaticiens et industriels
L. Miclet
P. Bosc
La 1re édition de Conception d’algorithmes a été finaliste
du prix Roberval 2017.
49 E
Algorithmes
3e é
3e é
Conception
3e édition
dit
dit
ion
ion
d’algorithmes
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Conception d’algorithmes
Laurent Miclet
Préface de Colin de la Higuera
Conception
La conception des algorithmes : une science !
Patrick Bosc L’algorithmique est l’art et la science de concevoir des algorithmes
était professeur corrects et efficaces. Pour beaucoup d’informaticiens, c’est l’aspect
d’informatique à l’Enssat, artistique qui prédomine : on cherche l’idée lumineuse, la structure
école d’ingénieurs de cachée, la réponse astucieuse. Mais la conception des algorithmes
l’université de Rennes 1 est d’abord une science dont il faut posséder les bases et les tech-
située à Lannion, où il a niques avant d’exprimer sa créativité. Ce livre invite le lecteur à une
enseigné une vingtaine approche rigoureuse de la construction d’algorithmes. Il explique
d’algorithmes
d’années la plupart des comment la même idée peut se retrouver dans plusieurs algorithmes
méthodes traitées dans correspondant à des problèmes différents. Il donne les outils pour
cet ouvrage. Son activité analyser rationnellement un problème, le classer dans une famille
de recherche a concerné de méthodes et produire une solution exacte.
la prise en compte de
la flexibilité dans les Un manuel de référence sur la construction raisonnée des
systèmes d’information. algorithmes
Marc Guyomard était Dans chaque chapitre de ce livre, les bases théoriques et techniques
professeur d’informatique sont rappelées et illustrées par des exemples. On y trouve ensuite un
grand nombre d’exercices, accompagnés d’une correction minutieuse
150 exercices corrigés
à l’Enssat. Il s’est plus
particulièrement intéressé et complète. De la sorte, on y voit comment une démarche rationnelle
M. Guyomard
• Aux étudiants et enseignants en science informatique
• Aux ingénieurs, enseignants-chercheurs,
informaticiens et industriels
L. Miclet
P. Bosc
La 1re édition de Conception d’algorithmes a été finaliste
du prix Roberval 2017.
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Conception
d’algorithmes
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Conception
d’algorithmes
Principes et 150 exercices corrigés
3e édition
ÉDITIONS EYROLLES
61, bd Saint-Germain
75240 Paris Cedex 05
www.editions-eyrolles.com
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Il s'est passé presque 5 ans depuis la première édition de ce livre. Et en 5 ans, si le livre
n'a pas vieilli, le contexte a énormément changé.
Tout d'abord, si ce livre n'a pas pris d'âge, c'est dans doute parce qu'il est très bien écrit.
Mais aussi parce que l'algorithmique de 2015 est sensiblement la même que l'algorithmique
de 2020 : les bons algorithmes le restent et les techniques de preuve n'ont pas subi de
changements majeurs. En soi, c'est déjà une bonne nouvelle !
Pour ce qui est du contexte, en revanche, d'une part, la promesse de l'arrivée de l'infor-
matique dans l'enseignement secondaire est devenue une réalité. En plusieurs étapes, en
protant d'une réforme ambitieuse du lycée, l'enseignement de spécialité Informatique et
Sciences du Numérique de terminale est devenue une spécialité Numérique et Sciences
informatiques (NSI) en première et en terminale. D'autres enseignements informatiques
ont vu le jour permettant ainsi une éducation à l'informatique de plus en plus complète.
Et au c÷ur de celle-ci, on trouve toujours l'algorithmique.
D'autre part, ces dernières années ont vu la montée en puissance de l'intelligence arti-
cielle (IA). Les exploits de celle-ci sur des tâches de plus en plus variées ont suscité un
intérêt généralisé et aujourd'hui la question se pose : faut-il former à l'IA ? Des questions
supplémentaires arrivent ensuite : est-ce de l'informatique ? Ou est-ce à nouveau une ma-
tière qu'on penserait transversale et qui serait alors à maîtriser par tous les enseignants ?
Notons le parallèle avec les questions qui se sont posées il y a quelques années lorsque
l'informatique a cherché sa place.
Cette arrivée un peu brusque de l'IA interpelle également sur la position de l'algorithmique.
Est-il encore nécessaire de l'étudier alors que, dans les langages de programmation, des
bibliothèques très bien faites orent de nombreux outils standardisés pour faire des calculs
complexes en un appel de fonction ? Une seconde question peut se poser : faut-il une
algorithmique diérente car celle enseignée pour l'informatique serait caduque ?
On répondra armativement à la première question. S'il s'agit juste de reproduire une
expérience existante, bien peu d'algorithmique est nécessaire. Et c'était déjà le cas avant :
on pouvait déjà récupérer du code produit par quelqu'un d'autre et l'utiliser aveuglément.
Mais si le problème qu'on cherche à résoudre est nouveau, cela ne marche pas. On notera
en passant qu'un enjeu majeur pour l'IA est celui de l'intelligibilité : et il semble bien
compliqué de comprendre comment une IA propose une solution si on n'étudie pas au
préalable les algorithmes utilisés.
Pour ce qui est de la seconde question, on répondra par la négative. S'il convient de faire
très attention, et si de nouveaux problèmes vont se poser, il est fort à parier cependant
que nombreux sont les algorithmes décrits et étudiés dans ce livre qui trouveront toute
leur place dans le domaine de l'intelligence articielle.
VI CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
Mais réexplorons aussi certains des éléments motivant la lecture de ce livre il y a 5 ans.
Parmi les idées reçues répandues encore aujourd'hui, celle que la génération Y, celle des en-
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
fants du numérique, n'a pas grand-chose à apprendre, a fait long feu. Elle était sans doute
liée au regard attendri de personnes admiratives devant un bambin qui se saisit d'une
tablette, ou d'un adolescent capable d'utiliser ses deux pouces pour taper un message
sur son téléphone portable. Maintenant, l'adulte doit comprendre que de pareilles perfor-
mances sont purement motrices et ne doivent pas faire croire que la nouvelle génération
est nativement dotée de capacités dont la sienne est dépourvue.
Une deuxième idée reçue tient au lieu commun a-t-on besoin de savoir comment fonctionne
un moteur pour pouvoir conduire une voiture ? . Elle se justiait par un modèle ancien,
dépassé, celui où il y avait d'un côté les informaticiens, de l'autre le reste de l'humanité,
et dans lequel un être humain n'avait qu'à faire appel à un informaticien quand il avait
besoin de résoudre un problème informatique. Aujourd'hui, sans doute parce que dans la
résolution de tout problème - ou presque - il y a une part d'informatique, les limites de
cette séparation binaire de l'humanité volent en éclats.
Une troisième idée reçue consiste à penser qu'une simple éducation aux usages est suf-
sante pour la grande majorité des jeunes, quelques-uns pouvant cependant être formés
à l'informatique parce qu'ils deviendront informaticiennes ou informaticiens. On peut ce-
pendant penser qu'avec la quantité croissante d'usages, leur enseignement direct n'est plus
rentable : s'il pouvait être plus raisonnable il y a quelques années d'enseigner l'usage d'une
suite bureautique que d'enseigner l'informatique, il faut aujourd'hui, si l'on en reste aux
usages qui s'avèrent indispensables y inclure également le travail coopératif avec les outils
du cloud, les questions de sécurité, d'intégrité des données, de réseau, l'interrogation de
bases de données, l'organisation de ses archives, les bonnes pratiques sur internet. . . C'est
tout simplement devenu plus compliqué d'enseigner les usages que d'enseigner l'informa-
tique !
Avant d'attaquer ce point, et d'expliquer - enn - en quoi ce livre est très utile, introduisons
cette question de changement de paradigme avec un exemple emprunté à Seymour Papert.
Il s'agit de résoudre la multiplication suivante :
XLIV × XVII
La méthode de résolution que l'on peut imaginer consiste à transformer la notation romaine
en notation arabe, de poser 44 × 17 et probablement d'utiliser un outil numérique pour
nir.
Mais on peut également se demander comment faisaient les Romains de l'époque, puis les
Européens qui jusqu'au Moyen Âge ont eu à utiliser les nombres romains. . .
Pour résoudre des questions faisant intervenir de l'arithmétique, il était nécessaire de reco-
der l'information autrement, d'une façon permettant l'utilisation d'algorithmes appropriés
que chacun pouvait utiliser. Le développement du commerce a entraîné, au Moyen âge,
le remplacement de la numération romaine par la numération arabe : adieu les chires
romains, bienvenue aux chires arabes.
C'est une révolution similaire qui est nécessaire aujourd'hui : celle-ci n'est pas technolo-
gique. Elle se situe au niveau de nos façons de raisonner, de résoudre des problèmes.
On constate maintenant qu'un nombre sans cesse croissant de problèmes se résolvent en
passant par trois étapes : transformation des données du problème en information, traite-
ment algorithmique de cette information, restitution de la solution sous une forme utile,
acceptable, agréable.
Cette façon de résoudre un problème, en passant par la transformation en information
et sa résolution informatique s'appelle le computational thinking en anglais. En français,
PRÉFACE VII
plusieurs traductions existent : la pensée informatique, la pensée computationnelle, la
pensée algorithmique.
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Or, la seconde étape de cette construction n'obéit pas à la simple logique du codage : elle
repose pour beaucoup sur l'algorithmique. La transformation de nos données en résultats,
qu'elle se fasse en une passe ou de façon continue, nécessite l'emploi d'algorithmes, de
savoir choisir parmi ceux-ci, de les prouver aussi.
La pensée algorithmique repose donc de manière forte sur une culture algorithmique. Et
celle-ci s'acquiert en utilisant des livres comme ce Conception d'algorithmes : Principes et
150 exercices corrigés que j'accueille de nouveau avec plaisir, et qui conrme sa place de
référence en matière d'enseignement de l'algorithmique dans le monde francophone.
L'algorithmique, pour beaucoup d'informaticiens, est un art : l'écriture de l'algorithme est
le moment où l'on cherche à trouver l'idée géniale, la structure cachée, celle qui va permettre
de résoudre la question. Les auteurs nous invitent à conserver cet aspect artistique, mais
à développer aussi une approche systématique. . . La même idée géniale se retrouve-t-elle
dans plusieurs algorithmes correspondant à des problèmes diérents ? Qu'est-ce qui, au
niveau de l'analyse, permet d'aborder ces problèmes, nalement, de façon homogène ?
Un enjeu pédagogique particulier est très bien défendu dans ce livre : celui d'écrire des
algorithmes prouvables. Si trouver des idées algorithmiques permettant de résoudre un
problème est tout à fait amusant, qu'il est dicile ensuite de prouver que l'algorithme qui
vient d'être écrit résout bien le problème !
Patrick Bosc, Marc Guyomard et Laurent Miclet, enseignants chevronnés, ont bâti sur
leur expérience devant des étudiants d'IUT, d'école d'ingénieur, d'université, et proposent
ici une approche tout à fait intéressante : plutôt que de proposer un cours avec quelques
exercices, les auteurs ont choisi ici de résumer le cours en retenant les éléments les plus
pertinents, de proposer des exercices et surtout de concentrer la plus grande partie de leur
analyse dans les corrections de ceux-ci : en fait, ce sont ces corrections qui constituent le
l conducteur de l'ouvrage.
Pour conclure, on peut se poser la question du public de ce livre. Ce public peut être
constitué d'enseignants et d'étudiants des lières informatiques des universités et des écoles
d'ingénieurs, qui auront intérêt à l'étudier dans le cadre de leurs études, mais également
comme livre de référence de leur vie professionnelle si dans celle-ci ils sont conduits à
résoudre des problèmes avec des algorithmes, on peut aussi présager qu'un public bien
plus large sera bientôt confronté à des questions similaires. . . L'informatique s'est installée
au lycée (ISN, puis ICN), dans les classes préparatoires, au collège et on parle même de
l'école primaire ! Pour faire face à ces besoins, il faut former des éducateurs, animateurs,
enseignants, des professeurs de toutes les disciplines. . . Bien entendu, un texte comme celui-
ci n'a pas immédiatement sa place : s'il est prévu de commencer à enseigner l'informatique
à tous les niveaux, il n'en demeure pas moins que les enseignants vont s'adresser, un peu
partout, à des débutants. Mais l'enfant de six ans qui va commencer à coder avec Scratch. . .
aura besoin à un moment ou un autre de connaissances plus étendues, et d'une enseignante
ou d'un enseignant qui les maîtrisera.
Je souhaite que cet enseignant francophone ait appris avec ce livre.
Bonne lecture
Colin de la Higuera
Titulaire de la Chaire Unesco en Ressources Educatives Libres à l'Université de Nantes
Président (2012-2015) de la Société informatique de France
Remerciements
Ce livre doit tout, ou presque, à nos établissements d'enseignement et de recherche : l'IUT
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Ce livre a été composé en LATEX par les auteurs avec les logiciels libres TeXstudio, Texmaker, TeX-
nicCenter, TeXShop et MiKTeX. Les gures ont été faites avec PGF/TikZ. Le code comporte environ
2.500.000 signes.
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
J. K. Toole
P. Struillou
The Richard Feynman
Problem-Solving Algorithm:
1. write down the problem;
2. think very hard;
3. write down the answer. Students identify computer science
with a computer driving license.
M. Gell-mann
J. Hromkovic
J. Erickson
2.3 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
6 PSEP 327
6.1 Les bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
6.1.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
6.1.2 L'algorithme générique PSEP . . . . . . . . . . . . . . . . . . . . . . 330
6.1.3 f? /f : un cas particulier intéressant . . . . . . . . . . . . . . . . . . . 333
6.1.4 Un exemple : le problème du voyageur de commerce . . . . . . . . . 334
TABLE DES MATIÈRES XIII
6.2 Ce qu'il faut retenir de la démarche PSEP . . . . . . . . . . . . . . . . . . . 340
6.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Notations 829
Liste des exercices 831
Bibliographie 835
Index 838
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Présentation
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Le sujet de cet ouvrage est l'algorithmique et son but est de l'enseigner. Selon nous, cette
discipline peut se dénir comme l'art et la science d'écrire un algorithme pour résoudre
un problème donné, de préférence en un temps minimal . Cet ouvrage vise par conséquent
à enseigner des méthodologies de conception d'algorithmes ecaces. Il cherche à le faire
essentiellement par l'exemple.
Il est construit selon une double règle.
Les chapitres couvrent un ensemble de méthodes qui s'appliquent à des structures
de données diverses. Par conséquent, à un chapitre correspond une méthodologie de
construction d'algorithme, non pas une structure de données. Par exemple, le cha-
pitre programmation dynamique comporte des problèmes résolus dans les tableaux,
d'autres dans les arbres, les graphes, les séquences, etc.
Un chapitre est le plus souvent constitué d'une présentation informelle par un exemple,
puis des bases techniques permettant d'écrire un algorithme selon cette méthode. En-
suite, au moins un problème complet est traité en détail. La suite du chapitre est
constituée de problèmes, énoncés et corrigés. Les problèmes un peu complexes sont
abordés de façon progressive an de mettre en évidence l'aspect constructif de la
solution proposée. Les corrigés sont détaillés an de rendre le plus explicite possible
les points clés du raisonnement suivi. L'exactitude des algorithmes a naturellement
été contrôlée par programmation. Nous ne fournissons pas les algorithmes codés
dans un langage particulier, mais écrits dans un pseudo-code spécié facilement
transposable en programme dans les langages usuels.
L'algorithmique est, avons-nous dit, l'art et la science d'écrire un algorithme. Nous souhai-
tons augmenter ces deux qualités chez le lecteur. Nous voudrions que, face à un nouveau
problème, il puisse développer, grâce aux exemples qu'il aura vus, une sorte d'intuition
de la méthode à employer (c'est le côté artiste, ou artisan). Mais nous désirons aussi qu'il
sache prouver que l'emploi de cette méthode est eectivement plus ecace que celui d'une
technique naïve (c'est le côté scientique). Enseigner par l'exemple ne veut pas dire sacri-
er la rigueur. Beaucoup de constructions d'algorithmes se font à partir de notions bien
XVI CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
que la preuve de la solution soit apparente. Cela donne parfois l'impression que cette solu-
tion sort du chapeau du magicien (c'est-à-dire de l'astuce du professeur) et encourage l'idée
exagérée qu'une bonne intuition peut remplacer une démonstration. Nous pensons que la
déduction et l'induction sont deux modes de raisonnement nécessaires dans la construction
d'un algorithme.
Ce livre est destiné à tous ceux qui, pour une raison ou pour une autre, sont concernés
par les sciences du numérique et veulent apprendre ou enseigner l'algorithmique. Il sera
évidemment utile aux élèves et aux étudiants en sciences du numérique, non pas comme
un ouvrage d'initiation, mais plutôt comme un manuel de référence destiné à accompagner
son lecteur non seulement pendant l'apprentissage, mais aussi dans sa vie professionnelle.
Nous pensons particulièrement aux élèves de terminale en spécialité ISN, ou dans certains
BTS, aux étudiants en IUT Informatique, Réseaux et Télécom, GEII, aux étudiants en
licence informatique ou à connotation informatique, aux élèves des classes préparatoires
scientiques et des écoles d'ingénieurs.
Ce livre est également destiné aux enseignants, qui trouveront au l des pages quantité de
matériel pour les cours et les séances d'exercices (sans parler des examens). Ils utiliseront
les introductions, les exercices et les corrections pour montrer à leurs apprenants comment
se modélise un problème et comment se construit rationnellement une solution. Enn, il
est aussi destiné, en dehors du système d'enseignement classique, à tous ceux qui veulent se
munir de connaissances solides sur une des bases de la science informatique : la construction
des algorithmes.
Plan
Comme nous l'avons dit, cet ouvrage a été organisé pour présenter successivement dié-
rentes méthodologies de construction d'algorithmes. Cependant, il commence par un cha-
pitre intitulé Mathématiques et informatique : notions utiles , dans lequel sont rappelées
un certain nombre de bases mathématiques (essentiellement les principes de démonstra-
tion, en particulier par récurrence) et de structures de données (ensembles, graphes, arbres,
les) et où une vingtaine d'exercices sont proposés. Le chapitre 2 Complexité d'un al-
gorithme , dans la même intention de consolider les connaissances de base, rappelle les
notions essentielles de ce domaine et donne quelques exercices.
Dans le chapitre 3, Spécication, invariants, itération sont exposés les principes de la
construction rationnelle de boucle, accompagnés d'une quinzaine d'exercices dont quelques-
uns sont assez diciles. Le chapitre suivant, intitulé Diminuer pour résoudre, récursivité
traite de la construction d'algorithmes récursifs, illustrée par une petite dizaine d'exer-
cices. Il montre en particulier comment les méthodes de démonstration par récurrence
s'appliquent pour certier l'exactitude de procédures récursives résolvant un problème de
taille donnée n, en faisant appel à la résolution de problèmes identiques de taille (n − 1).
XVII
On aborde dans le chapitre 5 la méthodologie des Essais successifs . Les techniques
d'énumération récursives des solutions à un problème combinatoire sont décrites et des
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
patrons de programmes sont donnés. Les principes d'élagage de l'arbre des solutions
sont décrits, qui sont illustrés par une vingtaine d'exercices. Le chapitre suivant reste dans
le même sujet, mais traite les méthodes PSEP (Séparation et évaluation progressive, ou
branch and bound ) qui sont, elles, itératives. Quatre exercices sont donnés pour concrétiser
cette méthode.
Le chapitre 7 est consacré aux Algorithmes gloutons , qui cherchent à résoudre des
problèmes analogues à ceux des chapitres précédents, en n'eectuant aucun retour en
arrière ; il est important de faire la preuve qu'ils résolvent le problème posé. On y présente
donc les façons usuelles pour démontrer qu'un tel algorithme est exact. Une quinzaine
d'exercices sont proposés pour illustrer cette technique.
Dans le chapitre 8, on s'intéresse à une approche particulièrement féconde de conception
d'algorithmes : Diviser pour Régner . Une classication des algorithmes de ce type est
proposée et leur construction est illustrée par une trentaine d'exercices, dont certains sont
diciles.
Enn, le chapitre 9 décrit la méthodologie de Programmation dynamique qui est éga-
lement très féconde pour construire une solution optimale à un problème combinatoire. La
richesse de cette technique est telle que nous proposons plus d'une trentaine d'exercices,
donnant lieu à une grande variété de constructions algorithmiques dont plusieurs ont un
intérêt pratique avéré. Là aussi, certains problèmes proposés sont diciles.
Nous avons essayé de choisir des exercices couvrant autant que possible la variété de chaque
domaine abordé. Nous avons aussi cherché à ne pas proposer deux problèmes trop proches,
tout en illustrant sur quelques problèmes l'applicabilité de plusieurs méthodologies. Au
total, cet ouvrage traite près de cent cinquante exercices : pour chacun l'énoncé a été
rédigé avec autant de précision que possible et les questions sont organisées pour aider le
lecteur à construire la solution. Le corrigé, quant à lui se veut méthodique, rigoureux et
complet.
Conventions de lecture
On trouvera dans la section Notations , page 829 les conventions que nous utilisons
pour les formules mathématiques et surtout pour les algorithmes. Il sera évidemment
indispensable au lecteur de s'y référer en cas de doute sur la signication de tel ou tel
symbole.
Tout au long de l'énoncé et du corrigé de chaque exercice, une note marginale rappelle les
numéros de l'exercice et de la question en cours. La note ci-contre indique par exemple que 42 - Q 3
l'on commence la question 3 de l'exercice 42. Sa réponse est signalée par la même note,
avec R à la place de Q.
Chaque exercice est doublement coté, pour son intérêt intrinsèque et pour sa diculté.
◦ ◦
◦
Il y a quatre niveaux croissants d'intérêt notés ◦ ◦
◦ ◦
◦ ◦
◦ et quatre niveaux
• •
•
croissants de diculté notés • •
• •
• •
• . La notion d'intérêt d'un problème est
assez subjective. Nous avons opté pour un croisement de divers critères, dont le principal
est la qualité avec laquelle ce problème illustre la méthodologie à laquelle il appartient.
Pour la diculté, la cotation tient naturellement compte de la façon dont l'enoncé a été
rédigé : un problème intrinsèquement dicile peut être adouci par une série de questions
préparatoires graduées.
XVIII CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
Autrement dit, nous ne renvoyons jamais aux articles originaux où ont été publiés (s'il l'ont
été) les algorithmes que nous présentons ici. C'est en eet le rôle d'un livre complet sur
le sujet que de citer exhaustivement ses sources, plutôt que celui d'un livre d'exercices.
Nous renvoyons donc aux livres de la bibliographie les lecteurs soucieux de connaître
l'historique des algorithmes présentés. De ce point de vue, les ouvrages de D. Knuth [44],
de G. Brassard et P. Bratley [15], de T. Cormen et al. [17] et de E. Horowitz et al. [39]
sont particulièrement conseillés.
Aucun des algorithmes présentés ici ne se veut original. Pour l'essentiel, les sujets des
exercices proviennent des livres de la bibliographie que nous présentons ci-après. Ils ont
été soigneusement réécrits à des ns pédagogiques. Les autres ont pour origine des sources
variées, en particulier le patrimoine commun des cours et travaux dirigés enseignés à l'Uni-
versité de Rennes 1 et à l'ENSSAT de Lannion. Notre originalité n'est pas dans la création
de nouveaux problèmes. En revanche, elle réside dans la construction de l'énoncé des exer-
cices et dans la rigueur de l'élaboration et de la description des solutions.
Dans son excellent petit livre d'exercices, I. Parberry [55] donne son jugement sur une
trentaine de livres d'enseignement d'algorithmique. Nous y renvoyons volontiers le lecteur
pour qu'il se fasse un avis sur la bibliographie de langue anglaise datant d'avant 1995. Pour
notre part, outre les inégalables ouvrages de T. Cormen et al. [17] et de D. Knuth [44],
nous avons une préférence pour les livres écrits par U. Manber [48], par D. Gries [33], et
plus récemment par J. Kleinberg et E. Tardos [43] et par J. Edmonds [27]. Les livres de
R. Johnsonbaugh et M. Shaeer [40], de E. Horowitz et al. [39], de S. Baase et A. Van Gel-
der [8], de R. Neapolitan et K. Naimipour [54], de A. Levitin [46] et de T. Goodrich and
R. Tamassia [30] sont également des ouvrages récents à recommander.
La bibliographie en langue française sur l'algorithmique est plus mince. La référence (sur-
tout pour les structures de données, moins pour l'algorithmique proprement dite) a long-
temps été, à juste titre, l'ouvrage de C. Froidevaux et al. [28]. La traduction française
du livre déjà cité de T. Cormen et al. [17] peut désormais lui être préférée. D'autres tra-
duction ont été proposées, comme celles des ouvrages de R. Sedgewick [58]. Les livres
de M. Quercia [56], de J.-M. Léry [47] et de J. Courtin et I. Kowarsky [19] (ce dernier
est le plus complet) traitent plus de structures de données que d'algorithmique au sens
strict. Le livre d'exercices d'algorithmique de L. Bougé et al. [14] et celui de A. Darte
et S. Vaudenay [21] sont des recueils de problèmes du concours de l'ENS Lyon, toujours
intéressants mais elliptiques en ce qui concerne la construction des solutions. L'excellent
livre d'exercices et de problèmes d'algorithmique de B. Baynat et al. [9] est organisé par
structures de données, non pas par types d'algorithmes. Il donne des solutions détaillées
et des rappels de cours. Nous le conseillons bien volontiers, de même que le très bon ou-
vrage de J. Beauquier et al. [10], organisé selon le même principe et désormais disponible
gratuitement sur le Web. On trouve aussi en français de remarquables livres sur les algo-
rithmes dans les graphes (par exemple celui de M. Gondran et M. Minoux [29]), dans les
séquences (M. Crochemore [20]) et pour des problèmes d'algèbre et d'analyse (P. Naudin
et C. Quitté [53]).
Un ouvrage concis, mais de référence, sur la construction de programmes est celui de
P. Berlioux et Ph. Bizard [13]. Celui de J. Arsac [5] mérite aussi d'être lu avec attention.
Le livre récent de J. Julliand [41] est un excellent document d'introduction aux méthodes
formelles de conception de programmes.
CHAPITRE 1
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Mathématiques et informatique :
quelques notions utiles
Who can does; who cannot do,
teaches; who cannot teach, teaches
teachers.
Paul Erd®s
Tout au long de cet ouvrage, nous nous plaçons dans le cadre d'un développement progressif
des algorithmes dans lequel chaque étape repose sur une construction saine. À cet eet,
ce chapitre présente une variété d'outils permettant d'assurer la validité des constructions
utilisées. Par ailleurs, au cours de cette démarche de développement, une première version
d'un programme fait souvent appel, d'une part à des conditions exprimées dans le langage
des prédicats, et d'autre part à des structures de données spéciées dans le langage de la
théorie des ensembles. Cette démarche est cependant insusante lorsque l'on cherche à
obtenir une solution ecace (notamment sur le plan de la complexité temporelle voir
chapitre 2). Il faut alors procéder à un ranement sur la base de structures de données
taillées sur mesure. C'est pourquoi cette introduction est consacrée à divers objets et outils
mathématiques, ainsi qu'aux principales structures de données utilisées ultérieurement.
Ce chapitre débute par des notions relatives aux raisonnements conduits fréquemment
par la suite : i) le calcul propositionnel et le calcul des prédicats, ii) la démonstration
par l'absurde, et enn iii) la démonstration par récurrence, outil central des chapitres 4
et 8. Nous abordons ensuite les relations de récurrence et leur calcul, qui occupent une
place privilégiée dans le chapitre 9. Nous en protons pour donner notre acception des
termes récurrence, induction et récursivité. La suite du chapitre s'articule principalement
autour de la notion d'ensemble, et nous passons en revue les concepts de produit cartésien,
de sac (multiensemble), de relation et de fonction ainsi que les principaux opérateurs s'y
rattachant. Nous nous intéressons aux listes vues comme une illustration de la notion de
structure inductive dénie à partir de celle de produit cartésien. Nous nous arrêtons plus
longuement sur les notions de graphe et d'arbre qui sont à l'origine de nombreux exercices,
avant d'achever ce chapitre en présentant la notion de le de priorité dont l'intérêt se
manifeste principalement à travers les chapitres 6 et 7, consacrés respectivement à la
démarche PSEP et aux algorithmes gloutons.
Pour le lecteur intéressé, une construction rigoureuse de la logique classique et de la théo-
rie des ensembles peut être trouvée dans [1]. Pour ce qui concerne la problématique du
ranement formel de structures de données, on peut consulter avec prot [36].
2 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
L'ensemble prédéni B est déni par B =b {vrai, faux}. Ces deux valeurs seront parfois
représentées par V/F ou v/f dans des tableaux pour des raisons de place. Si a et b sont
des éléments de B, alors :
a et b vaut vrai si et seulement si a et b valent tous les deux vrai.
a ou b vaut faux si et seulement si a et b valent tous les deux faux.
non a vaut vrai si et seulement si a vaut faux.
a ⇒ b vaut faux si et seulement si non a et b valent tous les deux
faux.
a ⇔ b est un opérateur logique qui vaut vrai si et seulement si a ⇒ b
et b ⇒ a.
a = b signie que l'expression a possède la même valeur que l'expres-
sion b et qu'elles peuvent se substituer l'une à l'autre.
L'existence d'expressions indénies (par exemple pour cause d'accès en dehors du domaine
d'une fonction, ou pour cause de division par 0) exige d'utiliser des opérateurs dits courts-
circuits qui arrêtent l'évaluation dès que le résultat est acquis. Les deux opérateurs
courts-circuits et alors et ou sinon se dénissent de la manière suivante :
Si a et b sont dénis :
a et alors b ⇔ a et b.
a ou sinon b ⇔ a ou b.
Si a est déni mais pas b :
faux et alors b ⇔ faux.
vrai et alors b n'est pas déni.
faux ou sinon b n'est pas déni.
vrai ou sinon b ⇔ vrai.
Si a n'est pas déni, alors, quel que soit b :
a et alors b n'est pas déni.
a ou sinon b n'est pas déni.
Les quanticateurs ∀ et ∃ du calcul des prédicats se dénissent par :
∀x · (D ⇒ T (x)) vaut vrai si et seulement si, pour tout x appartenant
au domaine D alors T (x) vaut vrai. La formule vaut donc vrai si D est
vide.
∃x · (D et T (x)) vaut vrai si et seulement s'il existe un x appartenant
au domaine D tel que T (x) vaut vrai. La formule vaut donc faux si D est
vide.
La notation @ est une abréviation pour non ∃. La double égalité :
(a ⇒ b) = (non a ou b) = (non b ⇒ non a)
Le raisonnement par l'absurde ou démonstration par l'absurde (en anglais proof by contra-
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
le tiers exclu, qui arme qu'une propriété qui n'est pas fausse est for-
cément vraie, donc que la conjonction d'une propriété et de sa négation
prend la valeur logique faux,
b (non P
la dénition de l'implication : (P ⇒ Q) = ou Q).
Ces deux propriétés ont en particulier pour conséquence que (non P ⇒ faux) est équivalent
à P, ce qui valide le raisonnement par l'absurde. En eet :
(non P ⇒ faux)
⇔ dénition de l'implication
(non(non P) ou faux)
⇔ involutivité de la négation
(P ou faux)
⇔ propriété de la disjonction
P.
Il est à noter que si l'on ne parvient pas à une contradiction, on ne peut rien conclure
quant à P.
Second exemple On veut montrer qu'il n'existe pas de rationnel positif dont le carré
est 2, autrement dit prouver la proposition P s'énonçant la racine carrée de 2 est irra-
tionnelle .
2
p
=2
q
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
⇔ arithmétique
p2 = 2q2
⇔ reformulation
2 divise p2
⇔ tout carré pair est celui d'un nombre pair
2 divise p
⇔ p = 2p0
∃p0 · (p2 = 4p02 = 2q2 )
⇔ reformulation
2 divise q2
⇔ tout carré pair est celui d'un nombre pair
2 divise q.
On en déduit que 2 divise à la fois p et q, donc que p et q ne sont pas premiers entre eux,
ce qui contredit le fait que p/q est une fraction irréductible.
De façon analogue, on peut montrer qu'il n'existe pas de rationnel négatif dont le carré
est 2, sinon l'opposé de ce nombre serait un rationnel positif dont le carré serait 2. Par
conséquent, la racine carrée de 2 est irrationnelle 1 .
Nous abordons dans cette section un autre type de preuve, à savoir la démonstration par
récurrence ou par induction à un indice. Nous en déclinons successivement les variantes
les plus usuelles, en particulier celles qui sont utilisées dans les chapitres 4 et 8.
On appelle hypothèse de récurrence le fait de supposer vraie P(n), pour (essayer de) dé-
montrer P(n + 1). La base s'appelle aussi l'initialisation et l'étape de récurrence est aussi
appelée induction.
et, comme m est le plus petit élément de X, m − 1 6∈ X et P(m − 1) est vraie. En utilisant
l'étape de récurrence, on déduit que P(m) est vraie, ce qui est contradictoire avec m ∈ X.
Par conséquent, X est vide.
X
1
i=1
i=1
X
n+1
i
i=1
= arithmétique
X
n
!
i + (n + 1)
i=1
= hypothèse de récurrence
n(n + 1)
+ (n + 1)
2
= arithmétique
(n + 1)(n + 2)
.
2
Conclusion La formule est vraie pour n0 = 1. De plus, si elle est vraie pour n (avec
n > 1), alors elle est vraie pour (n + 1). Par conséquent, cette démonstration par
récurrence a prouvé que la formule est vraie pour tout entier strictement positif.
6 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
alors :
Cette variante concerne une proposition sur les entiers qui sont des puissances de 2. On
peut aussi démontrer une propriété sur les nombres pairs, ou d'une manière générale sur
tout sous-ensemble inni de N constructible par induction (voir la section 1.3, page 15).
alors :
Une forme importante de raisonnement par récurrence est l'induction de partition (aussi
appelée induction DpR compte tenu de son importance dans la technique de conception
d'algorithmes appelée Diviser pour Régner que nous étudierons au chapitre 8).
On considère un prédicat P(i, s) dépendant des entiers naturels i et s tels que i 6 s.
L'induction de partition consiste à prouver la validité de P sur tout intervalle I = i .. s :
1) en l'établissant en tout point de I, et 2) en montrant que la validité de P sur chacun des
intervalles I1 = i..m et I2 = m+1..s (partition de I voir dans ce chapitre la section 1.4.3,
page 18) entraîne celle de P sur I.
Démonstration. On procède à une preuve par l'absurde. Soit F l'ensemble des couples qui
ne satisfont pas le prédicat P, soit :
Remarque 1 L'induction de partition doit impérativement se fonder sur une base P(i, s)
pour laquelle s−i+1 = 1. En particulier, elle ne peut s'appuyer sur une base où s−i+1 = 0.
En eet, dans ce cas, il n'existe pas de valeur m telle que i 6 m < s. De même, l'induction
ne peut se fonder sur une base P(i, s) telle que s − i + 1 > 1. Prenons l'exemple de P(i, i + 1)
pour base et tentons de démontrer P(i, i + 2). Les deux valeurs possibles pour m sont
m = i et m = i + 1. Si m = i, la première hypothèse d'induction est P(i, i) et si m = i + 1,
la seconde hypothèse d'induction est P(i + 2, i + 2). Aucun de ces prédicats n'étant une
instance de la base, le schéma associé est invalide.
X
n
n · (n + 1)
k=
k=1
2
P
mais cette fois en utilisant le principe de l'induction de partition. Posons S(i, s) = sk=i k et
appelons P(i, s) le prédicat S(i, s) = (s2 −i2 +s+i)/2. Si nous parvenons à démontrerPP(i, s),
on aura en particulier P(1, n) et on pourra en conclure que S(1, n) = (n2 + n)/2 = n k=1 k.
P
Base Pour tout i, on a : S(i, i) = (i2 − i2 + i + i)/2 = i = k=i k.
i
S(i, s)
= dénition
X
s
k
k=i
= arithmétique (i < s), avec m = b(i + s)/2c
X
m X
s
k+ k
k=i k=m+1
= dénition
S (i, m) + S (m + 1, s)
= hypothèses d'induction
m2 − i2 + m + i s2 − (m + 1)2 + s + m + 1
+
2 2
= arithmétique
s 2 − i2 + s + i
2
X
s
s 2 − i2 + s + i
Conclusion k= .
k=i
2
Remarque 1 L'un des artices utilisés dans l'exemple ci-dessus consiste à remplacer
une constante (1 dans la borne inférieure de la quantication) par une variable (i). Cette
technique sera rencontrée dans la construction des itérations, dans le cadre du renforce-
ment par introduction de variables (voir section 3.3.3, page 104) consistant à démontrer
plus que nécessaire an (en général) de faciliter la démonstration.
Dans les paragraphes précédents, nous avons vu quelques cas de démonstration par récur-
rence, tous fondés sur l'ordre naturel des nombres entiers. Il est intéressant et très utile de
généraliser ce type de démonstration à des propriétés non plus caractérisées par un nombre
entier, mais par un élément d'un ensemble totalement ordonné.
La démonstration par récurrence (plus souvent appelée dans ce cas par induction ) provient
de la propriété suivante.
alors ∀x · (x ∈ E ⇒ P(x)).
alors :
La validité de ce schéma provient du fait que l'ensemble N2 des couples d'entiers est muni
d'un ordre total (induit par l'ordre naturel sur N), déni de la manière suivante :
(a, b) (c, d) =
b a<c ou (a = c et b 6 d).
Considérons le point q de coordonnées (i, j). Le schéma proposé ci-dessus vise à établir
que si P est satisfaite en tout point : i) du rectangle 0 .. i − 1, 0 .. j − 1 (les cas i = 0 ou
j = 0 sont couverts par la base), ii) de (i, 0) à (i, j − 1) de la ligne i, et iii) (0, j) à (i − 1, j)
de la colonne j, alors P est également satisfaite au point (i, j). En d'autres termes, si P est
vériée en tout point inférieur (au sens de l'ordre ) au point (i, j), P(i, j) est également
vraie, ce qui correspond à l'instance de la proposition 1.1.5 pour le couple (N2 , ).
Ce schéma de démonstration est utilisé dans l'exercice 21, page 48. Il peut être transposé
à N1 si besoin avec la base portant sur N1 , la récurrence sur N1 − {1} et la conclusion étant
alors :
∀(m, n) · ((m ∈ N1 et n ∈ N1 ) ⇒ P(m, n)).
10 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
D'autres schémas sont applicables pour démontrer une récurrence à deux indices (ou plus).
Leur validité est assurée pour autant qu'ils se conforment à la propriété 1.1.5 pour un
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Par dénition, une suite S(n), avec n ∈ N, est dénie par une relation de récurrence si l'on
a, pour n assez grand, une relation du type : S(n) = f(S(n − 1), . . . , S(n − p)). De plus, il
faut connaître des valeurs permettant d'initialiser le calcul de S. Nous ne considérons ici
que les suites dont les valeurs sont des nombres entiers positifs ou nuls (notamment parce
que ces suites sont associées à des calculs de complexité).
Dans la relation de récurrence dénissant la suite de Fibonacci :
F(1) = 1
F(2) = 1
F(n) = F(n − 1) + F(n − 2) n>2
P(1) = 1
P(2) = 1
P(3) = 1
P(n) = P(n − 2) + P(n − 3) n>3
la fonction f est linéaire. En revanche, celle qui apparaît dans la relation dénissant les
factorielles (nombre de permutations d'un ensemble à n éléments) ne l'est pas :
Fact(1) = 1
Fact(n) = n · Fact(n − 1) n > 1.
Les mathématiques fournissent, grâce à la théorie des fonctions génératrices (voir par
exemple [31]), de puissants moyens pour trouver des formes closes (c'est-à-dire non récur-
rentes) à certaines suites dénies par des relations de récurrence, en particulier si f est
linéaire, mais dans bien d'autres cas aussi. Ainsi, la suite de Fibonacci s'exprime sous la
forme close :
" √ !n √ !n #
1 1+ 5 1− 5
F(n) = √ − n > 1.
5 2 2
La suite des nombres de Catalan, dont nous reparlerons dans les exercices 5, page 37, et 13,
page 42, est dénie par la récurrence :
CHAPITRE 1. MATHÉMATIQUES ET INFORMATIQUE : NOTIONS UTILES 11
Cat(1) = 1
X
n−1
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
et aussi par :
Cat(1) = 1
4n − 6
Cat(n) = · Cat(n − 1) n > 1.
n
(2n − 2)! 1
Cat(n) = = · Cn−1
2n−2 n > 1.
(n − 1)! · n! n
D'un point de vue algorithmique, la forme close apparaît attractive puisque simple à
calculer. Cependant, si ce choix est raisonnable pour le calcul du ne nombre de Catalan,
il peut ne pas être approprié, comme le montre l'exercice 12, page 41, à propos du calcul
des nombres de Fibonacci.
Une relation de récurrence peut servir de dénition à une suite dénie sur plus d'un indice
entier. Par exemple, les nombres d'Ackerman sont dénis par la récurrence imbriquée à
deux indices :
A(0, n) = n + 1 n>0
A(m, 0) = A(m − 1, 1) m>0
A(m, n) = A(m − 1, A(m, n − 1)) m>0 et n > 0.
Un autre exemple de relation de récurrence à deux indices est celui des nombres de Stirling,
qui se dénissent comme le nombre de partitions à p blocs d'un ensemble ayant n éléments.
Ils se construisent par une récurrence beaucoup plus simple que la précédente, et ils sont
étudiés à l'exercice 16, page 44.
Principes
Nous nous intéressons maintenant à l'établissement et au calcul de suites dénies par une
(relation de) récurrence. Il s'avère que de nombreux problèmes, liés au dénombrement
par exemple, mais aussi au calcul de valeur optimale d'une fonction (voir chapitre 9),
se résolvent en mettant en évidence une récurrence permettant le calcul de la grandeur
voulue. Il importe que la récurrence soit complète, c'est-à-dire que toutes les situations
pouvant survenir soient prises en compte.
D'un point de vue algorithmique, comme il est fréquent que l'on ne connaisse pas de forme
close, on procède au calcul en construisant un programme itératif dans lequel un tableau à
une ou deux dimensions (voire plus) stocke la succession des valeurs de la suite calculées.
Cette approche sera discutée et justiée au chapitre 4.
2. On admet que les formes closes peuvent contenir tout type de quanticateur, ici le produit sous-
tendant le calcul des factorielles.
12 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
Le principe retenu consiste à calculer la valeur d'une cellule à partir de celles déjà pré-
sentes dans le tableau. L'ordre de remplissage est donc primordial et la progression du
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
calcul dépend des relations de dépendance entre éléments. Si pour les récurrences à une
seule dimension l'aaire est généralement simple (progression selon l'ordre croissant ou dé-
croissant des valeurs de l'indice), une récurrence à plusieurs indices mérite plus d'attention.
Les exemples qui suivent illustrent la démarche proposée.
Quelques exemples
Récurrence à un indice : arbres binaires à n n÷uds On veut calculer le nombre
nbab(n) d'arbres binaires (voir section 1.6, page 29) ayant n n÷uds (feuilles comprises).
On va d'abord établir la récurrence dénissant ce nombre. On remarque qu'il y a un seul
arbre binaire n'ayant aucun élément : l'arbre vide. Pour établir une récurrence sur nbab(n),
on considère la décomposition d'un arbre binaire à n n÷uds en arbres plus petits. Pour
n positif, un arbre à n n÷uds est constitué d'une racine (un n÷ud), éventuellement d'un
sous-arbre gauche ayant i n÷uds, et éventuellement d'un sous-arbre droit ayant (n − i − 1)
n÷uds. Examinons le nombre de façons possibles de faire la décomposition :
on peut placer zéro n÷ud à gauche (sous-arbre vide), ce qui fait
nbab(0)(= 1) façon, et (n − 1) n÷uds dans le sous-arbre droit, avec par
dénition nbab(n−1) possibilités, ce qui fait au total nbab(0)·nbab(n−1)
cas,
on peut placer un n÷ud à gauche et (n − 2) n÷uds à droite, ce qui fait
nbab(1) · nbab(n − 2) cas,
...
Plus généralement, on place i n÷uds à gauche, d'où nbab(i) sous-arbres gauches, et
(n − i − 1) n÷uds à droite, d'où nbab(n − i − 1) sous-arbres droits, ce qui fait au total
nbab(i) · nbab(n − i − 1) arbres de cette sorte. Cela vaut pour toutes les valeurs de i de 0
à (n − 1). Finalement, le nombre d'arbres ayant n n÷uds est :
nbab(n) = nbab(0) · nbab(n − 1) + nbab(1) · nbab(n − 2) + · · ·
· · · + nbab(i) · nbab(n − i − 1) + · · ·
· · · + nbab(n − 1) · nbab(0)
et on en déduit la récurrence :
nbab(0) = 1
X
n−1
nbab(n) = nbab(i) · nbab(n − i − 1) n > 1.
i=0
Après avoir vérié par énumération que nbab(1) = 1 et que nbab(2) = 2, la valeur suivante
est :
X
2
nbab(3) = nbab(i) · nbab(n − i − 1)
i=0
= nbab(0) · nbab(2) + nbab(1) · nbab(1) + nbab(2) · nbab(0)
= 2 + 1 + 2 = 5.
CHAPITRE 1. MATHÉMATIQUES ET INFORMATIQUE : NOTIONS UTILES 13
La gure 1.1 met en évidence les arbres binaires pour n ∈ 0 .. 3.
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
• • •
• •
• • • • •
• • • • • •
• • • •
On va donc procéder de façon itérative, mais sans stocker les valeurs calculées, d'où le
programme :
14 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
1. constantes
2. n ∈ N1 et n = ...
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
3. variables
4. Facto ∈ N1
5. début
6. Facto ← 1 ;
7. pour i parcourant 2 .. n faire
8. Facto ← Facto · i
9. n pour ;
10. écrire(pour n = , n, la valeur de n ! est , Facto)
11. n
nbdel(0, j) = 1 06j6m
nbdel(i, 0) =
1 16i6n
16i6n
nbdel(i, j − 1) +
nbdel(i, j) = nbdel(i − 1, j) +
et
nbdel(i − 1, j − 1) 16j6m
Pour calculer nbdel(n, m) avec m et n deux entiers donnés, on associe à nbdel un tableau
NBD[0 .. n, 0 .. m]. On observe que, dans le cas général, pour calculer l'élément NBD[i, j],
il faut connaître : i) la valeur de la cellule de même indice de ligne et d'indice de colonne
immédiatement inférieur, ii) la valeur de la cellule de même indice de colonne et d'indice
de ligne immédiatement inférieur, et iii) la valeur de la cellule d'indices ligne et colonne
immédiatement inférieurs. On peut donc remplir NBD par ligne (mais aussi par colonne
ou par diagonale). Après avoir initialisé la ligne 0 à 1 (premier terme de la récurrence), on
remplit les lignes par valeurs croissantes de l'indice i (jusqu'à n) : la cellule (i, 0) est mise
à 1 (second terme de la récurrence), puis on remplit les cellules (i, 1) à (i, m) en utilisant
le dernier terme de la récurrence.
d'être vigilant sur la représentation des nombres, surtout en présence d'une récurrence
dont les valeurs croissent extrêmement rapidement. Il peut être prudent de travailler en
représentation ottante plutôt qu'avec des entiers. Par exemple, les nombres d'Ackerman
2
..
sont tels que A(3, n) = 2n+3 −3 et A(4, n) = 22 −3 (n+3 occurrences de 2), et ce nombre
2
22
devient très vite gigantesque (A(4, 2) = 2 − 3 = 216 − 3 = 265536 − 3). Enn, la relation
de dépendance liant partie gauche et partie droite peut être non triviale. Nous renvoyons
ici aussi le lecteur aux nombres d'Ackerman avec le calcul de A(6, 1) = A(5, 65533).
Nous avons vu aux sections précédentes ce que sont une démonstration par récurrence
(aussi appelée démonstration par induction) et une suite dénie par une relation de récur-
rence. Dans cette section, nous allons essayer d'éclaircir une terminologie souvent perçue
de manière un peu confuse.
Programme récursif
En informatique, un algorithme (comme un programme qui le code) est dit récursif s'il
s'appelle lui-même directement ou par l'intermédiaire d'autres programmes. La fonction
Fact de la page 16 illustre la notion d'algorithme récursif, de même que de nombreux
programmes des chapitres 4 et 8.
La mise en ÷uvre canonique d'une récurrence est un algorithme récursif. Cependant,
comme on le verra au chapitre 4, on préférera très souvent, pour des raisons d'ecacité,
une version itérative remplissant une structure tabulaire (comme cela a été le cas dans
les exemples précédents). Ceci ne doit pas être confondu avec le fait qu'un programme
récursif peut être transformé (de façon automatique avec gestion explicite d'une pile) en
un programme itératif, qui lui, aura le même comportement (en particulier les mêmes per-
formances) que le programme récursif initial. Il existe malgré tout un type d'algorithme
récursif pouvant être transformé avec intérêt en un algorithme itératif : lorsque la récur-
sivité est dite terminale . Nous allons développer cette notion dans le cadre des fonctions,
mais ce qui est dit se transpose aux procédures. Une fonction est (directement) récursive
terminale si elle obéit au schéma suivant :
1. fonction F(. . .) résultat ... pré
2. ...
3. début
4. si C alors
16 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
5. résultat V
6. sinon
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
7. résultat F(. . .)
8. n si
9. n
Il est alors possible d'obtenir un programme itératif (dont l'exécution est plus ecace), ce
qu'un compilateur évolué sait faire.
Exemple La fonction :
1.4 Ensembles
Un couple est constitué de deux expressions séparées par une virgule ou par le symbole 7→.
La formule x, y + 3 est un couple, qui peut également se noter x 7→ y + 3, ou encore
(x, y + 3) (toute expression peut être parenthésée). Dans cette notation, le premier élément
est appelé l'origine et le second l'extrémité.
CHAPITRE 1. MATHÉMATIQUES ET INFORMATIQUE : NOTIONS UTILES 17
C=b (x, y + 3) attribue le nom C à l'objet (x, y + 3).
Les opérateurs relationnels = et 6=, avec leur sens habituel, sont supposés toujours dispo-
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Soit E un ensemble, x ∈ E est une expression booléenne qui établit que x est un élément
de l'ensemble E. Sa négation se note ∈ /.
L'ensemble qui ne contient aucun élément (l'ensemble vide) se note ∅.
Soit E et F deux ensembles. L'expression E × F, produit cartésien de E et de F, se dénit
par l'équivalence (a, b) ∈ E × F ≡ (a ∈ E et b ∈ F).
Un ensemble se dénit par les propriétés de ses éléments. C'est la dénition en compréhen-
sion ou en intension. Elle se note {x | x ∈ E et P}, où E est un ensemble et P un prédicat
de sélection, et dénit l'ensemble des éléments de E possédant la propriété P. Ainsi
{x | x ∈ N et @ · (y ∈ N et x = 2 · y)}
E × F = {(x, y) | x ∈ E et y ∈ F}
Par exemple, l'ensemble P des nombres pairs peut se dénir comme le plus petit sous-
ensemble de N satisfaisant l'équation P = {0} ∪ {n | n ∈ N et n − 2 ∈ P ⇒ n ∈ P}.
Nous verrons dans la suite de cet ouvrage plusieurs exemples d'ensembles dénis de façon
inductive, en particulier les arbres. Très souvent, les propriétés de tels ensembles sont
prouvées par un raisonnement par induction.
Si E est un ensemble, P(E) représente l'ensemble des parties de E et se dénit par :
x ∈ P(E) ⇔ ∀y · (y ∈ x ⇒ y ∈ E).
Ainsi, si E =
b {1, 2, 3}, P(E) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}}.
18 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
Outre l'ensemble B déjà déni, les ensembles numériques suivants sont supposés connus :
N (entiers naturels), Z (entiers relatifs), R (réels numériques, c'est-à-dire réels discrétisés
en représentation informatique), C (nombres complexes).
Certains sous-ensembles des ensembles ci-dessus se notent de manière particulière. Il s'agit
de N1 (qui représente N − {0}), R+ (qui représente les éléments de R positifs ou nuls),
R∗+ (qui représente les éléments de R strictement positifs).
Pour ce qui concerne les complexes, i est la constante telle que i2 = −1. Si c est un
complexe, sa partie réelle se note re(c) et sa partie imaginaire im(c). Ainsi, pour c = b 1 − 2i,
on a re(c) = 1 et im(c) = −2.
Si E est un ensemble numérique totalement ordonné, l'opérateur min(E) (resp. max(E))
désigne le plus petit (resp. le plus grand) élément de E. Si E est vide min(E) = ∞ et
max(E) = −∞.
Les intervalles de Z se notent exp1 .. exp2 . Si exp2 < exp1 l'intervalle dénote l'ensemble
vide. Dans la mesure où Z est un ensemble ordonné, on peut assimiler un intervalle à une
liste (voir section 1.4.7, page 20). De même pour une expression telle que exp1 .. exp2 − (F).
Cette particularité est utilisée dans les boucles pour avec l'option parcourant où, par
exemple, le domaine de variation de la variable de la boucle 1 .. 5 − {3, 4} correspond à
l'ensemble {1, 2, 5} et est parcouru dans cet ordre lors de l'exécution de la boucle.
Relations
Soit E et F des ensembles et R ⊆ E × F. R est appelé relation (binaire) entre la source E
et la destination F. Si F = E, le couple (E, R) est appelé graphe (voir section 1.5, page 22).
Les fonctions sont des relations binaires particulières, et les tableaux sont des fonctions
particulières. Les notions dénies pour les relations s'appliquent donc naturellement à ces
deux dernières notions.
Soit R une relation binaire entre E et F. La relation inverse (ou réciproque) de R se note R−1
et se dénit par :
R−1 =b {(b, a) | (b, a) ∈ F × E et (a, b) ∈ R}.
Soit R une relation entre E et F. Le domaine de R se note dom(R) et se dénit comme
le sous-ensemble de E dont les éléments constituent l'origine d'au moins l'un des couples
de R. Plus formellement :
dom(R) =
b {a | a ∈ E et ∃b · (b ∈ F et (a, b) ∈ R)}.
CHAPITRE 1. MATHÉMATIQUES ET INFORMATIQUE : NOTIONS UTILES 19
domaine de R−1 . C'est aussi le sous-ensemble de F dont les éléments constituent l'extrémité
d'au moins l'un des couples de R.
Soit E un ensemble, la relation identité sur E se note id(E) et se dénit par :
id(E) =
b {(a, b) | (a, b) ∈ E × E et a = b}.
Soit S une relation entre F et G, et R une relation entre E et F. La relation R ◦ S est appelée
composition de R et de S. Elle se dénit par :
b {(a, c) | (a, c) ∈ E × G
R◦S= et ∃b · (b ∈ F et (a, b) ∈ R et (b, c) ∈ S)}.
Fonctions
Une fonction f de E dans F est une relation dans laquelle il n'existe pas deux couples (a, b)
et (a, c) tels que b 6= c. On note f ∈ E → F. Dans la suite, il sera souvent nécessaire de
distinguer diérents types de fonctions. Soit f ∈ E → F.
1. Si f est une fonction partielle, il peut exister des éléments de E qui ne sont l'origine
d'aucun couple de f.
2. Si f est une fonction totale, tout élément de E est l'origine d'un (et d'un seul) couple
de f.
3. Si f est une fonction injective , tout élément de F est l'extrémité d'au plus un couple
de f.
4. Si f est une fonction surjective , tout élément de F est l'extrémité d'au moins un
couple de f.
5. Si f est une fonction bijective , f est à la fois injective et surjective.
Notons qu'une fonction totale est aussi une fonction partielle. La gure 1.2, page 19, montre
les relations d'inclusion qui existent entre les diérents types de fonction.
Dans la suite, un prédicat tel que f ∈ E → F et T I(f) doit se comprendre comme
f est une fonction totale injective de E dans F .
T : Totale
PI T PS P : Partielle
I : Injective
S : Surjective
TI TS B : Bijective
TB
Fig. 1.2 Diagramme d'inclusion des diérents types de fonction. A → B signie que les
fonctions du type A sont incluses au sens large dans les fonctions du type B. D'après [1].
20 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
Tableaux
Un tableau t est une fonction totale d'un intervalle i .. s dans un ensemble F. On note
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
1.4.6 Sacs
Les structures inductives, c'est-à-dire les structures dénies par induction (voir page 17),
jouent un rôle important comme structures de données dans l'ensemble de l'ouvrage. Les
deux cas les plus typiques sont les listes nies et les arbres nis. Ces derniers sont traités à
la section 1.6, page 29. Nous nous limitons ici à présenter les listes nies. Quel sens doit-on
attribuer à une formule telle que :
d'une telle liste. En principe, il ne faut pas confondre une telle structure linguistique (qui
est une représentation externe des liste) avec les listes proprement dites. Dans la pratique,
nous nous autorisons cet abus de langage. Il est nécessaire d'ajouter que l'on ne s'intéresse
qu'aux structures nies et qu'une liste ainsi dénie est le plus petit ensemble satisfaisant
l'équation 1.1. Compte tenu de la convention portant sur l'utilisation de la notation pointée
(voir section 1.4.2, page 17), si l'on a l'aectation l ← (3, (1, (8, /))), on aura l.val = 3 et
l.svt = (1, (8, /)). Les listes ne permettent pas l'accès direct à leurs éléments, il faut toujours
passer par l'un des champs (l.svt.svt.val par exemple).
Dans la pratique, lorsque c'est possible, on s'autorise la notation plus concise h. . .i. Ainsi
(3, (1, (8, /))) peut également se noter h3, 1, 8i. L'opération de concaténation de listes est
notée ·.
Les chaînes (ou séquences, parfois mots ) sont des tableaux exibles à droite dont la borne
gauche est implicitement 1. Leurs éléments sont souvent appelés caractères. Ce sont donc
des fonctions totales pour lesquelles les opérateurs ensemblistes habituels sont disponibles
(dom, codom, etc.). La longueur de la chaîne c est notée |c|. L'opération de concaténation
(notée ·) permet d'allonger une chaîne en lui adjoignant une autre chaîne mais aussi un
caractère (qui est alors implicitement converti en chaîne). Si c = c[1] . . . c[n] dénote une
chaîne (séquence), c = c[n] . . . c[1] est la séquence miroir de c. D'un point de vue algorith-
mique, une chaîne c passée en paramètre d'entrée véhicule implicitement son domaine de
dénition (dom(c)). Si c est une chaîne dénie sur le domaine 1 .. n, la tranche c[i .. s] est
une chaîne dénie sur le domaine 1 .. s − i + 1 à condition que i .. s ⊆ 1 .. n. La chaîne vide ε
est dénie sur le domaine 1 .. 0. La déclaration d'une constante symbolique, d'une variable
ou d'un paramètre c de type chaîne se fait par c ∈ chaîne avec comme vocabulaire impli-
cite les lettres, chires et caractères spéciaux. Le recours à un vocabulaire spécique Σ est
réalisé par c ∈ chaîne(Σ). L'exemple suivant illustre l'utilisation des chaînes, en particulier
des constantes non délimitées par des guillemets pour lesquelles on fait usage d'une police
spéciale.
1. constantes
2. a =abcd /% constante symbolique de type chaîne %/
3. variables
4. b ∈ chaîne({a,b,c,d,1,2,3,4}) /% variable de type chaîne sur le vocabu-
laire Σ = {a,b,c,d,1,2,3,4} %/
5. début
6. écrire(Impair(a)) ; /% la fonction Impair(x) (voir code) délivre une chaîne
constituée des éléments d'indice impair de x %/
7. lire(b) ; écrire(Impair(b)) ;
8. b ← acbd · 1234 · a[3 .. 4] · a[1] ; /% exemple de concaténation %/
9. écrire(Impair(b))
10. n
1. fonction Impair(x) résultat chaîne pré
2. x ∈ chaîne et y ∈ chaîne
3. début
4. y ← ε ; /% y devient une chaîne vide %/
5. pour i parcourant dom(x) faire
22 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
i
6. si 2 · 6= i alors
2
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
1.5 Graphes
Intuitivement, un graphe est un ensemble de points dont certains peuvent être reliés deux à
deux. C'est donc une notion plutôt simple qui permet de modéliser de nombreux problèmes
présentant une grande utilité pratique, comme la recherche, par un appareil GPS, du
meilleur trajet pour rejoindre un lieu de vacances.
La théorie des graphes est aussi la source de plusieurs dés mathématiques et/ou infor-
matiques complexes comme celui du problème des quatre couleurs, dont la démonstration
complète et automatique a été réalisée par l'assistant de preuve Coq.
Plus simplement, pour nous, la notion de graphe est à l'origine de nombreux exercices
intéressants qui jalonnent cet ouvrage.
La théorie des graphes peut être vue comme une émanation de la théorie des ensembles
(à travers la notion de relation binaire). Mais, s'étant développées de manière séparée, les
deux théories utilisent des vocabulaires qui souvent divergent. Nous étudions tout d'abord
les graphes orientés, avant de nous arrêter sur les graphes non orientés. Le tour d'horizon
s'achève par le cas des graphes valués. Dans tous les cas, nous ne considérerons que des
graphes nis.
Les éléments de N sont appelés sommets ou n÷uds ; ceux de V sont appelés arcs. Le
cardinal de N est appelé ordre du graphe.
b
c
0 1 1 0 0 1
1 0 1 1 0 0
a d 0 0 0 0 1 0
0 0 0 1 0 1
e 1 0 0 0 0 1
f 0 0 1 0 0 0
(a) (b)
a× ×a
a • b • c • f /
b× ×b
b • a • c • d /
c× ×c c • e /
d× ×d d • d • f /
e • a • f /
e× ×e
f • c /
f× ×f
(c)
(d)
Fig. 1.3 Quatre représentations d'un graphe orienté. Le schéma (a) est la représenta-
tion sagittale classique, (b) est la représentation par la matrice d'adjacence, (c) est une
représentation bipartite, enn (d) est une représentation par listes des successeurs.
Dénition 3 (Demi-degré) :
Soit G un graphe et s un sommet de G. Le demi-degré extérieur (resp. intérieur) de s
dans G, noté d+ G (s) (resp. dG (s)), est le nombre d'arcs ayant pour origine (resp. pour
−
extrémité) le sommet s.
Exemple Dans l'exemple du graphe G de la gure 1.3, page 23, nous avons d+ G (d) = 2,
d−
G (d) = 2, SuccG (a) = {b, c, f} et PrédG (c) = {a, b, f}. On notera que l'arc (d, d) constitue
une boucle (sur le sommet d). Le graphe G1 = ({a, b, d, f}, {(a, b), (b, a), (a, f), (b, d),
(d, d), (d, f)}) est le graphe induit de G par l'ensemble de sommets {a, b, d, f}.
Dans le schéma (a) de la gure 1.4, page 26, le chemin hd, b, c, a, b, e, d, c, ei est eulérien.
Dans le graphe (b) de la gure 1.4, page 26, le chemin hd, b, c, a, b, e, d, c, e, f, di est un
circuit eulérien.
Autrement dit, G+ est la fermeture transitive de G si, lorsque dans G il existe un chemin
entre x et y, il existe un arc entre x et y dans G+ .
Dans le schéma ci-dessous, le graphe (b) représente la fermeture transitive du graphe (a).
Les arcs résultant de la fermeture apparaissent en pointillés.
26 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
a a
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
b c b c
d e d e
(a) (b)
Fig. 1.4 Deux graphes orientés. Le graphe (a) possède un chemin eulérien
(hd, b, c, a, b, e, d, c, ei) mais pas de circuit eulérien. Le graphe (b) possède au moins un
circuit eulérien (hd, b, c, a, b, e, d, c, e, f, di).
b b
a c a c
f d f d
e e
(a) (b)
Dans le schéma ci-dessous, le graphe (a) est représenté dans le plan, tandis que (b) (le cy-
lindre en l de fer) est représenté en trois dimensions. Ce sont deux graphes isomorphes
par la bijection p suivante :
p = {(H, c), (G, b), (J, a), (I, d), (C, g), (D, f), (F, e), (A, h)}.
CHAPITRE 1. MATHÉMATIQUES ET INFORMATIQUE : NOTIONS UTILES 27
g
c •
I H •
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
A C
•h •f
d• b•
F D
•
J G • e
a
(a) (b)
Comme dans les graphes orientés, les éléments de N sont appelés sommets ou n÷uds. Les
éléments de V sont appelés arêtes, ou boucles s'ils ne contiennent qu'un seul sommet.
{a,b,c,d,e,f},
G=
{a, b}, {a, e}, {a, f}, {b, c}, {b, d}, {d}, {c, e}, {a, f}, {e, f}, {d, f}
est un graphe non orienté. La gure 1.5 ore trois représentations possibles pour ce graphe.
Les notions de chaîne et de cycle sont les homologues, pour les graphes non orientés, des
notions de chemin et de circuit dans les graphes orientés. Les qualicatifs élémentaire,
simple, hamiltonien et eulérien se transposent aux graphes non orientés. Il en va de même
pour la dénition d'un sous-graphe, d'un graphe induit par un ensemble de sommets et de
la fermeture transitive.
Intuitivement, un graphe orienté valué est un graphe dans lequel chaque arc est doté d'un
attribut (en général un réel, mais cela peut être toute autre valeur). Cet attribut peut
représenter une distance, un temps, un coût, un potentiel, etc.
La gure 1.6 reprend le graphe orienté de la gure 1.3 page 23, en valuant tous ses arcs
dans R (E = R).
Un graphe non orienté valué est un graphe dans lequel chaque arête est dotée d'un attribut.
Formellement, on peut en donner la dénition suivante :
28 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
a× ×a
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
b
c b× ×b
0 1 1 0 1 1
1 0 1 1 0 0 c× ×c
fgk
a d 1 1 0 0 1 1
0 1 0 1 0 1
d× ×d
e 1 0 1 0 0 1 e× ×e
f
1 0 1 1 1 0
f× ×f
Fig. 1.5 Trois représentations d'un graphe non orienté. Le schéma (a) est la représen-
tation traditionnelle ; (b) est la représentation par une matrice d'adjacence (cette matrice
est toujours symétrique) ; (c) est une représentation bipartite.
9. 0
b 3.4
0
1.
c
∞ ∞ ∞
1.6 1.0 1.6 4.2
.7
3 3.7 ∞ 3.4 9.0 ∞ ∞
∞ ∞ ∞ ∞ ∞
.0
a 5.0 d −2.7 5.0
7.0
12
∞ ∞ ∞ ∞
4.
−
2
−2.7 8.3
∞ ∞ ∞ ∞
e 7.0 −1.0
f −1.0
∞ ∞ −12.0 ∞ ∞ ∞
8.3
(a) (b)
Fig. 1.6 Deux représentations d'un graphe orienté valué. Le schéma (a) est la représenta-
tion sagittale classique, (b) est la représentation matricielle dans laquelle les arcs absents
sont dotés d'un symbole conventionnel (ici ∞).
1.6 Arbres
un sommet la racine est distinguée). Notre préférence est cependant en faveur d'une
dénition inductive, qui se prête mieux à l'usage que nous en faisons.
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
La gure 1.7, page 30, fournit un exemple d'arbre binaire et un exemple d'arbre ternaire.
Il s'agit de graphes orientés. Sur ce point, la terminologie graphique et celle adoptée ici
divergent, puisqu'en théorie des graphes, ces structures seraient dénommées arbores-
cences . Le terme chemin est utilisé dans le sens de la théorie des graphes. Par abus de
langage, nous utilisons le vocable chemin pour des trajets qui font abstraction du sens
des èches. Quant au terme distance, il est utilisé indiéremment pour les chemins et pour
les chemins .
v=5?
3 <
= >
1 7 v=3? P v=9?
< > < >
= =
0 5 9
A P A v=7? P A
4 6 < = >
(a) A P A
(b)
Fig. 1.7 Schéma (a) : un arbre binaire Schéma (b) : un arbre (de décision) ternaire
(A : absent P : présent)
L'exemple ci-dessous montre comment se dénit inductivement un arbre binaire étiqueté 3
(à chaque n÷ud est associée une valeur, ici un entier naturel) :
1. constantes
2. ab = {/} ∪ {(g, n, d) | g ∈ ab et n∈N et d ∈ ab}
3. variables
4. t ∈ ab
5. début
6. t ← /;
7. t ← (((/, 0, /), 1, /), 3, (((/, 4, /), 5, (/, 6, /)), 7, (/, 9, /))) ;
8. écrire(t.g)
9. n
Ici, ab est l'ensemble de tous les arbres binaires nis d'entiers. Il se dénit (ligne 2 du
code) comme l'union de deux ensembles : l'ensemble {/} (l'arbre vide) et l'ensemble des
triplets (g, n, d), où g et d sont des arbres binaires (respectivement le sous-arbre gauche et
le sous-arbre droit) et n un entier naturel. À la ligne 4, la variable t est dénie comme l'un
des éléments de l'ensemble ab. L'instruction de la ligne 6 aecte l'arbre vide à t. Celle de
la ligne suivante aecte à t l'arbre du schéma (a) de la gure 1.7. La ligne 8 ache, sur un
terminal standard, le sous-arbre gauche de t (noté t.g). Dans un arbre binaire, une feuille
est un n÷ud sans aucun ls (sans aucun successeur) ; un point simple est un n÷ud n'ayant
qu'un seul ls. La hauteur d'un arbre binaire est la distance (c'est-à-dire le nombre d'arcs)
entre la racine et la feuille la plus éloignée. Le poids d'un arbre binaire est son nombre de
n÷uds. Parmi tous les chemins simples possibles dans un arbre non vide, il en existe
3. Même si, par commodité, ils peuvent occuper la même place dans les schémas, il convient de ne
pas confondre le nom d'un sommet ou d'un n÷ud, qui est un identiant, avec l'étiquette, qui est
une valeur quelconque. La dénition inductive des arbres permet en général de faire l'impasse sur
le nom du n÷ud.
CHAPITRE 1. MATHÉMATIQUES ET INFORMATIQUE : NOTIONS UTILES 31
(au moins) un dont la longueur est maximale. Cette longueur est appelée diamètre . Un
diamètre ne passe pas nécessairement par la racine (voir exercice 94, page 451).
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Dans les schémas ci-dessous, les chemins entre les n÷uds grisés sont matérialisés par
des arcs en gras. Dans le schéma (a) (resp. (b)) la longueur du chemin considéré est
de cinq arcs (resp. sept arcs). La hauteur des deux arbres est de 4, leur diamètre de 7. Le
chemin en gras du schéma (b) est un diamètre.
(a) (b)
La plupart des dénitions ci-dessus se transposent aux arbres ternaires sans diculté.
Parmi les arbres binaires particuliers, citons les arbres liformes , les complets, les pleins
et les parfaits. Un arbre est liforme quand aucun n÷ud ne possède deux ls. Un arbre
complet ne possède pas de point simple. Les arbres (a) et (b) de la gure 1.8, page 32, sont
des arbres complets. Ce n'est pas le cas des trois autres arbres de la gure. Un arbre plein
est un arbre complet dont toutes les feuilles sont situées à la même hauteur. C'est le cas
de l'arbre (b). C'est le seul arbre de ce type dans cette gure. Un arbre parfait est tel que :
i) toutes les feuilles sont situées sur les deux derniers niveaux, c'est-à-dire les niveaux plus
bas, ii) quand l'arbre parfait n'est pas un arbre plein, c'est-à-dire quand les feuilles sont
eectivement réparties sur deux niveaux, les feuilles du dernier niveau sont regroupées sur
la gauche, iii) il existe au plus un point simple et il est situé sur l'avant-dernier niveau.
Le schéma (c) fournit un exemple d'arbre parfait. L'arbre (b) est aussi un arbre parfait
particulier (car sans point simple). En revanche, les arbres (d) et (e) ne sont pas parfaits,
le premier parce qu'il présente deux points simples et le second parce que les feuilles du
dernier niveau ne sont pas regroupées à gauche. L'arbre (a) n'est pas non plus parfait.
Il est facile et souvent utile de fournir une dénition inductive des notions étudiées
dans cette section (voir exercice 94, page 451). Nous mettons en garde le lecteur contre le
caractère non consensuel des dénitions portant sur les arbres.
Un type d'arbre binaire particulier mérite notre attention, il s'agit des arbres binaires de
recherche (ou abr en abrégé). Un abr est soit un arbre vide, soit un arbre binaire dont
les n÷uds contiennent des valeurs numériques et qui est tel que, si v est la racine, son
sous-arbre gauche (resp. droit) est un abr qui contient, s'il n'est pas vide, des valeurs
inférieures (resp. supérieures) à v. L'arbre (a) de la gure 1.7, page 30, est un abr.
À plusieurs occasions, nous faisons usage d'arbres particuliers appelés arbres de déci-
sion . Un arbre de décision permet par exemple de structurer une classication (voir
gure 8.1, page 439), de représenter l'ensemble des exécutions d'un algorithme (voir -
gure 89, page 446), parfois dans le but de calculer sa complexité (voir gure 96, page 453).
Un arbre de décision se présente en général comme un arbre binaire dont chaque n÷ud est
un prédicat, chaque branche une réponse possible (vrai ou faux). Le prédicat peut être
remplacé par une question à choix multiples qui dote chaque n÷ud d'autant de branches.
L'arbre (b) de la gure 1.7, page 30, est un arbre de décision ternaire qui évalue si une
certaine valeur v appartient à l'ensemble {3, 5, 7, 9}. Dans cet arbre, on cherche à situer
32 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
(a)
(b)
v par rapport à la valeur présente dans chaque n÷ud considéré. Les feuilles répondent à
la question relative à l'arbre de décision (P : la valeur numérique présente dans la feuille
appartient à l'ensemble {3, 5, 7, 9}, A : la valeur présente dans la feuille ne gure pas dans
l'ensemble {3, 5, 7, 9} elle est absente).
Cette notion apparaît également à la gure 8.1, page 439, en tant qu'arbre de décision
pour présenter une typologie des méthodes Diviser pour Régner .
CHAPITRE 1. MATHÉMATIQUES ET INFORMATIQUE : NOTIONS UTILES 33
1.7 Files de priorité
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
1.7.1 Définition
Une le de priorité est une structure de données dont chaque élément est muni d'une valeur
numérique qui représente une priorité. Si la convention est que plus la valeur est petite
plus elle est prioritaire, une suppression a pour eet d'enlever de la le une occurrence de
la plus petite valeur.
Dans sa version standard, une le de priorité se dénit par les cinq opérations suivantes :
Il est parfois nécessaire d'enrichir ce jeu d'opérations par des opérations complémentaires,
comme celle qui consiste à modier la priorité d'un élément quelconque de la le (voir
par exemple l'exercice 78, page 368). Ces modications se font au coup par coup. La taille
d'une le de priorité f est notée |f|.
La littérature (voir par exemple [36]) présente plusieurs mises en ÷uvre plus ou moins
sophistiquées de les de priorité. Rappelons deux d'entre elles, pour des les de priorité
de n éléments :
Les listes triées, pour lesquelles l'opération d'ajout est en O(n), l'opération de (ré)initia-
lisation est, selon que l'on récupère ou non la place occupée, en Θ(n) ou Θ(1). Les
autres opérations sont en Θ(1). Ce type de solution ne peut convenir que si n est
petit.
Les tas. Du point de vue structurel, un tas est un arbre binaire parfait (les feuilles
sont situées sur au plus deux niveaux consécutifs) à gauche (les feuilles du dernier
niveau sont regroupées sur la gauche). Pour ce qui concerne le contenu, un tas est
un minimier (pour tout n÷ud, sa valeur est inférieure ou égale à celle de tous ses
descendants).
Une caractéristique importante est qu'un tas peut se représenter avantageusement
par un tableau T tel que, pour un i donné, T [2i] et T [2i + 1], s'ils existent, sont les
ls de T [i].
Le schéma (a) suivant montre, sous sa forme arborescente, un tas déni sur R+ . Le
schéma (b) en est la représentation en tableau.
34 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
2.3
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
4.0 5.6 1 2 3 4 5 5 7 8 9 10
T 2.3 4.0 5.6 6.1 7.9 7.3 9.8 9.5 8.0 8.3
6.1 7.9 7.3 9.8
(a) (b)
Références à la notion de le de priorité Cette notion est au c÷ur de deux chapitres
de cet ouvrage : le chapitre 6 sur la démarche PSEP (Programmation par Séparation et
Évaluation Progressive) et le chapitre 7 sur les algorithmes gloutons.
Une le FIFO (First In, First Out : premier entré, premier sorti) peut être vue comme une
le de priorité particulière dont les éléments ne portent pas de priorité explicite. La gestion
des priorités est eectuée implicitement, puisqu'un élément est toujours inséré en n de le
et que, lors d'un retrait, c'est l'élément en tête de le (le plus anciennement entré donc)
qui est extrait. FIFO(E) représente toutes les les FIFO sur des éléments appartenant à E.
Ainsi, si l'on écrit P ∈ FIFO(R+ × R+ ), on déclare que P est une le de couples de réels
non négatifs. Les opérations nécessaires à la gestion des les FIFO sont les suivantes :
Comme pour les les de priorité, il est parfois nécessaire d'enrichir ce jeu d'opérations ou
de modier légèrement certaines d'entre elles.
Références à la notion de le FIFO La notion de le FIFO est utilisée dans le
chapitre 7 sur les algorithmes gloutons.
CHAPITRE 1. MATHÉMATIQUES ET INFORMATIQUE : NOTIONS UTILES 35
1.9 Exercices
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
1.9.1 Démonstrations
Soit un ensemble S muni d'un opérateur interne ⊕. Soit u ∈ S un élément neutre à gauche
pour ⊕, autrement dit :
∀x · (x ∈ S ⇒ u ⊕ x = x).
Soit v un élément neutre à droite pour ⊕.
Soit E un ensemble ni muni d'une relation d'ordre partiel notée et F un sous-ensemble
strict non vide de E. On appelle antécédent strict de x un élément y diérent de x tel
que y x. Un élément m de F est dit minimum si m ne possède aucun antécédent strict
dans F.
Question 1. Montrer par l'absurde que F possède au moins un élément minimum. 2-Q1
Question 2. Montrer par récurrence que F possède au moins un élément minimum. 2-Q2
Question 3. On considère l'ensemble E constitué des couples d'entiers naturels et la re- 2-Q3
lation d'ordre partiel dénie par :
(a, b) (c, d) =
b a6c et b 6 d.
Soit F(⊂ E) = {(a, b) | a ∈ 1 .. 3 et b ∈ 1 .. 2 et a 6= b}. Dénombrer les éléments minimaux
de F.
Dans cet exercice, on établit deux résultats sur la comparaison de valeurs de facto-
rielles et d'exponentielles. Le premier constitue un résultat utile sur l'ordre des deux
classes de complexité associées (voir chapitre 2).
∀n · (n ∈ N1 ⇒ n! > 2n−1 ).
4-Q2 Question 2. Démontrer à l'aide de ce schéma que toute somme n de six centimes ou plus
peut être obtenue avec des pièces de deux et de sept centimes.
Question 5. Selon vous, laquelle de ces deux preuves est-elle la plus simple à établir ? 4-Q5
Dans cet exercice, on démontre par récurrence simple que la forme close de la relation
de récurrence proposée pour les nombres de Catalan est correcte. On établit également
une majoration de la valeur du ne nombre de Catalan.
On s'est intéressé aux nombres de Catalan dénis notamment par la relation de récurrence
(voir page 11) :
Cat(1) = 1
4n − 6
Cat(n) = · Cat(n − 1) n > 1.
n
Question 1. Montrer par récurrence simple que cette relation de récurrence admet comme 5-Q1
forme close pour tout entier n positif (voir page 11) :
(2n − 2)!
Cat(n) = .
(n − 1)! n!
Question 2. Montrer par récurrence simple que pour tout entier n positif, on a : 5-Q2
4n−1
Cat(n) 6 .
n
Cet exercice vise à attirer l'attention sur le respect des hypothèses pour eectuer une
démonstration par récurrence correcte. Deux exemples sont successivement proposés,
dans lesquels la proposition P à démontrer est à l'évidence fausse. Le raisonnement
avancé conduisant à la démontrer, il est intéressant de mettre en évidence l'erreur
commise.
38 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
Premier cas
On envisage de démontrer par récurrence la propriété P1 suivante :
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
La récurrence se fait sur le maximum des deux nombres a et b, noté max(a, b).
Second cas
On se propose de démontrer par récurrence sur n la propriété P2 suivante :
n points quelconques du plan sont toujours alignés.
Base Pour n = 2, la proposition P2 est vraie, puisque deux points sont toujours alignés.
Récurrence Supposons la propriété P2 vraie pour p points (hypothèse de récurrence).
Montrons qu'alors les (p + 1) points nommés A1 , A2 , A3 , . . . , Ap+1 sont alignés.
D'après l'hypothèse de récurrence, les p premiers points A1 , A2 , A3 , . . . , Ap sont
alignés sur une droite (d1 ) et les p derniers points A2 , A3 , . . . , Ap+1 sont alignés sur
une droite (d2 ). Les deux droites (d1 ) et (d2 ) ont en commun les deux points A2 et
A3 et sont donc forcément confondues. On a (d1 ) = (d2 ) = (A2 A3 ) et les points A1 ,
A2 , A3 , . . . , Ap , Ap+1 sont donc alignés.
Conclusion la proposition P2 est vraie pour tout nombre de points supérieur ou égal à 2.
Dans la lignée du précédent, cet exercice vise à mettre en évidence une erreur dans
un raisonnement par récurrence. Cependant, ici, la formule à démontrer est juste et
on en demande une démonstration directe convenable.
CHAPITRE 1. MATHÉMATIQUES ET INFORMATIQUE : NOTIONS UTILES 39
On se propose de démontrer par récurrence simple que, pour n entier supérieur ou égal
à 1, on a :
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
s r q p
n = 1 + (n − 1) 1 + n 1 + (n + 1) 1 + (n + 2) . . .
Pour commencer, on admettra que cette expression a un sens, c'est-à-dire qu'elle converge
quand n augmente indéniment (ce qui est vrai, comme on le constatera ultérieurement).
La démonstration par récurrence forte se fait alors ainsi :
q
Base Pour n = 1, la partie droite de la formule devient 1 + 0 1 + 1(. . .) = 1 et l'égalité
p
Récurrence On a :
s r q p
(n − 1) = 1 + (n − 2) 1 + (n − 1) 1 + n 1 + (n + 1) . . .
⇒ r élévation au carré
q p
(n − 1)2 = 1 + (n − 2) 1 + (n − 1) 1 + n 1 + (n + 1) . . .
⇔ r identité remarquable
q p
2
n − 2n + 1 = 1 + (n − 2) 1 + (n − 1) 1 + n 1 + (n + 1) . . .
⇔ r arithmétique
q p
n(n − 2) = (n − 2) 1 + (n − 1) 1 + n 1 + (n + 1) . . .
⇔ r division des deux membres par n − 2
q p
n= 1 + (n − 1) 1 + n 1 + (n + 1) . . . .
Exercice 9 De 7 à 77 et plus si . . . ◦ •
Cet exercice est consacré à la démonstration par récurrence d'une propriété des élé-
ments d'une suite d'entiers donnée d'emblée sous sa forme close.
Soit l'entier A(n, p) déni par A(n, p) = 32n − 2n−p n ∈ N1 et p∈N et n > p.
9-Q1 Question 1. Montrer par récurrence simple que, si A(n, p) est (resp. n'est pas) divisible
par 7, alors A(n + 1, p) l'est aussi (resp. ne l'est pas non plus).
9-Q2 Question 2. Que dire de la divisibilité par 7 des nombres des suites A(n, 0), A(n, 1),
A(n, 2) et A(n, 3) ?
A(1) = 1
n2 − 3n + 1
A(n) = A(n − 1) + n > 2.
(n − 1)2 · n2
CHAPITRE 1. MATHÉMATIQUES ET INFORMATIQUE : NOTIONS UTILES 41
Question 1. Montrer par récurrence simple que la forme close des nombres A(n) est 10 - Q 1
(n2 − n + 1)/n2 pour tout n > 1. Qu'en déduire quant à la nature de ces nombres ?
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Question 2. Montrer que pour tout n > 2, A(n) est dans l'intervalle ouvert A(2) .. A(1). 10 - Q 2
Dans cet exercice, on cherche à construire toute suite innie de nombres binaires
qui est égale à celle obtenue en ne prenant qu'un terme sur trois, mais aussi à celle
obtenue en ne gardant que les deux termes sur trois restants. On écarte les deux
suites triviales composées exclusivement de 0 ou de 1.
Soit une suite binaire S = hs1 , s2 , . . . , sn , . . .i autre que celle (triviale) composée uniquement
de 0 (resp. 1). On note S/3 la suite construite en prenant un élément sur trois dans S de la
façon suivante : S/3 = hs3 , s6 , . . . , s3n , . . .i. On note S − S/3 la suite qui reste de S quand
on a enlevé S/3, soit : S − S/3 = hs1 , s2 , s4 , s5 , s7 , s8 , . . ., s3n−2 , s3n−1 , s3n+1 , s3n+2 , . . .i.
Par exemple, pour S = h0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, . . .i, on a :
Cet exercice met en lumière le fait que, même si l'on connaît la forme close d'une
récurrence, celle-ci peut ne pas être transposable dans un algorithme.
On rappelle que la suite de Fibonacci est dénie (voir page 10) par la récurrence :
F(1) = 1
F(2) = 1
F(n) = F(n − 1) + F(n − 2) n>2
42 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
"
1 1+ 5 1− 5
F(n) = √ − n > 1.
5 2 2
Remarque Dans l'exercice 88, page 443, plusieurs autres façons d'eectuer ce calcul
sont examinées.
La solution est en page 57.
Cet exercice complète l'exemple donné page 12. Son objectif est de construire une
variante de l'algorithme de calcul du nombre d'arbres binaires ayant n n÷uds fondée
sur une forme close, donc a priori plus ecace.
On a établi que le nombre d'arbres binaires possédant n n÷uds est donné par la récurrence :
nbab(0) = 1
X
n−1
nbab(n) = nbab(i) · nbab(n − i − 1) n > 1.
i=0
L'intérêt de cet exercice est double. D'une part, on y étudie une façon pratique de
calculer la valeur des éléments d'une récurrence à deux indices. D'autre part, on en
établit une forme close qui, pour être prouvée, requiert de valider un nouveau schéma
de démonstration par récurrence à deux indices.
CHAPITRE 1. MATHÉMATIQUES ET INFORMATIQUE : NOTIONS UTILES 43
On considère la suite récurrente à deux indices dénie par :
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
a(0, j) = j + 1 j>0
a(i, 0) = 2 · a(i − 1, 0) + a(i − 1, 1) i>0
a(i, j) = a(i − 1, j − 1) + 2 · a(i − 1, j) + a(i − 1, j + 1) i>0 et j > 0.
Question 1. Calculer a(3, 2). Proposer une structure tabulaire et décrire la progression 14 - Q 1
pour calculer plus généralement la valeur de l'élément a(i, j) (i, j > 0).
1.9.2 Dénombrements
On considère les diérents parcours d'un cavalier (dans l'esprit du jeu d'échecs)
évoluant sous contrainte entre deux coins extrêmes d'une grille et on les dénombre
grâce à une récurrence.
On s'intéresse aux parcours d'un cavalier (au sens du jeu d'échecs) sur une grille ayant
n > 4 lignes et m > 3 colonnes. On veut connaître le nombre de façons diérentes dont il
dispose pour se rendre de la case (1, 1) à la case d'arrivée (n, m). On adopte la convention
selon laquelle (i, j) désigne la case de la grille située en ligne i et colonne j. Contrairement
au jeu d'échecs où un cavalier dispose de huit possibilités de déplacement (sauf s'il est
amené à sortir de l'échiquier), on impose ici que le cavalier ne puisse se déplacer qu'en
augmentant l'indice de colonne (le second), comme sur la gure 1.9.
7
ZnZ0Z0Z0Z
6
0Z0M0Z0Z0
5
Z0M0Z0M0Z
4
0Z0Z0Z0M0
3
Z0Z0ZnZ0Z
2
0Z0Z0Z0M0
1
Z0Z0Z0M0Z
1 2 3 4 5 6 7 8 9
Fig. 1.9 Le cavalier situé en (7, 2) (resp. (3, 6)), tracé en noir, peut aller en deux (resp.
quatre) positions, tracées en blanc.
L'objectif essentiel de cet exercice est d'établir la récurrence des nombres de Stirling.
On note S(p, n) le nombre de partitions à p blocs d'un ensemble à n éléments. Les valeurs
S(p, n) sont appelées nombres de Stirling. Par exemple, {{a, c}, {b, d}} et {{b}, {a, c, d}} sont
deux des sept partitions à deux blocs de l'ensemble à quatre éléments {a, b, c, d}.
16 - Q 1 Question 1. Donner toutes les partitions à un, deux, trois et quatre blocs de cet ensemble
à quatre éléments (un bloc ne peut pas être vide).
16 - Q 3 Question 3. Proposer une progression du calcul de S(p, n), puis l'algorithme itératif cor-
respondant.
Cet exercice vise d'une part à établir une récurrence, d'autre part à en eectuer le
calcul algorithmique en évitant l'évaluation de certaines cellules.
On considère un escalier de m marches que l'on veut gravir avec des sauts de a1 ou a2 ou
. . . ou an marches. Le problème est de trouver le nombre nbf(s, m) de façons diérentes
de gravir exactement les m marches en s sauts.
Par exemple, si m = 12 marches et si les sauts possibles sont a1 = 2, a2 = 3 et
a3 = 5 marches, on peut gravir exactement les 12 marches de l'escalier par (entre autres)
les suites de sauts :
Cet exercice introduit le jeu patagon, auquel on joue seul pour amasser un mon-
tant maximal. On cherche à dénombrer les façons de jouer dites raisonnables, qui
respectent la règle du jeu et sont susceptibles de conduire au gain maximal. L'exer-
cice 145, page 717, s'intéresse à déterminer la (une) façon de jouer permettant d'at-
teindre le gain maximal.
Dans le jeu patagon, le joueur est devant n objets, disposés en ligne. Chaque objet a
une certaine valeur qui est visible. Le joueur peut prendre autant d'objets qu'il veut en
cherchant naturellement à amasser une valeur totale aussi grande que possible. Il y a
cependant une contrainte (et une seule) : le joueur n'a pas le droit de prendre deux objets
placés l'un à côté de l'autre dans la conguration initiale.
Question 1. Avec la ligne d'objets suivante, où un objet est représenté par sa valeur, quel 18 - Q 1
sera le meilleur choix ?
46 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
23 41 40 21 42 24
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
18 - Q 3 Question 3. Certaines façons de jouer sont à coup sûr moins bonnes que d'autres. Par
exemple, jouer [0, 1, 0, 1, 0, 0] (qui rapporte 62) est moins bon que [0, 1, 0, 1, 0, 1]. On appelle
raisonnable une façon de jouer qui, tout en respectant la règle, ne laisse pas d'objets qu'il
aurait été possible de prendre. C'est ainsi que jouer [0, 1, 0, 1, 0, 1] est raisonnable, tandis
que jouer [0, 1, 0, 0, 0, 1] ou [0, 1, 0, 1, 0, 0] ne l'est pas. Comment caractériser les façons
raisonnables de jouer ?
Montrer que :
nfr0 (1) = 0, nfr1 (1) = 1, nfr0 (2) = 1, nfr1 (2) = 1, nfr0 (3) = 1, nfr1 (3) = 1
et que pour n > 3 :
18 - Q 6 Question 6. Donner les valeurs de nfr0 (n), nfr1 (n) et nfr(n) pour n allant de 1 à 15.
Quelle relation indépendante de nfr0 a-t-on entre nfr et nfr1 ? Aurait-on pu l'établir avant ?
Dans cet exercice, on s'intéresse au nombre nfg de façons de gagner dans un jeu où
l'on ajoute et soustrait des jetons situés sur deux tas. Une propriété du nombre nfg
est mise en évidence et prouvée par récurrence.
Question 1. Raisonnons d'abord pour former non pas un euro, mais toute somme allant 20 - Q 1
de un à neuf centimes. Pour former un centime, il y a une seule solution. Pour deux
centimes, on peut prendre une pièce de deux centimes, ou une pièce de un centime et il
reste à former un centime. Pour former la somme s de trois ou quatre centimes, on prend
une pièce de un centime et il reste à former la somme (s − 1), ou on prend une pièce de
deux centimes et il reste à former la somme (s − 2). Pour former cinq centimes, on prend
une pièce de cinq centimes, ou une pièce de un centime et il reste à former quatre centimes,
48 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
ou une pièce de deux centimes et il reste à former trois centimes. Enn, pour former la
somme s de six à neuf centimes, on prend une pièce de cinq centimes et il reste à former la
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
somme (s−5), ou une pièce de un centime et il reste à former la somme (s−1), ou une pièce
de deux centimes et il reste à former la somme (s−2). On en déduit la récurrence :
nbf(1) = 1
nbf(2) = 1 + nbf(1)
nbf(i) = nbf(i − 1) + nbf(i − 2) 36i64
nbf(5) = 1 + nbf(4) + nbf(3)
nbf(i) = nbf(i − 5) + nbf(i − 2) + nbf(i − 1) 6 6 i 6 9.
On se dénit une opération de mélange de deux mots et on veut d'une part déterminer
le nombre de mélanges possibles de deux mots donnés, d'autre part décider si un mot
est ou non un mélange de deux autres.
∀x · (x ∈ S ⇒ u ⊕ x = x ⊕ u).
Réponse 2. Supposons que l'élément neutre à gauche u et l'élément neutre à droite v de 1-R2
l'opérateur ⊕ soient diérents. Du fait que u est élément neutre à gauche, on a : u ⊕ v = v.
De même, puisque v est élément neutre à droite, on a : u ⊕ v = u. Supposer que u 6= v
conduit à dire que l'opération u ⊕ v prend deux valeurs distinctes, ce qui est contraire à
la dénition d'une opération interne.
Par conséquent, puisque supposer u et v diérents mène à une contradiction, u et v sont
nécessairement égaux.
Réponse 1. Supposons que tout élément x de F ait au moins un antécédent strict, c'est- 2-R1
à-dire que pour tout x ∈ F il existe un élément a(x) tel que a(x) 6= x et a(x) x.
Dans ce cas, il existe au moins un élément a(a(x)) = a2 (x) et de même au moins un
élément an (x) pour tout entier n > 1. Dès que n dépasse le cardinal de F, il y a dans la
suite an (x), . . . , a(x) au moins deux fois le même élément 4 . On a donc une situation du
type a1 a2 . . . ap a1 , avec tous les éléments a1 , . . . , ap diérents, ce qui est
impossible, car contraire à la dénition d'une relation d'ordre dont la propriété d'anti-
symétrie entraîne que a b et b a ⇒ a = b.
L'hypothèse selon laquelle tout élément x de F a au moins un antécédent strict est donc
fausse. Par conséquent, F possède un élément qui n'a pas d'antécédent strict, c'est-à-dire
un élément minimal.
Base Tout sous-ensemble de cardinal 1 possède un élément minimum (le seul élément de
cet ensemble).
Récurrence Soit F un sous-ensemble strict de E de cardinal n possédant un élément
minimal m (hypothèse de récurrence). Considérons l'ensemble F auquel on ajoute un
élément quelconque x de E n'appartenant pas à F (x existe puisque F est un sous-
ensemble strict de E). On distingue trois cas exclusifs :
4. Cette armation est une conséquence du principe des cases de courrier , qui arme que, si
(k + 1) objets ou plus sont rangés dans k boîtes, alors il y a au moins une boîte qui contient deux
objets ou plus.
50 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
(n + 1)!
= dénition de factorielle
(n + 1) · n!
> hypothèse de récurrence
(n + 1) · 2n−1
> n ∈ N1 ⇒ n > 1
2 · 2n−1
= arithmétique
2n .
Conclusion L'inégalité est vraie pour n = 1 ainsi que pour (n + 1) si elle l'est pour n. On
en déduit que l'inégalité n! > 2n−1 est vraie pour tout entier n strictement positif.
3-R2 Réponse 2. Il est aisé de constater que l'inégalité n! > n2n est fausse jusqu'à n = 8 où
l'on a 8! = 40320 et 216 = 65536. En revanche, elle est vraie pour n = 9 puisque 9! = 362880
et 218 = 262144.
Montrons que pour n > 9, si n! > 22n alors (n + 1)! > 22n+2 . On a :
(n + 1)!
= dénition de factorielle
(n + 1) · n!
> hypothèse de récurrence
(n + 1) · 22n
> n>9
4 · 22n
= propriété de l'exponentielle
22n+2 .
CHAPITRE 1. MATHÉMATIQUES ET INFORMATIQUE : NOTIONS UTILES 51
On en déduit donc que la formule proposée (n! > 22n ) est vraie pour tout entier n supérieur
ou égal à 9.
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Réponse 2. On utilise tout d'abord ce schéma pour démontrer la propriété armant que 4-R2
toute somme n de six centimes ou plus peut être obtenue avec des pièces de deux et de
sept centimes.
Base On prend n0 = 6 car on ne sait pas former la somme de cinq centimes avec les
pièces considérées. Pour former six (resp. sept) centimes, on prend trois pièces de
deux (resp. une pièce de sept centimes).
Récurrence Supposons la propriété vraie pour toute somme s > 6 (hypothèse de récur-
rence). Pour former la somme (s + 2), il sut d'ajouter une pièce de deux centimes à
la combinaison de pièces ayant servi à former la somme s que l'on sait former d'après
l'hypothèse de récurrence.
Conclusion La propriété est vraie pour toute somme n > 6.
Base On compose la somme de six centimes avec trois pièces de deux centimes.
Récurrence Supposons la propriété vraie pour la valeur n (n > 6). On distingue deux
cas exclusifs :
La valeur n a été obtenue avec au moins une pièce de sept centimes. Dans ce
cas, on lui enlève cette pièce, on lui ajoute quatre pièces de deux centimes
et on obtient ainsi la somme (n + 1).
La valeur n a été obtenue avec seulement des pièces de deux centimes. Dans
ce cas, on lui en enlève trois, on lui ajoute une pièce de sept centimes, ce
qui permet de composer la somme (n + 1).
Conclusion On sait former la somme de six centimes avec des pièces de deux et sept
centimes et, si l'on sait le faire pour la somme n, on sait composer la somme (n + 1)
avec ces mêmes pièces. On peut donc former toute somme supérieure ou égale à six
centimes avec des pièces de deux et sept centimes.
Réponse 4. Selon le premier schéma, il ne peut exister qu'une seule pièce de sept centimes 4-R4
(précisément celle prise pour former la somme de sept centimes), puisqu'ensuite on ne fait
qu'ajouter des pièces de deux centimes. Il en va de même avec le second schéma, puisque,
dès qu'une pièce de sept centimes est présente, on la retire.
Réponse 5. Le premier (resp. second) schéma impose de prouver la validité de la pro- 4-R5
priété pour n0 et n0 + 1 (resp. n0 ). En revanche, sur l'exemple, la preuve de l'étape de
récurrence est plus courte pour le premier schéma, dans lequel on n'a pas à distinguer deux
situations.
52 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
Base Pour n = 1, la forme close proposée donne : 0!/(0!·1!) = 1 (en admettant que 0! = 1).
Récurrence On suppose que pour n > 1 la forme close convient (hypothèse de récur-
rence). Pour (n + 1), on peut utiliser le terme général de la récurrence et on a :
Cat(n + 1)
= terme général de la relation de récurrence
4(n + 1) − 6
· Cat(n)
n+1
= hypothèse de récurrence
4n − 2 (2n − 2)!
·
n + 1 (n − 1)! · n!
= arithmétique
(4n − 2) · (2n − 2)!
(n − 1)! · (n + 1)!
= multiplication par n du numérateur et du dénominateur
(4n2 − 2n) · (2n − 2)!
n! · (n + 1)!
= arithmétique
(2n)!
n! · (n + 1)!
cette dernière expression n'étant autre que la forme close pour (n + 1).
Conclusion La forme close est valide pour n = 1 et, si elle l'est pour n > 1, elle l'est pour
(n + 1). On en conclut que la forme close convient pour toute valeur positive de n.
Cat(n + 1)
= terme général de la relation de récurrence
4(n + 1) − 6
· Cat(n)
n+1
6 hypothèse de récurrence
4(n + 1) − 6 4n−1
·
n+1 n
= réécriture
4n − 2 4n−1
·
n n+1
< (4n − 2)/n < 4 pour n > 1
4n
n+1
En eet, on divise par (n − 2) qui est nul quand n = 2, ce qui est illégal.
q
n = 1 + (n − 1) 1 + n(n + 2).
p
r q
n = 1 + (n − 1) 1 + n 1 + (n + 1)(n + 3).
p
54 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
s r q p
n = 1 + (n − 1) 1 + n 1 + (n + 1) 1 + (n + 2) . . . .
8-R1 Réponse 1. On utilise la même relation d'ordre total sur N1 2 qu'à la section 1.1.6, page
9, à savoir :
(a, b) (c, d) =
b a<c ou (a = c et b 6 d).
Le schéma proposé ci-dessus vise à établir que, si P est satisfaite en tout point du rectangle
(1 .. m, 1 .. n) les cas m = 1 ou n = 1 étant couverts par la base , alors P est également
satisfaite en tout point (m + 1, 1) à (m + 1, n) et en tout point (1, n + 1) à (m, n + 1) ; on a
alors P vériée sur tous les points inférieurs (au sens de l'ordre ) au point (m+1, n+1).
Si l'on montre de plus que P est satisfaite en (m + 1, n + 1) (à partir de sa validité sur
le rectangle (1 .. m, 1 .. n)), on établit que le schéma de démonstration proposé est une
instance particulière de la propriété 1.1.5, page 9, pour le couple (N1 2 , ).
9-R1 Réponse 1. Notons A(n, p) = q, avec q entier positif ou nul. Donc : 32n = 2n−p + q. Par
dénition :
A(n + 1, p) = 32(n+1) − 2(n+1)−p = 9 · 32n − 2 · 2n−p .
En remplaçant 32n par (2n−p + q) dans la partie droite de l'expression précédente, on
obtient :
A(n + 1, p) = 9 · (2n−p + q) − 2 · 2n−p = 7 · 2n−p + 9 · q.
Cette dernière expression ne peut produire un multiple de 7 que si q (soit A(n, p)) est
lui-même multiple de 7. On a alors :
A(n, p) = q = 7k et A(n + 1, p) = 7 · (2n−p + 9k).
Par conséquent, si A(n, p) est un multiple de 7, A(n + 1, p) l'est aussi et, si A(n, p) n'est
pas divisible par 7, A(n + 1, p) ne l'est pas non plus.
9-R2 Réponse 2. D'après ce qui précède, pour qu'une suite A(n, p) soit constituée d'entiers
divisibles par 7, il faut et il sut que le premier terme de la suite (A(n0 , p) = A(p, p)) soit
multiple de 7. On étudie le premier terme de chacune des quatre suites proposées :
le premier terme de la suite A(n, 2) est A(2, 2) = 34 − 20 = 80, cette suite est
donc constituée d'entiers non divisibles par 7 pour tout n supérieur ou égal
à 2,
la suite A(n, 3) débute par A(3, 3) = 36 − 20 = 728 = 7 · 104. On en déduit que
tout nombre de la suite A(n, 3) est divisible par 7 pour tout n supérieur ou
égal à 3.
Réponse 1. Pour n = 1, la forme close proposée donne A(1) = 1, ce qui est conforme à 10 - R 1
la valeur de la récurrence. On va montrer que pour tout n > 1 :
(n + 1)2 − (n + 1) + 1 n2 + n + 1
A(n + 1) = = .
(n + 1)2 (n + 1)2
On a :
(n + 1)2 − 3(n + 1) + 1 n2 − n − 1
A(n + 1) = A(n) + = A(n) + 2
2
n · (n + 1) 2 n · (n + 1)2
soit en remplaçant A(n) par sa valeur dénie par la relation de récurrence :
n2 − n + 1 n2 − n − 1 n4 + n3 + n2 n2 + n + 1
A(n + 1) = 2
+ 2 = 2 =
n n · (n + 1) 2 n · (n + 1) 2 (n + 1)2
qui est bien l'expression attendue.
Comme le numérateur et le dénominateur de l'expression dénissant les nombres A(n)
sont des entiers, ces nombres sont donc des rationnels.
D'autre part, ces nombres sont positifs puisque pour tout n positif :
2
n2 − n + 1
n−1
A(n) = > > 0.
n2 n
étant aisée, on la préfère à une démonstration par récurrence. Calculons tout d'abord
(A(n) − 3/4) :
2
n2 − n + 1 3 n2 − 4n + 4
3 n−2
A(n) − = 2
− = =
4 n 4 4n2 2n
Or, ((n − 1)/n2 ) est une expression à valeur strictement positive pour n > 1. On en
conclut donc que, pour n > 3, toute valeur A(n) est strictement supérieure à 3/4 (A(2))
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
11 - R 1 Réponse 1. On appelle a et b les deux premiers termes d'une suite S répondant aux
contraintes de l'énoncé. On va montrer que si l'on suppose connus les (3k − 1) premiers
termes de la suite S = ha, b, s3 , . . . , s3k−1 , . . .i pour k > 1, on peut déterminer les trois
termes suivants. On pourra alors déduire que l'on peut construire une suite du lézard S
aussi longue que voulu. On notera qu'il s'agit ici d'un raisonnement par récurrence forte.
Récurrence Pour k > 1, on suppose connus les (3k − 1) premiers termes de S (hypothèse
de récurrence).
On a donc S = ha, b, s3 , . . . , s3k−1 , x, y, z, . . .i et on veut déterminer la valeur des
termes x, y et z de rangs respectifs 3k, 3k + 1 et 3k + 2. De façon plus détaillée, les
trois suites s'écrivent :
S = ha, b, s3 , . . . , sk , . . . , s2k+1 , s2k+2 . . . , s3k−1 , x, y, z, . . .i
S/3 = hs3 , . . . , x, . . .i
S − S/3 = ha, b, . . . , y, z, . . .i.
Il apparaît que : i) x est le ke terme de S/3 et doit donc être égal au ke terme de S,
d'où x = sk et sk est connu puisque k ∈ 1..3k−1, ii) y est le (2k+1)e terme de S−S/3
et doit donc être égal au (2k + 1)e terme de S, d'où y = s2k+1 . Or, (2k + 1) se situe
dans l'intervalle 1 .. 3k − 1 seulement si k > 2. Cependant, pour k = 1, le terme s2k+1
n'est autre que x que l'on connaît d'après ce qui précède, iii) z est le (2k + 2)e terme
de S − S/3 et doit donc être égal au (2k + 2)e terme de S, d'où z = s2k+2 . Or, (2k + 2)
se situe dans l'intervalle 1 .. 3k − 1 seulement si k > 3. Cependant, pour k = 1, le
terme s2k+2 n'est autre que y que l'on connaît d'après ce qui précède et, si k = 2, le
terme s2k+2 s'identie à x lui aussi connu.
Conclusion On peut donc construire une suite S de longueur quelconque en se donnant
les deux premiers termes a et b.
ha, b, a, a, a, b, a, b, a, a, b, a, a, a, a, b, a, b, a, ai.
Outre les deux suites triviales composées uniquement de 0 ou de 1, il y a donc deux suites
du lézard, selon les valeurs 0 ou 1 que prennent a et b :
S1 = h0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0i
S2 = h1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1i
où S2 (resp. S1 ) s'obtient à partir de S1 (resp. S2 ) en inversant les 0 et les 1.
CHAPITRE 1. MATHÉMATIQUES ET INFORMATIQUE : NOTIONS UTILES 57
Solution de l'exercice 12 À propos de la forme close
de la suite de Fibonacci
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
13 - R 2 Réponse 2. On a vu, page 11, la forme close des nombres de Catalan, à savoir :
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
(2n − 2)! 1
Cat(n) = = · Cn−1
2n−2 n > 1.
(n − 1)! n! n
On peut donc calculer nbab(n) à partir de l'expression précédente du (n + 1)e nombre de
Catalan :
nbab(0) = 1
nbab(1) = 1
1 (n + 2) · · · 2n
nbab(n) = Cat(n + 1) = · Cn
2n = n > 1.
n+1 2···n
Le programme correspondant est le suivant :
1. constantes
2. n ∈ N et n = . . .
3. variables
4. Nbab ∈ N1 et Denom ∈ N1
5. début
6. Nbab ← 1 ;
7. pour i parcourant n + 2 .. 2n faire
8. Nbab ← Nbab · i
9. n pour ;
10. Denom ← 1 ;
11. pour i parcourant 2 .. n faire
12. denom ← Denom · i
13. n pour ;
14. Nbab ← Nbab/Denom ;
15. écrire(le nombre d’arbres binaires ayant , n, nœuds est , Nbab)
16. n
14 - R 1 Réponse 1. Pour calculer a(3, 2), on a besoin de a(2, 1), a(2, 2) et a(2, 3), dont le calcul,
à son tour, nécessite la connaissance des valeurs a(1, 0), . . . , a(1, 4). Le calcul de ces valeurs
suppose connues les valeurs a(0, 0), . . . , a(0, 5), ce qui est le cas puisque la valeur de tout
élément de premier indice nul est donnée directement.
On calcule : i) les éléments de premier indice nul et de second indice j de l'intervalle 0 .. 5
grâce à la première ligne de la récurrence, ii) l'élément a(1, 0) grâce à la seconde ligne de
la récurrence et les éléments de premier indice égal à 1 et de second indice appartenant à
l'intervalle 1 .. 4 grâce à la troisième ligne de la récurrence, iii) les éléments a(2, 1), a(2, 2)
et a(2, 3) grâce à la troisième ligne de la récurrence, et enn iv) l'élément a(3, 2) par la
formule de la dernière ligne de la récurrence. Concrètement, les calculs vont conduire au
remplissage (partiel) d'un tableau A[0 .. i, 0 .. i + j] dont les valeurs sont données dans la
gure 1.10.
De façon générale, le calcul de a(i, j) va correspondre au remplissage de la cellule A[i, j].
On commence par remplir les cellules A[0, max({j − i, 0})] à A[0, j + i] (première ligne de la
récurrence), puis (si i > 0) toute ligne d'indice k de 1 à i des cellules A[k, max({j − i + k, 0})]
à A[k, j + i − k] en utilisant la seconde (resp. troisième) ligne de la récurrence pour la
CHAPITRE 1. MATHÉMATIQUES ET INFORMATIQUE : NOTIONS UTILES 59
j 0 1 2 3 4 5
i=0 1 2 3 4 5 6
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
1 4 8 12 16 20
2 32 48 64
3 192
première cellule si max({j − i + k, 0}) = 0 (resp. max({j − i + k, 0}) > 0) et la troisième ligne
de la récurrence pour toutes les autres cellules.
Réponse 2. L'algorithme qui suit calcule l'élément A[n, m] associé à la valeur a(n, m) 14 - R 2
selon la progression décrite à la question précédente.
1. constantes
2. n ∈ N et n = . . . et m∈N et m = ...
3. variables
4. A ∈ 0..n × 0..n + m → N1
5. début
6. pour j ∈ 0 .. m + n faire
7. A[0, j] ← j + 1
8. n pour ;
9. pour i parcourant 1 .. n faire
10. pour j parcourant max({m − n + i, 0}) .. n + m − i faire
11. si j = 0 alors
12. A[i, 0] ← 2 · A[i − 1, 0] + A[i − 1, 1]
13. sinon
14. A[i, j] ← A[i − 1, j − 1] + 2 · A[i − 1, j] + A[i − 1, j + 1]
15. n si
16. n pour
17. n pour ;
18. écrire(la valeur de la suite en , n, m, est , A[n, m])
19. n
Remarque Nous laissons le soin au lecteur de construire une version dans laquelle on
utilise un tableau A ayant seulement deux lignes.
Réponse 3. On constate que la formule a(i, j) = (j + 1) · 4i pour i, j > 0 est vériée sur 14 - R 3
tous les éléments du tableau de la gure 1.10, page 59.
Pour la démontrer par récurrence, encore faut-il utiliser un schéma valide de démonstra-
tion de récurrence à deux indices. Un examen rapide de la formule de récurrence dénis-
sant a(i, j) amène à penser que ni le schéma de la page 9 ni celui proposé dans l'exercice
8, page 39 ne convient, puisque leur base suppose de montrer la validité de la formule dans
la première colonne de la structure tabulaire. À partir de la relation d'ordre total sur N2
dénie à la section 1.1.6, page 9 :
(a, b) (c, d) =
b a<c ou (a = c et b 6 d)
il est facile de montrer que le schéma de démonstration ci-après est une instance de la
propriété 1.1.5, page 9, pour le couple (N2 , ) :
60 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
On note que la preuve à eectuer nécessite seulement un ordre sur les lignes, mais que la
propriété de référence (propriété 1.1.5, page 9) exige un ordre total. On utilise maintenant
ce schéma pour montrer que :
∀(i, j) · (i ∈ N et j ∈ N ⇒ a(i, j) = (j + 1) · 4i ).
Base Examinons d'abord la formule pour les éléments a(0, j). Par dénition de la suite, on
a a(0, j) = j+1. Or j+1 = (j+1)·40 pour tout j > 0. On a donc bien a(0, j) = (j+1)·4i
pour i = 0 et j > 0.
Récurrence Supposons la formule vraie pour tout élément de premier indice égal à n
(hypothèse de récurrence) et montrons qu'elle l'est pour l'élément a(n + 1, j) (j positif
ou nul quelconque). On distingue deux cas selon la valeur de j :
Si j = 0, par dénition on a a(i, 0) = 2 · a(i − 1, 0) + a(i − 1, 1). D'après
l'hypothèse de récurrence, on peut écrire :
a(i, 0) = 2 · (0 + 1) · 4i−1 + (1 + 1) · 4i−1 = 4 · 4i−1 = (j + 1) · 4i .
Si j > 0, le dernier terme de la récurrence stipule que :
a(i, j) = a(i − 1, j − 1) + 2 · a(i − 1, j) + a(i − 1, j + 1). En utilisant l'hypothèse
de récurrence pour réécrire chacun des termes de la partie droite, il vient :
a(i, j) = (j − 1 + 1) · 4i−1 + 2(j + 1) · 4i−1 + (j + 1 + 1) · 4i−1 = 4(j + 1) · 4i−1
= (j + 1) · 4i .
Conclusion La formule a(i, j) = (j + 1) · 4i est donc vraie pour tout i et tout j entiers
positifs ou nuls.
1. constantes
2. n ∈ N et n = . . . et m ∈ N et m = . . .
3. début
4. écrire(la valeur de la suite en , n, m, est , (m + 1) · 4n )
5. n
à la fois plus simple et plus ecace que l'algorithme de la question précédente.
CHAPITRE 1. MATHÉMATIQUES ET INFORMATIQUE : NOTIONS UTILES 61
Solution de l'exercice 15 Déplacements d'un cavalier sous contrainte
Énoncé page 43.
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
nparc(1, 1) = nparc(3, 2) = 1
nparc(i, 1) = 0 26i6n
nparc(i, 2) = 0 1 6 i 6 n et i 6= 3
nparc(1, j) = nparc(3, j − 1) + nparc(2, j − 2) 36j6m
nparc(2, j) = nparc(3, j − 2) + nparc(1, j − 2) + nparc(4, j − 1) 36j6m
nparc(n, j) = nparc(n
− 2, j − 1) + nparc(n − 1, j − 2) 36j6m
nparc(n − 3, j − 1)+
nparc(n − 1, j) = nparc(n − 2, j − 2)+ 36j6m
nparc(n, j − 2)
nparc(i − 2, j − 1)+
nparc(i − 1, j − 2)+ 36i6n−2
nparc(i, j) =
nparc(i + 1, j − 2)+
et .
36j6m
nparc(i + 2, j − 1)
1. constantes
2. n ∈ N1 − {1 .. 4} et n = ... et m ∈ N1 − {1 .. 3} et m = ...
3. variables
4. NP ∈ 1 .. n × 1 .. m → N1
5. début
6. NP[1, 1] ← 1 ;
7. pour i parcourant 2 .. n faire
8. NP[i, 1] ← 0
9. n pour ;
10. pour i parcourant 1 .. n faire
11. NP[i, 2] ← 0
12. n pour ;
13. NP[3, 2] ← 1 ;
14. pour j parcourant 3 .. m faire
15. NP[n, j] ← NP[n − 1, j − 2] + NP[n − 2, j − 1] ;
62 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
16 - R 1 Réponse 1. Il y a :
une partition à un bloc : {{a, b, c, d}},
sept partitions à deux blocs : {{a, b}, {c, d}}, {{a, c}, {b, d}}, {{a, d}, {b, c}},
{{a}, {b, c, d}}, {{b}, {a, c, d}}, {{c}, {a, b, d}}, {{d}, {a, b, c}},
six partitions à trois blocs : {{a}, {b}, {c, d}}, {{a, b}, {c}, {d}}, {{a, c}, {b}, {d}},
{{a}, {c}, {b, d}}, {{a, d}, {b}, {c}}, {{a}, {d}, {b, c}},
une partition à quatre blocs : {{a}, {b}, {c}, {d}}.
Cas particuliers Pour tout n, il existe une seule partition à un bloc d'un ensemble à
n éléments, donc : S(1, n) = 1 pour n > 1. Par ailleurs, pour tout p > 1, si n < p,
S(p, n) est nul, puisqu'un bloc ne pouvant être vide on ne peut avoir plus de blocs
qu'il y a d'objets. Enn, pour tout p > 1, il y a exactement une partition à p éléments
d'un ensemble à p éléments, donc S(p, p) = 1.
Cas général Quand n augmente de 1, l'élément (n + 1) peut être ajouté seul dans un
bloc, et dans ce cas il y a S(p − 1, n) possibilités diérentes, ou mis dans un des p
blocs déjà existants, et alors il y a p · S(p, n) possibilités diérentes.
On en déduit la récurrence :
S(1, n) = 1 n>1
S(p, p) = 1 p>1
CHAPITRE 1. MATHÉMATIQUES ET INFORMATIQUE : NOTIONS UTILES 63
S(p, n) = 0 p>n
S(p, n) = p · S(p, n − 1) + S(p − 1, n − 1) n>1 et p < n.
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Réponse 3. Pour le calcul de cette récurrence, on utilise un tableau S[1 .. p, 1 .. n]. L'ob- 16 - R 3
servation de la récurrence fait apparaître que, dans le cas général (quatrième terme de la
récurrence), l'élément S[i, j] dépend de deux éléments se situant dans la colonne précédente
(j − 1), ce qui rend possible un calcul par valeurs croissantes de l'indice de colonne. On
remplit chaque colonne j de la façon suivante : i) la cellule S[1, j] est initialisée à 1 (premier
terme de la récurrence), ii) on utilise le terme général pour le calcul de toute cellule S[i, j]
avec i < j et i 6 p, iii) si elle est dans le tableau, la cellule S[j, j] est mise à 1, et enn
iv) les cellules S[i, j] avec i > j reçoivent la valeur 0.
L'algorithme correspondant à la description précédente est le suivant :
1. constantes
2. n ∈ N1 et n = ... et p ∈ N1 et p6n et p = ...
3. variables
4. S ∈ 1 .. p × 1 .. n → N
5. début
6. S[1, 1] ← 1 ;
7. pour i parcourant 2 .. p faire
8. S[i, 1] ← 0
9. n pour ;
10. pour j parcourant 2 .. n faire
11. S[1, j] ← 1 ;
12. pour i parcourant 2 .. p faire
13. si i < j alors
14. S[i, j] ← i · S[i, j − 1] + S[i − 1, j − 1]
15. sinonsi i = j alors
16. S[i, j] ← 1
17. sinon
18. S[i, j] ← 0
19. n si
20. n pour
21. n pour ;
22. écrire(le nombre de partitions à , p, blocs d’un ensemble à , n, éléments
23. est , S[p, n])
24. n
n 1 2 3 4 5 6 7
p=1 1 1 1 1 1 1 1
2 0 1 3 7 15 31 63
3 0 0 1 6 25 90 301
4 0 0 0 1 10 65 350
5 0 0 0 0 1 15 140
64 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
17 - R 1 Réponse 1. On peut par exemple eectuer la suite de sauts h5, 2, 5i, ou encore h2, 5, 5i,
ce qui montre qu'ici l'ordre des sauts eectués (s'ils sont diérents) importe.
Cas particuliers Il y a une seule façon de franchir 0 marches avec 0 sauts, ce qui implique
nbf(0, 0) = 1. De plus, il n'y a aucune façon d'eectuer un ou plusieurs sauts sans
franchir de marche, donc nbf(s, 0) = 0 pour s > 1. Enn, on a nbf(0, m) = 0 pour
m > 0, puisqu'il n'y a aucune manière de franchir au moins une marche sans eectuer
de saut(s).
Cas général Supposons que l'on se trouve sur la marche m après avoir eectué s sauts,
avec s et m strictement positifs. Comme s > 0, on vient d'eectuer un saut (qui a
amené à la marche m) à partir d'une des marches d'où l'on peut atteindre m en un
saut. Le nombre de façons d'atteindre la marche m en s sauts est donc égal à la
somme des façons que l'on avait d'atteindre ces marches.
nbf(0, 0) = 1
nbf(0, m) = 0 m>0
nbf(s, 0) = 0 X s>0
nbf(s, m) = nbf(s − 1, m − ai ) s>0 et m > 0.
i∈1..n et
(m−ai )>0
1. constantes
2. n ∈ N1 et n = . . . et s ∈ N1 et s = . . . et m ∈ N1 et m = ... et
3. A ∈ 1 .. n → N1 et A = [. . .]
4. variables
5. NF ∈ 0 .. s × 0 .. m → N
6. début
7. NF[0, 0] ← 1 ;
8. pour j parcourant 1 .. m faire
9. NF[0, j] ← 0
10. n pour ;
11. pour i parcourant 1 .. s faire
CHAPITRE 1. MATHÉMATIQUES ET INFORMATIQUE : NOTIONS UTILES 65
12. NF[i, 0] ← 0 ;
13. pour j parcourant 1 .. m faire
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
14. NF[i, j] ← 0 ;
15. pour k parcourant 1 .. n faire
16. si j − A[k] > 0 alors
17. NF[i, j] ← NF[i, j] + NF[i − 1, j − A[k]]
18. n si
19. n pour
20. n pour
21. n pour ;
22. écrire(le nombre de façons de monter , m, marches en , s, sauts
23. est , NF[s, m])
24. n
j 0 1 2 3 4 5 6 7 8 9 10 11 12
i=0 1 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 1 0 0 0 0 0 0 0
2 0 0 0 0 1 0 0 2 0 0 1 0 0
3 0 0 0 0 0 0 1 0 0 3 0 0 3
4 0 0 0 0 0 0 0 0 1 0 0 4 0
5 0 0 0 0 0 0 0 0 0 0 1 0 0
6 0 0 0 0 0 0 0 0 0 0 0 0 1
18 - R 1 Réponse 1. On a bien entendu plusieurs choix, mais celui qui semble le meilleur (in-
tuitivement ou après avoir évalué tous les choix autorisés) est la suite h23, 40, 42i, qui
rapporte le total 105.
18 - R 3 Réponse 3. Le vecteur binaire ne doit pas avoir deux 1 consécutifs (règle du jeu). Un
vecteur raisonnable ne doit pas non plus avoir trois 0 consécutifs (dans ce cas, celui du
milieu peut être remplacé par un 1). Il ne doit ni commencer ni nir par 00.
18 - R 4 Réponse 4. Les premières formules s'établissent par énumération. Pour un jeu de taille 1,
seul le choix de cet élément est raisonnable, d'où nfr0 (1) = 0 et nfr1 (1) = 1. Avec un jeu de
taille 2, seuls les choix 01 et 10 sont raisonnables. On a donc nfr0 (2) = nfr1 (2) = 1. Enn,
avec un jeu de taille 3, les congurations raisonnables sont 010 et 101, d'où nfr0 (3) =
nfr1 (3) = 1.
Le terme général de la récurrence s'élabore en étudiant les quatre cas exclusifs et exhaustifs
suivants de vecteur raisonnable de taille n > 3 : V1 = [. . . , 0, 0, 1, 0], V2 = [. . . , 1, 0, 1, 0],
V3 = [. . . , 1, 0, 0, 1], V4 = [. . . , 0, 1, 0, 1]. On remarque que, si l'on enlève le 0 terminal de
V1 et V2 , on obtient un vecteur raisonnable ayant un 1 en position n − 1, d'où nfr0 (n) =
nfr1 (n − 1). Il n'en va pas de même si l'on enlève le 1 terminal des vecteurs V3 et V4 ,
puisqu'alors, si V40 = [. . . , 0, 1, 0] est bien un vecteur raisonnable, V30 = [. . . , 1, 0, 0] n'en est
pas un. On doit donc étudier ce qui se passe si l'on enlève les deux derniers éléments de V3 .
On obtient alors V300 = [. . . , 1, 0], qui est un vecteur raisonnable. On en déduit donc que :
nfr1 (n) = nfr0 (n − 1) + nfr0 (n − 2) = nfr1 (n − 2) + nfr1 (n − 3)
18 - R 5 Réponse 5. Les valeurs de nfr(1), nfr(2) et nfr(3) sont obtenues par somme des valeurs
correspondantes de nfr0 et nfr1 , soit :
18 - R 6 Réponse 6. Les valeurs de nfr0 (n), nfr1 (n) et nfr(n) pour n allant de 1 à 15 sont re-
groupées dans le tableau ci-après :
CHAPITRE 1. MATHÉMATIQUES ET INFORMATIQUE : NOTIONS UTILES 67
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
nfr0 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
nfr1 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37
nfr 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65
On observe que pour n > 2, on a : nfr1 (n) = nfr(n − 2). Ce n'est pas surprenant, car on
a vu : i) que la forme de leur récurrence est identique, nfr1 (3) = nfr(1) = 1 et nfr1 (4) =
nfr(2) = 2, ii) à la question 4 que :
Remarque Comme on l'a vu page 10, la suite de terme général P(n) = P(n−2)+P(n−3)
pour tout n > 2 avec P(0) = P(1) = P(2) = 1, dénit la suite de Padovan. Cette suite a
une croissance exponentielle de l'ordre de (1.324 · · · )n−1 . Plus exactement, le ne nombre
est l'entier le plus proche de (1.324 · · · )n−1 /1.045 · · · . On a par exemple P(20) = 200.
Le nombre 1.324 · · · est parfois appelé nombre d'argent , par analogie avec le nombre d'or
associé à la suite de Fibonacci.
Réponse 7. On voit que le calcul de nfr(i) ne fait appel qu'aux deux valeurs nfr(i − 2) 18 - R 7
et nfr(i − 3). Pour calculer nfr(n), on va utiliser un tableau T [1 .. 4] et on conserve dans T
les quatre dernières valeurs de nfr, d'où l'algorithme :
1. constantes
2. n ∈ N1 et n = ...
3. variables
4. T ∈ 1 .. 4 → N1
5. début
6. T [1] ← 1 ; T [2] ← 2 ; T [3] ← 2 ;
7. pour i parcourant 4 .. n faire
8. T [4] ← T [1] + T [2] ;
9. pour j parcourant 1 .. 3 faire
10. T [j] ← T [j + 1]
11. n pour
12. n pour ;
13. écrire(le nombre de façons raisonnables de jouer avec un jeu
14. de taille , n, est , T [4])
15. n
Réponse 1. Il y a une façon et une seule d'atteindre l'un des deux états gagnants quand 19 - R 1
on s'y trouve déjà : ne rien faire. Lorsque l'on se trouve dans la situation p = 1, q = 1,
on ne peut plus jouer ; on n'atteindra donc pas un des états gagnants désirés : on aura en
fait perdu. On a deux possibilités de jouer quand p > 2 et q > 2 ; le nombre de façons
d'atteindre un état gagnant est donné par la somme des façons depuis les deux situations
atteintes en jouant (p − 2, q + 1 ou p + 1, q − 2). Quand p ou q est inférieur à 2, on a une
seule façon de jouer et le nombre de façons d'atteindre un des états gagnants depuis (p, q)
68 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
nfg(0, 1) = nfg(1, 0) = 1
nfg(1, 1) = 0
nfg(0, q) = nfg(1, q − 2) q>1
nfg(1, q) = nfg(2, q − 2) q>1
nfg(p, 0) = nfg(p − 2, 1) p>1
nfg(p, 1) = nfg(p − 2, 2) p>1
nfg(p, q) = nfg(p − 2, q + 1) + nfg(p + 1, q − 2) p>1 et q > 1.
19 - R 2 Réponse 2. Du fait que le nombre p (resp. q) de jetons du tas P (resp. Q) peut augmen-
ter, la structure tabulaire ne peut se limiter à un tableau à (p + 1) lignes et (q + 1) colonnes
(ou l'inverse). En toute rigueur, un tableau ayant (p + bq/2c + 1) lignes et (q + bp/2c + 1)
colonnes sut, mais pour simplier le remplissage, on utilise une structure tabulaire carrée
T [0 .. p + q, 0 .. p + q] où T [i, j] correspond à nfg(i, j).
Pour ce qui concerne le cas général, le remplissage de ce tableau peut être eectué par
diagonales d'équation (p+q) de valeur croissante, puisque nfg(p, q) se situe sur la diagonale
d'équation (p+q) et les deux éléments requis sur celle d'équation (p+q−1). Il sera commode
de remplir les diagonales 1, 2 et 3 (0 étant sans objet) dans une phase d'initialisation, en
utilisant les termes appropriés de la récurrence. Ensuite, les éléments d'une diagonale sont
remplis grâce au terme général de la récurrence à l'exception des quatre éléments extrêmes
pour lesquels on utilise les termes de la récurrence correspondant à p ou q inférieur à 2.
1. constantes
2. p ∈ N1 − {1} et p = ... et q ∈ N1 − {1} et q = ...
3. variables
4. T ∈ 0 .. p + q × 0 .. p + q → N
5. début
6. T [0, 1] ← 1 ; T [1, 0] ← 1 ;
7. T [2, 0] ← 1 ; T [0, 2] ← 1 ; T [1, 1] ← 0 ;
8. T [3, 0] ← 0 ; T [1, 2] ← 1 ; T [2, 1] ← 1 ; T [0, 3] ← 0 ;
9. pour k parcourant 4 .. p + q faire
10. T [0, k] ← T [1, k − 2] ;
11. T [1, k − 1] ← T [2, k − 3] ;
12. T [k, 0] ← T [k − 2, 1] ;
13. T [k − 1, 1] ← T [k − 3, 2] ;
14. pour j parcourant 2 .. k − 2 faire
15. T [j, k − j] ← T [j − 2, k − j + 1] + T [j + 1, k − j − 2]
16. n pour
17. n pour ;
18. écrire(le nombre de façons de gagner avec deux piles de , p, et , q, jetons
19. est , T [p, q])
20. n
CHAPITRE 1. MATHÉMATIQUES ET INFORMATIQUE : NOTIONS UTILES 69
Réponse 4. Le calcul de nfg(4, 2) se fait en remplissant le tableau ci-après : 19 - R 4
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
q 0 1 2 3 4 5 6
p=0 1 1 0 1 1 0
1 1 0 1 1 0 2
2 1 1 0 2 3
3 0 1 2 0
4 1 0 3
5 1 2
6 0
Base Pour n = 1, seuls les éléments nfg(0, 1) et nfg(1, 0) sont tels que (i + j) = n, mais
|i − j| = 1 n'est pas multiple de 3. Pour n = 2, nfg(0, 2), nfg(2, 0) et nfg(1, 1) sont tels
que (i + j) = n. Le seul élément vériant |i − j| = 3k , est nfg(1, 1) dont la valeur est 0
d'après le second terme de la récurrence. La propriété est donc vériée pour n = 1 et
n = 2.
Récurrence Supposons la propriété vraie pour n > 2, on va prouver (en utilisant la
récurrence établie précédemment) que tout élément nfg(i, j) tel que |i − j| est multiple
de 3 et (i + j = n + 1) prend la valeur 0. On examine donc successivement les éléments
tels que (i + j = n + 1).
nfg(0, n + 1) et nfg(n + 1, 0) On a nfg(0, n + 1) = nfg(1, n − 1) (troisième terme de
la récurrence) ; la somme des indices de ce dernier élément étant égale à n, on
peut utiliser l'hypothèse de récurrence. Si (|0 − (n + 1)| = n + 1) est multiple de 3,
(|1 − (n − 1)| = n − 2) l'est aussi et donc nfg(0, n + 1) = nfg(1, n − 1) = 0. Le
même raisonnement vaut pour nfg(n + 1, 0) de par la symétrie des termes de la
récurrence.
nfg(1, n) et nfg(n, 1) D'après le quatrième terme de la récurrence, on a
nfg(1, n) = nfg(2, n − 2). Le fait que la somme des indices de nfg(2, n − 2) vaut
n permet d'utiliser l'hypothèse de récurrence. Si (|1 − n| = n − 1) est multiple
de 3, (|2 − (n − 2)| = |n − 4|) l'est aussi et donc nfg(1, n) = nfg(2, n − 2) = 0.
Le même raisonnement vaut pour nfg(n, 1) de par la symétrie des termes de la
récurrence.
Cas général de nfg(i, j) avec i + j = n + 1, i > 1 et j > 1 Un tel élément est la
somme de nfg(i − 2, j + 1) et nfg(i + 1, j − 2), tous deux tels que la somme de leurs
indices vaut n ; l'hypothèse de récurrence s'applique donc. Si |i − j| est multiple
de 3, (|i−2−(j+1)| = |i−j−3|) l'est aussi, de même que (|i+1−(j−2)| = |i−j+3|).
Par suite, nfg(i, j) = nfg(i − 2, j + 1) + nfg(i + 1, j − 2) = 0.
Conclusion On en déduit que tout élément nfg(i, j) tel que |i − j| est multiple de 3 prend
la valeur 0 à l'exception de nfg(0, 0) pour tout couple (i, j) avec i > 0 et j > 0.
70 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
nbf(m, p)
= j k
distinction du premier terme
m
X
v(p)
à 6.
On aboutit donc à la récurrence ci-après :
nbf(0, p) = 1 16p66
nbf(m, 6) = 1 m est multiple de v(6) et 1 6 m 6 100
nbf(m, 6) = 0 m n'est pas multiple de v(6) et 1 6 m 6 100
nbf(m, p) = nbf(m, p + 1) + nbf(m − v(p), p) m > v(p) et 1 6 p < 6 et 1 6 m 6 100
nbf(m, p) = nbf(m, p + 1) m < v(p) et 1 6 p < 6 et 1 6 m 6 100.
Remarque 1 Il est à noter que l'ordre des pièces n'importe pas, prime seulement le fait
que l'on prend en compte toutes les pièces et que l'on calcule donc nbf(100, 1). Si l'on fait
l'hypothèse que les pièces sont ordonnées de façon croissante, on peut remplacer le dernier
terme de la récurrence par nbf(m, p) = 0, puisque, si m est inférieur à v(p), il est inférieur
à v(p + 1).
Réponse 3. Dans l'exemple consistant à former le montant de trois centimes avec les 20 - R 3
pièces jaunes telles que v(1) = 20, v(2) = 5, v(3) = 10, v(4) = 1, v(5) = 50 et v(6) = 2 (mais
toute autre organisation des pièces conviendrait aussi bien), on a :
Or :
3. variables
4. T ∈ 0 .. 100 × 1 .. 6 → N
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
5. début
6. pour i parcourant 0 .. 100 faire
7. T [i, 6] ← 0
8. n pour ;
9. pour i parcourant 0 .. b V[6] 100
c faire
10. T [V[6] · i, 6] ← 1
11. n pour ;
12. pour p parcourant inverse 1 .. 5 faire
13. T [0, p] ← 1 ;
14. pour m parcourant 1 .. V[p] − 1 faire
15. T [m, p] ← T [m, p + 1]
16. n pour ;
17. pour m parcourant V[p] .. 100 faire
18. T [m, p] ← T [m, p + 1] + T [m − V[p], p]
19. n pour
20. n pour ;
21. écrire(nombre de façons de former un euro en pièces jaunes : , T [100, 1])
22. n
20 - R 6 Réponse 6. On a vu que nbf(m, 1) ne dépend pas de l'ordre dans lequel sont prises en
compte les pièces jaunes, donc de l'ordre des valeurs dans V . On peut donc raisonner en
prenant pour vecteur V = [1, 2, 5, 10, 20, 50]. Dans ce contexte, pour m > 0, nbf(m, 1) est
déni comme la somme de nbf(m, 2) et nbf(m − 1, 1). Puisque nbf(m, 2) > 0, on a :
nbf(m, 1) > nbf(m − 1, 1).
Une autre façon de justier ce résultat est de constater que, pour former le montant m
avec les six pièces jaunes, on peut commencer par former (m − 1) ; en ajoutant une pièce
de un centime, on obtient le montant m.
21 - R 1 Réponse 1. Notons nbmlg(i, j) le nombre de mélanges diérents que l'on peut construire
à partir des préxes u[1 .. i] et v[1 .. j] des mots u et v. Dans le cas général, la lettre w[i + j]
peut être soit u[i], soit v[j]. Dans le premier cas, on a nbmlg(i − 1, j) mélanges possibles se
terminant par la lettre u[i] et, dans le second cas, on a nbmlg(i, j − 1) mélanges possibles
se terminant par la lettre v[j]. Si u (resp. v) est le mot vide, on a une façon unique de faire
le mélange. On aboutit donc à la récurrence :
CHAPITRE 1. MATHÉMATIQUES ET INFORMATIQUE : NOTIONS UTILES 73
nbmlg(i, 0) = 1 06i6m
nbmlg(0, j) = 1 06j6n
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
j 0 1 2 3 4
i=0 1 1 1 1 1
1 1 2 3 4 5
2 1 3 6 10 15
3 1 4 10 20 35
4 1 5 15 35 70
5 1 6 21 56 126
Remarque On observe que le tableau est symétrique par rapport à la diagonale d'équa-
tion i − j = 0, ce qui est cohérent avec le fait que les deux indices i et j jouent le même
rôle.
i!
nbmlg(i, 0) = 1 =
i! · 0!
de même que pour tout entier j :
j!
nbmlg(0, j) = 1 = .
j! · 0!
Récurrence Supposons (hypothèse de récurrence) que pour tout couple (i, j) d'entiers
positifs :
(i + j − 1)! (i + j − 1)!
nbmlg(i − 1, j) = , nbmlg(i, j − 1) =
(i − 1)! · j! i! · (j − 1)!
(i + j)!
il faut montrer que nbmlg(i, j) =
i! · j!
74 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
On a :
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
nbmlg(i, j)
= terme général de la récurrence
nbmlg(i − 1, j) + nbmlg(i, j − 1)
= hypothèse de récurrence
(i + j − 1)! (i + j − 1)!
+
(i − 1)! · j! i! · (j − 1)!
= arithmétique
i · (i + j − 1)! j · (i + j − 1)!
+
i! · j! i! · j!
= arithmétique
(i + j) · (i + j − 1)!
i! · j!
= dénition de factorielle
(i + j)!
.
i! · j!
(m + n)!
Conclusion ∀(m, n) · m ∈ N et n ∈ N ⇒ nbmlg(m, n) = .
m! · n!
(m + n)!
nbmlg(m, n) = = Cm n
m+n = Cm+n
m! · n!
j 0 1 2
d b
i=0 V V F
1 a F V V
2 b F V V
3 c F F V
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
CHAPITRE 2
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Alan Perlis
2.1.1 Algorithme
Rappelons d'abord que l'on dénit un algorithme comme un ensemble de règles permettant
de résoudre un problème sur des données d'entrée. Cet ensemble de règles dénit avec
précision une séquence d'opérations qui se termine dans un temps ni.
Par exemple, soit le problème consistant à trouver le résultat de la multiplication de deux
nombres entiers positifs écrits en base 10. Nous avons tous appris un certain algorithme
pour résoudre ce problème, fondé sur une suite précise d'opérations élémentaires : l'utili-
sation de la table de multiplication, l'addition, l'écriture de la retenue, etc. Nous savons
que cet algorithme permet de calculer le produit de tout couple de nombres en un temps
ni, fonction de la longueur des nombres.
Il est à remarquer que la technique de multiplication à l'aide d'un boulier produit le même
résultat avec un procédé assez proche, mais non identique. Il existe encore d'autres algo-
rithmes pour résoudre le même problème, parfois fondés sur des techniques bien diérentes,
comme la multiplication dite à la russe.
Ces algorithmes sont assez simples pour être appris par le plus grand nombre. Ils sont
assez ecaces, au sens où ils fournissent le résultat cherché rapidement et ne nécessitent ni
une grande mémoire, ni l'écriture de grandes quantités de chires. En eet, comparons-les
avec l'algorithme naïf suivant : pour multiplier un nombre n par un nombre m, écrire n
lignes, de chacune m croix, les unes sous les autres, puis compter le nombre de croix. Ce
dernier procédé ne demande que de savoir compter, mais il est terriblement coûteux en
temps et en place.
Nous venons de voir qu'il existe plusieurs méthodes (ou algorithmes) pour eectuer la mul-
tiplication de deux nombres. C'est généralement le cas pour de nombreux problèmes, et il
est utile de pouvoir comparer les divers algorithmes qui, équivalents sur le plan fonction-
nel, peuvent être bien diérents au niveau de leur ecacité. L'algorithmique, science de la
78 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
production des algorithmes, a pour but principal, pour un problème donné, de trouver un
algorithme aussi ecace que possible.
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Il est naturel de quantier l'ecacité d'un algorithme en mesurant ce que l'on appelle sa
complexité en temps (ou temporelle ) et sa complexité en espace mémoire (ou spatiale ).
Cependant, parce que la taille de la mémoire des ordinateurs a énormément augmenté au
cours des années, la complexité en espace est un critère de moins en moins critique. C'est
pourquoi, dans la suite de cet ouvrage, nous considèrerons le plus souvent uniquement la
complexité en temps.
Compte tenu de cette remarque, pour l'essentiel, le but de l'algorithmique devient donc
de chercher, pour un problème donné, un algorithme le plus rapide possible. La question
légitime qui se pose est donc de mesurer cette rapidité.
Un premier point à noter est qu'il est souhaitable de mesurer la complexité d'un algorithme
indépendamment à la fois du langage dans lequel il est codé et de la machine sur laquelle
il est exécuté. On va donc analyser la complexité selon une ou plusieurs opération(s) élé-
mentaire(s) , qui varie(nt) selon les problèmes, mais est (sont) représentative(s) de ce que
fait l'algorithme considéré. Ainsi, pour un algorithme de recherche dans un tableau, l'opé-
ration élémentaire sera la comparaison, alors que pour un algorithme de tri, on aura deux
opérations élémentaires à considérer : la comparaison et l'échange de deux données. Enn,
pour un produit de deux matrices, la multiplication de deux nombres réels constituera
l'opération élémentaire.
Un second point est que la complexité d'un algorithme s'exprime en fonction de la taille
des données qu'il a à traiter. Cette taille est un nombre entier caractéristique du problème.
Pour un algorithme de recherche dans un tableau ou de tri d'un tableau, ce sera le nombre
d'éléments (ou taille) du tableau ; pour le produit de deux matrices carrées (forcément de
même taille), ce sera le nombre de lignes ou de colonnes des matrices.
Il est souvent impossible de donner la complexité exacte d'un algorithme comme le nombre
d'opérations élémentaires en fonction de la taille des données. En eet, la complexité
dépend la plupart du temps des données elles-mêmes. Par exemple, certains algorithmes
de tri fonctionnent très rapidement si le tableau est déjà à peu près trié et beaucoup plus
lentement si le tableau est trié à l'envers. C'est pour cette raison que l'on doit souvent
renoncer à calculer une complexité exacte, mais que l'on s'intéresse à une complexité
minimale ou au mieux (quand les données sont favorables) et une complexité maximale
ou au pire. Il est tentant de dénir une complexité moyenne, mais c'est en général dicile
et cela nécessite de faire des hypothèses statistiques parfois arbitraires sur la répartition
des données.
Une autre analyse en moyenne est celle de la complexité amortie, pour laquelle nous
renvoyons, comme pour la complexité moyenne, aux ouvrages [17] et [35].
Une autre manière de faire l'analyse en temps d'un algorithme est d'utiliser la notion
d'ordre de grandeur de complexité, qui exprime le comportement de la complexité quand
la taille des données devient grande .
Dans les deux sections suivantes, nous présentons les notions de complexité minimale et
maximale, puis l'analyse par ordre de grandeur de complexité.
Nous allons traiter ces notions avec un exemple, celui de la recherche dans un dictionnaire.
Supposons que nous voulions rechercher un mot dans un dictionnaire, pour en connaître la
dénition s'il s'y trouve, ou pour conclure qu'il n'est pas dans ce dictionnaire. Appelons n
la taille des données, c'est-à-dire le nombre de mots dans le dictionnaire. Convenons que
CHAPITRE 2. COMPLEXITÉ D'UN ALGORITHME 79
l'opération élémentaire est la comparaison de deux mots et appelons x le mot recherché.
Un premier algorithme consiste à parcourir les mots du dictionnaire du début à la n dans
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
l'ordre, jusqu'à la terminaison du processus. Cette terminaison peut prendre deux formes :
soit on trouve le mot et on aura eectué un nombre de comparaisons inférieur ou égal à n,
soit on ne le trouve pas et il aura fallu consulter tout le dictionnaire. Pour matérialiser ce
second cas, une technique possible est celle de la sentinelle : on allonge le dictionnaire du
mot cherché x. Avec cette technique, on trouve nalement toujours x dans le dictionnaire
et on sait quand on le trouve à la (n + 1)e comparaison qu'il n'est pas dans le dictionnaire
original.
L'algorithme RechDict1 ci-dessous prend en donnée le dictionnaire sous la forme du ta-
bleau DIC[1 .. n] de mots tous diérents, classés par ordre lexicographique croissant, et un
mot x. Si x est dans DIC, l'algorithme donne en résultat l'indice où x se trouve, sinon il
produit la valeur (n + 1).
1. constantes
2. n ∈ N1 et n = ... et x ∈ chaîne et x = . . .
3. variables
4. DIC ∈ 1 .. n + 1 → chaîne et DIC = [. . .]
5. début
6. DIC[n + 1] ← x ; i ← 1 ;
7. tant que DIC[i] 6= x faire
8. i←i+1
9. n tant que ;
10. si i < n + 1 alors
11. écrire(le mot , x, est en position , i, du dictionnaire)
12. sinon
13. écrire(le mot , x, n’est pas dans le dictionnaire)
14. n si
15. n
Quelle est la complexité pratique de cet algorithme ? On sait déjà qu'au pire elle est
de (n + 1) comparaisons, le cas le pire étant quand x n'est pas dans DIC. De même, la
complexité minimale est d'une comparaison, si par bonheur le mot cherché est le premier du
dictionnaire. La complexité en moyenne peut être calculée sous des hypothèses statistiques
simples et il s'avère qu'elle n'est pas égale à n/2 (voir exercice 27, page 88).
Puisqu'un dictionnaire est trié, comme chacun sait, il existe une méthode plus rapide pour
y chercher un mot : la recherche dichotomique. Il en existe plusieurs variantes (voir par
exemple l'exercice 89, page 446) ; nous proposons la version itérative suivante. On prend
le mot situé au milieu du dictionnaire et on le compare à x. Si x est plus grand que
(resp. plus petit que ou égal à) l'élément du milieu au sens de l'ordre lexicographique,
on recommence l'opération dans le demi-dictionnaire supérieur (resp. inférieur) jusqu'à
atteindre une partie de dictionnaire ne contenant qu'un mot. On conclut positivement si
celui-ci est le mot x cherché, sinon x n'est pas dans le dictionnaire.
80 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
1. constantes
2. x ∈ chaîne et x = . . . et n ∈ N1 et n = . . .
3. variables
4. deb ∈ N1 et fin ∈ N1 et fin > deb et mil ∈ N1 et mil > deb et
5. mil 6 fin et DIC ∈ 1 .. n → chaîne et DIC = [. . .]
6. début
7. deb ← 1 ; fin ← n ;
8. tant quedeb 6= fin faire
deb + fin
9. mil ← ;
2
10. si x > T [mil] alors
11. deb ← mil + 1
12. sinon
13. fin ← mil
14. n si
15. n tant que ;
16. si x = T [deb] alors
17. écrire(le mot , x, est en position , deb, du dictionnaire)
18. sinon
19. écrire(le mot , x, n’est pas dans le dictionnaire)
20. n si
21. n
La manière la plus courante d'analyser le temps que prend un algorithme est d'utiliser
la notion d'ordre de grandeur de complexité (on parle aussi de classe de complexité ). On
note fA (n) la fonction qui exprime la complexité maximale d'un algorithme A en fonction
de la taille n des données qu'il traite.
CHAPITRE 2. COMPLEXITÉ D'UN ALGORITHME 81
L'idée de départ est de majorer fA (n) par une fonction à la croissance connue. À cet eet,
on considère un certain nombre de fonctions de référence dont la croissance est connue :
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
n2 (complexité quadratique), nn .
On pourrait chercher à écrire une formule du type fA (n) ∈ O(n2 ) pour signier (avec
des précautions que nous allons préciser) que fA (n) ne croît pas plus vite que n2 quand n
augmente. Cependant, cette première approche serait très restrictive puisque, par exemple,
fA (n) = n2 /2 + 3n/2 + 1 ou fA (n) = 2n2 − 1 n'obéiraient pas à la dénition. On révise donc
l'acception de fA (n) ∈ O(n2 ) de sorte que les deux exemples précédents soient acceptables.
Pour le premier, on va dire que fA (n) ne croît pas plus vite que la fonction de référence
(ici n2 ) quand n augmente, à partir d'un certain rang n0 . Ainsi, on peut écrire
(n2 /2 + 3n/2 + 1) ∈ O(n2 ), puisqu'à partir de n0 = 4 il est vrai que (n2 /2 + 3n/2 + 1) < n2 .
Cependant, nous ne pouvons toujours pas écrire que (2n2 − 1) ∈ O(n2 ), puisque pour
tout n > 1 : (2n2 − 1) > n2 . Pourtant, l'ordre de grandeur de croissance de (2n2 − 1) est
visiblement du même type que celui de n2 et il semble consistant de dire que (2n2 − 1)
et n2 croissent de la même manière. Nous dirons nalement que fA (n) ∈ O(n2 ), s'il existe
une constante C et un entier n0 au-dessus duquel l'inégalité fA (n) 6 C · n2 est toujours
vraie. Finalement, nous arrivons à la dénition suivante. Soit une fonction g : N → R+ .
On appelle ordre de grandeur maximal de complexité de g l'ensemble :
b {t : N → R+ | ∃(C, n0 ) · (C ∈ R+ et n0 ∈ N et ∀n·
O(g) =
((n ∈ N et n > n0 ) ⇒ t(n) 6 C · g(n)))}.
Avec cette dénition, on a bien (n2 /2 + 3n/2 + 1) ∈ O(n2 ), mais aussi (2n2 − 1) ∈ O(n2 ).
Puisque (2n2 − 1) ∈ O(n2 ), on a aussi (2n2 − 1) ∈ O(n3 ). En pratique, on prend la plus
petite fonction de référence r telle que fA (n) ∈ O(r(n)).
Une fois déni l'ensemble O(g) des fonctions qui croissent au plus aussi vite que g (avec
un sens désormais précis), il est logique de dénir de même l'ensemble Ω(g) des fonctions
qui croissent au moins aussi vite que g, ce qui permet en association avec O(g) d'encadrer
le comportement d'un algorithme.
On appelle ordre de grandeur minimal de complexité de g l'ensemble :
b {t : N → R+ | ∃(D, n0 ) · (D ∈ R+ et n0 ∈ N et ∀n·
Ω(g) =
(n > n0 ⇒ t(n) > D · g(n)))}.
Pour nir, on appelle ordre de grandeur exact de complexité de g l'ensemble Θ(g) déni
par l'intersection des deux ordres de grandeur maximal et minimal :
b t ∈ O(g)
t ∈ Θ(g) = et t ∈ Ω(g)
ou encore :
b {t : N → R+ | ∃(C, D, n0 ) · (C ∈ R+ et D ∈ R+ et n0 ∈ N et ∀n·
Θ(g) =
(n > n0 ⇒ D · g(n) 6 t(n) 6 C · g(n)))}.
82 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
f ∈ O(g) (resp. Ω(g), Θ(g)) se lit souvent f est en grand o de g (resp. en est en oméga
de g, en théta de g).
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Remarques
1. f ∈ O(1) signie qu'à partir d'un certain rang n0 il existe une constante C telle que
f(n) 6 C.
2. La fonction de complexité fA (n) de tout algorithme A est telle que fA (n) ∈ Ω(1).
3. Pour tout entier a > 2, on a : O(loga (n)) = O(log2 (n)) et Θ(loga (n)) = Θ(log2 (n))
puisque loga (n) = log2 (a) · log2 (n). En général, on prend la fonction de référence
log2 (n).
4. La formule de Stirling
√ n n
n! ≈ 2πn ·
e
permet d'écrire (en passant au logarithme) que log2 (n!) ∈ Θ(n · log2 (n)).
La complexité des algorithmes mis en évidence sera étudiée de façon systématique dans
chacun des chapitres suivants. On va donc se limiter à l'illustrer avec quelques-uns des
algorithmes rencontrés jusqu'ici. Il est aisé de statuer sur les algorithmes suivants :
nbpasmax(1) = 1 j n k
nbpasmax(n) = 1 + nbpasmax n>1
2
souvent un rôle prépondérant dans nombre d'algorithmes. Dès lors, elle peut être choisie
à juste titre comme opération élémentaire, d'autant plus lorsque aucune autre opération
ne s'impose pour l'algorithme considéré.
Chaque case du tableau ci-dessous indique la taille approximative des données que peut
traiter un algorithme dont la complexité exacte est en colonne, dans le temps donné en
ligne, pour un temps élémentaire d'instruction de 1µs. Par exemple, en une heure, un
algorithme en n3 peut traiter un problème de taille 1500. Une taille astronomique est
supérieure au nombre estimé d'atomes dans l'univers (1080 ).
Pour le même temps élémentaire d'instruction de 1µs, le tableau suivant donne le temps
qu'il faut à un algorithme de complexité exacte indiquée en colonne pour traiter des don-
nées de la taille donnée en ligne. Par exemple, un programme en n2 peut traiter un pro-
blème de taille 1000 en une seconde. Un temps astronomique est supérieur à un milliard
de milliard d'années.
Remarque nale Pour certains problèmes, la taille des données peut s'évaluer en fonc-
tion de plusieurs paramètres et non pas d'un seul. Par exemple, nous verrons au chapitre 9
le problème de distribution de skis qui consiste à choisir pour chaque skieur (parmi n)
la meilleure paire de skis (parmi m) à lui aecter. Les valeurs de n et de m sont indé-
pendantes, à la condition près que m > n. L'ordre de grandeur de complexité du meilleur
algorithme connu pour ce problème est O(n · m). Il est donc impossible de caractériser
cette complexité en fonction d'un seul paramètre : dans un cas comme celui-ci, la taille du
problème se mesure par une quantité fondamentalement multi-dimensionnelle et l'ordre de
grandeur de complexité s'exprime comme un polynôme à plusieurs variables.
2.2 Exercices
Dire si les armations suivantes sont vraies, pour toute fonction f de N dans R+ :
Dans cet exercice, on établit une propriété intéressante relative à la somme de deux
fonctions dont on connaît l'ordre de grandeur maximal ou exact. Ce résultat est utile
en pratique pour décider de l'ordre de grandeur maximal ou exact d'un programme
obtenu par composition séquentielle de plusieurs composants.
Le but principal de cet exercice est d'attirer l'attention sur le fait que l'on ne peut
pas tirer de conclusion hâtive lors de la manipulation des ordres de grandeur.
Il est fréquent que la fonction de complexité d'un algorithme soit donnée par un
polynôme. Dans cet exercice, on montre qu'une version simpliée sut pour exprimer
l'ordre de grandeur de complexité d'un tel algorithme.
f(n, k) = 1k + 2k + · · · + nk ∈ Θ(nk+1 ).
Dans l'exercice 23, page 86, on a vu une propriété de la somme de deux fonctions
de complexité. L'étendre à une somme multiple est légitime, encore faut-il prendre
garde à distinguer image d'une fonction et somme de fonctions.
Or :
X
n
i ∈ O(1 + 2 + · · · + n)
i=1
et
O(1 + 2 + · · · + n) = O(max({1, 2, . . . , n})) = O(n).
Donc :
n · (n + 1)
∈ O(n).
2
Où est l'erreur ?
1. constantes
2. x ∈ N1 et x = . . . et n ∈ N1 et n = . . .
3. variables
4. T ∈ 1 .. n + 1 → N1 et T = . . . et i ∈ N1
5. début
6. i ← 1 ; T [n + 1] ← x ;
7. tant que T [i] 6= x faire
8. i←i+1
9. n tant que ;
10. écrire(i)
11. n
27 - Q 2 Question 2. On fait l'hypothèse probabiliste selon laquelle : i) les entiers du tableau sont
tirés équi-probablement sans remise entre 1 et N, avec N > n, et ii) x est tiré équi-
probablement entre 1 et N. Quelle est la complexité en moyenne de l'algorithme ?
Cet exercice, qui traite d'un problème plus courant que sa présentation peut le lais-
ser supposer, montre comment deux stratégies a priori analogues peuvent produire
des algorithmes de complexités diérentes. On cherche ultimement une solution de
complexité linéaire, mais aussi une borne sur la constante de proportionnalité, ce qui
n'est pas usuel.
Une rivière, un épais brouillard, un gué dans les parages, mais est-il à gauche ou à droite,
et à quelle distance ? Avec ce brouillard, on voit l'entrée du gué uniquement quand on se
trouve juste devant. Comment faire pour traverser la rivière ?
Il faut explorer successivement à droite, à gauche, à droite, etc. en augmentant à chaque
fois la distance. Commencer par la gauche ou par la droite n'a pas d'importance, mais il
CHAPITRE 2. COMPLEXITÉ D'UN ALGORITHME 89
faut traiter les deux côtés de manière équilibrée et augmenter la distance régulièrement
an d'éviter de faire trop de chemin du côté où le passage ne se trouve pas.
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Une première méthode consiste à faire un pas à droite, revenir au point de départ, un
pas à gauche, revenir au point de départ, deux pas à droite, revenir au point de départ,
deux pas à gauche, revenir au point de départ, trois pas à droite, et ainsi de suite jusqu'au
succès selon le schéma ci-après :
Supposons que le gué se trouve à gauche à 15 pas. Pour le trouver, le nombre de pas
eectués est :
1 + (1 + 1) + (1 + 2) + (2 + 2) + (2 + 3) + · · · + (14 + 15) + (15 + 15)
soit au total 465 pas, plus de 30 fois les 15 pas strictement nécessaires.
De façon générale, appelons n la distance en pas entre le point de départ et le gué, c'est-
à-dire le nombre minimal de pas strictement nécessaires pour atteindre le gué.
Question 1. Donner le nombre N de pas eectués avec la méthode proposée si le gué est 28 - Q 1
situé à n pas à gauche (resp. à droite) du point de départ. Quelle est la classe de complexité
de cette méthode en termes de nombre de pas ?
On souhaite trouver une méthode fondamentalement plus rapide (au sens de la classe de
complexité) garantissant que le gué est trouvé en moins de 9n pas. Le défaut de la précé-
dente méthode réside dans une progression trop équilibrée et trop prudente . Augmenter
d'un pas à chaque fois (progression arithmétique) coûte nalement cher et on envisage de
doubler le nombre de pas à chaque passage (progression géométrique), ce que traduit le
schéma ci-dessous :
16 8 4 2 1 1 2 4 8 16
Question 2. Donner le nombre de pas eectués selon que le gué se trouve à neuf (resp. 15) 28 - Q 2
pas à gauche ou à droite du point de départ. Conclure.
Question 3. Vérier qu'avec une progression selon les puissances de 3 (au lieu de 2), on 28 - Q 3
n'atteint toujours pas l'objectif xé.
Question 4. Modier la méthode proposée dans la seconde question, toujours en progres- 28 - Q 4
sant selon les puissances de 2, de façon à ce que la contrainte sur le nombre de pas soit
satisfaite. Il est demandé de donner le nombre maximal de pas eectivement eectués ainsi
que leur nombre minimal, en fonction de n (distance en pas entre le point de départ et le
gué). Cette méthode permet-elle d'atteindre l'objectif xé avec une progression selon les
puissances de 3 ?
2.3 Solutions
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
On en déduit successivement :
∀n · (n > max({n1 , n2 }) ⇒ (g(n) + h(n)) 6 (C1 · f1 (n) + C2 · f2 (n)))
et D2 ∈ R+ et n2 ∈ N et ∀n·
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
∃(C2 , D2 , n2 ) · (C2 ∈ R+
(n > n2 ⇒ C2 · f2 (n) 6 h(n) 6 D2 · f2 (n))).
On en déduit :
donc :
et enn :
Réponse 1. On doit montrer que chacune des fonctions f et g est encadrée par deux 25 - R 1
termes de la forme K · n3 . On a d'abord f(n) ∈ Θ(n3 ), puisque
∀n · (n ∈ N1 ⇒ (1 · n3 6 f(n) 6 18 · n3 ))
Quant au polynôme g(n), 3n2 − 6n + 9 prend des valeurs positives pour tout n ∈ D (et
même pour tout n ∈ N). Donc, pour n ∈ D, g(n) 6 n3 . De plus :
n3 n3
g 0 (n) = g(n) − =2· − 3n2 + 6n − 9
3 3
92 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
est une fonction à valeurs positives (pas forcément entières) pour tout n ∈ D, donc
g(n) > n3 /3. Finalement, on a établi que pour n > 3 :
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
1
· n3 6 g(n) 6 1 · n3
3
Or, cette dernière expression est positive pour n > n0 = 2 + (2c/ap ). On conclut donc :
ap
∀n · n ∈ D et n > n0 ⇒ f(n) >
· np .
2
On va maintenant chercher un polynôme majorant f. Soit b la plus grande des valeurs |ai |,
pour i ∈ 0 .. p. On a :
Par ailleurs, on a :
f(n, k) = 1k + 2k + · · · + nk 6 n · nk = nk+1 .
Par ailleurs :
f(n, k) = 1k + 2k + · · · + (n − 1)k + nk
1k 1k 2k 2k (n − 1)k (n − 1)k nk nk
= + + + + ··· + + + +
2 2 2 2 2 2 2 2
1k + 1k + 2k + 2k + · · · + (n − 1)k + (n − 1)k + nk + nk
=
2
1k + nk + 2k + (n − 1)k + · · · + (n − 1)k + 2k + nk + 1k
= .
2
k k ! n n + 1 k
1 n+1 n+1
f(n, k) > + ··· + =
2 2 2 2 2
k+1
n
> .
2k+1
Au nal :
1
∀n · n ∈ N1 ⇒ · nk+1
6 f(n, k) 6 1 · nk+1
2k+1
f(n, k) ∈ Θ(nk+1 ).
Réponse 1. On a : 26 - R 1
X
n
n(n + 1) n2 n X
n
= 1 + 2 + ··· + n = = + donc = 1 + 2 + · · · + n ∈ O(n2 )
i=1
2 2 2 i=1
94 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
26 - R 2 Réponse 2. Le raisonnement suivi opère sur l'image de la fonction et non pas sur la
fonction elle-même. En eet, la décomposition de la fonction considérée en termes de
somme de fonctions conduit à l'expression :
X
n X
∞
f(n) = i= fi (n)
i=1 i=1
Xn
! !
1 (N − 1)! (N − n)(N − 1)! n
N!
i + (n + 1) = (n + 1) 1 − .
(N−n)! i=1
(N − n)! (N − n)! 2N
28 - R 1 Réponse 1. D'une manière générale, si le gué est situé n pas à gauche du point de départ,
la méthode proposée nécessite un nombre de pas égal à :
X
n−1
4· i + 3n = 4(n(n − 1))/2 + 3n = 2n2 + n.
i=1
2. Il s'agit d'arrangements de n objets parmi N et non de combinaisons, car l'ordre dans lequel les
objets arrivent importe. Par exemple, il y a 60 tableaux diérents quand N = 5 et n = 3.
CHAPITRE 2. COMPLEXITÉ D'UN ALGORITHME 95
S'il est distant de n pas sur la droite, le nombre de pas devient :
X
n−1
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
16 8 2 1 4 16
Il faut tout d'abord prendre garde au fait que, contrairement aux deux méthodes pré-
cédentes, la position eective du gué à gauche du point de départ n'est pas forcément
un handicap. En eet, si le gué se trouve à cinq pas à gauche, il faut faire au total
(1 + 1) + (2 + 2) + (4 + 4) + 5 = 19 pas, alors que, s'il est situé à cinq pas à droite, il
faudra faire (1 + 1) + (2 + 2) + (4 + 4) + (8 + 8) + 5 = 35 pas. Dans les deux cas, le nombre
de pas se révèle inférieur à 9 · 5 = 45, ce qui est de bon augure.
Calculons tout d'abord le nombre N de pas à faire quand le gué est à gauche du point de
départ. Si le gué est à un (resp. deux) pas à gauche, on l'atteint en trois (resp. quatre) pas
et la contrainte est satisfaite puisque 3 < 9 · 1 et 4 < 9 · 1. S'il est situé à une distance n
supérieure à deux pas, on a alors :
∃p · (p ∈ N1 et 22p−1 < n 6 22p+1 ).
96 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
En eet, il faut eectuer des allers-retours alternativement à gauche et à droite (ou inver-
sement) tant que l'on n'atteint pas le gué. En développant, il vient :
N
= formule 2.2
2(20 + 21 + · · · + 22p ) + n
= somme d'une suite géométrique
2(22p+1 − 1) + n
= arithmétique
8 · 22p−1 + n − 2
= récriture
2 · 22p+1 + n − 2.
Étudions les valeurs prises par N pour n ∈ 22p−1 + 1 .. 22p+1 avec p > 0 :
si n = 22p+1 , N = 3 · 22p+1 − 2 = 3n − 2,
si n = 22p+1 − 1, N = 3 · 22p+1 = 3n,
si n = 22p+1 − 2, N = 3 · 22p+1 + 2 = 3n + 2,
...
si n = 22p−1 + 2, N = 8 · 22p−1 + 22p−1 + 2 − 2 = 9n − 18
si n = 22p−1 + 1, N = 8 · 22p−1 + 22p−1 + 1 − 2 = 9n − 10.
On voit donc que, dans l'intervalle 22p−1 + 1 .. 22p+1 (p > 0), on a : 3n − 2 6 N 6 9n − 10.
Puisque quand le gué est situé à un seul pas à gauche, on a N = 3 (= 9n − 6), il apparaît
que : ∀n > 1, 3n − 2 6 N 6 9n − 6. Ceci montre que, d'une part le nombre de pas eectués
est toujours inférieur à 9n comme demandé, d'autre part il varie dans la proportion de 1
à 3.
Le même résultat est obtenu dans le cas où le gué se trouve à n pas à droite du point
de départ (on étudie les valeurs de n encadrées par des puissances de 2 paires après avoir
traité le cas n = 1 de façon séparée, pour lequel on a N = 1).
On en déduit que l'objectif xé n'est pas atteint puisque le nombre de pas eectués peut
dépasser 9n, mais que la borne inférieure de ce nombre est abaissée par rapport à celle
obtenue avec une progression géométrique de raison 2.
CHAPITRE 2. COMPLEXITÉ D'UN ALGORITHME 97
Complément
Nous allons maintenant montrer que, si l'on s'en tient aux progressions géométriques,
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
choisir celle de raison 2 est optimal. À cette n, on se place dans un cadre continu plutôt
que discret et on évalue les distances, non plus en nombre de pas, mais en unités divisibles,
comme le mètre. On considère donc que le gué est à distance n mètres du point de départ,
où n est cette fois un nombre réel positif. Si on explore du côté du gué et que l'on rebrousse
chemin après avoir parcouru une longueur strictement inférieure à n, le gué n'est par
dénition pas encore atteint.
Notons E (réel supérieur à 1) la raison de la progression géométrique. La stratégie consiste
donc à eectuer 1.0 mètre à droite, E mètres à gauche, E2 mètres à droite, etc. On va
supposer que le gué est à droite, à distance supérieure ou égale à 2.0 mètres, mais cela
n'importe pas comme on l'a vu auparavant. Examinons quels sont les cas les pires et les
meilleurs, du point de vue du rapport N/n, où N est, rappelons-le, la distance (cette fois
en mètres) parcourue avant de trouver le gué.
Prenons par exemple E = 3.0 et n = 9.01. On commence par faire un mètre à droite, puis
on rebrousse chemin jusqu'au point de départ (encore un mètre), puis on va à gauche à
la distance E = 3.0, on revient au départ (jusque là, on a parcouru sept mètres). On va
maintenant faire neuf mètres à droite et rater de très peu le gué. On rebrousse chemin
sur les neuf mètres (total provisoire : 25.0), on fait un aller et retour à gauche et on re-
vient au point de départ pour un total de (25.0 + 2 · 27.0) = 79.0 mètres. Plus que 9.01
mètres et on aura atteint le gué. On a alors parcouru une distance totale de N = 88.01
mètres, avec un rapport N/n = 9.768 · · · . Imaginons maintenant que le gué n'ait pas été à
n = 9.01 mètres, mais à dix mètres. On aurait parcouru N = 89.0 mètres, pour un rapport
N/n de 8.9, qui aurait été meilleur que le précédent. Plus le gué aurait été loin à droite, à
une distance inférieure ou égale à 81.0 mètres, plus ce rapport aurait diminué. Le gué se
trouve ici à droite, à une distance n telle que E2 < n 6 E4 . D'une manière générale, s'il
est à droite, il existe un entier p tel que E2p < n 6 E2p+2 et le cas le pire (celui qui maxi-
mise le rapport N/n) est quand n = E2p + avec aussi petit que désiré. Le meilleur cas
est quand n = E2p+2 . La preuve de la validité de ces deux armations est laissée au lecteur.
Quelle est la meilleure valeur de E pour minimiser cette distance dans le pire cas ? En
dérivant le terme (2E2 + E − 1)/(E − 1), on voit qu'il est minimum pour E = 2.0 et que dans
ce cas : N = 9n − 10.
On suppose le gué à droite à distance n > 2.0. Dans le meilleur cas (n = E2p ), le nombre
de pas vaut alors :
E+1 2
N = 2(1 + E + E2 + · · · + E2p−1 ) + E2p = n− .
E−1 E−1
98 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
La gure suivante trace les courbes du rapport N/n en fonction de E, dans le cas le pire
(courbe du dessus), pour petit par rapport à n, et dans le cas le meilleur (courbe du
dessous).
On peut remarquer que remplacer E par E/(E − 1) dans le coecient (2E2 + E − 1)/(E − 1)
laisse ce coecient inchangé. Il en résulte des valeurs limites (notées L) de N/n identiques,
conrmées par les expérimentations menées par les auteurs dont un extrait gure dans le
tableau ci-dessous :
E 1.2 1.25 1.4 1.5 1.8 2 2.25 3 3.5 5 6
L 15.4 13.5 10.8 10 9.1 9 9.1 10 10.8 13.5 15.4
CHAPITRE 3
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
M. Kundera
....par invariant
Il importe de noter que les deux premiers composants (l'invariant et la condition d'arrêt)
portent sur des situations tandis que les deux suivants (la progression et l'initialisation)
concernent des actions. À la lecture des points A, B et C, il apparaît clairement que
l'invariant est une pièce centrale puisqu'apparaissant dans les éléments A, B-a, B-b et C.
Il constitue la clé de voûte de la conception des boucles, en d'autres termes la colle qui lie
les autres constituants entre eux. C'est par son identication que va débuter la construction
d'une boucle.
La gure 3.1, page 101, reprend et résume les diérents points abordés précédemment.
Le codage de la boucle générique correspondante se présente comme suit :
1. initialisation ;
2. tant que non condition d'arrêt faire
3. progression
4. n tant que
Cette notation minimale ne fait pas apparaître dans le code la précondition, la postcon-
dition, l'invariant et l'expression de terminaison. Les deux derniers étant assez largement
développés dans la phase de construction, dans la suite nous ne ferons généralement gu-
rer dans le code que les deux premiers sous forme de commentaires. La complexité d'une
boucle simple s'exprime en termes de conditions à évaluer ou éventuellement d'une opé-
ration caractéristique apparaissant dans son corps. La complexité est linéaire dans le cas
des boucles pour sauf en cas d'appel de procédure ou fonction dans la condition d'arrêt.
En présence de boucles pour imbriquées, la complexité est généralement polynomiale. Ce-
pendant, il est fréquent qu'une itération ne soit que l'un des constituants de la solution en
cours de construction et l'évaluation de conditions (liée au contrôle de la boucle) sera bien
souvent retenue comme opération élémentaire.
CHAPITRE 3. SPÉCIFICATION, INVARIANTS, ITÉRATION 101
précondition postcondition
de la boucle de la boucle
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
initialisation
et
instaure
condition
invariant
d'arrêt
et
non
progression
conserve
Précondition : ( A ∈ N) et (B ∈ N1 ).
(A = B · q + r) et (0 6 r < B).
(A = B · q + r) et (0 6 r)
et comme condition d'arrêt : r < B. Il reste à exprimer les actions liées à la progression
et l'initialisation, ainsi que l'expression de terminaison. Concernant la progression, il sut
d'incrémenter q de 1 et de décrémenter r de la valeur B pour rétablir l'invariant (ce qui
est possible puisque, la condition d'arrêt n'étant pas satisfaite, on a r > B). L'invariant est
instauré à partir de la précondition en aectant 0 à q et A à r. Quant à l'expression de
terminaison, on observe que l'expression (A − q · B) vaut A après l'initialisation et décroît
de B tout en restant positive après chaque pas de la progression (elle est éventuellement
102 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
nulle après la dernière itération). À partir des cinq constituants mis en évidence et du code
générique, on déduit le programme ci-après :
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
1. constantes
2. A ∈ N et A = . . . et B ∈ N1 et B = ...
3. variables
4. q ∈ 0 .. A et r ∈ 0 .. B − 1
5. début
6. /% PRE : (A ∈ N) et (B ∈ N1 ) %/
7. q ← 0; r ← A;
8. tant que non(r < B) faire
9. q ← q+1; r ← r−B
10. n tant que ;
11. /% POST : (A = q · B + r) et (r > 0) et (r < B) %/
12. écrire(le quotient de la division de , A, par , B, est , q, le reste est , r)
13. n
On notera que si A = 0 on n'entre pas dans la boucle tant que (c'est le seul cas
d'ailleurs). De plus, si A est un multiple de B, le reste r vaut 0.
Si, dans l'exemple précédent, le problème était susamment simple pour être traité sans
diculté, il n'en va pas toujours ainsi. Il faut assez souvent reformuler la précondition
et/ou la postcondition, et ceci doit se faire de façon à garantir la correction du programme
construit in ne. Nous passons en revue quelques techniques permettant de faire des trans-
formations légales.
Nous avons vu que construire un programme fondé sur une boucle se fait en décomposant le
problème en cinq sous-problèmes. Il existe une autre forme de décomposition fréquemment
utilisée, à savoir celle fondée sur la règle de la séquentialité qui stipule que si {P} prog1 {R}
et {R} prog2 {S} alors {P} prog1 ; prog2 {S}. Dans cette règle, le ; est l'opérateur de
séquentialité ; {R} est appelée situation intermédiaire. Cette règle peut également être ap-
pliquée pour dire que, si l'on recherche un programme spécié par le couple (P, S), il sut
de trouver une situation intermédiaire R et deux programmes prog1 et prog2 tels que :
i) {P} prog1 {R} et ii) {R} prog2 {S}. La composition séquentielle de prog1 et de prog2 est
une solution au problème initial spécié par (P, S).
Prenons un exemple : on souhaite savoir si l'élément d'indice K du tableau T est son unique
minimum. On veut construire le programme spécié par :
Postcondition : infk = (T [K] est strictement inférieur à tous les autres éléments).
3. Progression i←i+1
4. Initialisation i←1
5. Terminaison N+1−i
2. N ∈ N1 et N = ... et T ∈ 1 .. N → N et T = [. . .] et K ∈ 1 .. N et K=
...
3. variables
4. i ∈ 1 .. N + 1 et infk ∈ B
5. début
6. /% première partie : Boucle %/
7. /% PRE : (T est un tableau constant de N entiers naturels) et
(N > 1) et (K constant) et (K ∈ 1 .. N) %/
8. i ← 1;
9. tant que non((i = N + 1) ou sinon ((i 6= K) et (T [i] 6 T [K]))) faire
10. i←i+1
11. n tant que ;
12. /% POST : i est l'indice de l'intervalle 1 .. N diérent de K tel que
T [i] 6 T [K] (s'il existe un tel i) ou sinon (N + 1) %/
13. /% deuxième partie : PartComp %/
14. infk ← (i = N + 1) ;
15. si infk alors
16. écrire(l’élément d’indice, K, du tableau, T , est son unique minimum)
17. sinon
18. écrire(l’élément d’indice, K, du tableau, T, n’est pas son unique
minimum
19. n si
20. n
La notion de renforcement du prédicat pred s'entend souvent dans un sens logique, c'est-
à-dire que l'on considère un prédicat pred0 (renforçant pred) car satisfaisant la propriété :
pred0 ⇒ pred. Cette démarche peut se révéler particulièrement intéressante lorsque l'on se
trouve face à la spécication (P, Q) et qu'il est plus facile de construire le programme prog0
tel que {P} prog0 {Q0 } avec Q0 ⇒ Q (notamment si Q0 est déni par l'ajout d'un conjoint
à Q), que le programme prog tel que {P} prog {Q}.
De façon duale, on peut parler d'aaiblissement de prédicat en considérant un prédicat
pred00 (aaiblissant pred) vériant la propriété : pred ⇒ pred00 . Cette démarche présente
un intérêt quand, face à la spécication (P, Q), il est plus facile de construire le programme
prog00 tel que {P00 } prog00 {Q} avec P ⇒ P00 que le programme prog tel que {P} prog {Q}.
C'est notamment le cas si P00 est obtenu par suppression d'un conjoint de P.
On considère ici un second type de renforcement d'un prédicat dans lequel l'espace d'états
du problème (l'ensemble de ses variables) s'enrichit d'(au moins) une variable. Par exemple,
considérons un tableau T [1 .. N] (N > 1) d'entiers naturels et le prédicat P =
b s représente
la somme des éléments du tableau T . Une formulation équivalente de P est
b (s représente la somme des i premiers éléments de T ) et (i ∈ 1 .. N) et (i = N) .
P0 =
La variable i a été introduite et on a un renforcement du prédicat P initial. Le principal
CHAPITRE 3. SPÉCIFICATION, INVARIANTS, ITÉRATION 105
intérêt de cette démarche réside dans le fait qu'elle introduit au moins une conjonction qui
va pouvoir être exploitée pour découvrir un invariant pour le problème considéré (voir par
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
La programmation est une activité dirigée par le but. La recherche de l'invariant d'une
boucle n'échappe pas à cette règle et les trois heuristiques proposées ci-dessous se fondent
sur la relation qui lie postcondition et invariant. Nous étudions successivement trois tech-
niques de base concurrentes. La première, l'éclatement de la postcondition, fait l'hypothèse
que la postcondition se présente sous la forme d'une conjonction. Comme c'est rarement
le cas, il est fréquemment nécessaire de procéder à un renforcement préalable de la post-
condition de façon à exhiber une ou plusieurs conjonctions. La seconde, l'hypothèse du
travail réalisé en partie, conduit de par sa nature à un renforcement implicite de la post-
condition par l'introduction de variables. La dernière heuristique concerne le renforcement
de la postcondition suite à celui de l'invariant.
Compte tenu de la propriété associée à la relation A (voir page 100), il est légitime,
lorsque la postcondition s'exprime comme une conjonction, d'identier l'un des conjoints
à l'invariant et le second à la condition d'arrêt. La démarche est identique dans le cas où
la postcondition s'exprime par plusieurs conjonctions. On peut alors chercher d'une part
à isoler un ou plusieurs conjoint(s) pour constituer la condition d'arrêt, d'autre part à
mettre de côté le(s) conjoint(s) restant(s) pour former l'invariant :
Postcondition : B1 et B2 et . . . et Bn
Condition d'arrêt : Bi
Invariant : B1 et B2 et . . . et Bi−1 et Bi+1 et ... et Bn
En supposant que l'on n'isole qu'un seul conjoint, comment va-t-on choisir parmi les n pos-
sibilités ? Il n'y a pas de réponse systématique à cette question. On peut cependant proposer
les heuristiques suivantes :
On illustre la démarche avec l'exemple suivant, où l'on recherche le premier zéro d'un
tableau de nombres. On veut construire le programme spécié par :
106 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
Postcondition : La variable i désigne le zéro de T ayant le plus petit indice (le zéro le
plus à gauche ).
On remarque que, puisqu'il existe au moins un zéro dans T , c'est donc que N > 1. Puisque
cet algorithme exige de parcourir tout ou partie du tableau, on va construire une itération.
De plus, la postcondition ne se présente pas sous forme conjonctive. On va la renforcer
dans cet objectif en remplaçant une expression exp (ici N) par une variable v (ici i), puis
en ajoutant le conjoint (v = exp). Dans la suite, ce traitement est dénommé mise sous
forme constructive . On reformule la postcondition initiale en :
1. Invariant Les deux premiers conjoints sont faciles à établir et on les prend donc pour
constituer l'invariant, soit :
1 i N
T
6= 0
2. Condition d'arrêt Il sut de prendre le conjoint écarté, soit : T [i] = 0. On note que
ce prédicat ne contient pas de quanticateurs ; sa négation pourra donc être intégrée
au programme nal.
Une solution pour la progression consiste à déplacer i d'une position vers la droite
par l'aectation : i ← i + 1. L'invariant est bien satisfait par la nouvelle situation
puisqu'il n'y a pas de zéro dans T [1 .. i − 1] et qu'il doit y en avoir un après (selon la
précondition) donc i 6 N (d'où i ∈ 1 .. N).
CHAPITRE 3. SPÉCIFICATION, INVARIANTS, ITÉRATION 107
4. Initialisation L'initialisation est spéciée par :
Précondition : et
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
1/i N
T
Dans la section 3.7, plusieurs exercices sont proposés dans lesquels la postcondition initiale
n'est pas exprimée sous forme conjonctive. Dans ce type de situation très fréquent en
pratique, la postcondition doit d'abord être mise sous forme constructive , c'est-à-dire
exprimée comme une conjonction qui pourra être éclatée.
L'une des caractéristiques de l'invariant est qu'il s'agit d'une propriété qui se retrouve
identique à elle-même à chaque pas de boucle. Il est légitime d'exploiter cette particularité
pour rechercher un invariant.
108 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
En faisant l'hypothèse qu'une partie du travail a déjà été réalisée, on peut se poser la
question :
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
dont la réponse est souvent l'invariant recherché. Cette technique est illustrée avec l'exemple
classique et simple dit du drapeau monégasque , dont l'énoncé est le suivant. La
situation initiale est un tableau T [1 .. N] (N > 0) dont les éléments sont de couleur blanche
ou rouge et forment le sac S. La situation nale est un tableau formant le même sac S, dans
lequel les éléments blancs occupent la partie gauche et les éléments rouges la partie droite.
On s'impose de passer de la situation initiale à la situation nale en une seule boucle, qui
parcourt le tableau de gauche à droite. Les seuls changements du tableau T s'eectuent
par l'opération d'échange des éléments d'indice i et j de T (Échanger (i, j)), ce qui garantit
la préservation du sac de valeurs S initial.
On va chercher un invariant en admettant que le travail est partiellement eectué et que
l'on a atteint la conguration décrite dans la gure 3.2, page 108.
1 i k N
T Blanc ? Rouge
2. Condition d'arrêt La boucle est terminée quand k = i−1. On a mis en évidence (voir
item ii) qu'alors la conjonction de l'invariant et de la condition d'arrêt implique la
postcondition.
4. Initialisation
Les opérations relatives à l'initialisation ont été évoquées dans l'item i,
précédemment, et consistent donc à faire les deux aectations : i ← 1 et k ← N.
1. constantes
2. N ∈ N et N = . . . et T ∈ 1 .. N → N et T = [. . .]
3. variables
4. i ∈ 1 .. N et k ∈ 1 .. N
5. début
6. /% PRE : T [1 .. N] est un tableau dont les éléments sont de couleur
blanche ou rouge %/
7. i ← 1; k ← N;
8. tant que k 6= i − 1 faire
9. si T [i] = Blanc alors
10. i←i+1
11. sinon
12. Échanger (i, k) ; k ← k − 1
13. n si
14. n tant que ;
15. /% POST : les éléments blancs de T occupent la partie gauche et les
éléments rouges de T la partie droite %/
16. écrire(T )
17. n
Cet algorithme est en Θ(N) comparaisons (N comparaisons portant sur les valeurs de T
et N pour le contrôle de la boucle). Il demande autant d'échanges qu'il y a d'éléments de
couleur rouge (quelle que soit leur position initiale) ; il est donc en O(N) échanges.
Comme dans la majorité des problèmes, ici l'invariant n'est pas unique. Le lecteur intéressé
pourra rééchir à celui qui dérive de la situation du travail réalisé en partie donnée dans
la gure 3.3.
110 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
1 i k N
Blanc Rouge ?
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Fig. 3.3 Autre situation dans laquelle le travail est réalisé en partie.
(P et B) ⇒ R.
(P et P0 et B) ⇒ (P et B)
⇒ on a soit (P et B) = R, soit au pire (P et B) ⇒ R
(P et P0 et B) ⇒ R.
3. On fait l'hypothèse que cette valeur est disponible (dans une variable introduite à
cette n). Ceci conduit à adjoindre un nouveau conjoint à l'invariant existant.
Nous allons développer cette démarche pour calculer la somme des éléments d'un tableau
situés à gauche de sa valeur maximale (supposée unique). On veut construire le pro-
gramme constitué d'une seule boucle spécié par :
Précondition : Soit (T un tableau d'entiers relatifs constant injectif (toutes les valeurs
de T sont diérentes) de N éléments) et (N > 1).
1 m N
T
X
m−1
s= T [j]
j=1
soit plus formellement, et en ajoutant les domaines de variation des variables, la postcon-
dition :
X
m−1
!
(m ∈ 1 .. N) et (T [m] = maxj∈1..N T [j]) et (s ∈ Z) et s = T [j] .
j=1
1 m i N
T
X
m−1
s= T [j]
j=1
Étudions d'abord le domaine de variation des variables i, m et s. Pour que m puisse prendre
une valeur, il faut que le sous-tableau T [1 .. i − 1] ne soit pas vide, ce qui impose que i ne
prenne pas la valeur 1. Donc, i varie sur l'intervalle 2 .. N + 1, tandis que m ∈ 1 .. i − 1 et
s ∈ Z. En ajoutant le domaine de variation de ces variables, on obtient :
1. Invariant Les cinq premiers conjoints sont faciles à établir, on les retient pour consti-
tuer l'invariant :
X
i−1
!
(T [m] = max T [j])
j∈1..i−1
et v= T [j]
j=1
1 m i N
T
X
m−1
s= T [j]
j=1
Progression
PostconditionP : (i ∈ 2 .. N + 1) et (m ∈ 1 .. i P
− 1) et (T [m] = maxj∈1..i−1 T [j]) et
j=1 T [j]) et (v ∈ Z) et (v =
(s ∈ Z) et (s = m−1 j=1 T [j]).
i−1
Initialisation
PostconditionP : (i ∈ 2 .. N + 1) et (m ∈ 1 .. i P
− 1) et (T [m] = maxj∈1..i−1 T [j]) et
(s ∈ Z) et (s = m−1
j=1 T [j]) et (v ∈ Z) et (v = j=1 T [j]).
i−1
On donne la valeur 2 à i, ce qui impose aux autres variables les contraintes suivantes
(on peut le vérier par substitution) :
(s = T [1]) et (v = T [1]) et (m = 1).
La recherche linéaire est une classe d'algorithmes où, étant donné un prédicat P(i) tel qu'il
existe un ensemble non vide de valeurs le satisfaisant, on recherche le plus petit élément
de cet ensemble.
La recherche linéaire bornée s'apparente à la recherche linéaire, mais ici l'ensemble des
solutions peut être vide. En général, le résultat fourni en cas d'échec est soit une valeur
conventionnelle située en dehors du domaine de dénition de P, soit un booléen qui signale
l'échec.
3.5.1 Un exemple
Précondition : et et et
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
La présence d'une quantication laisse augurer un problème quant à son évaluation telle
quelle ; on procède à un second renforcement en introduisant la variable sp calculant la
somme partielle des (i − 1) premiers éléments de T , d'où :
P
Postcondition : (i ∈ 1 .. N + 1) et (sp = i−1j=1 T [j]) et (sss = (sp > S)) et (i = N + 1).
1. Invariant Les trois premiers conjoints sont faciles à établir. On les conserve pour
constituer l'invariant :
X
i−1
!
(i ∈ 1 .. N + 1) et sp = T [j] et (sss = (sp > S)).
j=1
Il est facile de constater que l'arrêt pourrait avoir lieu dès que sss prend la valeur vrai,
ce qui serait susceptible de limiter le nombre de passages dans la boucle et donc la com-
plexité au pire. Cette remarque conduit à modier la condition d'arrêt et la progression
de la construction précédente. On va modier la condition d'arrêt en conséquence dans la
construction d'une nouvelle boucle.
CHAPITRE 3. SPÉCIFICATION, INVARIANTS, ITÉRATION 115
1. Invariant Il est inchangé.
3. Progression La seconde aectation de la progression est (sss ou (sp > S)), dont l'éva-
luation se fait dans le contexte de la précondition de la progression (impliquant que
sss est faux), d'où :
1. constantes
2. N ∈ N et N = . . . et T ∈ 1 .. N → N et T = [. . .] et S ∈ N1 et S = ...
3. variables
4. i ∈ 1 .. N + 1 et sss ∈ B et sp ∈ N
5. début
6. /% PRE : (T est un tableau de N entiers naturels) et (N > 0) et (S constant) et
(S ∈ N1 ) %/
7. i ← 1 ; sss ← faux ; sp ← 0 ;
8. tant que non((i = N + 1) ou sss) faire
9. sp ← sp + T [i] ; sss ← (sp > S) ; i ← i + 1
10. n tant que ;
XN
!
11. /% POST : sss = T [j] > S %/
j=1
12. écrire(sss)
13. n
En termes de comparaisons, la complexité de cet algorithme est en O(N).
Il arrive fréquemment que l'on soit confronté à des problèmes ressemblant au précédent et
il est intéressant de dégager un patron de programmation pour la recherche linéaire bornée
pouvant être instancié plutôt que de procéder à une construction ex nihilo.
On se place dans le cadre de la recherche du premier élément (peu importe la structure
utilisée, ensemble, sac, tableau, etc.) parmi N rendant vraie une propriété P ; j contient
l'identité de cet élément ou (N + 1) s'il n'existe pas. On suppose de plus que la propriété P,
notée PL(j), est locale à l'élément j, au sens où son évaluation ne dépend pas des élé-
ments examinés avant lui. Enn, il peut arriver que, contrairement à l'exemple précédent,
la propriété PL ne puisse être évaluée pour j = N + 1. En conséquence, la condition d'arrêt
utilise alors une disjonction court-circuit . On a donc le modèle de programme suivant.
Ce patron est utilisé dans les exercices 34, page 120, et 41, page 128.
116 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
1. constantes
2. N ∈ N et N = . . .
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
3. variables
4. j ∈ 1 .. N + 1 et PL ∈ B et ...
5. début
6. /% PRE : . . . %/
7. j ← 1; ...
8. invariant
9. ...
10. terminaison
11. N+1−j
12. tant que non((j = N + 1) ou sinon PL) faire
13. j←j+1
14. n faire ;
15. /% POST : . . . %/
16. si j = N + 1 alors
17. écrire(pas d’élément . . . )
18. sinon
19. écrire(l’élément , j, . . . )
20. n si
21. n
Un premier point clé de la construction d'une boucle est qu'elle débute par la recherche
d'un invariant autour duquel s'articulent les autres composants de la boucle : initialisation,
condition d'arrêt, progression et terminaison. La notion d'invariant précise les relations
qu'entretiennent les variables impliquées dans la boucle.
Il n'existe pas de recette permettant de trouver à coup sûr un invariant, mais nous re-
commandons de le dériver de la postcondition du programme à construire, exprimant
la situation dans laquelle on souhaite se trouver à l'issue de l'exécution de la boucle. La
conjonction de l'invariant et de la condition d'arrêt doit impliquer logiquement la post-
condition. Par suite, une heuristique de découverte d'un invariant consiste à éclater la
postcondition an de faire apparaître d'une part un invariant, de l'autre une condition
d'arrêt. On peut renforcer la postcondition par l'introduction de nouvelles variables an
de faciliter un tel éclatement. Dans la mesure où un invariant constitue une propriété sa-
tisfaite à chaque pas de la boucle, on peut également le trouver en supposant le travail
réalisé en partie et en formalisant la situation atteinte.
Pour sa part, la précondition de la boucle spécie la situation avant que la boucle ne
démarre. Le rôle de l'initialisation est d'instaurer l'invariant et donc de faire passer de la
précondition à l'invariant. La progression doit préserver l'invariant tout en faisant avan-
cer la résolution du problème. Enn, pour s'assurer de la terminaison de la boucle, une
expression entière positive ou nulle est attachée à l'évolution de la boucle dont on montre
la décroissance à chaque pas.
CHAPITRE 3. SPÉCIFICATION, INVARIANTS, ITÉRATION 117
3.7 Exercices
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Cet exercice met en évidence le fait qu'il est possible de raisonner sur un algorithme
(ou un programme) donné en identiant son invariant.
Une boîte de conserve contient une certain nombre B de haricots blancs et un certain
nombre R de haricots rouges (B + R > 1). On dispose d'une réserve de haricots rouges
susante pour réaliser l'opération suivante tant que c'est possible :
On prend deux haricots au hasard dans la boîte
si ils sont de la même couleur alors
on les jette ; on remet un haricot rouge dans la boîte
sinon
on jette le haricot rouge ; on replace le haricot blanc dans la boîte
n si
3. Progression :
1. si T [i] > sup alors
2. sup ← T [i]
3. n si ;
4. i ← i + 1
5. Terminaison : (N + 1 − i)
118 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
Question 2.
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
32 - Q 1 Question 1. Proposer les éléments d'une boucle unique répondant à cette spécication,
en appliquant l'hypothèse du travail réalisé en partie.
de conception.
On présente maintenant un programme réalisant un tri. S'il ne gure pas parmi les
tris ecaces , il n'en demeure pas moins intéressant au plan pédagogique. De plus,
à la diérence de l'exercice précédent, il s'appuie sur l'imbrication de deux boucles
avec une démarche se révélant ici simple et progressive.
Postcondition : (T est trié par ordre croissant) et (S est le sac des valeurs contenues
dans T ).
Le second conjoint de la postcondition exprime que globalement les valeurs présentes dans
le tableau ne changent pas. On va en assurer le respect en ne modiant T qu'avec la
procédure Échanger(i, j) qui échange les éléments de T d'indices respectifs i et j. De cette
façon, on peut dénitivement abandonner ce conjoint.
Si l'on suppose le travail réalisé en partie, on est dans la situation représentée ci-dessous :
1 i N
T
trié
On entrevoit déjà que la progression vise à faire en sorte que T [1 .. i] soit trié. On a le
choix entre : i) insérer T [i] à sa place dans T [1 .. i] et ii) ne pas modier T [1 .. i − 1] en
supposant toutes les valeurs de T [i .. N] supérieures ou égales à celles de T [1 .. i − 1]. La
première option correspond au tri par insertion ; nous allons choisir la seconde, appelée tri
par sélection, car il faut sélectionner la plus petite valeur de T [i .. N].
On illustre ici l'utilisation du patron proposé pour la recherche linéaire bornée (voir
section 3.5, page 113) sur un exemple simple.
Soit T [1 .. N] (N > 0), une chaîne de caractères donnée. T est un palindrome si le mot (ou
phrase sans espace) qu'elle représente s'écrit de la même façon de gauche à droite et de
droite à gauche.
Schématiquement, la postcondition se présente comme suit (la zone du milieu n'est pas
vide puisque qu'elle contient au moins un exemplaire de V ) :
1 p q N
<V =V >V q>p
Toutes les modications de T vont s'eectuer par des échanges entre des valeurs de T au
moyen de la procédure Échanger(i, j) où i et j désignent l'indice d'un élément de T . Par
conséquent, comme dans l'exercice 33, page 119, on peut abandonner le premier conjoint
de la postcondition. La complexité de la (des) solution(s) se fait en dénombrant les appels
à la procédure Échanger. Tout d'abord, formalisons l'expression de la postcondition :
Cette version de la postcondition n'est pas utilisable telle quelle pour un éclatement. On
la transforme (renforce) en remplaçant les variables de quantication existentielle p et q
par les variables de programmation b et w (voir section 3.3.3, page 104), d'où :
36 - Q 1 Question 1. Compléter le schéma ci-après an d'exhiber un invariant sur la base de l'hy-
pothèse du travail réalisé en partie.
1 i j N
Exercice 37 Le Me zéro ◦ •
•
Notons tout d'abord que la précondition implique que N > M. Le quanticateur # dénote
le dénombrement. Ainsi :
Bien que cette postcondition soit sous forme constructive, on peut penser que la présence
de la quantication de dénombrement va être gênante pour identier un invariant ecace.
Postcondition : (S est le sac des valeurs contenues dans T ) et ((les positions d'indice
pair contiennent les valeurs paires) ou (les positions d'indice impair contiennent les
valeurs impaires)).
Cependant, il ne s'agit toujours pas d'une forme conjonctive et il faut à nouveau renforcer
cette version. Pour ce faire, posons :
(p ∈ 2 .. 2N + 2) et (p est pair) et
(P et (p = 2N)) ou (Q et (i = 2N + 1)).
A et B et (C ou D) ⇒ (A et C) ou (B et D).
38 - Q 2 Question 2. Donner les éléments de la boucle construite à partir de cette nouvelle post-
condition.
38 - Q 5 Question 5. Justier le fait que l'on peut aussi construire une boucle à partir de la post-
condition :
La postcondition n'est pas sous forme conjonctive ; pour y parvenir, on peut introduire la
variable i de la manière suivante :
Première tentative
Cette formulation suggère un invariant et une condition d'arrêt :
1. Invariant Les deux premiers conjoints sont faciles à établir, on les conserve pour consti-
tuer l'invariant :
1 i N
T 0 ········· 0
lg
qu'à incrémenter i. Sinon (T [i] = 0), il faut exprimer que T [i] peut faire partie de la
plus longue chaîne de zéros du sous-tableau T [1 .. i] (avant de rétablir l'invariant),
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
ce qui peut se faire en calculant, par une boucle rétrograde, la longueur p de la plus
longue chaîne de zéros consécutifs s'achevant en i. Mais on remarquera que tous les
éléments de T [1 .. i − 1] ont déjà été examinés et qu'il serait dommage de les examiner
à nouveau (même en partie). On va supposer cette longueur p déjà connue, ce qui
conduit à un nouvel invariant, issu du précédent par renforcement, en lui adjoignant
cette hypothèse. Le prix à payer est la reconstruction de la boucle sur la base du
nouvel invariant.
Seconde tentative
On eectue la construction fondée sur la suggestion précédente.
39 - Q 4 Question 4. Proposer et justier une autre condition d'arrêt susceptible d'améliorer l'ef-
cacité de la boucle.
Cet exercice sur la recherche d'un élément majoritaire dans un sac est également
abordé dans le chapitre Diviser pour Régner (voir exercice 105, page 465). La
solution développée ici fait appel à une technique originale. En eet, on exploite fré-
quemment l'heuristique éprouvée qui consiste à renforcer la postcondition an d'obte-
nir une bonne ecacité temporelle. Ici, au contraire, on va aaiblir la postcondition
an d'obtenir un algorithme simple (mais ne fournissant qu'une solution possible
devant être conrmée ). La solution obtenue est concise, ecace et élégante.
Un algorithme naïf
Il est aisé de spécier un algorithme naïf, au mieux en Θ(N) et au pire en Θ(N2 ) compa-
raisons résolvant ce problème, en considérant la comparaison entre éléments de S comme
opération élémentaire. On prend un élément quelconque de S et on compte son nombre
d'occurrences dans S. S'il n'est pas majoritaire, on prend un autre élément de S, et ainsi
de suite jusqu'à trouver un élément majoritaire ou avoir traité les éléments de la moitié
de S sans en avoir trouvé.
Invariant Soit S le sac de valeurs pour lequel on recherche un éventuel élément majori-
taire et sa partition multiensembliste (hypothèse du travail réalisé en partie) composée de :
P un sac des paires de valeurs tel que, pour toute paire, les deux valeurs sont dié-
rentes,
C un sac dénommé sac des célibataires dont tous les éléments ont la même valeur.
S
P R
× (1, 3) ×5 ×2
× (4, 1)
×5 ×1
× (1, 3)
C
128 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
De façon analogue à l'exercice précédent (voir exercice 40, page 126), on cherche une
solution en aaiblissant la postcondition. La solution retenue fait, pour partie, appel
à la recherche linéaire bornée (voir section 3.5, page 113). La solution obtenue se
révèle élégante et de complexité linéaire.
Dans un groupe de N personnes, une star est une personne que tout le monde connaît et
qui ne connaît personne. On considère un groupe de N (N > 1) personnes et on cherche
une star dans le groupe, s'il y en a une. Par convention, un groupe d'une seule personne a
cette personne pour star. La seule opération autorisée, notée Connaît(i, j) est de choisir une
personne i et de lui demander si elle connaît la personne j (diérente d'elle-même). L'opé-
ration Connaît(i, j) rend vrai ou faux en fonction de la réponse (obligatoire et sincère) de
la personne interrogée.
CHAPITRE 3. SPÉCIFICATION, INVARIANTS, ITÉRATION 129
Comme il y a N(N − 1)/2 paires de personnes, le problème peut être à coup sûr résolu
par au plus N(N − 1) opérations. Cependant, on cherche à eectuer moins d'opérations, si
Ce document est la propriété exclusive de Jean-Claude LALLEMENT ([email protected]) - dimanche 22 août 2021 à 18h12
Question 4. Spécier les constituants d'une boucle identiant une personne susceptible 41 - Q 4
d'être la star du groupe et appelée star potentielle .
On a vu en section 3.3.2 qu'il est légal que, cherchant à résoudre le problème spécié par
{P} prog {Q}, on résolve le problème spécié par {P0 } prog0 {Q} avec P ⇒ P0 . En d'autres
termes, on aaiblit la précondition et on peut s'interroger sur l'impact de cette démarche
au plan des performances. Deux exemples sont traités pour éclairer cette question.
Postcondition : (T est trié par ordre croissant) et (S est le sac des valeurs contenues
dans T ).
130 CONCEPTION D'ALGORITHMES PRINCIPES ET 150 EXERCICES CORRIGÉS
42 - Q 2 Question 2. Quelle complexité atteint-on si l'on utilise l'algorithme proposé dans l'exer-
cice 33, page 119 ? Peut-on espérer mieux en recourant à un algorithme de tri classique ?
Conclure.
Cette spécication dière de celle de l'exemple traité page 105, puisque l'on dispose d'une
propriété sur la variation des nombres présents dans T . Ici encore, deux stratégies sont
envisageables : programme spécique ou utilisation de l'algorithme proposé page 107. Cette
seconde option correspond à l'aaiblissement de la précondition du problème posé dont on
ignore le troisième conjoint.
42 - Q 3 Question 3. Montrer que si T est tel que l'écart entre deux éléments consécutifs de T est
d'au plus 1, alors :
42 - Q 4 Question 4. Développer la solution spécique fondée sur une boucle dont on donnera les
constituants.
Le problème traité ici est une variante assez sophistiquée de la recherche séquentielle.
Habituellement, dans un problème de ce type, l'emploi de la technique d'arrêt au
plus tôt n'a pas d'incidence sur la complexité asymptotique. Ce n'est pas le cas
ici, où elle est la clé de voûte de l'amélioration d'ecacité obtenue par rapport à
une méthode naïve. Par ailleurs, ce problème trouve une formulation dans un espace
à deux dimensions généralement résolue par deux boucles imbriquées. Ici, comme
dans l'exercice 32, page 118, l'utilisation d'une seule boucle rend la construction plus