[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

PROBLÈMES310

PARTIE 4€TECHNIQUES AVANCÉES DE CONCEPTION ET D"ANALYSE

CHAPITRE 15€PROGRAMMATION DYNAMIQUE315

15.1 Ordonnancement de chaînes de montage316

Exercices322

15.2 Multiplications matricielles enchaînées323

Exercices330

15.3 Éléments de la programmation dynamique330

Exercices341

15.4 Plus longue sous-séquence commune341

Exercices347

15.5 Arbres binaires de recherche optimaux347

Exercices354

PROBLÈMES354

CHAPITRE 16€ALGORITHMES GLOUTONS361

16.1 Un problème de choix d"activités362

Exercices370

16.2 Éléments de la stratégie gloutonne370

Exercices375

16.3 Codages de Huffman376

Exercices382

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

VIIITable des matières

16.4 Fondements théoriques

des méthodes gloutonnes 383

Exercices388

16.5 Un problème d"ordonnancement de tâches389

Exercices392

PROBLÈMES392

CHAPITRE 17€ANALYSE AMORTIE395

17.1 Méthode de l"agrégat396

Exercices400

17.2 Méthode comptable400

Exercices402

17.3 Méthode du potentiel402

Exercices405

17.4 Tables dynamiques406

Exercices414

PROBLÈMES415

PARTIE 5€STRUCTURES DE DONNÉES AVANCÉES

CHAPITRE 18€B-ARBRES425

18.1 Définition d"un B-arbre429

Exercices431

18.2 Opérations fondamentales sur les B-arbres432

Exercices437

18.3 Suppression d"une clé dans un B-arbre439

Exercices442

PROBLÈMES442

CHAPITRE 19€TAS BINOMIAUX445

19.1 Arbres binomiaux et tas binomiaux447

Exercices450

19.2 Opérations sur les tas binomiaux451

Exercices461

PROBLÈMES462

Table des matièresIX

CHAPITRE 20€TAS DE FIBONACCI465

20.1 Structure des tas de Fibonacci466

20.2 Opérations sur les tas fusionnables469

Exercices477

20.3 Diminution d"une clé et suppression d"un noeud478

Exercices481

20.4 Borne pour le degré maximal482

Exercices484

PROBLÈMES484

CHAPITRE 21€STRUCTURES DE DONNÉES POUR ENSEMBLES DISJOINTS487

21.1 Opérations sur les ensembles disjoints487

Exercices490

21.2 Représentation d"ensembles disjoints par des listes chaînées490

Exercices493

21.3 Forêts d"ensembles disjoints494

Exercices497

21.4 Analyse de l"union par rang avec compression de chemin498

Exercices505

PROBLÈMES506

PARTIE 6€ALGORITHMES POUR LES GRAPHES

CHAPITRE 22€ALGORITHMES ÉLÉMENTAIRES POUR LES GRAPHES513

22.1 Représentation des graphes514

Exercices516

22.2 Parcours en largeur517

Exercices524

22.3 Parcours en profondeur525

Exercices532

22.4 Tri topologique534

Exercices536

22.5 Composantes fortement connexes536

Exercices541

PROBLÈMES542

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

XTable des matières

CHAPITRE 23€ARBRES COUVRANTS DE POIDS MINIMUM545

23.1 Construction d"un arbre couvrant minimum546

Exercices550

23.2 Algorithmes de Kruskal et de Prim551

Exercices556

PROBLÈMES558

CHAPITRE 24€PLUS COURTS CHEMINS À ORIGINE UNIQUE563

24.1 Algorithme de Bellman-Ford571

Exercices574

24.2 Plus courts chemins à origine unique dans les graphes orientés sans circuit575

Exercices577

24.3 Algorithme de Dijkstra577

Exercices582

24.4 Contraintes de potentiel et plus courts chemins583

Exercices587

24.5 Démonstrations des propriétés de plus court chemin589

Exercices594

PROBLÈMES595

CHAPITRE 25€PLUS COURTS CHEMINS POUR TOUT COUPLE DE SOMMETS601

25.1 Plus courts chemins et multiplication de matrices603

Exercices608

25.2 L"algorithme de Floyd-Warshall609

Exercices614

25.3 Algorithme de Johnson pour les graphes peu denses616

Exercices620

PROBLÈMES621

CHAPITRE 26€FLOT MAXIMUM625

26.1 Réseaux de transport626

Exercices631

26.2 La méthode de Ford-Fulkerson632

Exercices643

26.3 Couplage maximum dans un graphe biparti644

Exercices648

26.4 Algorithmes de préflots649

Exercices658

Table des matièresXI

26.5 Algorithme réétiqueter-vers-l"avant659

Exercices669

PROBLÈMES669

PARTIE 7€MORCEAUX CHOISIS

CHAPITRE 27€RÉSEAUX DE TRI681

27.1 Réseaux de comparaison682

Exercices685

27.2 Le principe du zéro-un686

Exercices688

27.3 Un réseau de tri bitonique689

Exercices690

27.4 Un réseau de fusion692

Exercices693

27.5 Un réseau de tri694

Exercices696

PROBLÈMES697

CHAPITRE 28€CALCUL MATRICIEL701

28.1 Propriétés des matrices702

Exercices709

28.2 Algorithme de Strassen pour la multiplication des matrices710

Exercices716

28.3 Résolution de systèmes d"équations linéaires717

Exercices730

28.4 Inversion des matrices730

Exercices734

28.5 Matrices symétriques définies positives et approximation des moindres carrés735

Exercices740

PROBLÈMES741

CHAPITRE 29€PROGRAMMATION LINÉAIRE745

29.1 Forme canonique et forme standard752

Exercices759

29.2 Formulation de problèmes comme programmes linéaires760

Exercices764

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

XIITable des matières

29.3 Algorithme du simplexe765

Exercices778

29.4 Dualité779

Exercices784

29.5 Solution de base réalisable initiale785

Exercices790

PROBLÈMES791

CHAPITRE 30€POLYNÔMES ET TRANSFORMÉE RAPIDE DE FOURIER795

30.1 Représentation des polynômes797

Exercices802

30.2 Transformée discrète de Fourier et transformée rapide de Fourier803

Exercices810

30.3 Implémentations efficaces de la FFT811

Exercices816

PROBLÈMES816

CHAPITRE 31€ALGORITHMES DE LA THÉORIE DES NOMBRES821

31.1 Notions de théorie des nombres823

Exercices827

31.2 Plus grand commun diviseur828

Exercices832

31.3 Arithmétique modulaire833

Exercices839

31.4 Résolution d"équations linéaires modulaires839

Exercices842

31.5 Théorème du reste chinois843

Exercices845

31.6 Puissances d"un élément846

Exercices850

31.7 Le cryptosystème à clés publiques RSA850

Exercices856

31.8 Test de primarité856

Exercices865

31.9 Factorisation des entiers865

Exercices870

PROBLÈMES870

Table des matièresXIII

CHAPITRE 32€RECHERCHE DE CHAÎNES DE CARACTÈRES875

32.1 Algorithme naïf de recherche de chaîne de caractères878

Exercices879

32.2 Algorithme de Rabin-Karp880

Exercices884

32.3 Recherche de chaîne de caractères au moyen d"automates finis885

Exercices891

32.4 Algorithme de Knuth-Morris-Pratt891

Exercices898

PROBLÈMES899

CHAPITRE 33€GÉOMÉTRIE ALGORITHMIQUE901

33.1 Propriétés des segments de droite902

Exercices907

33.2 Déterminer si deux segments donnés se coupent908

Exercices914

33.3 Recherche de l"enveloppe convexe915

Exercices924

33.4 Recherche des deux points les plus rapprochés925

Exercices929

PROBLÈMES930

CHAPITRE 34€NP-COMPLÉTUDE933

34.1 Temps polynomial939

Exercices945

34.2 Vérification en temps polynomial946

Exercices950

34.3 NP-complétude et réductibilité951

Exercices960

34.4 Preuves de NP-complétude961

Exercices968

34.5 Problèmes NP-complets969

Exercices982

PROBLÈMES983

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

XIVTable des matières

CHAPITRE 35€ALGORITHMES D"APPROXIMATION987

35.1 Problème de la couverture de sommets989

Exercices992

35.2 Problème du voyageur de commerce992

Exercices997

35.3 Problème de la couverture d"ensemble997

Exercices1002

35.4 Randomisation et programmation linéaire1002

Exercices1007

35.5 Problème de la somme de sous-ensemble1007

Exercices1012

PROBLÈMES1013

PARTIE 8€ANNEXES : ÉLÉMENTS DE MATHÉMATIQUES

ANNEXE A€SOMMATIONS1021

A.1 Formules et propriétés des sommations1022

Exercices1025

A.2 Bornes des sommations1025

Exercices1031

PROBLÈMES1031

ANNEXE B€ENSEMBLES, ETC.1033

B.1 Ensembles1033

Exercices1037

B.2 Relations1038

quotesdbs_dbs22.pdfusesText_28

[PDF] poème contre la guerre

[PDF] comment faire un quadrillage sur scratch

[PDF] acrogym a 2

[PDF] poeme poilus 14-18

[PDF] poeme maladie cancer

[PDF] poeme pour combattre le cancer

[PDF] poeme triste maladie

[PDF] poeme maladie courage

[PDF] poeme maladie coeur

[PDF] texte sur la maladie

[PDF] pendant une maladie hugo

[PDF] dictionnaire grec biblique pdf

[PDF] poème 20ème siècle amour

[PDF] alimentation cm2 exercices

[PDF] hermaion initiation au grec ancien pdf