Logique et complexité
Coll. Informatique

Auteurs :

Langue : Français
Date de parution :
Ouvrage 322 p. · 15.5x23.5 cm · Broché
Épuisé
ISBN : 9782866014964 EAN : 9782866014964
Hermes Science

· PDF x2 : 59,00 € ·
Acheter l'e-book e-book
Cet ouvrage présente certains résultats importants de la théorie de la complexité : son objet est la classification des problèmes suivant l'importance des ressources nécessaires à leur résolution. L'origine de cette théorie apparaît dans l'étude des problèmes difficiles à résoudre sur un ordinateur. Ce domaine, considérablement développé au cours des vingt dernières années, concentre actuellement une large part de la recherche en informatique.
1. Complexité : le temps et l'espace 2. Définissabilité 3. Définitions inductives et logique du second ordre 4. La complexité en temps : les classes P et NP 5. Modèles de calcul parallèle 6. La complexité en espace : L, FL, NL, PESPACE 7. Classes probabilistes 8. Approximation 9. Classes au-dessus de NP 10. Logique et calculabilité Bibliographie - Index
Cet ouvrage présente certains résultats importants de la théorie de la complexité : son objet est la classification des problèmes suivant l'importance des ressources nécessaires à leur résolution. L'origine de cette théorie appara\'94t dans l'étude des problèmes difficiles à résoudre sur un ordinateur. Ce domaine considérablement développé au cours des vingt dernières années, concentre actuellement une large part de la recherche en informatique.