This material is presented to ensure timely dissemination of scholarly work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse copyrighted component of this work in other works, must be obtained from the publishers.

COMPLEXITÉ ALGORITHMIQUE
et
problèmes de communications :

TABLE DES MATIÈRES

PRÉFACE ... p. v

TABLE DES MATIÈRES ... p. ix

CONTENTS ... p. xiii

NOTATIONS ... p. xvii

GRAPHES : NOTATIONS ET DÉFINITIONS ... p. xxi

INTRODUCTION ... p. xxiii

CHAPITRE 1 : Problèmes et langages ... p. 1

1. Quelques problèmes ... p. 1
2. Problèmes, langages et codages ... p. 6
3. Réductibilité ... p. 12
4. Classification algorithmique des problèmes ... p. 16

CHAPITRE 2 : Machines, langages et problèmes. Les classes P et NP ... p. 23

1. Machines de Turing ... p. 24
2. Le calcul déterministe ... p. 28
3. Décision déterministe, langages récursifs et langages polynomiaux ... p. 30
4. Problèmes polynomiaux ... p. 33
5. La classe NP ... p. 35
6. Problèmes NP-complets ... p. 42
7. Principes de survie ... p. 54
8. Problèmes pseudo-polynomiaux ... p. 56
9. Exercices et problèmes ... p. 62

CHAPITRE 3 : Problèmes et langages NP-difficiles ... p. 69

1. Machines de Turing à oracle et problèmes de recherche NP-difficiles ... p. 70
2. La hiérarchie polynomiale ... p. 77
3. Compléments sur la complexité algorithmique ... p. 87

CHAPITRE 4 : Complexité et codage ... p. 93

1. Codes linéaires ... p. 93
2. Code dual, syndrome, détection d'erreur ... p. 95
3. Le décodage ... p. 97
4. Quelques exemples : les codes parfaits ... p. 105
5. Sur la complexité du calcul de la distance minimale ... p. 109
6. Le rayon de recouvrement ... p. 116
7. Une application à l'écriture sur des mémoires ... p. 118
Appendices ... p. 121

CHAPITRE 5 : Complexité et cryptologie ... p. 143

1. Introduction générale à la cryptologie ... p. 143
2. Introduction à la cryptographie à clé publique ... p. 147
3. Le premier cryptosystème à clé publique : le RSA ... p. 153
4. Un système malmené : le sac à dos ... p. 160
5. Un système emcore peu étudié : le système de McEliece ... p. 177
6. Protocoles d'authentification ... p. 184
Appendice ... p. 193

CHAPITRE 6 : Quantification vectorielle ... p. 195

1. Rappels de théorie de l'information ... p. 195
2. Quantification vectorielle et décodage ... p. 197
3. Théorie de la distorsion ... p. 198
4. Approche par les codes correcteurs ... p. 199
5. Quelques considérations de complexité ... p. 202

CASCADE des réductions polynomiales utilisées ... p. 205

BIBLIOGRAPHIE ... p. 207

INDEX ... p. 215

REMERCIEMENTS ... p. 221

NOTES SUR LES AUTEURS ... p. 223