11FCT.tex

   1 Cette section  présente deux  approches permettant de
   2 générer des fonctions $f$ dont le graphe des itérations $\textsc{giu}(f)$
   3 est fortement
   4 connexe.
   5 La première est algorithmique mais grossière (section~\ref{sub:sccg2})
   6 tandis que la seconde s'appuie sur des conditions suffisantes
   7 sur le graphe d'interactions de la fonction booléenne $f$
   8 (Section~\ref{sub:sccg1}).
   9 %pour obtenir un graphe d'itérations fortement connexe (Section~\ref{sub:sccg1}).
  10
  11 \subsection{Génération algorithmique grossière}\label{sub:sccg2}
  12 Cette section présente une première approche permettant
  13 de générer une fonction booléenne $f$ dont le graphe des itérations $\textsc{giu}(f)$
  14 est fortement connexe.
  15 La méthode est itérative et basée sur une démarche générer-tester.
  16
  17 On considère en premier lieu la fonction
  18 négation $\neg$ dont le graphe des itérations
  19 $\textsc{giu}(\neg)$ est fortement connexe.
  20 Soit un  graphe $\textsc{giu}$, initialisé avec
  21 $\textsc{giu}(\neg)$. L'algorithme  effectue itérativement les deux étapes suivantes:
  22 \begin{enumerate}
  23 \item sélection aléatoire d'un arc du graphe d'itérations en cours,
  24   $\textsc{giu}$, puis
  25 \item analyse de la forte connexité du graphe d'itérations en cours auquel on enlèverait cet arc.
  26   Dans le cas positif, cet arc est enlevé de $\textsc{giu}$,
  27 \end{enumerate} et ce jusqu'à ce qu'un taux $r$ d'arcs
  28 enlevés soit supérieur à un seuil donné
  29 par l'utilisateur.
  30 Si $r$  est proche de  $0\%$ (\textit{i.e.} peu d'arcs ont été supprimés),
  31 il reste peu ou prou $n\times 2^n$ arcs.
  32 Dans le cas contraire, si $r$ est proche de
  33 $100\%$, il ne reste plus qu'environ $2^n$ arcs.
  34 Dans tous les cas, cette étape retourne un graphe $\textsc{giu}$
  35 qui est fortement connexe.
  36 A partir du graphe $\textsc{giu}$, il est alors  facile de construire la
  37 fonction $f$.
  38
  39 Même si cet algorithme retourne toujours des fonctions dont le graphe
  40 des itérations est fortement connexe, il n'en est pas pour le moins efficace.
  41 Un défaut de l'algorithme est de nécessiter une vérification systématique de
  42 forte connexité sur le graphe entier composé de  $2^{\mathsf{N}}$ sommets et ce,
  43 à chaque itération!
  44 La section suivante propose une solution à ce problème.
  45 Elle présente des conditions suffisantes sur un graphe à ${\mathsf{N}}$ sommets
  46 qui permettent d'obtenir des graphes d'itérations fortement connexes.
  47
  48
  49
  50 \subsection{Conditions suffisantes sur le graphe d'interactions}\label{sub:sccg1}
  51
  52 Cette partie énonce un théorème dont les hypothèses
  53 portent sur les interactions entre $x_i$ et
  54 $f_j$ et qui permet de n'engendrer que des fonctions
  55 $f$ dont le  graphe d'itérations
  56  $\textsc{giu}(f)$  est fortement connexe.
  57
  58 \begin{theorem}\label{th:Adrien}
  59 Soit $f$ une fonction de $\Bool^{\mathsf{N}}$ vers lui-même telle que:
  60 \begin{enumerate}
  61 \item
  62 $\Gamma(f)$ n'a pas de cycle de longueur supérieure ou égale à deux;
  63 \item
  64 chaque sommet de  $\Gamma(f)$ qui possède une boucle
  65 positive a aussi une boucle négative;
  66 \item
  67 chaque sommet de $\Gamma(f)$ est accessible depuis un sommet qui possède
  68 une boucle négative.
  69 \end{enumerate}
  70 Alors, $\textsc{giu}(f)$ est fortement connexe.
  71 \end{theorem}
  72
  73 La preuve de ce théorème est donnée en annexe~\ref{anx:sccg}.
  74
  75 Illustrons ce théorème par un exemple. On considère par le graphe d'interactions
  76 $\Gamma(f)$ donné en figure~\ref{fig:Adrien:G}.
  77 Il vérifie le théorème~\ref{th:Adrien}:
  78 toutes les fonctions $f$ possédant un tel graphe d'interactions
  79 ont un graphe d'itérations  $\textsc{giu}(f)$ fortement connexe.
  80 Pratiquement, il existe 34226 fonctions de $\Bool^4$ dans lui même qui
  81 vérifient ce graphe d'intéraction.
  82 Cependant, nombreuses sont celles qui possèdent un comportement équivalent.
  83 Deux fonctions sont equivalentes si leurs \textsc{giu} sont isomorphes
  84 (au sens de l'isomorphisme de graphes). Il ne reste alors plus que
  85 520 fonctions $f$ non équivalentes de graphe d'interactions $\Gamma(f)$.
  86
  87 \begin{figure}%[h]
  88   \begin{center}
  89     \includegraphics[scale=0.5]{images/Gi.pdf}
  90   \end{center}
  91 \caption{Exemple de graphe d'interactions vérifiant le théorème~\ref{th:Adrien}} \label{fig:Adrien:G}
  92 \end{figure}
  93