Siguiente: Códigos binarios Arriba: Primeras listas Anterior: Ejercicios

Programas

1. Enumeración de subconjuntos. Escriba un programa que reciba dos enteros positivos $(n,k)$, con $0<k\leq n$ y haga lo siguiente:

1. Reciba un índice $\ell\in[\![0,{n \choose k}-1]\!]$ y escriba el $\ell$-ésimo subconjunto de $k$ elementos en $[\![0,n-1]\!]$.
2. Reciba un subconjunto $I$ de $k$ elementos en $[\![0,n-1]\!]$ y calcule el índice que le corresponda de acuerdo con la enumeración anterior.

2. Código 4-en-8. Sea $A$ el alfabeto de 70 símbolos

$$A= \{\mbox{\tt A,...,Z}\}\cup \{\mbox{\tt a,...,z}\}\cup \{\mbox{\tt0,...,9}\}\cup \{\mbox{\tt !,?,(,),:,.,\ ,,}\}$$

(en el último bloque el penúltimo carácter es el blanco y el último la coma). Escriba un programa que considerando el Código 4-en-8 $\gamma$ del ejemplo 2.1:

1. Reciba una palabra $\sigma\in A^*$ y escriba el código $\gamma(\sigma)$ correspondiente a esa palabra.
2. Reciba una palabra $\omega\in \{\mbox{\tt0,1}\}^*$ y revise si acaso está en la imagen de $\gamma$. Si no lo está marque el primer lugar en $\omega$ donde ocurra una violación a las reglas sintácticas, y si lo está entonces encuentre $\sigma\in A^*$ tal que $\gamma(\sigma)=\omega$.

3. Escriba un programa que habiendo recibido como entrada una lista de números enteros positivos $\left(\ell_{\nu}\right)_{\nu=0}^{n-1}$:

1. Calcule el mínimo $k\in\mathbb{N}$ que satisface la desigualdad de Kraft,
2. Sea $A_n$ el alfabeto consistente de los $n$ símbolos consecutivos ASCII a partir del carácter numérico con código decimal 33 (``!''). Sea $C_k$ el alfabeto consistente de los $k$ símbolos consecutivos del alfabeto latino de minúsculas. Calcule la función de codificación de un código instantáneo de $A_n$ sobre $C_k^*$ tal que el símbolo $i$-ésimo se codifica por una cadena de longitud $\ell_i$.

4. Escriba un programa que reciba como entrada la tabla correspondiente a la función de codificación de un código.

1. Decida si el código es instantáneo,
2. En caso de que lo sea, reciba palabras codificadas y las decodifique procediendo de manera voraz..

5. Escriba un programa que habiendo recibido como entrada una lista de números enteros positivos $\left(\ell_{\nu}\right)_{\nu=0}^{n-1}$ y un entero $k\in\mathbb{N}$ que satisfagan la desigualdad de Kraft, cuente cuántas funciones de codificación existen tales que el símbolo $i$-ésimo se codifica por una cadena de longitud $\ell_i$.

6. Escriba un programa que calcule la codificación de Huffman. Como entrada debe darse una tabla de símbolos y frecuencias y una bandera que indique si se quiere un código binario, terciario o cuternario. Como salida debe dar la función de codificación correspondiente.

7. Escriba un programa que reciba un entero positivo $n\in\mathbb{N}$ y un valor real $h\in\mathbb{R}$. Para ellos debe decidir si existe una distribución ${\bf p}$ tal que $H({\bf p}) = h$ y en tal caso debe encontrar una tal distribución, la longitud esperada de su código de Huffman y su efectividad.

8. Escriba un programa que reciba una distribución ${\bf p}$ de un alfabeto de $n$ símbolos, y un entero $k\in\mathbb{N}$ y calcule la extensión ${\bf p}^k$ como una lista de $n^k$ valores reales.

9. Escriba un programa que reciba como entrada $n\in\mathbb{N}$ y un vector ${\bf p}\in\mathbb{R}^n$ y compruebe experimentalmente que vale la igualdad de límite enunciada en el teorema de Shannon 3.1.

10. Escriba un programa que realice la situación descrita en el ejemplo 3.2:

• Inicialmente recibe $n,m\in\mathbb{N}$ y $p\in[0,1]$.
• Genera una matriz $M\in\{0,1\}^{m\times n}$ de manera que la frecuencia de 1 sea $p$ (y en consecuencia la de 0 habría de ser $1-p$).
• Realiza la codificación mostrada en el ejemplo, y calcula la tasa de compresión.
• Muestra estadísticas para muchas repeticiones del experimento.

Siguiente: Códigos binarios Arriba: Primeras listas Anterior: Ejercicios