Logique et complexité / Richard Lassaigne, Michel de Rougemont [ Livre]
Langue: Français.Publication : Paris : Hermès, 1996Description : 322 p. ; 24 cmISBN: 2866014960.Collection: Collection Informatique, 1242-7691Classification: F 4 1 Logique mathématiqueRésumé: Sommaire 1. COMPLEXITE : LE TEMPS ET L'ESPACE 1.1. Classes de complexité 1.2. Hiérarchies en temps et en espace 1.3. Les machines à accès aléatoire 1.4. Exercices 2. DEFINISSABILITE 2.1. Définitions explicites 2.2. Lois 0-1 2.3. Définitions implicites 2.4. Exercices 3. DEFINITIONS INDUCTIVES ET LOGIQUE DU SECOND ORDRE 3.1. Les définitions inductives 3.2. La logique du second ordre 3.3. Exercices 4. LA COMPLEXITE EN TEMPS : LES CLASSES P et NP 4.1. Les classes NP et les problèmes NP-COMPLETS 4.2. Caractérisations logiques des classes P et FP 4.3 Exercices 5. MODELES DE CALCUL PARALLELE 5.1. Les circuits booléens 5.2. Complexité dans les modèles parallèles 5.3. Exemples de problèmes NC 5.4. Les PRAM 5.5. Exercices 6. LA COMPLEXITE EN ESPACE : L, FL, NL; PESPACE 6.1. Les classes L, NL et FL 6.2. L'espace séquentiel et le temps parallèle 6.3. La classe P ESPACE 6.4. Exercices 7. CLASSES PROBABILISTES 7.1. Classes probabilistes de décision 7.2. Vérification probabiliste 7.3. Exercices 8. APPROXIMATION 8.1. Problèmes d'optimisation 8.2. Problèmes de comptage 8.3. Exercices 9. CLASSES AU-DESSUS DE NP 9.1. La hiérarchie polynomiale 9.2. Généralisation de NP 9.3. Le temps exponentiel 9.4. Exercices 10. LOGIQUE ET CALCULABILITE 10.1. Logique propositionnelle 10.2. Logique du premier ordre 10.3. Calculabilité et récursivité 10.4. Indécidabilité et incomplétude.Sujet - Nom commun: Logique symbolique et mathématique | Logique du premier ordre | Décidabilité (logique mathématique) | Complexité de calcul (informatique)| Current location | Call number | Status | Notes | Date due | Barcode |
|---|---|---|---|---|---|
| ENS Rennes - Bibliothèque Informatique | F 4 1 LAS (Browse shelf) | Available | F 4 1 Logique mathématique | 00005873 | |
| ENS Rennes - Bibliothèque Informatique | F 4 1 LAS (Browse shelf) | Available | F 4 1 Logique mathématique | 00000937 |
L'ouvrage porte par erreur : ISSN 0993-5037
Bibliogr. p. 309-317. Index
Sommaire
1. COMPLEXITE : LE TEMPS ET L'ESPACE
1.1. Classes de complexité
1.2. Hiérarchies en temps et en espace
1.3. Les machines à accès aléatoire
1.4. Exercices
2. DEFINISSABILITE
2.1. Définitions explicites
2.2. Lois 0-1
2.3. Définitions implicites
2.4. Exercices
3. DEFINITIONS INDUCTIVES ET LOGIQUE DU SECOND ORDRE
3.1. Les définitions inductives
3.2. La logique du second ordre
3.3. Exercices
4. LA COMPLEXITE EN TEMPS : LES CLASSES P et NP
4.1. Les classes NP et les problèmes NP-COMPLETS
4.2. Caractérisations logiques des classes P et FP
4.3 Exercices
5. MODELES DE CALCUL PARALLELE
5.1. Les circuits booléens
5.2. Complexité dans les modèles parallèles
5.3. Exemples de problèmes NC
5.4. Les PRAM
5.5. Exercices
6. LA COMPLEXITE EN ESPACE : L, FL, NL; PESPACE
6.1. Les classes L, NL et FL
6.2. L'espace séquentiel et le temps parallèle
6.3. La classe P ESPACE
6.4. Exercices
7. CLASSES PROBABILISTES
7.1. Classes probabilistes de décision
7.2. Vérification probabiliste
7.3. Exercices
8. APPROXIMATION
8.1. Problèmes d'optimisation
8.2. Problèmes de comptage
8.3. Exercices
9. CLASSES AU-DESSUS DE NP
9.1. La hiérarchie polynomiale
9.2. Généralisation de NP
9.3. Le temps exponentiel
9.4. Exercices
10. LOGIQUE ET CALCULABILITE
10.1. Logique propositionnelle
10.2. Logique du premier ordre
10.3. Calculabilité et récursivité
10.4. Indécidabilité et incomplétude