COMPLEXITÉ ALGORITHMIQUE

Ce livre présente d'abord les notions de base en théorie de la complexité algorithmique avant de traiter de nombreux sujets avancés. Il s'agit du seul ouvrage en français couvrant un si large spectre dans ce domaine central en informatique théorique. Les notions mathématiques utiles sont rappelées et aucun prérequis, outre une culture mathématique de base, n'est supposé. La description rigoureuse du modèle de calcul (la machine de Turing) permet d'aborder solidement les bases de la complexité en temps et en espace (théorèmes de hiérarchie, accélération, etc.) et d'étudier le problème P = NP: NP-complétude, théorèmes de Ladner, de Mahaney… Le non-déterminisme est aussi exploré par les oracles et la hiérarchie polynomiale, ainsi que par les protocoles interactifs qui poursuivent l'étude menée sur les algorithmes probabilistes. Un chapitre est consacré aux classes de comptage avec le théorème de Toda et la complétude du permanent. Enfin, la problématique du calcul par circuits (non-uniformité) est détaillée, de nombreuses bornes inférieures sont montrées ainsi que les liens profonds avec la dérandomisation. Au sommaire: 1: Le modèle de calcul; 2: Considérations de base sur le temps; 3: NP-complétude; 4: Considérations de base sur l'espace; 5: Uniformité et non-uniformité; 6: Algorithmes probabilistes; 7: Oracles et limites de la diagonalisation; 8: La hiérarchie polynomiale; 9: Comptage; 10: Protocoles interactifs; 11: Bornes inférieures non uniformes; 12: Dérandomisation et bornes inférieures.