From: couchot Date: Thu, 16 Jul 2015 14:39:54 +0000 (+0200) Subject: 15raro: c'est une distance X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/commitdiff_plain/2bf0bca226facdce323e96552021bf90952eefce?ds=inline 15raro: c'est une distance --- diff --git a/15RairoGen.tex b/15RairoGen.tex index e4f8858..aff664f 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -517,45 +517,76 @@ $\mathcal{X}_{\mathsf{N},\mathcal{P}} = \mathds{B}^\mathsf{N} \times \mathds{S}_ où $s=(u,v)$ et $\check{s}=(\check{u},\check{v})$ sont dans $ \mathds{S}_{\mathsf{N},\mathcal{P}} = \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$. \begin{itemize} -\item $e$ et $\check{e}$ sont des entiers appartenant à $\llbracket 0, 2^{\mathsf{N}-1} \rrbracket$. The Hamming distance -on their binary decomposition, that is, the number of dissimilar binary digits, constitutes the integral -part of $d(X,\check{X})$. -\item The fractional part is constituted by the differences between $v^0$ and $\check{v}^0$, followed by the differences -between finite sequences $u^0, u^1, \hdots, u^{v^0-1}$ and $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$, followed by - differences between $v^1$ and $\check{v}^1$, followed by the differences -between $u^{v^0}, u^{v^0+1}, \hdots, u^{v^1-1}$ and $\check{u}^{\check{v}^0}, \check{u}^{\check{v}^0+1}, \hdots, \check{u}^{\check{v}^1-1}$, etc. -More precisely, let $p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ and $n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$. +\item $e$ et $\check{e}$ sont des entiers appartenant à $\llbracket 0, 2^{\mathsf{N}-1} \rrbracket$. +La distance de Hamming $d_{\mathds{B}^\mathsf{N}}$ sur entre les +décompositions binaires de $e$ et de $\check{e}$ (\textit{i.e.}, le +le nombre de bits qu'elles ont de différent) constitue +la partie entière de $d(X,\check{X})$. +\item la partie décimale est construite à partir des différences entre +$v^0$ et $\check{v}^0$, suivie des différences entre les séquences finies +$u^0, u^1, \hdots, u^{v^0-1}$ et $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$, suivie par les différences entre $v^1$ et $\check{v}^1$, +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 +$p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ et +$n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$. \begin{itemize} -\item The $p$ first digits of $d(x,\check{x})$ is $|v^0-\check{v}^0|$ written in decimal numeration (and with $p$ digits). -\item The next $n\times \max{(\mathcal{P})}$ digits aim at measuring how much $u^0, u^1, \hdots, u^{v^0-1}$ differs from $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$. The $n$ first -digits are $|u^0-\check{u}^0|$. They are followed by -$|u^1-\check{u}^1|$ written with $n$ digits, etc. +\item Les $p$ premiers éléments de $d(x,\check{x})$ sont $|v^0-\check{v}^0|$ + écrits en base 10 et sur $p$ indices; +\item les $n\times \max{(\mathcal{P})}$ éléments suivants servent + à évaluer de combien $u^0, u^1, \hdots, u^{v^0-1}$ diffère de + $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$. + Les $n$ premiers éléments sont $|u^0-\check{u}^0|$. Il sont suivis de +$|u^1-\check{u}^1|$ écrits à l'aide de $n$ éléments, etc. \begin{itemize} -\item If -$v^0=\check{v}^0$, then the process is continued until $|u^{v^0-1}-\check{u}^{\check{v}^0-1}|$ and the fractional -part of $d(X,\check{X})$ is completed by 0's until reaching -$p+n\times \max{(\mathcal{P})}$ digits. -\item If $v^0<\check{v}^0$, then the $ \max{(\mathcal{P})}$ blocs of $n$ -digits are $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$, -$\check{u}^{v^0}$ (on $n$ digits), ..., $\check{u}^{\check{v}^0-1}$ (on $n$ digits), followed by 0's if required. -\item The case $v^0>\check{v}^0$ is dealt similarly. +\item Si +$v^0=\check{v}^0$, +alors le processus se continue jusqu'à $|u^{v^0-1}-\check{u}^{\check{v}^0-1}|$ et la +partie décimale de $d(X,\check{X})$ est complétée par des 0 +jusqu'à atteindre +$p+n\times \max{(\mathcal{P})}$ éléments. +\item Si $v^0<\check{v}^0$, alors les $ \max{(\mathcal{P})}$ blocs de $n$ +éléments sont $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$, +$\check{u}^{v^0}$ (sur $n$ éléments), ..., $\check{u}^{\check{v}^0-1}$ (sur $n$ éléments), suivi par des 0, si besoin. +\item Le cas $v^0>\check{v}^0$ est similaire, et donc omis \end{itemize} -\item The next $p$ digits are $|v^1-\check{v}^1|$, etc. +\item Les $p$ suivants sont $|v^1-\check{v}^1|$, etc. \end{itemize} \end{itemize} +La fonction $d$ peut se formaliser comme suit: +$$d(x,\check{x})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})+d_{\mathds{B}^\mathsf{N}}(e,\check{e}),$$ +où: % $p=\max \mathcal{P}$ and: +\begin{itemize} +\item $d_{\mathds{B}^\mathsf{N}}$ est la distance de Hamming, +\item $\forall s=(u,v), \check{s}=(\check{u},\check{v}) \in \mathcal{S}_{\mathsf{N},\mathcal{P}}$,\newline +$$\begin{array}{rcl} + d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) &= & + \sum_{k=0}^\infty \dfrac{1}{10^{(k+1)p+kn\max{(\mathcal{P})}}} + \bigg(|v^k - \check{v}^k| \\ + & & + \left| \sum_{l=0}^{v^k-1} + \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{(l+1)n}} - + \sum_{l=0}^{\check{v}^k-1} + \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{(l+1)n}} \right| \bigg) +\end{array} +$$ %\left| \sum_{l=0}^{v^k-1} \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{l}} - \sum_{l=0}^{\check{v}^k-1} \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{l}}\right|\right)}.$$ +\end{itemize} + \begin{xpl} -Consider for instance that $\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ (so $\mathsf{p}=3$), and that +On considère par exemple +$\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ ($\mathsf{p}$ vaut ainsi $3$), +et $s=\left\{ \begin{array}{l} u=\underline{6,} ~ \underline{11,5}, ...\\ v=1,2,... \end{array} \right.$ -while +avec $\check{s}=\left\{ \begin{array}{l} \check{u}=\underline{6,4} ~ \underline{1}, ...\\ @@ -563,65 +594,56 @@ $\check{s}=\left\{ \end{array} \right.$. -So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.010004000000000000000000011005 ...$ -Indeed, the $p=2$ first digits are 01, as $|v^0-\check{v}^0|=1$, -and we use $p$ digits to code this difference ($\mathcal{P}$ being $\{1,2,11\}$, this difference can be equal to 10). We then take the $v^0=1$ first terms of $u$, each term being coded in $n=2$ digits, that is, 06. As we can iterate -at most $\max{(\mathcal{P})}$ times, we must complete this -value by some 0's in such a way that the obtained result -has $n\times \max{(\mathcal{P})}=22$ digits, that is: -0600000000000000000000. Similarly, the $\check{v}^0=2$ first -terms in $\check{u}$ are represented by 0604000000000000000000, and the absolute value of their -difference is equal to 0004000000000000000000. These digits are concatenated to 01, and -we start again with the remainder of the sequences. +Ainsi $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.010004000000000000000000011005 ...$ +En effet, les $p=2$ premiers éléments sont 01, c'est-à-dire +$|v^0-\check{v}^0|=1$, +et on utilise $p$ éléments pour représenter cette différence +(Comme $\mathcal{P}=\{1,2,11\}$, cette différence peut valoir 10). +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: +0600000000000000000000. +De manière similaire, les $\check{v}^0=2$ premiers +termes de $\check{u}$ sont représentés par +0604000000000000000000. +LA valeur absolue de leur différence est égale à +0004000000000000000000. +Ces éléments sont concaténés avec 01. On peut construire alors le reste de +la séquence. \end{xpl} \begin{xpl} -Consider now that $\mathsf{N}=9$, and $\mathcal{P}=\{2,7\}$, and that - -$s=\left\{ +On considère à présent que $\mathsf{N}=9$, que $\mathcal{P}=\{2,7\}$ et que +$$s=\left\{ \begin{array}{l} u=\underline{6,7,} ~ \underline{4,2,} ...\\ v=2,2,... \end{array} -\right.$ -while -$\check{s}=\left\{ +\right.$$ +avec +$$\check{s}=\left\{ \begin{array}{l} \check{u}=\underline{4, 9, 6, 3, 6, 6, 7,} ~ \underline{9, 8}, ...\\ \check{v}=7,2,... \end{array} -\right.$ +\right. +$$ -So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.5173633305600000...$, as $|v^0-\check{v}^0|=5$, $|4963667-6700000| = 1736333$, $|v^1-\check{v}^1|=0$, -and $|9800000-4200000| = 5600000$. +Ainsi $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.5173633305600000...$, +puisque +$|v^0-\check{v}^0|=5$, $|4963667-6700000| = 1736333$, $|v^1-\check{v}^1|=0$, +et $|9800000-4200000| = 5600000$. \end{xpl} -$d$ can be more rigorously written as follows: -$$d(x,\check{x})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})+d_{\mathds{B}^\mathsf{N}}(e,\check{e}),$$ -where: % $p=\max \mathcal{P}$ and: -\begin{itemize} -\item $d_{\mathds{B}^\mathsf{N}}$ is the Hamming distance, -\item $\forall s=(u,v), \check{s}=(\check{u},\check{v}) \in \mathcal{S}_{\mathsf{N},\mathcal{P}}$,\newline -$$\begin{array}{rcl} - d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) &= & - \sum_{k=0}^\infty \dfrac{1}{10^{(k+1)p+kn\max{(\mathcal{P})}}} - \bigg(|v^k - \check{v}^k| \\ - & & + \left| \sum_{l=0}^{v^k-1} - \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{(l+1)n}} - - \sum_{l=0}^{\check{v}^k-1} - \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{(l+1)n}} \right| \bigg) -\end{array} -$$ %\left| \sum_{l=0}^{v^k-1} \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{l}} - \sum_{l=0}^{\check{v}^k-1} \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{l}}\right|\right)}.$$ -\end{itemize} - - -Let us show that, -\begin{prpstn} -$d$ is a distance on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$. -\end{prpstn} +On a la proposition suivante, qui est démontrée en annexes~\ref{anx:generateur}. +\begin{lemma} +$d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$. +\end{lemma} \subsection{Le graphe $\textsc{giu}_{\mathcal{P}}(f)$ étendant $\textsc{giu}(f)$} diff --git a/annexePreuveDistribution.tex b/annexePreuveDistribution.tex index 7a05f11..8de466c 100644 --- a/annexePreuveDistribution.tex +++ b/annexePreuveDistribution.tex @@ -55,3 +55,33 @@ Ces résultats permettent formuler et de prouver le théorème suivant: $M$ est doublement stochastique. \end{Proof} + + +Montrons que +\begin{lemma} +$d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$. +\end{lemma} + + +\begin{proof} + $d_{\mathds{B}^\mathsf{N}}$ est la distance de Hamming. + Prouvons que + $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ est aussi une distance; +$d$ sera ainsi une distance comme somme de deux distances. + \begin{itemize} +\item De manière évidente, $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})\geqslant 0$, et si $s=\check{s}$, alors +$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$. +Réciproquement si $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$, alors +$\forall k \in \mathds{N}, v^k=\check{v}^k$ d'après la définition de $d$. +Or les éléments entre les positions $p+1$ et $p+n$ +sont nules et correspondent à $|u^0-\check{u}^0|$, +on peut conclure que $u^0=\check{u}^0$. +On peut étendre ce résultat aux $n \times \max{(\mathcal{P})}$ premiers +bloc engendrant $u^i=\check{u}^i$, $\forall i \leqslant v^0=\check{v}^0$, +et en vérifiant tous les $n \times \max{(\mathcal{P})}$ blocs, $u=\check{u}$. + \item $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ est évidemment symétrique +($d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(\check{s},s)$). +\item l'inégalité triangulaire est établie puisque la valeur absolue la vérifie +aussi. + \end{itemize} +\end{proof}