Introduction à la calculabilité
"Quelles sont les limites de l'informatique ? La théorie de la calculabilité apporte des réponses à cette question : elle démontre notamment que certains problèmes informatiques ne peuvent pas être résolus par des programmes. Cet ouvrage a pour but de présenter aux informaticiens les éléme...
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Livre papier |
| Langue: | Français |
| Publié: |
Paris :
InterÉditions
DL 1991.
|
| Collection: | IIA. Informatique intelligence artificielle
|
| Sujets: | |
| Autres localisations: | Voir dans le Sudoc |
| LEADER | 04333nam a22003977a 4500 | ||
|---|---|---|---|
| 001 | 48093 | ||
| 008 | 911118t19911991xxe ||| |||| 00| 0 fre d | ||
| 009 | PPN00242794X | ||
| 020 | |a 9782729603724 (br.) : |c 150 FRF | ||
| 020 | |a 2729603727 (br.) : |c 150 FRF | ||
| 024 | |a 9782729603724 | ||
| 041 | 0 | |a fre | |
| 080 | |a 51 | ||
| 082 | |a 511.35 | ||
| 082 | |a 511.352 | ||
| 084 | |a 03-01. 2010 | ||
| 084 | |a 68-01. 2010 | ||
| 084 | |a 68Qxx. 2010 | ||
| 084 | |a 03Dxx. 2010 | ||
| 084 | |a F.1 | ||
| 100 | 1 | |a Wolper, Pierre, |d 1955- | |
| 245 | 1 | 0 | |a Introduction à la calculabilité |c Pierre Wolper,... |
| 260 | |a Paris : |b InterÉditions, |c DL 1991. | ||
| 300 | |a 1 volume (268 pages) : |b illustrations, couverture illustrée en couleurs ; |c 23 cm. | ||
| 490 | 1 | |a IIA. Informatique intelligence artificielle | |
| 504 | |a Bibliographie p. [261]-262. Index | ||
| 505 | 0 | |a 1. Introduction -- 1.1 Motivation -- 1.2 Problèmes et programmes -- 1.3 La formalisation des problèmes -- 1.4 La description de langages -- 1.5 Les langages non réguliers -- 1.6 Un aperçu de la suite -- 1.7 Exercices -- 2. Les automates finis -- 2.1 Introduction -- 2.2 Description -- 2.3 Formalisation -- 2.4 Représentation et exemples -- 2.5 Les automates finis et exemples -- 2.6 L'élimination du non-déterminisme -- 2.7 Automates finis et expression régulières -- 2.8 Exercices -- 3. Les grammaires régulières -- 3.1 Introduction -- 3.2 Les grammaires -- 3.3 Les grammaires régulières -- 3.4 Les langages réguliers -- 3.5 Au-delà des langages réguliers -- 3.6 Les applications des langages réguliers -- 3.7 Exercices -- 4. Automates à pile et langages hors-contexte -- 4.1 Les automates à pile -- 4.2 Les langages hors-contexte -- 4.3 Au-delà des langages hors-contexte -- 4.4 Les automates à pile déterministes -- 4.5 Exercices -- 5. Les machines de Turing -- 5.1 Introduction -- 5.2 Définition -- 5.3 Thèse de Turing-Church -- 5.4 Machines de Turing non déterministes -- 5.5 Machines de Turing universelles -- 5.6 Fonctions calculables par une machine de Turing -- 5.7 Exercices -- 6. Les fonctions récursives -- 6.1 Introduction -- 6.2 Les fonctions primitives récursives -- 6.3 Les prédicats primitifs récursifs -- 6.4 Au-delà des focntions primitives récursives -- 6.5 Les fonctions [mu]-récursives -- 6.6 Fonctions [mu]-récursives et fonctions calculables -- 6.7 Fonctions partielles -- 6.8 Exercices -- 7. La non-calculabilité -- 7.1 Introduction -- 7.2 Démontrer l'indécidabilité -- 7.3 Des problèmes indécidables -- 7.4 Les propriétés des langages récursivement énumérables -- 7.5 D'autres problèmes indécidables -- 7.6 Fonctions non calculables -- 7.7 Exercices -- 8. La complexité -- 8.1 Introduction -- 8.2 Mesurer la complexité -- 8.3 Le sproblèmes polynomiaux -- 8.4 Les transformations polynomiales -- 8.5 La classe NP -- 8.6 Un premier problème NP-complet -- 8.7 D'autres problèmes NP-complets -- 8.8 Interpréter la NP-complétude -- 8.9 Autres classes de complexité -- 8.10 Exercices | |
| 520 | |a "Quelles sont les limites de l'informatique ? La théorie de la calculabilité apporte des réponses à cette question : elle démontre notamment que certains problèmes informatiques ne peuvent pas être résolus par des programmes. Cet ouvrage a pour but de présenter aux informaticiens les éléments essentiels de cette science qui consiste en l'étude de ce qu'il est possible ou non de résoudre grâce à l'outil informatique, quels que soient le type et les performances de la machine utilisée. Il aborde en premier lieu les langages formels, les automates et les grammaires puis introduit la notion de calculabilité par le biais des machines de Turing et des fonctions récursives. en dernier lieu, sont étudiées les notions de complexité, et plus particulièrement les problèmes NP-complets.[...] (source : 4ème de couverture) | ||
| 650 | |a Décidabilité (logique mathématique) | ||
| 650 | |a Calcul formel | ||
| 650 | |a Langages formels | ||
| 650 | |a Complexité de calcul (informatique) | ||
| 650 | |a Fonctions récursives | ||
| 650 | |a Automates mathématiques, Théorie des | ||
| 650 | |a Fonctions calculables | ||
| 997 | |0 48093 |1 Livre papier |a Ressource papier |c 0/Orléans/ |c 1/Orléans/BU Sciences, Technologies, STAPS/ |z Orléans, BU Sciences, Technologies, STAPS, F276-14 | ||