Exercices et problèmes d'algorithmique - 3e éd.

De
Publié par

Ce livre s'appuie sur l'expérience d'enseignants-chercheurs chevronnés qui ont souhaité offrir un support de travail aux étudiants de fin de licence et début de master ainsi qu'aux élèves ingénieurs dans leur approche de l'algorithmique.
Sur des sujets très divers (algorithmes sur les arbres, sur les graphes, les mots, la géométrie), ce livre propose des exercices de forme et de difficulté variables, exercices d'entraînement ou sujets d'examens. 
Les corrigés comportent les rédactions complètes des preuves et des algorithmes exprimés selon un formalisme proche de celui des langages de programmation impératifs (C, C++, Pascal, Java...). 
Cette troisième édition s'enrichit de quelques nouveaux exercices.
Publié le : mercredi 17 novembre 2010
Lecture(s) : 264
Licence : Tous droits réservés
EAN13 : 9782100556755
Nombre de pages : 496
Voir plus Voir moins
Cette publication est uniquement disponible à l'achat
AVANT-PROPOS
C’est en forgeant qu’on devient forgeron... Ce vieil adage, dont les hommes ont usé depuis la nuit des temps, est mis dans cet ouvrage au service des étudiants de licence et de première année de master de mathématiques et d’informatique, des élèvesingénieurs et de toute autre personne souhaitant goûter les joies et maîtriser les dicultés de l’algorithmique. Au cœur de l’informatique, cette science est celle de la conception de méthodes ecaces pour résoudre des problèmes à l’aide d’un ordinateur. Elle définit des outils généraux permettant de répondre aux questions suivantes : Sur quelle propriété ma thématique d’un problème peuton établir une méthode de résolution ? Étant donné un algorithme, résoutil le problème posé ? Lorsque l’on dispose de deux méthodes de résolution diérentes, laquelle est préférable ? L’algorithmique a donné lieu à de nombreux ouvrages remarquables depuis plus de trente ans, sur lesquels se fondent les enseignements dispensés dans les universités et écoles d’ingénieurs, et dont nous donnons une liste non exhaustive à la fin de cet ouvrage. L’expérience des auteurs, enseignants chevronnés dans diérentes universi tés, les a depuis longtemps confrontés aux dicultés de leurs étudiants face à cette matière. Cellesci semblent de plusieurs ordres : il est nécessaire de pouvoir expérimenter les algorithmes sur diérents exemples pour en comprendre intuitivement le fonctionnement ; apprendre des éléments de cours implique de pouvoir refaire, au besoin, les dé monstrations qui y ont été présentées, de les rédiger ; les algorithmes manipulent des entités qui évoluent dans le temps, et cela ajoute une dimension inhabituelle aux raisonnements mathématiques nécessaires pour les prouver et analyser leurs performances ; l’apprentissage souvent simultané d’un langage de programmation peut parfois ajouter des dicultés de compréhension dues à la syntaxe propre du langage. C’est pour répondre à ces dicultés que les auteurs ont formé le projet de cet ouvrage, à partir d’exercices progressifs conçus lors de leurs années de pratique, et utilisés dans le cadre de travaux dirigés, d’examens, ou pour des devoirs de plus grande envergure. L’ouvrage a pour objectif d’aider l’étudiant dans son apprentissage de la conception et de l’analyse d’algorithmes en insistant sur le raisonnement et sa rédaction, en vue d’écrire dans le langage de son choix des programmes ecaces. Si la plupart des ouvrages de cours d’algorithmique contiennent des énoncés Dunod. La photocopie non autorisée estun délit. ©on corrigés. d’exerci es, peu C’est donc l’une des originalités de ce livre que de
VII
Avant-propos
proposer une correction entièrement rédigée, rigoureuse et complète de chaque ques tion. On y trouvera, pour chaque notion, des exercices visant la compréhension du cours, qui permettent d’appliquer un algorithme connu à des données numériques, ou de redémontrer, à partir d’éléments de base dont les définitions sont explicitées, les pro priétés de certains algorithmes du cours décomposées en questions progressives. On y trouvera aussi des exercices qui enrichissent des algorithmes classiques de nouvelles fonctionnalités ou qui permettent de les intégrer dans des applications originales. Concernant la programmation, le parti pris de cet ouvrage est d’employer, pour la rédaction des algorithmes, un pseudolangage impératif, plutôt qu’un véritable lan gage de programmation, afin de se concentrer sur ce qui ressort de la conception de l’algorithme, et non sur son implémentation. Ce choix devrait toutefois permettre une implémentation aisée des algorithmes dans des langages comme Pascal, C ou C++, avec sans doute un eort supplémentaire en ce qui concerne les langages objets. Nous indiquons plus loin les conventions d’écriture de ce langage, auxquelles le lecteur pourra se référer pour comprendre, mais aussi pour programmer les algorithmes dans le langage de son choix. L’ouvrage aborde un panel assez vaste de domaines d’application de l’algorith mique, et devrait couvrir la plupart des cours dispensés actuellement en license et master de mathématiques et informatique et en écoles d’ingénieurs. On y développe notamment, après un chapitre méthodologique qui traite de la preuve et de l’analyse de la complexité d’un algorithme, les types de données abstraits pour représenter, gérer et manipuler des ensembles dynamiques, et leur implémenta tion à l’aide de structures de données linéaires ou arborescentes (piles, files, listes, arbres binaires de recherche, arbres équilibrés, tas). On aborde ensuite l’étude des algorithmes de tri. Les chapitres suivants sont consacrés à l’étude de l’algorithmique de base des graphes valués et non valués : connexité, accessibilité, parcours, arbres couvrants et chemins de coût minimum, pour ne citer que les principaux problèmes abordés. Ensuite, deux chapitres consacrés l’un aux algorithmes relatifs à la géomé trie plane et l’autre aux algorithmes relatifs aux automates et aux mots achèvent cet ouvrage. Dans chaque section, les exercices sont présentés dans un ordre de diculté crois sante, sauf nécessité de regroupement thématique, et souvent les questions d’un exer cice respectent une certaine progressivité dans la diculté. D’autres algorithmes auraient mérité de figurer dans ce livre, plus proches de l’al gorithmique numérique, ou de la recherche opérationnelle. Avec quelques encoura gements, les auteurs pourraient envisager une suite...
VIII
Avant-propos
Prérequis Le livre nécessite les connaissances de mathématiques du niveau des deux premières années de licence, en particulier une bonne maîtrise du raisonnement par récurrence, ainsi que la connaissance de base d’un langage de programmation. Chacun des cha pitres demande des prérequis, explicités dans les exercices lorsque cela semble né cessaire. Il est recommandé de traiter les exercices en ayant d’autre part étudié un cours oral ou un livre de référence. Toutefois, de nombreux exercices peuvent être traités en se référant uniquement aux définitions et résultats de base rappelés en début de souschapitre. Cet entête de chapitre n’a pas pour objectif d’être un abrégé de cours. Les définitions présentées sont loin d’être exhaustives, mais sont celles jugées indis pensables pour traiter les exercices avec le plus d’autonomie possible.
Conventions relatives à la présentation des algorithmes Les algorithmes se présentent sous la forme de segments de code, de fonctions ou de procédures. Les types des paramètres, des fonctions et des variables sont toujours explicités. Par défaut, les passages de paramètres se font par valeur. Un texte accom pagne l’algorithme lorsqu’un paramètre est modifié, et que le passage doit se faire par référence. Comme dans tous les langages de programmation impératifs, les structures de contrôle suivantes sont employées : siconditionalorsinstructionsinoninstructionfinsi; tant queconditionfaireinstructionfintantque; répéterinstructionjusqu’àconditionfinrépéter; pourvariable de valeur initialeàvaleur finalefaireinstructionfinpour; pour toutélément d’un ensemblefaireinstructionfinpour. Les tableaux sont indexés par des entiers, et un élément d’indiceid’un tableau Ts’écritT[i], de même les éléments d’un tableauMà deux dimensions se notent M[i,j]. La principale spécificité du pseudolangage est le traitement des pointeurs. D’abord, nous nous aranchissons des problèmes liés à l’allocation dynamique de mémoire (les objets manipulés sont supposés alloués). Ensuite, pour ne pas alour dir la présentation des algorithmes, lorsqu’une variablexdésigne un pointeur sur un enregistrement à plusieurs champs, par exemple un enregistrement comportant des champs nommésaetb, alors on noterax.ala variable correspondant au champade l’enregistrement pointé parx. La même notation sera employée lorsquexreprésente l’enregistrement luimême. Un pointeur qui ne pointe sur aucun enregistrement a la Dunod. La photocopie non autorisée est un délit. ©valeurnul.
IX
Avant-propos
X
Conventions relatives à l’index Les entrées de l’index font référence à des notions de base traitées dans l’ouvrage. Lorsqu’une notion fait l’objet d’une définition explicite, ou d’un exercice qui lui est spécifiquement consacré, le numéro de page référencé apparaît en gras. Lorsqu’il s’agit d’un algorithme, le numéro de page apparaît en italique.
Remerciements Les auteurs se souviennent avec tendresse du vide de leurs premiers regards qu’une explication miraculeuse a un jour allumé d’une petite flamme. Ils saluent leurs maîtres, qui leur ont inculqué une forme de pensée archaïque consistant à chercher en toute circonstance la maîtrise absolue de la situation, par l’intermédiaire d’une preuve au pire longue et laborieuse, au mieux élégante et belle. Ils arrosent d’une larme émue les bancs des facultés, usés par ceux qui ont, depuis vingt ans, à leur insu, participé à la conception de cet ouvrage. Ils remercient chaleureusement les collègues dont ils ont sans vergogne pillé les archives.
Troisième édition La troisième édition introduit dans la plupart des chapitres des exercices nouveaux qui se caractérisent par une plus grande originalité, une plus grande diculté et par leur intérêt pédagogique pour appréhender en profondeur les fondements théoriques des concepts algorithmiques présentés dans le chapitre.
ET
PREUVE COMPLEXITÉ
1
Un algorithme (O,V,S) est formé d’un ensemble finiOd’opérations liées par une structure de contrôleSet dont les opérandes portent sur un ensemble finiVde va riables. Un algorithme résout le problèmePsi pour tout énoncéIdeP(stocké dans le sousensemble des variables d’entrée deV), d’une part la suite des opérations exé cutées est finie (condition de terminaison) et si d’autre part, lors de la terminaison, le sousensemble des variables de sortie deVcontient le résultat associé à l’énoncé I(condition de validité). Prouver un algorithme, c’est démontrer mathématiquement que la propriété précédente est satisfaite. Une mesure de complexité d’un algorithme est une estimation de son temps de calcul, mémoire utilisée ou de toute autre unité significative. On s’intéresse le plus souvent à la recherche d’une estimation par excès à une constante positive multiplicative près du cas le plus défavorable sur le sous ensemble des énoncés de taille fixéen(complexité dite « pirecas »). On obtient ainsi le taux asymptotique de croissance de la mesure indépendamment de la machine sur laquelle l’algorithme est exécuté et l’on peut alors comparer les complexités pirecas de plusieurs algorithmes résolvant un même problème. Ce chapitre propose d’exercer cette démarche d’analyse sur des algorithmes de base, itératifs et récursifs, en demandant le développement détaillé des preuves à l’aide de questions progressives. Afin de définir rigoureusement la notion de me sure de complexité, nous introduisons les trois notations de Landau relatives aux ensembles de fonctionsO(g),Ω(g) etΘ(g), lorsquegest une fonction de IN dans IN.
nition 1.1Borne supérieure asymptotique
O(g(n))={f:NIIN| ∃k>0 etn00 tels que nn00f(n)kg(n)}
Si une fonctionf(n)O(g(n)), on dit queg(n) est uneborne supérieure asympto tiquepourf(n). On note abusivement :f(n)=O(g(n)).
Dunod. La photocopie non autorisée est un délit. ©
1
Chapitre 1
2
Preuve et complexité
nition 1.2Borne inférieure asymptotique
Ω(g(n))={f:ININ| ∃k>0 etn00 tels que nn00kg(n)f(n)}
Si une fonctionf(n)Ω(g(n)), on dit queg(n) est uneborne inférieure asympto tiquepourf(n). On note abusivement :f(n)=Ω(g(n)).
nition 1.3Borne asymptotique
Θ(g(n))={fNI:IN| ∃k1>0,k2>0 etn00 tels que nn00k1g(n)f(n)k2g(n)}
Si une fonctionf(n)Θ(g(n)), on dit queg(n) est uneborne asymptotiquepour f(n). On note abusivement :f(n)=Θ(g(n)).
Exercice 1.1Généralités sur les notations asymptotiques 1.Démontrer que 25 3 nO(10n) 4 3 2 4 25n19n+13nO(n) n+100n 2O(2 )
n 2.Donner les relations d’inclusion entre les ensembles suivants :O(nlogn),O(2 ), 2 3 O(logn),O(1),O(n),O(n) etO(n). 6 3.Soit un ordinateur pour lequel toute instruction possède une durée de 10 se condes. On exécute un algorithme qui utilise, pour une donnée de taillen,f(n) ins 2 3n tructions,f(n) étant l’une des fonctions précédentes (logn,nlogn,n,n,net 2 ). Remplir un tableau qui donne, en fonction de la taillen=10, 20, 30 et 60, et de la fonctionf(n), la durée d’exécution de l’algorithme. Soientf,g,SetT:ININ. 4.Montrer que sif(n)O(g(n)), alorsg(n)Ω(f(n)). 5.Montrer que sif(n)O(g(n)), alorsf(n)+g(n)O(g(n)). 6.Montrer quef(n)+g(n)Θ(max(f(n),g(n))).
7.Montrer queO(f(n)+g(n))=O(max(f(n),g(n))). On suppose queS(n)O(f(n)) etT(n)O(g(n)). 8.Montrer que sif(n)O(g(n)), alorsS(n)+T(n)O(g(n)). 9.Montrer queS(n)T(n)O(f(n)g(n)).
Exercices
Solution 1.Pour la première relation, il sut donc de trouver deux entiers strictement positifsk etn0tels que 25 3 nk10nnn0
5 Si l’on prendk=10 etn0=1, il est évident que
235 3 nk10n=nnn0
25 3 doncnO(10n). Pour la seconde relation, remarquons tout d’abord que
4 3 2 4 3 2 4 25n19n+13n25n+19n+13n(25+19+13)nn1
4 3 2 4 On en déduit que 25n19n+13nO(n). Il sut en eet de choisirk=25+19+13=57 etn0=1. 100 Finalement, soitk=2 etn0=0, il est évident que
n+100n 2k2nn0
2 3 2.Il est évident queO(1)O(n)O(n)O(n), puisque
2 3 1nnnn1
On a égalementO(1)O(logn)O(n)O(nlogn), puisque
1lognn3
et lognnn1 2 et pour la même raison,O(nlogn)O(n). 3n On montre facilement queO(n)OEn e(2 ). et,
3n3n n2lognlog 23 lognnlog(2)
Dunod. La photocopie non autorisée est un délit. qui est vrai à partir d’une certaine valeur denpuisque lognO(n). ©
3
Chapitre 1
4
Preuve et complexité
L’ordre d’inclusion est donc finalement :
2 3n O(1)O(logn)O(n)O(nlogn)O(n)O(n)O(2 ) Un algorithme ayant une complexité logarithmique sera donc meilleur (en terme de com plexité) qu’un algorithme linéaire, luimême meilleur qu’un algorithme polynomial, à son tour meilleur qu’un algorithme exponentiel. 3.Le tableau suivant est calculé en utilisant un logarithme népérien : f(n)10 20 30 60 6666 logn2,30×10 3,00×10 3,40×10 4,09×10 5555 n10 2×10 3×10 6×10 5544 nlogn2,30×10 5,99×10 1,02×10 2,46×10 24443 n10 4×10 9×10 3,60×10 33321 n10 8×10 2,70×10 2,16×10 n123 3 21,02×1,0710 1,05 ×10 1,15×10 12 Il est intéressant de remarquer que 1,15×10 s36 558 ans. 4.Sif(n)O(g(n)), alors il existek>0 etn00 tels que
f(n)kg(n)nn0
On déduit de l’expression précédente que
1 f(n)g(n)nn0 k
Doncg(n) est enΩ(f(n)). 5.Sif(n)O(g(n)), alors il existek>0 etn00 tels que
f(n)kg(n)nn0
On déduit de l’expression précédente que
f(n)+g(n)(k+1)g(n)nn0
Doncf(n)+g(n) est enO(g(n)). 6.De façon évidente,
max(f(n),g(n))f(n)+g(n)2 max(f(n),g(n))n0
f(n)+g(n) est donc enΘ(max(f(n),g(n))). 7.Pour montrer l’égalité des deux ensemblesO(f(n)+g(n)) etO(max(f(n),g(n))), il faut montrer la double inclusion. O(f(n)+g(n))O(max(f(n),g(n))) :
Pour toute fonctionh(n)O(f(n)+g(n)), il existek>0 etn00 tels que
h(n)k(f(n)+g(n))2kmax(f(n),g(n))nn0
Donch(n) est donc enO(max(f(n),g(n))). O(max(f(n),g(n)))O(f(n)+g(n)) : Pour toute fonctionh(n)O(max(f(n),g(n))), il existek>0 etn00 tels que
h(n)kmax(f(n),g(n))k(f(n)+g(n))nn0
Exercices
Donch(n) est enO(f(n)+g(n)). ′ ′ 8.SiS(n)O(f(n)) etT(n)O(g(n)), alors il existek>0,k>0,n00 etn0 tels 0 que S(n)k f(n)nn0 ′ ′ T(n)kg(n)nn 0 ′′ ′′ Sif(n)O(g(n)), alors il existek>0 etn0 tels que 0 ′′ f(n)kg(n)nn0
′′ ′ ′ ′′ On définit alorsK=kk+ketm0=max(n0,n,n). De façon évidente : 0 0 ′ ′′ S(n)+T(n)k f(n)+kg(n)(kk+k)g(n)=Kg(n)nm0
DoncS(n)+T(n) est enO(g(n)). Si dans un algorithme, on a une première partie enO(f(n)) suivie (séquentiellement) d’une seconde partie enO(g(n)) et quef(n)O(g(n)), alors l’algorithme est globalement enO(g(n)). ′ ′ 9.De la même façon, si on définitK=kketm0=max(n0,n), on a de façon évidente : 0
S(n)T(n)K f(n)g(n)nm0
DoncS(n)T(n) est enO(f(n)g(n)). Si dans un algorithme, on a une première partie enO(f(n)) dans laquelle est imbriquée une seconde partie enO(g(n)), alors l’algorithme est globalement enO(f(n)g(n)).
Exercice 1.2Somme des éléments d’ un tableau SoitAun tableau denentiers (n1). 1.Écrire un algorithme itératif qui calcule la somme des éléments deAet prouver cet algorithme. Dunod. La photocopienon autorisée est un délit. ©2.er la complexité de cet algorithme.Dé ermi
5
Chapitre 1
6
Preuve et complexité
3.Écrire un algorithme récursif qui calcule la somme des éléments deAet prouver cet algorithme. 4.Déterminer la complexité de cet algorithme récursif.
Solution 1.L’algorithme calculant la somme desnéléments du tableauAest le suivant :
Somme:entier Somme0 pouri1ànfaire SommeSomme+A[i] fin pour
Pour prouver cet algorithme il faut démontrer deux choses : la terminaison et la validité de l’algorithme. La terminaison de l’algorithme est triviale puisque la boucle est exécutéenfois et que le corps de la boucle n’est constitué que d’une somme et d’une aectation, opérations qui s’exécutent en un temps fini. Pour démontrer la validité, nous allons considérer la propriété suivante : « À la fin de l’itérationi, la variableSommecontient la somme desipremiers éléments du tableau A». NotonsSommeila valeur de la variableSommeà la fin de l’itérationietSomme0=0 sa valeur initiale. On eectue alors un raisonnement par récurrence suri. La propriété est trivialement vraie pouri=1 puisqu’à l’issue de la première itérationSomme(initialisée à 0) contient la valeurA[1] :
Somme1=Somme0+A[1]=A[1]
Maintenant, si on suppose que la propriété est vraie pour une itérationi:
i Sommei=A[j] j=1
À la fin de l’itérationi+1,Sommecontiendra la valeur qu’elle contenait à la fin de l’itérationi, donc la somme desipremiers éléments, plusA[i+1] qui lui a été ajoutée à l’itérationi+1.Sommesera donc bien la somme desi+1 premiers éléments deA:
i i+1   Sommei+1=Sommei+A[i+1]=A[j]+A[i+1]=A[j] j=1j=1
Vraie initialement, la propriété reste vraie à chaque nouvelle itération. Cette propriété est donc un invariant de l’algorithme. On parle d’invariant de boucle. L’algorithme se terminant, à la fin de l’itérationn, il aura donc bien calculé la somme desnéléments du tableauA.
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.