From: couchot Date: Thu, 8 Mar 2012 15:56:36 +0000 (+0100) Subject: derniere modifs X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/slides_and.git/commitdiff_plain/HEAD?ds=sidebyside;hp=a462b53d610b423cbe1357e9b35268c0458be0e5 derniere modifs --- diff --git a/cbhfk.tex b/cbhfk.tex index fc5a238..68ccf70 100644 --- a/cbhfk.tex +++ b/cbhfk.tex @@ -1,7 +1,18 @@ -\vspace{-1em} + \begin{itemize} -\item \cite{Wang2003}\footnote{\bibentry{Wang2003}}, \cite{Xiao20094346}\footnote{\bibentry{Xiao20094346}},\cite{Xiao20092288}\footnote{\bibentry{Xiao20092288}},\cite{Xiao20102254}\footnote{\bibentry{Xiao20102254}}. -\item Logistic, tent, or Arnold's cat maps: included chaotic functions of -\alert<2>{real variables}. -\item Claim: chaos properties \alert<2>{preserved} in the final hash function. +\item Constat: +\begin{itemize} +\item Choix d'une fonction chaotique (réelle): logistique, tente, chat d'Arnold\ldots +\item Affirmation: les propriétés chaotiques sont préservées lors du développement +\item Embarquement dans: PRNGs, fonctions de hachage, du tatouage numérique\ldots +\item Validation par des tests (non exhaustifs) +\end{itemize} + +\item Proposition: +\begin{itemize} +\item Cadre cohérent pour le chaos informatique: itération de fonctions sur les entiers +\item Validation: des preuves et métriques mathématiques et des tests +\end{itemize} \end{itemize} + + diff --git a/ci.tex b/ci.tex index bf46756..5efd640 100644 --- a/ci.tex +++ b/ci.tex @@ -1,32 +1,31 @@ \vspace{-1.5em}\begin{itemize} -\item Discrete Iterative System: +\item Système itératif discret: \begin{itemize} -\item $x=(x_1,\dots,x_n)$ : $n$ components, $x_i$ in $\Bool=\{0,1\}$. -\item A \emph{strategy} \alert<2>{$(S^{t})^{t \in \Nats}$}: sequence of the - components that may be updated at time $t$. -\item Components evolution: defined for times $t=0,1,2,\ldots$ -by: +\item $x=(x_1,\dots,x_n)$ : $n$ composants, $x_i \in \Bool=\{0,1\}$. +\item Une \emph{stratégie} \alert<2>{$(J^{t})^{t \in \Nats}$}: suite des + composants qui peuvent être mis à jour au temps $t$. +\item \'Evolution des composants : définie pour les temps $t=0,1,2,\ldots$ +par: $$ \left\{ \begin{array}{l} - \alert<2>{x^{0}}\in \Bool^{n} \textrm{ and}\\ - x^{t+1}= (x^{t+1}_1,\dots,x^{t+1}_n) \textrm{ where } + \alert<2>{x^{0}}\in \Bool^{n} \textrm{ et}\\ + x^{t+1}= (x^{t+1}_1,\dots,x^{t+1}_n) \textrm{ où } x^{t+1}_i = \left\{ \begin{array}{l} - \overline{x^{t}_i} \textrm{ if $i = S^t$} \\ - x^t_i \textrm{ otherwise} + \overline{x^{t}_i} \textrm{ si $i = J^t$} \\ + x^t_i \textrm{ sinon} \end{array} \right. \end{array} \right. $$ \end{itemize} -\item Theoretical Results~\cite{GuyeuxThese10}\footnote{\bibentry{GuyeuxThese10}}: let $\mathcal{X}$ be -$ \llbracket 1 ; n \rrbracket^{\Nats} \times -\Bool^n$. We can define a distance $d$ on $\mathcal{X}$ and -a function $f: \mathcal{X} \rightarrow \mathcal{X}$ from the -iterative process -s.t. $f$ is a continuous and chaotic function. +\item Résultats théoriques: soit +$\mathcal{X} = \{1,\ldots, n\}^{\Nats} \times \Bool^n$. +On peut définir une distance $d$ sur $\mathcal{X}$ et +une fonction $f: \mathcal{X} \rightarrow \mathcal{X}$ à partir du processus +itératif t.-q. $f$ est une fonction continue et chaotique. \end{itemize} diff --git a/combMXpl.tex b/combMXpl.tex old mode 100755 new mode 100644 index fd2c583..b55fbd0 --- a/combMXpl.tex +++ b/combMXpl.tex @@ -1,7 +1,7 @@ \begin{exampleblock}{} \begin{itemize} -\item Graphe de connection: +\item Graphe de connexion: \begin{center} \includegraphics[width=3cm]{xplgraph.pdf} \end{center} diff --git a/combMixed.tex b/combMixed.tex old mode 100755 new mode 100644 index 29e122b..86dbd51 --- a/combMixed.tex +++ b/combMixed.tex @@ -6,7 +6,7 @@ \end{itemize} \item Formalisation: \begin{itemize} - \item Regroupement selon les composantes connexes (SCC) du graphe de connection + \item Regroupement selon les composantes connexes (SCC) du graphe de connexion \item Mode mixe: \begin{itemize} \item $S_{ij}^t = t$ si $i \in SCC(j)$. @@ -23,5 +23,5 @@ $ \end{itemize} \end{itemize} -\item Elements d'un même groupe: équivalents de l'extérieur. +\item Éléments d'un même groupe: équivalents de l'extérieur. \end{itemize} diff --git a/combMixedTheo.tex b/combMixedTheo.tex old mode 100755 new mode 100644 index 68af77f..95a4fc1 --- a/combMixedTheo.tex +++ b/combMixedTheo.tex @@ -2,5 +2,5 @@ Soit une fonction $F$ contenant un unique point fixe $X^*$. Si les itérations chaotiques convergent vers $X^*$, alors les itérations mixes convergent aussi $X^*$ - pour n'imoporte quelle stratégie pseudo périodique. + pour n'importe quelle stratégie pseudo périodique. \end{Theorem} diff --git a/devaney.tex b/devaney.tex index 2a7934e..ac73682 100644 --- a/devaney.tex +++ b/devaney.tex @@ -1,24 +1,20 @@ -\begin{block}{Definition: Chaotic function [4]$^4$} -Let $(\mathcal{X}; d)$ be a metric space. -A function $f: \mathcal{X} \rightarrow \mathcal{X}$ is chaotic on $\mathcal{X}$ if: +\begin{block}{Définition d'une fonction chaotique selon Devaney} +Soit $(\mathcal{X}; d)$ un espace métrique. +Une fonction $f: \mathcal{X} \rightarrow \mathcal{X}$ est chaotique sur $\mathcal{X}$ si: \begin{enumerate} -\item $f$: topologically transitive (\textit{i.e.}, indecomposability of the system)\\ -(for any pair of open sets $U,V \subset \mathcal{X}$, $\exists k > 0 . +\item $f$: topologiquement transitive (\textit{i.e.}, système indécomposable)\\ +(pour chaque paire d'ensembles ouverts $U,V \subset \mathcal{X}$, $\exists k > 0 . f^k (U) \cap V \neq \emptyset$) \\ -\onslide<2>{\alert<2>{Addressed property: preimage resistance}}. -\item $f$ is regular (\textit{i.e.}, fundamentally different points coexist)\\ -(the set of periodic points is dense in $\mathcal{X}$). -\item $f$: sensitive dependent on initial conditions (SDIC)\\ +\item $f$ est régulière (l'ensemble des points périodiques est dense dans $\mathcal{X}$). +\item $f$: sensible aux conditions initiales \\ ($ \exists \delta > 0 . \forall x \in \mathcal{X} \textrm{ and } -\forall V \textrm{ neighborhood of $x$}. -\exists y \in V \textrm{ and } +\forall V \textrm{ voisin de $x$}. +\exists y \in V \textrm{ et } \exists n \ge 0 . d(f^n(x); f^n(y))> \delta $)\\ -\onslide<2>{\alert<2>{Addressed properties: avalanche effect}}. \end{enumerate} \end{block} -\footnote{\bibentry{devaney}} \ No newline at end of file diff --git a/introModes.tex b/introModes.tex old mode 100755 new mode 100644 index edbe918..43105c7 --- a/introModes.tex +++ b/introModes.tex @@ -1,5 +1,5 @@ \begin{itemize} - \item \emph{Strategie}: les éléments $J^t$ modifiés au temps $t$; + \item \emph{Stratégie}: les éléments $J^t$ modifiés au temps $t$; \item \emph{Date de Visibilité}: suite de la date la plus récente où un composant connaît la valeur d'un autre. \begin{itemize} @@ -20,7 +20,7 @@ F_i \begin{itemize} \item Parallèle: $J^t=\{1,\ldots,n\}$ and $S^t=(t)$; \item Chaotique: $S^t=(t)$; -\item Asynchrone: aucune constrainte. +\item Asynchrone: aucune contrainte. \end{itemize} \end{itemize} diff --git a/introRIter.tex b/introRIter.tex old mode 100755 new mode 100644 index 8aa4f23..3a53162 --- a/introRIter.tex +++ b/introRIter.tex @@ -8,7 +8,7 @@ \begin{center} \includegraphics[width=4cm]{chao_iterate_excerpt.pdf} \end{center}} -\only<3>{\item Iterations asynchrones : divergence même avec $J^t=\{1,\ldots,n\}$ +\only<3>{\item Itérations asynchrones : divergence même avec $J^t=\{1,\ldots,n\}$ \begin{itemize} \item $S^t = \left( \begin{array}{lllll} @@ -19,7 +19,7 @@ t & t & t & t & t\\ t & t & t & t & t \\ \end{array} \right) -\textrm{ where } +\textrm{ où } t' = \left\{ \begin{array}{l} t \textrm{si $t$ est pair;} \\ diff --git a/secu.tex b/secu.tex index 0519ecb..162bd3b 100644 --- a/secu.tex +++ b/secu.tex @@ -1 +1,17 @@ - \ No newline at end of file +\begin{itemize} +\item PRNG: +\begin{itemize} +\item Classe de générateurs cryptographiquement sûrs +\item Succès sur les test les plus difficiles (DieHard, U01, Nist) +\end{itemize} +\item Stéganographie: +\begin{itemize} +\item Classe d'algorithmes $\epsilon$ sûrs +\item Robustesse et stégo sécurités du même ordre que les meilleurs algos + existants +\end{itemize} +\item Fonctions de hachage: +\begin{itemize} +\item Travaux en cours. +\end{itemize} +\end{itemize} diff --git a/slides_and.tex b/slides_and.tex index 5f37d59..c47b2f1 100644 --- a/slides_and.tex +++ b/slides_and.tex @@ -39,6 +39,9 @@ %\usepackage{xspace} %\usepackage{times} %\usepackage{ag-texgraphicx} + +\usepackage{dsfont} + \usepackage{lmodern} \usepackage[french]{babel} @@ -73,13 +76,15 @@ } +\newcommand{\Bool}[0]{\ensuremath{\mathds{B}}} +\newcommand{\Nats}[0]{\ensuremath{\mathds{N}}} %% titlepage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \author{J.-F. Couchot et R. Couturier} \institute{\large Institut Femto-ST \\ \normalsize{équipe AND (Algorithmique Numérique Distribuée) }} -\title[AND]{\Large présentation de l'équipe Algoithmique Numérique Distribuée} +\title[AND]{\Large Présentation de l'\'Equipe Algorithmique Numérique Distribuée} %\subject{HDR} \begin{document} @@ -93,7 +98,7 @@ \newcommand{\inputFrame}[2]{ -\subsection{#1} +%\subsection{#1} \frame{ \frametitle{#1} %\begin{small} @@ -102,18 +107,32 @@ }} - \begin{frame} %------------------------------------------------------- \frametitle{plan} - \begin{myitemize} - \item qssqdsqd - \item qsdsq - \item qqsd - \item sdqsd - \end{myitemize} + \tableofcontents[hideallsubsections] + % \begin{myitemize} + % \item qssqdsqd + % \item qsdsq + % \item qqsd + % \item sdqsd + % \end{myitemize} \end{frame} +\section{Itérations synchrone ou asynchrone} +\frame{\subsection{Plan}\tableofcontents[currentsection,hideallsubsections]} +\inputFrame{Exemple jouet}{introRunning} +\inputFrame{Du mode parallèle au mode asynchrone}{introModes} +\inputFrame{Itérations de l'exemple jouet}{introRIter} +\inputFrame{Mode mixe}{combMixed} +\inputFrame{Composantes Connexes de l'exemple jouet}{combMXpl} +\inputFrame{Résultats théoriques du mode mixe}{combMixedTheo} +\inputFrame{Expériences}{combMExp} + + + +\section{Algorithmique numérique asynchrone} +\frame{\subsection{Plan}\tableofcontents[currentsection,hideallsubsections]} \begin{frame} %------------------------------------------------------- \frametitle{Itérations asynchrones} @@ -134,44 +153,37 @@ \item Résolution de systèmes linéaires sur Grid'5000 avec des communications entre les n\oe uds \item Résolution du problème obstacle sur Grid'5000 ou sur cluster de GPU \item Résolution d'un problème d'advection-diffusion sur Grid'5000 - \item \alert{Algo iteratifs asynchrones permettent d'exécuter des algorithmes avec des dépendances de données dans des contextes ou les paramètres réseaux fluctuent => Grille} + \item \alert{Algos itératifs asynchrones permettent d'exécuter des algorithmes avec des dépendances de données dans des contextes où les paramètres réseaux fluctuent => Grille} \end{myitemize} \end{frame} \begin{frame} %------------------------------------------------------- - \frametitle{Equilibrage de charge} + \frametitle{Équilibrage de charge} \begin{myitemize} \item Contexte : des processeurs n'ont pas la même quantité de calcul - \item Raison : charge évolue avec le temps, charge extérieur, processeurs et/ou réseaux hétérogènes - \item But : Equilibrer la charge entre les processeurs + \item Raison : charge évolue avec le temps, charge extérieure, processeurs et/ou réseaux hétérogènes + \item But : Équilibrer la charge entre les processeurs \item Conception de nombreux algorithmes d'équilibrage de charge distribués \item Particularités : contexte distribué, preuve de convergence, support de pertes de liens, conception de stratégie d'équilibrage \end{myitemize} \end{frame} \begin{frame} %------------------------------------------------------- - \frametitle{GPU computing} + \frametitle{Calculs sur GPU} \begin{myitemize} \item Accélération importante dans certains cas (x50) - \item Encadrements de 2 thèses sur cette thématique : résolution systèmes linéaires sur clusters de gpu, segmentation et débruitage d'image + \item Encadrements de 2 thèses sur cette thématique : résolution systèmes linéaires sur clusters de GPUs, segmentation et débruitage d'image \item Conception d'un algorithme très performant pour générer des nombres pseudo-aléatoires : 50 Milliards nb/s \end{myitemize} \end{frame} - - -\section{Combinaison synchrone/asynchrone} +\section{Avancées autour du chaos} \frame{\subsection{Plan}\tableofcontents[currentsection,hideallsubsections]} -\inputFrame{Exemple jouet}{introRunning} -\inputFrame{Du mode parallèle au mode asynchrone}{introModes} -\inputFrame{Iterations de l'exemple jouet}{introRIter} -\inputFrame{Mode mixe}{combMixed} -\inputFrame{Composantes Connexes de l'exemple jouet}{combMXpl} -\inputFrame{Résultats théoriques du mode mixe}{combMixedTheo} -\inputFrame{Expériences}{combMExp} - -\section{Avancées autours du chaos} +\inputFrame{Chaos selon Devaney}{devaney} +\inputFrame{Motivations}{cbhfk} +\inputFrame{Fonctions chaotiques discrètes}{ci} +\inputFrame{Sécurité}{secu}