52 lines
3.1 KiB
TeX
52 lines
3.1 KiB
TeX
\begin{theorem}
|
|
Le nombre de blocs distincts de la partie stable dans le compressé n'est pas forcément une fonction croissante en la taille de la chaîne
|
|
\end{theorem}
|
|
\begin{proof}[Sketch]
|
|
Nous allons exhiber un contre-exemple ayant lieu avec probabilité non négligeable.
|
|
|
|
Sachant que le nombre de blocs distincts de la partie stable du compressé ne peut augmenter au maximum que d'un bloc lors de la compression avec un nouveau bloc d'après l'onliness, on prouve la perte d'au moins 2 blocs distincts dans la partie stable du compressé. Cela permettra donc de prouver la possible diminution du nombre de blocs distincts dans la partie stable du compressé.
|
|
|
|
En moyenne le $m$-ème dernier bloc du niveau 1 a la même hauteur que le $2m$-ème dernier bloc du niveau 0, donc la probabilité pour que le $m$-ème dernier bloc du niveau 1 soit derrière le $2m$-ème dernier bloc du niveau 0 de 2 blocs de niveau 0 est de $\frac{1}{2}^2$.
|
|
|
|
La probabilité que le bloc de la partie stable que l'on ajoute soit de niveau 1 est de probabilité $\frac{1}{2}$.
|
|
|
|
On en déduit que ce scénario où ce nouveau 1-superbloc s'ajoute et permet de diminuer d'au moins 1 le nombre de blocs distincts dans la partie stable du compressé a lieu à chaque nouveau bloc avec une probabilité $\frac{1}{2}^2 * \frac{1}{2} = \frac{1}{2}^3$.
|
|
\end{proof}
|
|
|
|
|
|
\begin{theorem}\label{thm:block-level}
|
|
Etant donné un compressé C de niveau l, l'ajout d'un bloc b à C donne C' de niveau $l' \geq l$
|
|
\end{theorem}
|
|
\begin{proof}[Sketch]
|
|
Oui, par contruction, si le compressé est de niveau l on a au moins 2m blocs de niveau l.
|
|
L'ajout d'un bloc de niveau l' < l ne change pas le nombre de blocs au niveau l dans le compressé qui reste de niveau l.
|
|
Si l' = l, le bloc ajouté remplace le plus vieux bloc de niveau l, ce qui ne change pas le niveau de C.
|
|
Si l' > l, le compressé peut soit rester au niveau l car il n'y a pas au moins 2m blocs au niveau l', soit passer au niveau l'.
|
|
\end{proof}
|
|
|
|
\begin{corollary}
|
|
Le niveau de la partie stable dans le compressé est une fonction croissante en la taille de la chaîne.
|
|
\end{corollary}
|
|
|
|
|
|
\begin{theorem}
|
|
Si un bloc de niveau l est éjecté du niveau l, alors il n'est plus présent du tout dans le compressé.
|
|
\end{theorem}
|
|
\begin{proof}[Sketch]
|
|
Oui, par construction plus un bloc appartient aussi aux niveaux inférieurs plus la propriété précédente, pour éjecter un bloc de niveau l, il faut un bloc de niveau l' >= l.
|
|
\end{proof}
|
|
|
|
|
|
\begin{theorem}
|
|
Si un bloc de niveau l est présent dans un niveau l'<l, alors il est présent dans tous les niveaux intermédiaires entre l' et l.
|
|
\end{theorem}
|
|
\begin{proof}[Sketch]
|
|
Oui, car virer un bloc au niveau l'', l' < l'' < l, nécessite un bloc de niveau >= l''. Comme il faut au moins 2m blocs par niveau, et qu'un bloc au niveau >= l'' compte aussi pour les niveaux inférieurs, il impacte de la même façon les niveaux inférieurs.
|
|
\end{proof}
|
|
|
|
|
|
\begin{theorem}
|
|
Pour un bloc b de niveau l, pour tout $0 \le i < j \le l$, on a $pos(i, b) \le pos(j, b)$.
|
|
\end{theorem}
|
|
|