From: Jean-François Couchot <couchot@couchot.iut-bm.univ-fcomte.fr>
Date: Fri, 22 May 2015 11:20:33 +0000 (+0200)
Subject: ajout FCT11.Tex-a
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/commitdiff_plain/5307c38b9fdbec499a398c994ee36eb2ac51b2fb?ds=sidebyside;hp=-c

ajout FCT11.Tex-a
---

5307c38b9fdbec499a398c994ee36eb2ac51b2fb
diff --git a/11FCT.tex b/11FCT.tex
new file mode 100644
index 0000000..5c7747a
--- /dev/null
+++ b/11FCT.tex
@@ -0,0 +1,73 @@
+Cette section  présente deux  approches permettant de 
+générer des fonctions $f$ dont le graphe des itérations $\textsc{giu}(f)$ 
+est fortement 
+connexe.
+La première est algorithmique mais grossière (section~\ref{sub:sccg2})
+tandis que la seconde s'appuie sur des conditions suffisantes 
+sur le graphe d'interactions de la fonction booléenne $f$ 
+(Section~\ref{sub:sccg1}). 
+%pour obtenir un graphe d'itérations fortement connexe (Section~\ref{sub:sccg1}).
+  
+\subsection{Génération algorithmique grossière}\label{sub:sccg2} 
+Cette section présente une première approche permettant 
+de générer une fonction booléenne $f$ dont le graphe des itérations $\textsc{giu}(f)$
+est fortement connexe.
+La méthode est itérative et basée sur une démarche générer-tester.
+
+On considère en premier lieu la fonction 
+négation $\neg$ dont le graphe des itérations 
+$\textsc{giu}(\neg)$ est fortement connexe. 
+Soit un  graphe $\textsc{giu}$, initialisé avec
+$\textsc{giu}(\neg)$. L'algorithme  effectue itérativement les deux étapes suivantes:
+\begin{enumerate}
+\item sélection aléatoire d'un arc du graphe d'itérations en cours,
+  $\textsc{giu}$, puis
+\item analyse de la forte connexité du graphe d'itérations en cours auquel on enlèverait cet arc.
+  Dans le cas positif, cet arc est enlevé de $\textsc{giu}$,
+\end{enumerate} et ce jusqu'à ce qu'un taux $r$ d'arcs 
+enlevés soit supérieur à un seuil donné 
+par l'utilisateur.
+Si $r$  est proche de  $0\%$ (\textit{i.e.} peu d'arcs ont été supprimés),
+il reste peu ou prou $n\times 2^n$ arcs.  
+Dans le cas contraire, si $r$ est proche de 
+$100\%$, il ne reste plus qu'environ $2^n$ arcs.
+Dans tous les cas, cette étape retourne un graphe $\textsc{giu}$ 
+qui est fortement connexe. 
+A partir du graphe $\textsc{giu}$, il est alors  facile de construire la 
+fonction $f$. 
+
+Même si cet algorithme retourne toujours des fonctions dont le graphe 
+des itérations est fortement connexe, il n'en est pas pour le moins efficace.
+Un défaut de l'algorithme est de nécessiter une vérification systématique de 
+forte connexité sur le graphe entier composé de  $2^{\mathsf{N}}$ sommets et ce,
+à chaque itération!   
+La section suivante propose une solution à ce problème.
+Elle présente des conditions suffisantes sur un graphe à ${\mathsf{N}}$ sommets
+qui permettent d'obtenir des graphes d'itérations fortement connexes.
+
+
+
+\subsection{Conditions suffisantes sur le graphe d'interactions}\label{sub:sccg1}
+
+Cette partie énonce un théorème dont les hypothèses 
+portent sur les interactions entre $x_i$ et 
+$f_j$ et qui permet de n'engendrer que des fonctions
+$f$ dont le  graphe d'itérations
+ $\textsc{giu}(f)$  est fortement connexe.
+
+\begin{theorem}\label{th:Adrien}
+Soit $f$ une fonction de $\Bool^{\mathsf{N}}$ vers lui-même telle que:
+\begin{enumerate}
+\item 
+$G(f)$ n'a pas de cycle de longueur supérieure ou égale à deux;
+\item 
+chaque sommet de  $G(f)$ qui possède une boucle 
+positive a aussi une boucle négative;
+\item
+chaque sommet de $G(f)$ est accessible depuis un sommet qui possède 
+une boucle négative.
+\end{enumerate}
+Alors, $\textsc{giu}(f)$ est fortement connexe.
+\end{theorem}
+
+La preuve de ce théorème est donnée en annexe~\ref{anx:sccg}.