From: Leandro Lucarella <llucax@gmail.com>
Date: Wed, 14 Jul 2004 03:53:06 +0000 (+0000)
Subject: Mas.
X-Git-Tag: svn_import~1
X-Git-Url: https://git.llucax.com/z.facultad/75.06/material.git/commitdiff_plain/45786d86aada14565bae9669c414923a5d890a2c

Mas.
---

diff --git a/ejemplos_bs_mtf.txt b/ejemplos_bs_mtf.txt
new file mode 100644
index 0000000..527d36f
--- /dev/null
+++ b/ejemplos_bs_mtf.txt
@@ -0,0 +1,179 @@
+
+
+
+Los siguientes son algunos de los ejemplos dados en la clase práctica 20040531
+Los mismos no reemplazan a la explicación; son publicados únicamente con el objeto de evitar la necesidad de copiar los ejemplos en clase.
+
+----------------------------------------------------------------
+
+1) El proceso es:
+
+Datos originales --BS--> D' --MTF--> D'' ---Compresión Aritmética---> Datos comprimidos
+
+----------------------------------------------------------------
+
+2) Ejemplo de Block Sort
+
+
+Datos originales: ABRACADABRA
+
+Generamos las rotaciones:
+
+ABRACADABRA
+BRACADABRAA
+RACADABRAAB
+ACADABRAABR
+CADABRAABRA
+ADABRAABRAC
+DABRAABRACA
+ABRAABRACAD
+BRAABRACADA
+RAABRACADAB
+AABRACADABR
+
+Las ordenamos lexicográficamente:
+
+AABRACADABR
+ABRAABRACAD
+ABRACADABRA
+ACADABRAABR
+ADABRAABRAC
+BRAABRACADA
+BRACADABRAA
+CADABRAABRA
+DABRAABRACA
+RAABRACADAB
+RACADABRAAB
+
+Nos quedamos con la última columna:
+
+V = RDARCAAAABB
+
+Determinamos cuál de las rotaciones es la original:
+
+K = 3
+
+Resultado del algoritmo BlockSort:
+* V = RDARCAAAABB
+* K = 3
+
+
+----------------------------------------------------------------
+
+
+3) Inversa del BlockSort:
+
+Datos:
+* V = RDARCAAAABB
+* K = 3
+
+Numeramos los elementos del vector V:
+
+1   2   3   4   5   6   7   8   9  10  11
+R   D   A   R   C   A   A   A   A   B   B
+
+Ahora ordenamos el vector V arrastrando también al orden los números:
+
+3   6   7   8   9  10  11   5   2   1   4   // orden original
+A   A   A   A   A   B   B   C   D   R   R   // elementos ordenados
+
+A continuación volvemos a numerar los elementos del V ordenado:
+
+1   2   3   4   5   6   7   8   9  10  11   // nuevo orden
+3   6   7   8   9  10  11   5   2   1   4   // orden original
+A   A   A   A   A   B   B   C   D   R   R   // elementos ordenados
+
+Luego empezamos por el elemento que tiene el número K en el nuevo orden. Lo emitimos, y el siguiente será el indicado por el número viejo del elemento emitido.
+
+K = 3
+
+Emitimos A, siguiente = 7
+Emitimos B, siguiente = 11
+Emitimos R, siguiente = 4
+Emitimos A, siguiente = 8
+Emitimos C, siguiente = 5
+Emitimos A, siguiente = 9
+Emitimos D, siguiente = 2
+Emitimos A, siguiente = 6
+Emitimos B, siguiente = 10
+Emitimos R, siguiente = 1
+Emitimos A, siguiente = 3 (3 era el original => fin)
+
+Resultado: ABRACADABRA
+
+----------------------------------------------------------------
+
+
+4) Ejemplo de MTF
+
+Datos originales:
+
+RDARCAAAABB
+
+Vector Z original: ABCDR
+(todos los caracteres posibles)
+
+ABCDR //datos del vector Z
+01234 //numeración de las posiciones (empezamos del cero)
+
+Dato  Emitimos  El vector Z queda:
+ R      4           RABCD
+ D      4           DRABC
+ A      2           ADRBC
+ R      2           RADBC
+ C      4           CRADB
+ A      2           ACRDB
+ A      0             =
+ A      0             =
+ A      0             =
+ B      4           BACRD
+ B      0             =
+
+
+Resultado del algoritmo MTF:
+4 4 2 2 4 2 0 0 0 4 0
+
+
+----------------------------------------------------------------
+
+
+5) Inversa del MTF:
+
+Dato:
+4 4 2 2 4 2 0 0 0 4 0
+
+Vector Z original:
+ABCDR
+
+Dato  Emitimos  El vector Z queda:
+ 4      R           RABCD
+ 4      D           DRABC
+ 2      A           ADRBC
+ 2      R           RADBC
+ 4      C           CRADB
+ 2      A           ACRDB
+ 0      A             =
+ 0      A             =
+ 0      A             =
+ 4      B           BACRD
+ 0      B             =
+
+
+Resultado:
+RDARCAAAABB
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+