Modèles de calcul, TD numéro 6

Natacha Portier vendredi 10 mars 2000

Question 1

Considérons le modèle des corps différentiels. Le corps R est muni d’une fonction unaire d, appelée dérivée, qui est additive et qui vérifie la formule de Leibniz : pour tous x et y nous avons d(x+y) = dx+dy et d(xy) = xdy+ydx. Nous considérons des circuits dont les portes sont soit des entrées étiquetées par une variable ou le réel 1, soit des dérivées et reçoivent une flèche, soit des portes de calcul arithmétique +, × ou − et reçoivent deux flèches.

Question 1,1

Donner le circuit dont les entrées sont x et y et dont l’unique sortie calcule d(2x + d^{2}(xy)), où d^{2} désigne la composée d ∘ d.

Faire remonter les dérivées : donner un circuit qui calcule la même chose mais dont les uniques portes de dérivées sont situées sous les entrées.

Un tel circuit est dit réduit. Nous allons généraliser cette méthode et trouver un polynôme p tel que tout circuit de taille n soit équivalent à un circuit réduit de taille p(n). C’est un outil pour l’étude de la complexité des problèmes dans les corps différentiels.

Question 1,2

Soit C un circuit et δ le nombre maximal de portes de dérivées sur un chemin allant d’une entrée à une sortie. Montrer par induction que C est équivalent à un circuit réduit qui a au plus δ dérivées successives sous chacune de ses entrées.

Remarque : La preuve donne un algorithme de construction du circuit réduit qui fait exploser le nombre de portes...

Question 1,3

Donner un circuit réduit dont les entrées sont x, y et 1 et dont l’unique sortie calcule d^{n}(xy). Donner sa taille, qui doit être polynomiale en n.

Question 1,4

Soit C un circuit, δ le nombre maximal de portes de dérivées sur un chemin allant d’une entrée à une sortie et N le nombre maximal de portes de calcul arithmétique sur un chemin allant d’une entrée à une sortie.

Nous définissons les niveaux (arithmétiques) du circuit de la manière suivante. Pour i compris entre 0 et N, une porte arithmétique appartient au niveau i si le nombre maximal de portes de calcul arithmétique sur un chemin allant d’une entrée à cette porte est i. Les portes de dérivées successives d’une porte arithmétique appartiennent alors au même niveau qu’elle.

Décomposer le circuit de la question 1,1 en niveaux et montrer qu’une porte arithmétique reçoit ses flèches des niveaux strictement supérieurs.

Un circuit est réduit si toutes les dérivées sont dans le niveau 0.

Question 1,5

Soit i compris entre 1 et N. Supposons que les dérivées les plus basses soient dans le niveau i, et que chaque porte arithmétique dans les niveaux 0, ..., i ait δ portes de dérivées successives.

Montrer commment nous pouvons construire un circuit équivalent dont les dérivées les plus basses sont dans le niveau i − 1, en supprimant les dérivées du niveau i, en laissant inchangés les niveaux 0, ..., i−1, en ajoutant des portes arithmétiques mais pas de porte de dérivée.

Question 1,6

En déduire une méthode de réduction d’un circuit et le polynôme p, ainsi que la profondeur du circuit obtenu.

Question 2

Soit S une fonction ternaire sur les booléens, appelée sélecteur et telle que pour tous y et z nous ayons S(0, y, z) = y et S(1, y, z) = z. Exprimer cette fonction à l’aide des connecteurs logiques et montrer que réciproquement toute fonction booléenne peut s’exprimer avec seulement le sélecteur.

Définitions

Nous généralisons la définition de sélecteur aux entrées réelles : S est un sélecteur si pour tous y et z nous avons S(0, y, z) = y, S(1, y, z) = z et si x n’est ni 0 ni 1 alors S(x, y, z) est un polynôme quelconque.

Nous définissons un modèle de calcul sur les réels en généralisant la notion de circuit.

Un circuit sur le corps R est un graphe orienté sans cycle orienté. Les sommets sont appelés portes, et les arêtes flèches. Ce n’est pas nécessairement un arbre : une porte peut émettre plusieurs flèches. Les portes qui ne reçoivent pas de flèches sont les entrées. Elles sont étiquetées par un élément de R ou par une variable. Les autres portes sont étiquetées par une opération arithmétique, +, × ou - et reçoivent deux flèches, ou par un test =0? ou ≥ 0? et n’en reçoivent qu’une, ou par la fonction sélecteur S et en reçoivent trois. C’est le modèle des corps ordonnés.

Le calcul dans un circuit s’effectue de proche en proche de manière canonique. Un porte de test calcule 1 si la réponse est oui et 0 sinon.

Question 3

Montrer que nous pouvons nous passer des portes de sélection en multipliant par une constante le nombre de portes et la profondeur.

Question 4

Supposons qu’il existe des portes de division qui reçoivent deux flèches (nous supposons que le cas de la division par zéro ne se produit jamais). Montrer que nous pouvons nous passer des portes de division pour faire les tests en multipliant par une constante le temps séquentiel et le temps parallèle.

Question 5

Montrer que la fonction calculée par une porte d’un circuit est une fonction polynôme par morceaux, les morceaux étant définis par des systèmes d’équations et d’inéquations polynomiales et les variables des polynômes étant les entrées du circuit.

Question 6

Que calculons nous s’il n’y a pas de porte de multiplication et que seuls les tests d’égalité sont autorisés? (circuit sur un groupe).

Montrer que dans ce cas nous ne pouvons pas nous passer du sélecteur.