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...
Guardat en:
| Autor principal: | |
|---|---|
| Format: | Livre papier |
| Idioma: | Français |
| Publicat: |
Paris :
InterÉditions
DL 1991.
|
| Col·lecció: | IIA. Informatique intelligence artificielle
|
| Matèries: | |
| Autres localisations: | Voir dans le Sudoc |
Taula de continguts:
- 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