Introduction à la calculabilité / Pierre Wolper,... [ Livre]

Auteur principal: Wolper, PierreLangue: Français.Publication : Paris : InterEditions, 1991Description : 268 p. ; 23 cmISBN: 2729603727.Collection: IIAClassification: F 4 1 Logique mathématiqueRésumé: Sommaire 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 non déterministes 2.6 L'élimination du non-déterminisme 2.7 Automates finis et expressions 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 fonctions primitives récursives 6.5 Les fonctions µ-récursives 6.6 Fonctions µ-récursives et fonctions calculables 6.7 Fonctions partielles 7 - La non-calculabilité 7.1 Introduction 7.2 Démonstrer 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 Les problè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.Sujet - Nom commun: Langages formels | Fonctions récursives | Fonctions calculables | Décidabilité (logique mathématique) | Complexité de calcul (informatique) | Calcul formel | Automates mathématiques, Théorie des
Current location Call number Status Notes Date due Barcode
ENS Rennes - Bibliothèque
Magasin (archives)
F 4 1 WOL (Browse shelf) Available F 4 1 Logique mathématique 00000966

Bibliogr. p. 261-262. Index

Bibliogr., index

Sommaire
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 non déterministes
2.6 L'élimination du non-déterminisme
2.7 Automates finis et expressions 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 fonctions primitives récursives
6.5 Les fonctions µ-récursives
6.6 Fonctions µ-récursives et fonctions calculables
6.7 Fonctions partielles
7 - La non-calculabilité
7.1 Introduction
7.2 Démonstrer 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 Les problè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

Powered by Koha