[PDF] Introduction à lalgorithmique

View - Download Introduction à lalgorithmique

Previous PDF

Next PDF

INTRODUCTION

À L"ALGORITHMIQUE

Cours et exercices

Thomas Cormen

Professeur associé d"informatique au Darmouth College

Charles Leiserson

Professeur d"informatique au MIT

Ronald Rivest

Professeur d"informatique au MIT

Clifford Stein

Professeur associé au génie industriel

et de recherche opérationelle à l"université de Columbia

Préface de

Philippe chrétienne , Claire Hanen, Alix Munier, Christophe Picouleau 1

ère

édition traduite de l"américain par Xavier Cazin

Compléments et mises à jour de la 2

e

édition traduits par Georges-Louis Kocher

2 e

édition

Massachusetts, sous le titre

Introduction to Algorithms

, second edition. © The Massachusetts Institute of Technology, 2001

First edition 1990

© Dunod, Paris, 1994, pour la 1

ère

édition

© Dunod, Paris, 2004, pour la présente édition

ISBN 2 10 003922 9

Ce pictogramme mŽrite une explication.

Son objet est dÕalerter le lecteur sur

la menace que reprŽsente pour lÕavenir le domaine de lՎdition tech- nique et universitaire, le dŽvelop- pement massif du photo- copillage.

Le Code de la propriŽtŽ

intellectuelle du 1 er juillet 1992 interdit en effet expressŽment la photocopie ˆ usage collectif sans autorisation des ayants droit. Or,

cette pratique sÕest gŽnŽralisŽe dans lesŽtablissements dÕenseignement supŽrieur,

provoquant une baisse brutale des achats de livres et de revues, au point que la possibilitŽ mme pour les auteurs de les faire Žditer correctement est aujourdÕhui menacŽe.

Nous rappelons donc que

toute reproduction, partielle ou totale, de la prŽsente publication est interdite sans autorisation du

Centre franais dÕexploitation du

droit de copie (CFC, 20 rue des Grands-

Augustins, 75006 Paris).

Table des matières

PRÉFACE À L"ÉDITION FRANÇAISEXVII

PRÉFACEXXI

PARTIE 1€INTRODUCTION

CHAPITRE 1€RÔLE DES ALGORITHMES EN INFORMATIQUE3

1.1 Algorithmes3

Exercices8

1.2 Algorithmes en tant que technologie8

Exercices11

PROBLÈMES11

CHAPITRE 2€PREMIERS PAS13

2.1 Tri par insertion13

Exercices18

2.2 Analyse des algorithmes19

Exercices25

2.3 Conception des algorithmes25

Exercices34

PROBLÈMES35

CHAPITRE 3€CROISSANCE DES FONCTIONS39

3.1 Notation asymptotique40

Exercices48

3.2 Notations standard et fonctions classiques48

Exercices54

PROBLÈMES55

c Dunod - La photocopie non autorisée est un délit

IVTable des matières

CHAPITRE 4€RÉCURRENCES59

4.1 Méthode de substitution60

Exercices64

4.2 Méthode de l"arbre récursif64

Exercices68

4.3 Méthode générale69

Exercices71

4.4 Démonstration du théorème général72

Exercices80

PROBLÈMES80

CHAPITRE 5€ANALYSE PROBABILISTE ET ALGORITHMES RANDOMISÉS87

5.1 Le problème de l"embauche87

Exercices90

5.2 Variables indicatrices91

Exercices94

5.3 Algorithmes randomisés95

Exercices100

5.4 Analyse probabiliste et autres emplois des variables indicatrices101

Exercices112

PROBLÈMES113

PARTIE 2€TRI ET RANGS

CHAPITRE 6€TRI PAR TAS121

6.1 Tas121

Exercices123

6.2 Conservation de la structure de tas124

Exercices125

6.3 Construction d"un tas126

Exercices128

6.4 Algorithme du tri par tas129

Exercices129

6.5 Files de priorité131

Exercices134

PROBLÈMES135

Table des matièresV

CHAPITRE 7€TRI RAPIDE139

7.1 Description du tri rapide139

Exercices142

7.2 Performances du tri rapide143

Exercices146

7.3 Versions randomisées du tri rapide147

Exercices148

7.4 Analyse du tri rapide148

Exercices152

PROBLÈMES153

CHAPITRE 8€TRI EN TEMPS LINÉAIRE159

8.1 Minorants pour le tri159

Exercices161

8.2 Tri par dénombrement162

Exercices164

8.3 Tri par base164

Exercices167

8.4 Tri par paquets167

Exercices171

PROBLÈMES171

CHAPITRE 9€MÉDIANS ET RANGS177

9.1 Minimum et maximum178

Exercices179

9.2 Sélection en temps moyen linéaire179

Exercices183

9.3 Sélection en temps linéaire dans le cas le plus défavorable183

Exercices186

PROBLÈMES187

PARTIE 3€STRUCTURES DE DONNÉES

CHAPITRE 10€STRUCTURES DE DONNÉES ÉLÉMENTAIRES195

10.1 Piles et files195

Exercices197

c Dunod - La photocopie non autorisée est un délit

VITable des matières

10.2 Listes chaînées199

Exercices203

10.3 Implémentation des pointeurs et des objets203

Exercices207

10.4 Représentation des arborescences208

Exercices209

PROBLÈMES211

CHAPITRE 11€TABLES DE HACHAGE215

11.1 Tables à adressage direct216

Exercices217

11.2 Tables de hachage218

Exercices222

11.3 Fonctions de hachage223

Exercices230

11.4 Adressage ouvert231

Exercices238

11.5 Hachage parfait238

Exercices242

PROBLÈMES243

CHAPITRE 12€ARBRES BINAIRES DE RECHERCHE247

12.1 Qu"est-ce qu"un arbre binaire de recherche ?248

Exercices249

12.2 Requête dans un arbre binaire de recherche250

Exercices253

12.3 Insertion et suppression254

Exercices257

12.4 Arbres binaires de recherche construits aléatoirement258

Exercices261

PROBLÈMES262

CHAPITRE 13€ARBRES ROUGE-NOIR267

13.1 Propriétés des arbres rouge-noir267

Exercices270

13.2 Rotation271

Exercices272

Table des matièresVII

13.3 Insertion273

Exercices280

13.4 Suppression281

Exercices286

PROBLÈMES287

CHAPITRE 14€EXTENSION D"UNE STRUCTURE DE DONNÉES295

14.1 Rangs dynamiques296

Exercices300

14.2 Comment étendre une structure de données301

Exercices303

14.3 Arbres d"intervalles304

Exercices309

quotesdbs_dbs46.pdfusesText_46

[PDF] algorithmique d'age de retraite 2nde Mathématiques

[PDF] algorithmique débranchée PDF Cours,Exercices ,Examens

[PDF] algorithmique débranchée collège PDF Cours,Exercices ,Examens

[PDF] algorithmique définition PDF Cours,Exercices ,Examens

[PDF] ALGORITHMIQUE dichotomie 1ère Mathématiques

[PDF] Algorithmique Dm math Terminale Mathématiques

[PDF] algorithmique et fonctions affines 2nde Mathématiques

[PDF] algorithmique et fonctions affines 2 2nde Mathématiques

[PDF] algorithmique et outils numériques 4ème Mathématiques

[PDF] Algorithmique et pourcentages (maths) 1ère Mathématiques

[PDF] algorithmique et programmation PDF Cours,Exercices ,Examens

[PDF] algorithmique et programmation au collège PDF Cours,Exercices ,Examens

[PDF] algorithmique et programmation en java cours et exercices corrigés pdf PDF Cours,Exercices ,Examens

[PDF] algorithmique et programmation en java pdf PDF Cours,Exercices ,Examens

[PDF] algorithmique et programmation exercices corrigés PDF Cours,Exercices ,Examens