Complexité et algorithmique avancée : une introduction

Auteur(s) :

Lavallée, Ivan (1946-....) Découvrir l'auteur

Résumé

Exposé introductif à la pratique de la théorie de la complexité. Introduction aux concepts fondamentaux du domaine, définition des trois principales classes de complexité P, NP et NPC, ainsi que du concept de quantité absolue d'information, et résolution de problèmes avec les concepts probabilistes ou les méthodes d'énumération implicite.

Éditeur(s)
- Hermann
Date
- impr. 2008
Notes
- Bibliogr. p. 311-330
Langues
- Français
Description matérielle
- 1 vol. (330 p.) : ill., couv. ill. ; 22 cm
Collections
- Méthodes
Sujet(s)
- Complexité de calcul (informatique)
ISBN
- 978-2-7056-6726-9
Indice
- 681.21 Algorithmes de programmation
Quatrième de couverture
- Complexité et algorithmique avancée
  une introduction
  « Complexité et algorithmique avancée » est un exposé introductif à la pratique de la théorie de la complexité, il a été enseigné dans les trois cycles universitaires d'informatique et de cognitique et l'ouvrage est conçu pour être abordé par les étudiants des trois cycles universitaires. Il s'agit là du premier ouvrage en langue française traitant de la complexité en tant que telle. On y trouvera une introduction aux concepts fondamentaux du domaine, qu'il s'agisse de machine de Turing élémentaire ou universelle, de complexité au sens de Levin-Cook ou de Kolmogorov. Dans ce livre sont définies les trois principales classes de complexité, P, NP et NPC ainsi que le concept de quantité absolue d'information dû à Kolmogorov. Dans une dernière partie, on montre comment résoudre certains problèmes en faisant « tomber » la complexité en utilisant des concepts probabilistes, ou en utilisant des méthodes d'énumération implicite dont les principes sont décrits. L'ouvrage se termine sur un chapitre consacré à l'informatique quantique. Ce livre est destiné tant aux étudiants en informatique qu'aux ingénieurs et chercheurs. L'ouvrage propose aussi des voies pour la recherche, abordant les aspects pratiques au travers de la conception des algorithmes de résolution pour problèmes dits NP- complets, une partie est consacrée à ces aspects pratiques.
  Public : Licence, Maitrise, Doctorat, Ingéniorat
Tables des matières
- - Complexité et algorithmique avancée
  - Une introduction
  - Ivan Lavallée
  - Hermann éditeurs
  - Remerciements2
  - 1 Introduction11
  - 1.1 Pourquoi tant de théorie ?12
  - I Historique19
  - 2 Histoires d'algorithmes21
  - 2.1 La notion naïve d'algorithme22
  - 2.1.1 L'algorithme d'Euclide24
  - 2.1.2 Algorithme de l'équation quadratique25
  - 2.1.3 Un algorithme qui vient de loin26
  - 2.1.4 L'algorithme du Labyrinthe29
  - II Survol34
  - 3 Un rapide tour d'horizon36
  - 3.1 Une stratégie de résolution37
  - 3.2 Deux exemples37
  - 3.3 Les classes P et NP39
  - 3.4 La classe NP39
  - 3.4.1 Réductibilité polynomiale40
  - 3.4.2 La classe NPC41
  - 3.5 Conclusion42
  - 4 La Machine de Turing43
  - 4.1 La Machine de Turing comme modèle d'algorithme43
  - 4.1.1 Description détaillée d'une Machine de Turing45
  - 4.1.2 Précision du concept d'algorithme48
  - 4.2 Un peu de formalisme51
  - 4.3 Machines de Turing élémentaires52
  - 4.3.1 Machine qui s'arrête52
  - 4.3.2 Machine « tout à gauche », machine « tout à droite »52
  - 4.3.3 Machine à effacement et écriture53
  - 4.3.4 Machines chercheuses de 1 ou de 053
  - 4.3.5 Composition de machines de Turing élémentaires53
  - 4.3.5.1 Mise en séquence de machines54
  - 4.3.5.2 Branchement de machines54
  - 5 La Machine de Turing Universelle56
  - 5.1 Le problème général56
  - 5.1.1 Le problème du codage58
  - 5.1.1.1 L'unidimensionnalité58
  - 5.1.1.2 La finitude du codage59
  - 5.1.1.3 Codage de l'instance61
  - 5.1.2 Numérotation des Machines de Turing64
  - 5.2 Machine de Turing à plusieurs rubans64
  - 5.3 Calculateur, calculateur universel66
  - 5.3.1 Calculateur universel69
  - 5.3.2 Le nombre de Chaïtin69
  - 6 Complexité de Kolmogorov (rudiments)71
  - 6.1 Introduction71
  - 6.1.1 Interprétation intuitive72
  - 6.1.2 Paradoxe73
  - 6.2 Description d'un objet73
  - 6.2.0.1 Fonction partiellement récursive74
  - 6.3 Descriptions et tailles75
  - III Théorie78
  - 7 Considérations théoriques80
  - 7.1 Quelques définitions fondamentales80
  - 7.1.1 Le problème, informellement80
  - 7.1.2 Essais de définitions81
  - 7.1.2.1 Ensembles récursifs81
  - 7.1.2.2 Ensembles récursivement énumérables82
  - 7.1.2.3 Ensembles approximables et inapproximables83
  - 7.1.3 Des ensembles bien particuliers85
  - 7.1.3.1 Taille d'un ensemble86
  - 7.1.3.2 Des cardinaux à l'infini87
  - 7.1.3.2.1 Cardinaux infinis88
  - 7.1.3.2.2 Calcul sur les cardinaux infinis89
  - 7.1.3.2.3 Ensembles dénombrables90
  - 7.1.3.2.4 De plus en plus infini91
  - 7.2 Indécidabilité92
  - 7.2.1 Plus ou moins indécidable94
  - 7.3 Mathématiques ou informatique ?94
  - 8 Ordres, Treillis et Algèbre de Boole96
  - 8.1 Relations d'équivalence96
  - 8.1.1 Ensemble quotient96
  - 8.2 Ordre, ordre partiel et préordre97
  - 8.2.1 Isomorphisme et dualité d'ensembles ordonnés98
  - 8.3 Treillis99
  - 8.3.1 Treillis distributifs100
  - 8.4 L'algèbre de Boole101
  - 8.5 L'algèbre de Boole des expressions logiques101
  - 8.6 Expressions booléennes et problème SAT103
  - 8.6.1 Satisfaction d'une expression105
  - 8.6.2 Algèbre de Boole107
  - 8.6.2.1 Formes normales107
  - 8.6.3 Le problème SAT108
  - 9 Circuits booléens109
  - 9.1 Portes et circuits digitaux109
  - 9.1.1 Base standard111
  - 9.2 Fonctions booléennes et circuits114
  - 9.3 Circuits booléens115
  - 9.3.0.1 Circuit-SAT118
  - 10 Quelques problèmes de référence119
  - 10.1 Introduction à la théorie des graphes119
  - 10.1.1 Petit vocabulaire de théorie des graphes120
  - 10.1.2 Exemple de représentation des graphes120
  - 10.1.3 Quelques sous-ensembles remarquables de sommets122
  - 10.1.4 Détermination des ensembles absorbants et du nombre d'absorption124
  - 10.2 Existence de chemin125
  - 10.2.1 Complexité129
  - 10.3 Flot maximal130
  - 10.4 Couplage dans un graphe biparti133
  - 10.5 La satisfiabilité134
  - 10.5.1 Une technique algorithmique : la réduction135
  - 10.6 Le voyageur de commerce138
  - 11 Algorithme, résolution141
  - 11.1 Faire son choix142
  - 11.2 Pourquoi la complexité ?143
  - 11.3 Comment interpréter la complexité ?147
  - 11.4 Des mots147
  - 11.4.1 Problème, instance, solution147
  - 11.4.2 Algorithme148
  - 11.4.3 Taille d'une instance148
  - 11.5 Fonction de complexité en temps149
  - 11.6 Problèmes de décision, langages, codage150
  - 11.6.1 Problème de décision150
  - 11.6.2 Langage151
  - 11.6.3 Codage151
  - IV Complexité154
  - 12 Classes de complexité156
  - 12.1 Machine de Turing et automates de Markov156
  - 12.1.1 Automates de Markov161
  - 12.1.1.1 Automate fini161
  - 12.1.1.2 Langage accepté, régulier162
  - 12.1.2 Machine à plusieurs rubans162
  - 12.2 Langage reconnaissable par une MT164
  - 12.2.1 Complexité en temps165
  - 12.3 La classe P166
  - 12.4 La classe NP167
  - 12.4.1 Approche informelle de la classe NP167
  - 13 NP complétude175
  - 13.1 Les relations entre P et NP175
  - 13.1.1 La transformation polynomiale175
  - 13.2 La classe des problèmes NP - complets, NPC177
  - 13.2.1 Un problème NP - complet, la satisfiabilité179
  - 13.2.2 Le problème de la satisfiabilité180
  - 13.3 SAT, problème NP - complet181
  - 13.3.1 Le théorème de Levin-Cook182
  - 13.3.1.1 Première partie : SAT est dans NP182
  - 13.3.1.2 Seconde partie182
  - 13.3.2 Équilibre190
  - 13.3.3 L'appartenance à NPC192
  - 13.3.3.1 Le cas de k-SAT193
  - 13.3.4 Couverture d'un graphe195
  - 14 Le pire n'est pas toujours certain204
  - 14.1 Autour de SAT204
  - 14.1.1 Le cas 2-SAT204
  - 14.2 Cas particuliers de SAT207
  - 14.2.1 SET et SAT207
  - 14.2.2 Validation, tautologie et non-satisfiabilité208
  - 14.2.3 Clauses de Horn209
  - 14.3 Le sac à dos212
  - 14.3.0.1 Recouvrement213
  - 14.3.0.2 Retour à SAD214
  - 14.3.1 Pseudo-polynomialité215
  - 14.4 Conclusion216
  - 15 Complexité et Efficacité218
  - 15.1 Le produit matriciel218
  - 15.2 La multiplication de Straßen219
  - 15.3 Complexité de la méthode de Straßen220
  - 15.3.1 De la complexité à l'efficacité222
  - 15.3.2 La programmation récursive223
  - 15.4 Reformulation de la méthode de Straßen224
  - 15.4.1 Hypothèses et notations préliminaires224
  - 15.4.2 Proposition de Straßen225
  - 15.4.3 Généralisation226
  - 15.5 L'algorithme228
  - 15.5.1 Idée de base228
  - 15.5.2 Obtention des produits de Straßen228
  - 15.6 Règles d'obtention des termes228
  - Conclusion228
  - V Que faire ?230
  - 16 Des algorithmes pour problèmes NPC232
  - 16.1 L'exhaustivité des procédures combinatoires232
  - 16.1.1 La méthode PSEP233
  - 16.1.1.1 Le principe de séparation233
  - 16.1.1.2 L'évaluation234
  - 16.1.1.2.1 La fonction d'évaluation234
  - 16.2 Le cas des jeux237
  - 16.2.1 La méthode alpha/bêta240
  - 16.3 En guise de conclusion243
  - 16.4 Introduction à l'algorithmique probabiliste245
  - 16.5 Des algorithmes aux parfums de casinos245
  - 16.5.0.0.2 Exemple246
  - 16.5.1 Algorithmes numériques probabilistes246
  - 16.5.2 Algorithmes de Las Vegas (deux cas à distinguer)247
  - 16.5.3 Algorithmes de Monte-Carlo247
  - 16.6 Probabilités versus déterminisme247
  - 16.6.1 Le problème247
  - 16.7 Les probabilités pour réduire la complexité249
  - 16.7.1 Généralités249
  - 16.7.2 Le Problème250
  - 16.7.3 L'algorithme de Borükva251
  - 16.7.3.1 Complexité de la phase Borükva252
  - 16.7.4 Arêtes « lourdes » et vérification d'arbre couvrant minimum253
  - 16.7.5 Echantillonnage aléatoire pour les arbres couvrants minimum254
  - 16.7.6 Algorithme d'arbre couvrant minimum linéaire256
  - 16.7.7 Algorithme probabiliste de construction d'un arbre couvrant minimal257
  - 16.8 Résoudre SAT de manière probabiliste258
  - 16.8.1 Rappel258
  - 16.8.2 Analyse d'une solution probabiliste à 2-SAT259
  - 16.8.3 Etude de la chaîne de Markov permettant d'estimer la complexité en temps de l'algorithme262
  - 16.8.3.1 Cas où la formule est éventuellement insatisfiable264
  - 16.8.4 Généralisation à 3-SAT265
  - 16.8.4.1 L'algorithme265
  - 16.8.5 Proposition d'algorithme modifié267
  - 16.9 Un problème d'accord270
  - 16.9.1 Un exemple issu de la Biologie271
  - 16.10 Une solution synchrone271
  - 16.10.1 Le protocole273
  - 16.10.2 Preuve de bon fonctionnement in absurdo273
  - 16.10.3 Évaluation de la complexité274
  - 16.11 Le cas asynchrone274
  - 16.11.1 Evaluation de la complexité275
  - 16.11.2 Preuve275
  - 17 Kolmogorov le retour278
  - 17.1 Introduction278
  - 17.2 Information et codage, de Shannon à Kolmogorov279
  - 17.2.1 Entropie279
  - 17.2.1.1 Le cas combinatoire280
  - 17.2.1.2 Le cas probabiliste281
  - 17.3 Notations284
  - 17.3.1 Le théorème d'invariance286
  - 17.3.2 Ne pas dépasser les bornes290
  - 17.3.3 Compressibilité et incompressibilité291
  - 18 Le modèle quantique294
  - 18.1 Introduction294
  - 18.2 Retour sur les bits classiques - Cbits295
  - 18.3 Opérations sur les Cbits297
  - 18.3.1 Transformation de Hadamard301
  - 18.4 Les bits quantiques ou Qbits301
  - 18.5 Opérations sur les Q-bits303
  - 18.6 Comment extraire l'information des Qbits ?305
  - A Notations de Bachman-Landau307
  - A.1 Les symboles grand Omicion, Oméga, Thêta307
  - A.1.1 Le symbole petit o308
  - Bibliographie310
Origine de la notice:
- BNF