SOLDES

Jusqu'à -70% sur une sélection d'articles*

Complexité et décidabilité

Par : Patrick Dehornoy
Formats :
Grand Format
65,80 €
Nous vous prions de nous excuser mais rencontrons momentanément des soucis d'approvisionnement. C’est le moment de vous laisser tenter par nos livres numériques et notre offre occasion.
  • Paiement en ligne :
    • Livraison à domicile ou en point Mondial Relay estimée à partir du 12 novembre
      Cet article sera commandé chez un fournisseur et vous sera envoyé 127 jours après la date de votre commande.
    • Retrait Click and Collect en magasin gratuit
  • Réservation en ligne avec paiement en magasin :
    • Indisponible pour réserver et payer en magasin
  • Nombre de pages200
  • FormatGrand Format
  • PrésentationBroché
  • Poids0.38 kg
  • Dimensions17,0 cm × 24,0 cm × 1,2 cm
  • ISBN3-540-56899-9
  • EAN9783540568995
  • Date de parution10/09/1993
  • CollectionMathématiques & Applications
  • ÉditeurSpringer

Résumé

Cet ouvrage présente les bases de la théorie de la complexité des algorithmes et en dérive les théorèmes fondamentaux de décidabilité et d'indécidabilité pour la logique et l'arithmétique, dont le premier théorème d'incomplétude de Gödel. En faisant reposer toutes les preuves sur le codage de l'arrêt d'une machine de Turing, on a souligné l'homogénéité et l'unité profonde des résultats présentés. L'approche par les machines de Turing est très accessible grâce à la familiarité donnée aujourd'hui par l'informatique.
Le livre n'est pas une encyclopédie exhaustive, mais parvient de façon rapide à démontrer un choix de résultats représentatifs de l'ensemble de la théorie.