سنگ‌ریزه‌های کوچک: یک رویکرد مدل‌نظری به الگوریتمی (نور المنطق و المعرفه)

Couverture Page de titre Préface. Exercices. Notes historiques et bibliographiques Chapitre 1 Quelques algorithmes I.A. Mots booléens 1.B. Les quatre opérations 1.C. Systèmes d'équations I.C.a. Equations linéaires booléennes I.C.b. Equations polynomiales booléennes, la question P = ? NP 1.C.c. Equations disjonctives, le problème SA T 1.C.d. Equations linéaires à coefficients entiers Exercices. Notes historiques et bibliographiques Chapitre 2 Termes et circuits booléens 2.A. Fonctions booléennes 2.B. Les définitions de base 2.C. Relations évidentes entre taille, profondeur, etc 2.D. Effet Shannon 2.E. Ecriture linéaire des tennes 2.F. Théorème de Spira, Problème du temps parallèle Exercices. Notes historiques et bibliographiques Chapitre 3 Fonctions et relations: termes et formules libres 3.A. Structures fonctionnelles 3.B. Relations 3.C. Remplacement des relations par des fonctions Exercices. Notes historiques et bibliographiques Chapitre 4 Calculs en temps polynomial 4.A. Calculs dans une structure quelconque 4.B. Représentation de la fonction de transition d'une machine par un circuit 4.C. Algorithmes et suites de circuits Exercices. Notes historiques et bibliographiques Chapitre 5 Problèmes booléens 5.A. Structures localement finies 5.B. Théorèmes de Koiran : les réels avec diverses opérations 5.C. Structures ad hoc: dictionnaires linéaires, arborescents et séquentiels Exercices. Notes historiques et bibliographiques Chapitre 6 Classes de complexité existentielles 6.A. Fonnules existentielles et classe NP 6.B. Problèmes NP-complets 6.C. P = NP et élimination des quanteurs Exercices. Notes historiques et bibliographiques Chapitre 7 Exemples 7.A. La problématique 7.B. Structures sans fonctions 7.C. Structures localement finies 7.D. Les dictionnaires 7.E. Encore une koirânerie 7.F. Elimination rapide des quanteurs Exercices. Notes historiques et bibliographiques Chapitre 8 Questions d'espace 8.A. La hiérarchie polynomiale 8.B. Liens entre classes unifonnes et non unifonnes 8.C. Le truc à Michaux Exercices. Notes historiques et bibliographiques Références bibliographiques Index rerum et personarum