\documentclass[11pt]{article}

\usepackage{fullpage,french,epsf,fancyheadings}

\pagestyle{fancy}
\lhead{Dessin de circuits élémentaires}
\rhead{Jean-Christophe Filliâtre}

\reversemarginpar
\newcommand{\question}{\marginpar{\hfill$\Box$}}

\begin{document}

\begin{center}
  \LARGE\bf Dessin de circuits élémentaires
\end{center}
\bigskip

On se propose ici de représenter graphiquement des circuits élémentaires
construits à partir de portes logiques AND, OR et NOT. Pour cela, on définit
le type \verb!circuit! des formules logiques correspondant à de tels
circuits :
\begin{verbatim}
     type circuit = AND of circuit * circuit
                  | OR  of circuit * circuit
                  | NOT of circuit
                  | Entree of string ;;
\end{verbatim}
Le constructeur \verb!Entree! correspond à un fil d'entrée du circuit,
c'est-à-dire à une variable propositionnelle libre de la formule
correspondante.


\section{Préliminaires}

\noindent
Ecrire \question des fonctions traçant, à une position \verb!x,y!
donnée, les portes AND, OR et NOT, de la manière suivante :

\medskip
\hfil\epsfbox{portes.eps}\hfil
\medskip

\noindent
Ecrire \question une fonction \verb!ligne_brisee! traçant une ligne
brisée d'un point \verb!x1,y1! à un point \verb!x2,y2! en effectuant
un coude sur la colonne \verb!xi!, de la manière suivante :

\medskip
\hfil\epsfbox{ligne_brisee.eps}\hfil
\medskip

\noindent
Ecrire \question une fonction \verb!hauteur! calculant la hauteur
d'un circuit (c'est-à-dire sa hauteur en tant qu'arbre), une fonction
\verb!largeur! calculant sa largeur  et une fonction {\tt parcours :
circuit ->~string list} collectant toutes les entrées d'un circuit
par un parcours préfixe.


\section{Dessin d'un circuit}

Etant donné un circuit $c$ à représenter graphiquement, on peut
commencer par calculer sa hauteur $h$ et l'ensemble $E = e_1, \dots,
e_n$ de ses entrées par un parcours préfixe.
On choisit d'orienter le circuit de la gauche vers la droite :
les entrées seront représentées sur une même colonne, à gauche, 
et les différentes profondeurs de l'arbre sur différentes colonnes, le
sommet de l'arbre (le résultat du circuit) se trouvant tout à droite.
Il y aura donc $h$ colonnes (une pour les entrées, et $h-1$ pour les
différentes profondeurs de l'arbre). 

\noindent
Exemple : le circuit $c = (a+\bar{b})b$, représenté par l'arbre
$$\verb!AND (OR (Entree "a", NOT (Entree "b")), Entree "b")!$$
sera  tracé de la manière suivante :

\medskip
\hfil\epsfbox{circuit1.eps}\hfil
\medskip


L'idée est  d'écrire une  fonction  de  dessin récursive, prenant   en
argument la profondeur $p$ dans  l'arbre, des bornes $ymin$ et  $ymax$
fixant les limites des ordonnées pour le tracé, et le sous-arbre $T$ à
tracer. Cette   fonction renvoie  en résultat  le  point de  sortie du
circuit qu'elle a tracé.

Cette  fonction se rappelle récursivement   sur les sous-arbes de $T$,
avec des paramètres $ymin$ et $ymax$ calculés suivants les largeurs de
ces  sous-arbres ($l_1$ et $l_2$ sur  le schéma). Les points de sortie
renvoyés  permettent alors de relier ces  circuits à  la porte logique
définissant  $T$, par des lignes  brisées. Lorsque l'on doit connecter
un arbre à une entrée (constructeur {\tt Entree}) la position de cette
entrée peut  être calculée  directement,  et on trace  alors une ligne
brisée  partant de cette  entrée (on choisira des colonnes différentes
pour les coudes de ces lignes brisées).
Ceci est illustré sur le schéma suivant :

\medskip
\hfil\epsfbox{circuit_idee.eps}\hfil
\medskip

\noindent
Ecrire \question une fonction \verb!dessine_circuit! réalisant cette méthode
de dessin, et testez la sur le circuit additionneur 1-bit.

\medskip
\epsfxsize=9cm
\hfil\epsfbox{add1.eps}\hfil


\end{document}