From: Jean-François Couchot Date: Wed, 22 Jul 2015 11:01:29 +0000 (+0200) Subject: plein d'aspel X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/commitdiff_plain/103fee06d77ee199f8956ccb0747b45676c834e5?ds=inline;hp=--cc plein d'aspel --- 103fee06d77ee199f8956ccb0747b45676c834e5 diff --git a/11FCT.tex b/11FCT.tex index ffa5775..0e9c64f 100644 --- a/11FCT.tex +++ b/11FCT.tex @@ -80,7 +80,7 @@ ont un graphe d'itérations $\textsc{giu}(f)$ fortement connexe. Pratiquement, il existe 34226 fonctions de $\Bool^4$ dans lui même qui vérifient ce graphe d'intéraction. Cependant, nombreuses sont celles qui possèdent un comportement équivalent. -Deux fonctions sont equivalentes si leurs \textsc{giu} sont isomorphes +Deux fonctions sont équivalentes si leurs \textsc{giu} sont isomorphes (au sens de l'isomorphisme de graphes). Il ne reste alors plus que 520 fonctions $f$ non équivalentes de graphe d'interactions $\Gamma(f)$. diff --git a/12TIPE.tex b/12TIPE.tex index 85efe78..7ebcfde 100644 --- a/12TIPE.tex +++ b/12TIPE.tex @@ -30,7 +30,7 @@ x^{t+1}=F_{f_u}(x^t,s_t). On peut alors construire l'espace $\mathcal{X}_u = \Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$ -et la fonction d'iteration $G_{f_u}$ définie de +et la fonction d'itération $G_{f_u}$ définie de $\mathcal{X}_u$ dans lui-même par \begin{equation} @@ -95,7 +95,7 @@ chaotiques $G_{f_u}$ sur $\mathcal{X}_u$} On peut tout d'abord démontrer que pour toute fonction booléenne $f$, $G_{f_u}$ est continue sur $\mathcal{X}_u$ (cf annexe~\ref{anx:cont}). -Pour charactérister les fonctions rendant chaotiques dans $\mathcal{X}_u$ les itérations de $G_{f_u}$ +Pour caractériser les fonctions rendant chaotiques dans $\mathcal{X}_u$ les itérations de $G_{f_u}$ on se focalise donc que sur la régularité et sur la transitivité de $G_{f_u}$. Ceci se réalise en établissant les relations d'inclusion entre les ensembles $\mathcal{T}$ des fonctions topologiquement transitives, @@ -111,7 +111,7 @@ et $\mathcal{C}$ des fonctions chaotiques définis respectivement ci-dessous: \end{itemize} -On énnonce les théorèmes successifs suivants. +On énonce les théorèmes successifs suivants. Leur preuve est donnée en annexe~\ref{anx:chaos:unaire}. \begin{theorem} $G_{f_u}$ est transitive si et seulement si diff --git a/14Secrypt.tex b/14Secrypt.tex index 9de2b0d..b2ae05d 100644 --- a/14Secrypt.tex +++ b/14Secrypt.tex @@ -23,7 +23,7 @@ results to provide a generation of DSSC matrices with small mixing times. \section{Programmation logique par contraintes sur des domaines finis} Tout d'abord, soit ${\mathsf{N}}$ le nombre d'éléments. -Pour éviter d'avoir à gérér des fractions, on peut considérer que +Pour éviter d'avoir à gérer des fractions, on peut considérer que les matrices (d'incidence) à générer ont des lignes et des colonnes dont les sommes valent ${\mathsf{N}}$ à chaque fois. On cherche ainsi toutes les matrices $M$ de taille $2^{\mathsf{N}}\times 2^{\mathsf{N}}$ telles que @@ -37,16 +37,16 @@ configuration $i$ est inférieur à ${\mathsf{N}}$; \item pour $j \neq i$, $0 \le M_{ij} \le 1$: on construit l'arc de $i$ à $j$ si et seulement si $M_{ij}$ vaut 1 (et 0 sinon) -\item pour chque indice de ligne $i$, $1 \le i\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le j\le 2^{\mathsf{N}}} M_{ij}$: +\item pour chaque indice de ligne $i$, $1 \le i\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le j\le 2^{\mathsf{N}}} M_{ij}$: la matrice est stochastique à droite; -\item pour chque indice de colonne $j$, +\item pour chaque indice de colonne $j$, $1 \le j\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le i\le 2^{\mathsf{N}}} M_{ij}$: la matrice est stochastique à gauche; \item Toutes les éléments de la somme $\sum_{1\le k\le 2^{\mathsf{N}}}M^k$ sont strictement positif, \textit{i.e.}, le graphe $\textsc{giu}(f)$ est fortement connexe; \end{enumerate} Ce problème s'exprime sur des domaines finis entiers avec des opérateurs -arithmétiques simples (sommes et poduits). il pourrait théoriquement être -traité par desdémarches de programation logique par contrainte +arithmétiques simples (sommes et produits). il pourrait théoriquement être +traité par des démarches de programmation logique par contrainte sur des domaines finis (comme en PROLOG). L'algorithme donné en Figure~\ref{fig:prolog} est en effet le c{\oe}ur du programme PROLOG @@ -86,7 +86,7 @@ bistoc(X):- \caption{Code PROLOG permettant de trouver toutes les matrices DSSC pour $n=2$}\label{fig:prolog} \end{figure} -Enfin, on définit la relation $\mathcal{R}$, qui est établie pourles deux +Enfin, on définit la relation $\mathcal{R}$, qui est établie pour les deux fonctions $f$ et $g$ si leur graphes respectifs $\textsf{giu}(f)$ et $\textsf{giu}(g)$ sont isomorphes. @@ -105,10 +105,10 @@ Cependant, l'approche ne permet pas d'engendrer toutes les solutions pour $n=4$. Cette approche, basée sur une démarche de type \emph{générer, tester} ne peut pas être retenue pour $n$ de grande taille, même -en s'appuyant sur l'éfficience de l'algorithme de backtrack natif de PROLOG. +en s'appuyant sur l'efficience de l'algorithme de backtrack natif de PROLOG. Cependant, pour des valeurs de $n$ petites, nous avons -comparé les fonctions non équivalantes selon leur proportion +comparé les fonctions non équivalentes selon leur proportion à engendrer des temps de mélange petits (cf. équation~\ref{eq:mt:ex}). @@ -395,17 +395,17 @@ sur des sous-ensembles des partitionnements possibles. Ces fonctions étant générée, on s'intéresse à étudier à quelle vitesse un générateur les embarquant converge vers la distribution uniforme. -C'est l'objeftif de la section suivante. +C'est l'objectif de la section suivante. \section{Quantifier l'écart par rapport à la distribution uniforme} On considère ici une fonction construite comme à la section précédente. On s'intéresse ici à étudier de manière théorique les -itérations définies à l'equation~(\ref{eq:asyn}) pour une +itérations définies à l'équation~(\ref{eq:asyn}) pour une stratégie donnée. -Tout d'abord, celles-ci peuvent être inerprétées comme une marche le long d'un +Tout d'abord, celles-ci peuvent être interprétées comme une marche le long d'un graphe d'itérations $\textsc{giu}(f)$ tel que le choix de tel ou tel arc est donné par la stratégie. -On remaque que ce graphe d'itération est toujours un sous graphe +On remarque que ce graphe d'itération est toujours un sous graphe du ${\mathsf{N}}$-cube augmenté des boucles sur chaque sommet, \textit{i.e.}, les arcs $(v,v)$ pour chaque $v \in \Bool^{\mathsf{N}}$. @@ -416,7 +416,7 @@ Ceci se base sur la théorie des chaînes de Markov. Pour une référence générale à ce sujet on pourra se référer au livre~\cite{LevinPeresWilmer2006}, -particulièrementau chapitre sur les temps d'arrêt. +particulièrement au chapitre sur les temps d'arrêt. @@ -433,7 +433,7 @@ p(e) \left\{ \end{array} \right. $$ -La matrice $P$ de la chaine de Markov associée à $f^*$ +La matrice $P$ de la chaîne de Markov associée à $f^*$ est \[ P=\dfrac{1}{6} \left( @@ -465,7 +465,7 @@ De plus, si $\nu$ est une distribution on $\Bool^{\mathsf{N}}$, on a $$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}.$$ -Soit $P$ une matrice d'une chaîne de Markovs sur $\Bool^{\mathsf{N}}$. +Soit $P$ une matrice d'une chaîne de Markov sur $\Bool^{\mathsf{N}}$. $P(X,\cdot)$ est la distribution induite par la $X^{\textrm{ème}}$ colonne de $P$. Si la chaîne de Markov induite par @@ -500,7 +500,7 @@ $f(X_{t-1},Z_t)$ une représentation fonctionnelle de celle-ci. Un \emph{temps d'arrêt aléatoire} pour la chaîne de Markov est un temps d'arrêt pour $(Z_t)_{t\in\mathbb{N}}$. -Si la chaîne de Markov est irreductible et a $\pi$ +Si la chaîne de Markov est irréductible et a $\pi$ comme distribution stationnaire, alors un \emph{temps stationnaire} $\tau$ est temps d'arrêt aléatoire (qui peut dépendre de la configuration initiale $X$), @@ -527,4 +527,4 @@ $E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. Sans entrer dans les détails de la preuve, on remarque que le calcul de cette borne ne tient pas en compte le fait qu'on préfère enlever des chemins hamiltoniens équilibrés. -En intégrant cette contrainte, la borne supérieure pourraît être réduite. +En intégrant cette contrainte, la borne supérieure pourrait être réduite. diff --git a/15RairoGen.tex b/15RairoGen.tex index 010beb9..fe1c034 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -16,7 +16,7 @@ Cette section présente une application directe de la théorie développée ci-a à la génération de nombres pseudo aléatoires. On présente tout d'abord le générateur basé sur des fonctions chaotiques (section~\ref{sub:prng:algo}), -puis comment intégrer la contrainte de distributionuniforme +puis comment intégrer la contrainte de distribution uniforme de la sortie dans le choix de la fonction à itérer (section~\ref{sub:prng:unif}). L'approche est évaluée dans la dernière section. @@ -69,14 +69,14 @@ de nombres pseudo aléatoires Cet algorithme est utilisée dans notre générateur pour construire la longueur de la stratégie ainsi que les éléments qui la composent. Pratiquement, il retourne des entiers dans $\llbracket 1 ; l \rrbracket$ -selon une distributionuniforme et utilise +selon une distribution uniforme et utilise \textit{XORshift} qui est une classe de générateurs de nombres pseudo aléatoires conçus par George Marsaglia. L'algorithme \textit{XORshift} exploite itérativement l'opérateur $\oplus$ -sur des nombres obtenus grâce à des decalages de bits. +sur des nombres obtenus grâce à des décalages de bits. Cet opérateur, défini dans $\Bool^{n}$, applique la fonction \og xor \fg{} aux bits de même rang de ses deux opérandes (\og opération bit à bit \fg{}). @@ -118,8 +118,8 @@ si la propriété suivante est établie: $$\exists k \in \mathds{N}^\ast, \forall i,j \in \llbracket 1; n \rrbracket, M_{ij}^k>0.$$ On énonce enfin le théorème suivant liant les -vecteur de probabilite -et les chaines de Markov. +vecteur de probabilités +et les chaînes de Markov. @@ -128,11 +128,11 @@ et les chaines de Markov. Si $M$ est une matrice stochastique régulière, alors $M$ possède un unique vecteur stationnaire de probabilités $\pi$ ($\pi.M = \pi$). - De plus, si $\pi^0$ est un {vecteurDeProbabilite} + De plus, si $\pi^0$ est un {vecteur de probabilités} et si on définit la suite $(\pi^{k})^{k \in \Nats}$ par $\pi^{k+1} = \pi^k.M $ pour $k = 0, 1,\dots$ - alors la {chaineDeMarkov} $\pi^k$ + alors la {chaîne de Markov} $\pi^k$ converge vers $\pi$ lorsque $k$ tend vers l'infini. \end{theorem} @@ -228,7 +228,7 @@ Il est facile de vérifier que la matrice de transitions d'un tel processus est $M_g = \frac{1}{2} \check{M}_g$, où $\check{M}_g$ est la matrice d' adjacence donnée en -figure~\ref{fig:g:incidence} (voir ci-après), et similairement pour $M_h$. +figure~\ref{fig:g:incidence} (voir ci-après), et de manière similaire pour $M_h$. \begin{figure}[h] \begin{center} @@ -293,7 +293,7 @@ de valeurs soit suffisamment grand de sorte que le vecteur d’état de la chaîne de Markov ait une distribution suffisamment proche de la distribution uniforme. -On énnonce directement le théorème suivant dont la preuve est donnée en annexes~\ref{anx:generateur}. +On énonce directement le théorème suivant dont la preuve est donnée en annexes~\ref{anx:generateur}. \begin{theorem} Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son @@ -311,7 +311,7 @@ On énnonce directement le théorème suivant dont la preuve est donnée en anne On reprend le graphe d'interactions $\Gamma(f)$ donné en figure~\ref{fig:G} à la section~\ref{sec:11FCT}. On a vu qu'il y avait 520 fonctions $f$ non isomorphes de graphe d'interactions $\Gamma(f)$, -dont seulement 16 d'entre elles possédent une matrice doublement stochastique. +dont seulement 16 d'entre elles possèdent une matrice doublement stochastique. La figure~\ref{fig:listfonction} explicite ces 16 fonctions en définissant les images des éléments de la liste @@ -432,8 +432,8 @@ L'expérience a montré notamment que toutes ces fonctions passent avec succès cette batterie de tests. Pour conclure cette section, on remarque que le générateur de nombres pseudo-aléatoires -a été prouvé chaotique pour $b=1$, \textit{i.e.}, lorqu'il y a une sortie pour chaque itération. -Ceci est difficilement compatible avec la volonté d'avoir une sortie uniformémement distribuée: +a été prouvé chaotique pour $b=1$, \textit{i.e.}, lorsqu'il y a une sortie pour chaque itération. +Ceci est difficilement compatible avec la volonté d'avoir une sortie uniformément distribuée: se rapprocher de cette distribution nécessite en effet un nombre plus élevé d'itérations $b$ entre chaque sortie. Par exemple, dans l'exemple précédent, il est nécessaire d'itérer au moins 42 fois entre chaque sortie pour suivre une loi uniforme à $10^{-4}$ près. @@ -444,7 +444,7 @@ est l'objectif de la section suivante. \section{Un PRNG basé sur des itérations unaires qui est chaotique } Cette section présente un espace métrique adapté au générateur de nombres pseudo-aléatoires -pésenté à l'algorithme~\ref{CI Algorithm} et prouve ensuite que la fonction qu'il représente +présenté à l'algorithme~\ref{CI Algorithm} et prouve ensuite que la fonction qu'il représente est chaotique sur cet espace. \subsection{Un espace $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ pour le PRNG de l'algorithme~\ref{CI Algorithm}} @@ -461,7 +461,7 @@ Dans l'algorithme~\ref{CI Algorithm}, $\mathsf{p}$ vaut 1 et $p_1=b$. -Cet algorithme peut être vu comme $b$ compostions de la function $F_{f_u}$. +Cet algorithme peut être vu comme $b$ compostions de la fonction $F_{f_u}$. Ceci peut cependant se généraliser à $p_i$, $p_i \in \mathcal{P}$, compositions fonctionnelles de $F_{f_u}$. Ainsi, pour chaque $p_i \in \mathcal{P}$, on construit la fonction @@ -485,7 +485,7 @@ Le second élément est aussi une paire $((u^k)_{k \in \Nats},(v^k)_{k \in \Nats La suite $(v^k)_{k \in \Nats}$ définit combien d'itérations sont exécutées au temps $k$ entre deux sorties. La séquence $(u^k)_{k \in \Nats}$ définit quel élément est modifié (toujours au temps $k$). -Définissons la fonction de décallage $\Sigma$ pour chaque élément de $\mathds{S}_{\mathsf{N},\mathcal{P}}$. +Définissons la fonction de décalage $\Sigma$ pour chaque élément de $\mathds{S}_{\mathsf{N},\mathcal{P}}$. $$\begin{array}{cccc} \Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\longrightarrow &\mathds{S}_{\mathsf{N},\mathcal{P}} \\ @@ -493,7 +493,7 @@ $$\begin{array}{cccc} \end{array} $$ En d'autres termes, $\Sigma$ reçoit deux suites $u$ et $v$ et -effectue $v^0$ décallage vers la droite sur la première et un décallage vers la droite +effectue $v^0$ décalage vers la droite sur la première et un décalage vers la droite sur la seconde. @@ -534,7 +534,7 @@ $u^0, u^1, \hdots, u^{v^0-1}$ et $\check{u}^0, \check{u}^1, \hdots, \check{u}^{ suivie par les différences entre $u^{v^0}, u^{v^0+1}, \hdots, u^{v^1-1}$ et $\check{u}^{\check{v}^0}, \check{u}^{\check{v}^0+1}, \hdots, \check{u}^{\check{v}^1-1}$, etc. -Plus précisemment, soit +Plus précisément, soit $p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ et $n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$. \begin{itemize} @@ -609,7 +609,7 @@ On prend alors le $v^0=1$ premier terme de $u$, chaque terme étant codé sur $n=2$ éléments, soit 06. Comme on itère au plus $\max{(\mathcal{P})}$ fois, on complète cette valeur par des 0 de sorte que -la chaine obtenue a $n\times \max{(\mathcal{P})}=22$ éléments, soit: +la chaîne obtenue a $n\times \max{(\mathcal{P})}=22$ éléments, soit: 0600000000000000000000. De manière similaire, les $\check{v}^0=2$ premiers termes de $\check{u}$ sont représentés par @@ -655,7 +655,7 @@ $d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$. \subsection{Le graphe $\textsc{giu}_{\mathcal{P}}(f)$ étendant $\textsc{giu}(f)$} A partir de $\mathcal{P}=\{p_1, p_2, \hdots, p_\mathsf{p}\}$, on -definit le graphe orienté $\textsc{giu}_{\mathcal{P}}(f)$ de la manière suivante: +définit le graphe orienté $\textsc{giu}_{\mathcal{P}}(f)$ de la manière suivante: \begin{itemize} \item les n{\oe}uds sont les $2^\mathsf{N}$ configurations de $\mathds{B}^\mathsf{N}$, %\item Each vertex has $\displaystyle{\sum_{i=1}^\mathsf{p} \mathsf{N}^{p_i}}$ arrows, namely all the $p_1, p_2, \hdots, p_\mathsf{p}$ tuples @@ -699,7 +699,7 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g } \end{center} - \caption{Graphes d'iterations $\textsc{giu}_{\mathcal{P}}(h)$ pour $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$} + \caption{Graphes d'itérations $\textsc{giu}_{\mathcal{P}}(h)$ pour $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$} %\label{fig:xplgraphIter} \end{figure} @@ -714,7 +714,7 @@ $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$ déjà détail Le graphe $\textsc{giu}_{\{1\}}(h)$ a déjà été donné à la figure~\ref{fig:h:iter}. Les graphes $\textsc{giu}_{\{2\}}(h)$, $\textsc{giu}_{\{3\}}(h)$ et $\textsc{giu}_{\{2,3\}}(h)$ sont respectivement donnés aux figure~\ref{fig:h2prng}, ~\ref{fig:h3prng} et ~\ref{fig:h23prng}. -Le premier (repsectivement le second) +Le premier (respectivement le second) illustre le comportement du générateur lorsque qu'on itère exactement 2 fois (resp. 3 fois) puis qu'on affiche le résultat. Le dernier donnerait le comportement d'un générateur qui s'autoriserait diff --git a/15TSI.tex b/15TSI.tex index 76e0203..f2fe17b 100644 --- a/15TSI.tex +++ b/15TSI.tex @@ -8,7 +8,7 @@ On reprend ici le même plan que dans la section précédente. Dans le schéma généralisé, à la $t^{\textrm{ème}}$ itération, c'est l'ensemble des $s_{t}^{\textrm{ème}}$ éléments (inclus dans $[n]$) qui -sont mis à jour (c.f. équation~(\ref{eq:schema:generalise})). +sont mis à jour (cf. équation~(\ref{eq:schema:generalise})). On redéfinit la fonction la fonction $F_{f_g}: \Bool^{\mathsf{N}} \times \mathcal{P}(\{1, \ldots, \mathsf{N}\}) \rightarrow \Bool^{\mathsf{N}}$ par @@ -42,7 +42,7 @@ configurations $x^t$ sont définies par la récurrence $X^0=(x^0,S)$ -On onstruit cette fois-ci l'espace +On construit cette fois ci l'espace $\mathcal{X}_g = \Bool^{\mathsf{N}} \times \mathcal{P}(\{1, \ldots, {\mathsf{N}}\})^{\Nats}$ diff --git a/chaosANN.tex b/chaosANN.tex index 239251e..b814c12 100644 --- a/chaosANN.tex +++ b/chaosANN.tex @@ -4,19 +4,19 @@ Les réseaux de neurones chaotiques ont été étudiés à de maintes reprises par le passé en raison notamment de leurs applications potentielles: %les mémoires associatives~\cite{Crook2007267} -les composants utils à la sécurité comme les fonctions de +les composants utiles à la sécurité comme les fonctions de hachage~\cite{Xiao10}, le tatouage numérique~\cite{1309431,Zhang2005759} ou les schémas de chiffrement~\cite{Lian20091296}. Dans tous ces cas, l'emploi de fonctions chaotiques est motivé par -leur comportement imprévisibile et proche de l'aléa. +leur comportement imprévisible et proche de l'aléa. Les réseaux de neurones chaotiques peuvent être conçus selon plusieurs principes. Des neurones modifiant leur état en suivant une fonction non linéaire son par exemple appelés neurones chaotiques~\cite{Crook2007267}. L'architecture de réseaux de neurones de type Perceptron multi-couches -(MLP) n'iterent quant à eux, pas nécesssairement de fonctions chaotiques. +(MLP) n'itèrent quant à eux, pas nécessairement de fonctions chaotiques. Il a cependant été démontré que ce sont des approximateurs universels~\cite{Cybenko89,DBLP:journals/nn/HornikSW89}. Ils permettent, dans certains cas, de simuler des comportements @@ -64,7 +64,7 @@ $f:\Bool^n\to\Bool^n$ telle que $\textsc{giu}(f)$ est fortement connexe. Ainsi $G_{f_u}$ est chaotique d'après le théorème~\ref{Th:CaracIC}. On considère ici le schéma unaire défini par l'équation (\ref{eq:asyn}). -On construit un perceptron multi-couche associé à la fonction +On construit un Perceptron multi-couches associé à la fonction $F_{f_u}$. Plus précisément, pour chaque entrée $(x,s) \in \mathds{B}^n \times [n]$, @@ -83,7 +83,7 @@ On obtient une réseau de neurones dont le comportement est le suivant à travers les liens de retours. \item Lorsque le réseau est activé à la $t^{th}$ itération, l'état du système $x^t \in \mathds{B}^n$ reçu depuis la couche de sortie ainsi que le - premier terme de la sequence $(S^t)^{t \in \Nats}$ + premier terme de la séquence $(S^t)^{t \in \Nats}$ (\textit{i.e.}, $S^0 \in [n]$) servent à construire le nouveau vecteur de sortie. Ce nouveau vecteur, qui représente le nouvel état du système dynamique, satisfait: \begin{equation} @@ -94,7 +94,7 @@ On obtient une réseau de neurones dont le comportement est le suivant \begin{figure} \centering \includegraphics[scale=0.625]{images/perceptron} - \caption{Un perceptron équivalent aux itérations unitaires} + \caption{Un Perceptron équivalent aux itérations unitaires} \label{Fig:perceptron} \end{figure} @@ -112,7 +112,7 @@ On peut donc le qualifier de chaotique au sens de Devaney. \section{Vérifier si un réseau de neurones est chaotique} \label{S3} On s'intéresse maintenant au cas où l'on dispose d'un -réseau de neurones de type perceptron multi-couches +réseau de neurones de type Perceptron multi-couches dont on cherche à savoir s'il est chaotique (parce qu'il a par exemple été déclaré comme tel) au sens de Devaney. On considère de plus que sa topologie est la suivante: @@ -136,7 +136,7 @@ $\left(\left(x_1,\dots,x_n\right),s\right) \in \mathds{B}^n \times[n]$ le vecteur $\left(y_1,\dots,y_n\right) \in \mathds{B}^n$, où $\left(y_1,\dots,y_n\right)$ sont les sorties du réseau neuronal -àaprès l'initialisation de la couche d'entrée avec +après l'initialisation de la couche d'entrée avec $\left(s,\left(x_1,\dots, x_n\right)\right)$. Ensuite, on définie $f: \mathds{B}^n \rightarrow \mathds{B}^n$ telle que $f\left(x_1,x_2,\dots,x_n\right)$ est égal à @@ -164,7 +164,7 @@ des itération unaires chaotiques?} Cette section s'intéresse à étudier le comportement d'un réseau de neurones face à des itérations unaires chaotiques, comme définies à la section~\ref{sec:TIPE12}. -Plus précésment, on considère dans cette partie une fonction dont le graphe +Plus précisément, on considère dans cette partie une fonction dont le graphe des itérations unaires est fortement connexe et une séquence dans $[n]^{\mathds{N}}$. On cherche à construire un réseau de neurones qui approximerait les itérations de la fonction $G_{f_u}$ comme définie @@ -211,17 +211,17 @@ Cependant, une telle représentation rapproche arbitrairement des configurations diamétralement opposées dans le $n$-cube comme une puissance de deux et la configuration immédiatement précédente: 10000 serait modélisée -par 16 et et 01111 par 15 alros que leur distance de Hamming est 15. +par 16 et et 01111 par 15 alors que leur distance de Hamming est 15. De manière similaire, ce codage éloigne des configurations qui sont très proches: par exemple 10000 et 00000 ont une distance de Hamming de 1 et sont respectivement représentées par 16 et 0. Pour ces raisons, le codage retenu est celui des codes de Gray~\cite{Gray47}. Concentrons nous sur la traduction de la stratégie. -Il n'est naturellement pas possible de traduire une stragtégie +Il n'est naturellement pas possible de traduire une stratégie infinie quelconque à l'aide d'un nombre fini d'éléments. On se restreint donc à des stratégies de taille -$l \in \llbracket 2,k\rrbracket$, où $k$ est un parametre défini +$l \in \llbracket 2,k\rrbracket$, où $k$ est un paramètre défini initialement. Chaque stratégie est mémorisée comme un entier naturel exprimé en base $n+1$: à chaque itération, soit aucun élément n'est modifié, soit un @@ -232,7 +232,7 @@ en commençant à $x$. Les sorties (stratégies et configurations) sont mémorisées selon les mêmes règles. -Concentrons nous sur la complexité du problèmew. +Concentrons nous sur la complexité du problème. Chaque entrée, de l'entrée-sortie de l'outil est un triplet composé d'une configuration $x$, d'un extrait $S$ de la stratégie à itérer de taille $l \in \llbracket 2, k\rrbracket$ et d'un nombre $m \in \llbracket 1, l-1\rrbracket$ d'itérations à exécuter. @@ -256,19 +256,19 @@ $$ 2^n \times \left(\dfrac{(k-1)\times n^{k+1}}{n-1} - \dfrac{n^{k+1}-n^2}{(n-1)^2}\right) \enspace . $$ Par exemple, pour $4$ éléments binaires et une stratégie d'au plus -$3$~termes on obtient 2304 couples d'entrée-sorties. +$3$~termes on obtient 2304 couples d'entrée-sortie. \subsection{Expérimentations} \label{section:experiments} -On se focalise dans cette section sur l'entraînement d'un perceptron -multi-couche pour apprendre des itérations chaotiques. Ce type de réseau +On se focalise dans cette section sur l'entraînement d'un Perceptron +multi-couches pour apprendre des itérations chaotiques. Ce type de réseau ayant déjà été évalué avec succès dans la prédiction de séries chaotiques temporelles. En effet, les auteurs de~\cite{dalkiran10} ont montré qu'un MLP pouvait apprendre la dynamique du circuit de Chua. Ce réseau avec rétropropagation est composé de deux couches -et entrainé à l'aide d'une propagation arrière Bayesienne. +et entraîné à l'aide d'une propagation arrière Bayesienne. -Le choix de l'achitecture du réseau ainsi que de la méthode d'apprentissage +Le choix de l'architecture du réseau ainsi que de la méthode d'apprentissage ont été détaillé dans~\cite{bcgs12:ij}. En pratique, nous avons considéré des configurations de quatre éléments booléens @@ -379,15 +379,15 @@ que ceux qui le sont. Ceci est est illustré au travers des figures~\ref{Fig:chaotic_predictions} et~\ref{Fig:non-chaotic_predictions}. De plus, comme dans le codage précédent, les stratégies ne peuvent pas être prédites. -On constate que ce second codage réduit certe le nombre de sorties, mais est +On constate que ce second codage réduit certes le nombre de sorties, mais est largement moins performant que le premier. On peut expliquer ceci par le fait que ce second codage garantit que deux entiers successifs correspondent -à deux configurations voisines, \textit{ie.e}, qui ne diffèrent que d'un +à deux configurations voisines, \textit{i.e.}, qui ne diffèrent que d'un élément. La réciproque n'est cependant pas établie et deux configurations voisines -peuvent être traduitent par des entiers très éloignés et ainsi difficils -àapprendre. +peuvent être traduites par des entiers très éloignés et ainsi difficiles + à apprendre. \begin{figure}[ht] @@ -415,8 +415,8 @@ peuvent être traduitent par des entiers très éloignés et ainsi difficils \section{Conclusion} -Dans ce chapitre, nous avons établi une simlilitude entre les itérations -chaotiques et une famille de perceptrons multicouches. +Dans ce chapitre, nous avons établi une similitude entre les itérations +chaotiques et une famille de Perceptrons multi-couches. Nous avons d'abord montré comment construire un réseau de neurones ayant un comportement chaotique. Nous avons présenté ensuite comment vérifier si un réseau de neurones diff --git a/mixage.tex b/mixage.tex index 0b24636..e4a283c 100644 --- a/mixage.tex +++ b/mixage.tex @@ -173,7 +173,7 @@ $$ \noindent sinon. En démarrant de $x^0=00011$, le système atteint $x^1 = 01011$ et boucle entre ces deux configurations. Pour une même stratégies, les itérations -asynhrones divergent alors que les synchrones convergent. +asynchrones divergent alors que les synchrones convergent. Les sections suivantes de ce chapitre montrent comment résoudre ce problème. \subsection{Itérations Mixes} diff --git a/modelchecking.tex b/modelchecking.tex index 0ee325e..1919416 100644 --- a/modelchecking.tex +++ b/modelchecking.tex @@ -26,7 +26,7 @@ donné par l'outil. Cependant, même pour des réseaux discrets à peu d'éléments, le nombre de configurations induites explose rapidement. Les \emph{Model-Checkers}~\cite{Hol03,nusmv02,Blast07,MCErlang07,Bogor03} -sont des classes d'outils qui addressent le problème de vérifier automatiquement +sont des classes d'outils qui adressent le problème de vérifier automatiquement qu'un modèle vérifie une propriété donnée. Pour traiter le problème d'explosion combinatoire, ces outils appliquent des méthodes d'ordre partiel, d'abstraction, de quotientage selon une relation d'équivalence. @@ -79,7 +79,7 @@ sont ensuite fournies (\Sec{sec:spin:practical}). \begin{xpl} On considère un exemple à trois éléments dans $\Bool$. - Chaque configuration est ainsi un élement de $\Bool^3$, \textit{i.e.}, + Chaque configuration est ainsi un élément de $\Bool^3$, \textit{i.e.}, un nombre entre 0 et 7. La \Fig{fig:map} précise la fonction $f$ considérée et la \Fig{fig:xplgraph:inter:mc} donne son graphe d'intéraction. @@ -300,7 +300,7 @@ active proctype scheduler(){ } \end{lstlisting} \end{tiny} -\caption{Process scheduler pour la stratégie pseudo pérodique. +\caption{Process scheduler pour la stratégie pseudo périodique. \label{fig:scheduler}} \end{minipage} \begin{minipage}[h]{.30\linewidth} @@ -340,7 +340,7 @@ ces notions est traduite vers un modèle PROMELA. \subsection{La stratégie}\label{sub:spin:strat} Regardons comment une stratégie pseudo périodique peut être représentée en PROMELA. Intuitivement, un process \verb+scheduler+ (comme représenté à la {\sc Figure}~\ref{fig:scheduler}) -est iterrativement appelé pour construire chaque $s^t$ représentant +est itérativement appelé pour construire chaque $s^t$ représentant les éléments possiblement mis à jour à l'itération $t$. Basiquement, le process est une boucle qui est débloquée lorsque la valeur du sémaphore @@ -435,7 +435,7 @@ inline F(){ \item elle mémorise dans \texttt{Xd} la valeurs disponible pour chaque élément grâce à la fonction \texttt{fetch\_values}; cette fonction est détaillée dans la section suivante; \item une boucle %sur les \texttt{ar\_len} éléments qui peuvent être modifiés - met à jour iterrativement la valeur de $j$ (grâce à l'appel de fonction \texttt{f(j)}) + met à jour itérativement la valeur de $j$ (grâce à l'appel de fonction \texttt{f(j)}) pour peu que celui-ci doive être modifié, \textit{i.e.}, pour peu qu'il soit renseigné dans \texttt{mods[count]}; le code source de \texttt{F} est donné en {\sc Figure}~\ref{fig:p} et est une traduction directe de l'application $f$; @@ -553,7 +553,7 @@ Il y a deux cas. Les valeurs des éléments sont ajoutées dans ce canal au travers de la fonction \verb+diffuse_values+. L'objectif de cette fonction est de stocker les valeurs de $x$ (représenté dans le modèle par \verb+Xp+) dans le canal \verb+channels+. -Il permet au modèle-checker SPIN d'exécuter +Il permet au model-checker SPIN d'exécuter le modèle PROMELA comme s'il pouvait y avoir des délais entre processus Il y a deux cas différents pour la valeur de $X_{j}$: \begin{itemize} @@ -658,7 +658,7 @@ puis présente ensuite les expérimentations issues de ce travail. de l'exécution en SPIN de $\psi$ est bornée par $2^{m(\delta_0+1)+n(n+2)}$. \end{theorem} \begin{Proof} - Une configuration est une valuation des variables globales. + Une configuration est une évaluation des variables globales. Leur nombre ne dépend que de celles qui ne sont pas constantes. Les variables \verb+Xp+ et \verb+X+ engendrent $2^{2n}$ états. diff --git a/sdd.tex b/sdd.tex index 83bee06..355e33c 100644 --- a/sdd.tex +++ b/sdd.tex @@ -332,7 +332,7 @@ les uns par rapport aux autres. Cette matrice est nommée \begin{theorem} Si $f_i$ ne dépend pas de $x_j$, alors pour tout $x\in [{\mathsf{N}}]$, -$f_i(\overline{x}^j)$ est égal à $f_i(x)$, \textit{i.e}, +$f_i(\overline{x}^j)$ est égal à $f_i(x)$, \textit{i.e.}, $f'_{ij}(x)=0$. Ainsi $B(f)_{ij}$ est nulle. La réciproque est aussi vraie. \end{theorem}