Les petits cailloux

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