Siguiente: Funciones recursivas primitivas Un nivel arriba: Conceptos básicos Anterior: Primera lista de ejercicios

Primera lista de programas

En esta sección, al construir un programa-while hay que utilizar variables de la forma Xw, donde $w\in\{0,1\}^*$ es una palabra que señala el orden de aparición de la variable.

1. Expansor de macros condicionales: Escriba un programa que traduzca macros ``programáticos''.

Entrada:
$\begin{pagi}{29}Un programa con instucciones {\bf if }-{\bf then }, {\bf if }-{\bf then }-{\bf else }, {\bf repeat }-{\bf until }.\end{pagi}$
Salida:
$\begin{pagi}{29}El prograna-{\bf while }equivalente.\end{pagi}$

2. Expansor de macros de pruebas complejas: Escriba un programa que traduzca pruebas compuestas.

Entrada:
$\begin{pagi}{29}Una prueba compuesta, es decir, una prueba escrita como una comp... ...ariables: \begin{displaymath}\Phi(X_1,\ldots,X_m).\end{displaymath} \end{pagi}$
Salida:
$\begin{pagi}{29}Una prueba b\'asica, es decir, de la forma $X\not=0$ , equivalen... ...playmath}\Phi(X_1,\ldots,X_m)\Leftrightarrow X\not=0.\end{displaymath}\end{pagi}$

3. Expansor de macros de expresiones aritméticas: Escriba un programa que reescriba expresiones aritméticas como programas-while 's. Las expresiones aritméticas se forman con constantes y variables e involucran a las cuatro operaciones aritméticas, a la exponenciación, div, mod, sqrt, parte entera, entero más próximo por arriba, etc.

Entrada:
$\begin{pagi}{29}Una asignaci\'on cuyo miembro a la derecha es una expresi\'on aritm\'etica: \begin{displaymath}X:=T(X_1,\ldots,X_m).\end{displaymath} \end{pagi}$
Salida:
$\begin{pagi}{29}Un programa-{\bf while }equivalente al anterior.\end{pagi}$

4. Esquema de recursión: Escriba un programa que aplique el esquema de recursión.

Entrada:
$\begin{pagi}{29} Dos programas-{\bf while }'s $G$\space y $H$ , vistos como pro... ...n las \'ultimas variables de $G$\space y $H$\space respectivamente. \end{pagi}$
Salida:
$\begin{pagi}{29} Un programa-{\bf while }que calcula a la funci\'on $f$\space t... ...*} f(0,x) &=& g(x) \\ f(n+1,x) &=& h(f(n,x),x). \end{eqnarray*} \end{pagi}$

5. Compresión sintáctica de programas: Considerando la codificación de símbolos mostrada en la tabla 1.7,

Table 1.7: Codificación de símbolos de los programas- while .

Símbolo	Código hexadecimal
while	0
do	1
{	2
}	3
++	4
-	5
$\not=$	6
X	7
0	8
1	9
;	A

escriba a cualquier programa-while como una sucesión de bytes.

6. Decompresión sintáctica de programas: Para la misma codificación de símbolos en el programa anterior, decida cuándo una sucesión de bytes es el código de un programa-while . Cuando lo sea, reescriba el programa como una cadena de caracteres ASCII.

7. Simulador de programas-while 's: Dado un programa-while y una configuración inicial a su lista de variables, aplicar el programa a esa configuración y visualizar el cómputo paso a paso.

Entrada:
$\begin{pagi}{29}Un programa-{\bf while }$P$\space y una instancia inicial $\mbox{\bf x}$\space a su lista de variables. \end{pagi}$
Salida:
$\begin{pagi}{29}Una visualizaci\'on del c\'omputo de $P(\mbox{\bf x})$ .\end{pagi}$

8. Traductor de máquinas de Turing a programas-while 's: Dada una máquina de Turing escriba el programa-while que calcula a la misma función calculada por la máquina de Turing. Aquí hay que suponer que la máquina de Turing está definida sobre el alfabeto $\{0,1\}$ , que el 0 hace el papel de ``blanco'' y que representa a los números en unario.

Siguiente: Funciones recursivas primitivas Un nivel arriba: Conceptos básicos Anterior: Primera lista de ejercicios

Guillermo Morales-Luna
2000-07-10