Logique et complexité / Richard Lassaigne, Michel de Rougemont [ Livre]

Auteur principal: Lassaigne, RichardCo-auteur: Rougemont, Michel deLangue: 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

Powered by Koha