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{restatable}{theorem}{thAdrien}
  59 \label{th:Adrien}
  60 Soit $f$ une fonction de $\Bool^{\mathsf{N}}$ vers lui-même telle que:
  61 \begin{enumerate}
  62 \item
  63 $\Gamma(f)$ n'a pas de cycle de longueur supérieure ou égale à deux;
  64 \item
  65 chaque sommet de  $\Gamma(f)$ qui possède une boucle
  66 positive a aussi une boucle négative;
  67 \item
  68 chaque sommet de $\Gamma(f)$ est accessible depuis un sommet qui possède
  69 une boucle négative.
  70 \end{enumerate}
  71 Alors, $\textsc{giu}(f)$ est fortement connexe.
  72 \end{restatable}
  73
  74 La preuve de ce théorème est donnée en annexe~\ref{anx:sccg}.
  75
  76 Illustrons ce théorème par un exemple. On considère le graphe d'interactions
  77 $\Gamma(f)$ donné en figure~\ref{fig:Adrien:G}.
  78 Il vérifie le théorème~\ref{th:Adrien}:
  79 toutes les fonctions $f$ possédant un tel graphe d'interactions
  80 ont un graphe d'itérations  $\textsc{giu}(f)$ fortement connexe.
  81 Pratiquement, il existe 34226 fonctions de $\Bool^4$ dans lui même qui
  82 vérifient ce graphe d'intéraction.
  83 Cependant, nombreuses sont celles qui possèdent un comportement équivalent.
  84 Deux fonctions sont équivalentes si leurs \textsc{giu} sont isomorphes
  85 (au sens de l'isomorphisme de graphes). Il ne reste alors plus que
  86 520 fonctions $f$ non équivalentes de graphe d'interactions $\Gamma(f)$.
  87
  88 \begin{figure}%[h]
  89   \begin{center}
  90     \includegraphics[scale=0.5]{images/Gi.pdf}
  91   \end{center}
  92 \caption{Exemple de graphe d'interactions vérifiant le théorème~\ref{th:Adrien}} \label{fig:Adrien:G}
  93 \end{figure}