[PDF] Exercices et problemes d'algorithmique

View - Download Exercices et problemes d'algorithmique

Previous PDF

Next PDF

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 difficultés de l"algorithmique. Au coeur de l"informatique, cette science est celle de la conception de méthodes efficaces 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 diffé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 différentes universi-

tés, les a depuis longtemps confrontés aux difficulté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 diffé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 ajouteune 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 parfoisajouter des difficultés de compréhension dues à la syntaxe propre du langage.

C"est pour répondre à ces difficulté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 efficaces. Si la plupart des ouvrages de cours d"algorithmique contiennent des énoncés

d"exercices, peu sont corrigés. C"est donc l"une des originalités de ce livre que de©Dunod. La photocopie non autorisée est un délit.

VIIRetrouver ce titre sur Numilog.com

Avant-propos

proposer une correction entièrement rédigée, rigoureuse et complète de chaque ques- tion. Ony trouvera, pour chaque notion, des exercices visant lacompré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 enquestions progressives. Ony 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 effort 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 etdel"analyse de lacomplexité 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 difficulté crois- sante, sauf nécessité de regroupement thématique, et souvent les questions d"un exer- cice respectent une certaine progressivité dans la difficulté. 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...

VIIIRetrouver ce titre sur Numilog.com

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 :

•tant queconditionfaireinstructionfintantque;

•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 affranchissons 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 valeurnul. ©Dunod. La photocopie non autorisée est un délit.

IXRetrouver ce titre sur Numilog.com

Avant-propos

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 difficulté 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.

XRetrouver ce titre sur Numilog.com

PREUVE

ET 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.

Définition 1.1Borne supérieure asymptotique

O(g(n))={f:IN→IN|?k>0etn

0 ≥0 tels que ?n≥n 0 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.

1Retrouver ce titre sur Numilog.com

Chapitre 1

Preuve et complexité

Définition 1.2Borne inférieure asymptotique

Ω(g(n))={f:IN→IN|?k>0etn

0 ≥0 tels que ?n≥n 0 Si une fonctionf(n)?Ω(g(n)), on dit queg(n) est uneborne inférieure asympto- tiquepourf(n).

On note abusivement :f(n)=Ω(g(n)).

Définition 1.3Borne asymptotique

Θ(g(n))={f:IN→IN|?k

1 >0,k 2 >0etn 0 ≥0 tels que ?n≥n 0 1 2 g(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

n 2 ?O(10 -5 n 3 25n
4 -19n 3 +13n 2 ?O(n 4 2 n+100 ?O(2 n

2.Donner les relations d"inclusion entre les ensembles suivants :O(nlogn),O(2

n

O(logn),O(1),O(n

2 ),O(n 3 )etO(n).

3.Soit un ordinateur pour lequel toute instruction possède une durée de 10

-6 se- condes. On exécute un algorithme qui utilise, pour une donnée de taillen,f(n)ins- tructions,f(n) étant l"une des fonctions précédentes (logn,nlogn,n,n 2 ,n 3 et 2 n 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:IN→IN.

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))).

2Retrouver ce titre sur Numilog.com

Exercices

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)).

Solution

1.Pour la première relation, il suffit donc de trouver deux entiers strictement positifsk

etn 0 tels que n 2 -5 n 3 ?n≥n 0

Si l"on prendk=10

5 etn 0 =1, il est évident que n 2 -5 n 3 =n 3 ?n≥n 0 doncn 2 ?O(10 -5 n 3 Pour la seconde relation, remarquonstout d"abord que 25n
4 -19n 3 +13n 2 4 +19nquotesdbs_dbs14.pdfusesText_20

[PDF] exercices corrigés d'automatique pdf

[PDF] exercices corrigés déconométrie des variables qualitatives pdf

[PDF] exercices corrigés d'économie des transports

[PDF] exercices corrigés délectricité pdf

[PDF] exercices corrigés délectrophorèse

[PDF] exercices corrigés dimmunologie pdf

[PDF] exercices corrigés doptimisation avec contrainte pdf

[PDF] exercices corrigés de béton précontraint pdf

[PDF] exercices corrigés de bioénergétique pdf

[PDF] exercices corrigés de chimie organique descriptive pdf

[PDF] exercices corrigés de chimie organique s3

[PDF] exercices corrigés de consolidation des comptes pdf

[PDF] exercices corriges de demographie pdf

[PDF] exercices corrigés de didactique des mathématiques

[PDF] exercices corrigés de dihybridisme