next up previous contents
suivant: Transformation polynomiale du problème monter: Conditions nécessaires et suffisantes précédent: Valeurs pertinentes pour   Table des matières

Exemple

Les expressions :


\begin{displaymath}C(b_{2}, b_{1}) = ((\Delta(b_{2}) \geq 8) \wedge (\Delta(b_{1...
...)) \vee ((\Delta(b_{2}) \geq 6) \wedge (\Delta(b_{1}) \geq 5)) \end{displaymath}


\begin{displaymath}\vee ((\Delta(b_{2}) \geq 4) \wedge (\Delta(b_{1}) \geq 6)) \vee ((\Delta(b_{2}) \geq 1) \wedge (\Delta(b_{1}) \geq 7))\end{displaymath}

et


\begin{displaymath}C(b_{1}, b_{2}) = ((\Delta(b_{1}) \geq 10) \wedge (\Delta(b_{...
...)) \vee ((\Delta(b_{1}) \geq 6) \wedge (\Delta(b_{2}) \geq 5)) \end{displaymath}


\begin{displaymath}\vee ((\Delta(b_{1}) \geq 1) \wedge (\Delta(b_{2}) \geq 8))\end{displaymath}

s'écrivent sous forme clausale de la façon suivante :


\begin{displaymath}C(b_{2}, b_{1}) = (\Delta(b_{2}) \geq 1) \wedge (\Delta(b_{1}...
...1) \wedge ((\Delta(b_{2}) \geq 8) \vee (\Delta(b_{1}) \geq 5)) \end{displaymath}


\begin{displaymath}\wedge ((\Delta(b_{2}) \geq 6) \vee (\Delta(b_{1}) \geq 6)) \wedge ((\Delta(b_{2}) \geq 4) \vee (\Delta(b_{1}) \geq 7))\end{displaymath}

et


\begin{displaymath}C(b_{1}, b_{2}) = (\Delta(b_{1}) \geq 1) \wedge (\Delta(b_{2}...
...) \wedge ((\Delta(b_{1}) \geq 10) \vee (\Delta(b_{2}) \geq 5)) \end{displaymath}


\begin{displaymath}\wedge ((\Delta(b_{1}) \geq 6) \vee (\Delta(b_{2}) \geq 8))\end{displaymath}

On cherche ensuite le « maximin » sur chaque buffer :


\begin{displaymath}\Delta_{min}(b_{1}) = \max ( x_{min}(C(b_{1}, b_{2})), y_{min}(C(b_{2}, b_{1}))) \end{displaymath}


\begin{displaymath}\Delta_{min}(b_{2}) = \max ( x_{min}(C(b_{2}, b_{1})), y_{min}(C(b_{1}, b_{2}))) \end{displaymath}

Ce qui nous donne :


\begin{displaymath}\Delta_{min}(b_{1}) = \max ( x_{l} , y_{1} ) \end{displaymath}


\begin{displaymath}\Delta_{min}(b_{2}) = \max ( x_{l} , y_{1} ) \end{displaymath}

Avec les valeurs :


\begin{displaymath}\Delta_{min}(b_{1}) = \max ( 1 , 1 ) \end{displaymath}


\begin{displaymath}\Delta_{min}(b_{2}) = \max ( 1 , 1 ) \end{displaymath}

On remarque que quand les buffers sont tous de sens opposés, les valeurs minimales sont des $1$. Les domaines de définition sont les suivants :


\begin{displaymath}\Delta^{0}(b_{1}) = 1, \Delta^{1}(b_{1}) = 5, \Delta^{2}(b_{1}) = 6, \Delta^{3}(b_{1}) = 7, \Delta^{4}(b_{1}) = 10 \end{displaymath}


\begin{displaymath}\Delta^{0}(b_{2}) = 1, \Delta^{1}(b_{2}) = 4, \Delta^{2}(b_{2}) = 5, \Delta^{3}(b_{2}) = 6, \Delta^{5}(b_{2}) = 8 \end{displaymath}


next up previous contents
suivant: Transformation polynomiale du problème monter: Conditions nécessaires et suffisantes précédent: Valeurs pertinentes pour   Table des matières
Alexandre 2009-05-14