Complexité algorithmique
Par :Formats :
- Réservation en ligne avec paiement en magasin :
- Indisponible pour réserver et payer en magasin
- Nombre de pages410
- PrésentationBroché
- Poids0.796 kg
- Dimensions19,0 cm × 24,0 cm × 2,3 cm
- ISBN978-2-7298-8692-9
- EAN9782729886929
- Date de parution22/04/2014
- CollectionRéférences sciences
- ÉditeurEllipses
Résumé
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.