Práctica 1 (LyC Verano)
Ejercicio 1
Sin usar macros, mostrar en Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mathcal{S}} un programa que compute la función vacía Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \emptyset : I\!\!N^k \to I\!\!N} ; es decir, la función que no está definida para ninguna k-tupla de naturales.
Solución
Y ← Y + 1 [A1] IF Y ≠ 0 GOTO A1
Ejercicio 2
Escribir en Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mathcal{S}} programas que computen los siguientes predicados.
Pueden utilizarse las macros
GOTO A
(salto incondicional),
V ← k
(asignación de constantes) y
V1 ← V2
(asignación de variables).
Ítem a
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle igual(x_1, x_2) = \begin{cases} 1 & \mbox{si } x_1 = x_2 \\ 0 & \mbox{si } x_1 \ne x_2 \\ \end{cases} }
Solución
[A1] IF X1 ≠ 0 GOTO A2 IF X2 ≠ 0 GOTO E Y ← Y + 1 GOTO E [A2] IF X1 ≠ 0 GOTO A3 GOTO E [A3] X1 ← X1 - 1 X2 ← X2 - 1 GOTO A1
Ítem b
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle distinto(x_1, x_2) = \begin{cases} 1 & \mbox{si } x_1 \ne x_2 \\ 0 & \mbox{si } x_1 = x_2 \\ \end{cases} }
Solución
Y ← Y + 1 [A1] IF X1 ≠ 0 GOTO A2 IF X2 ≠ 0 GOTO E Y ← Y - 1 GOTO E [A2] IF X1 ≠ 0 GOTO A3 GOTO E [A3] X1 ← X1 - 1 X2 ← X2 - 1 GOTO A1
Ítem c
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle mayor(x_1, x_2) = \begin{cases} 1 & \mbox{si } x_1 > x_2 \\ 0 & \mbox{si } x_1 \le x_2 \\ \end{cases} }
Solución
[A1] IF X1 ≠ 0 GOTO A2 GOTO E [A2] IF X2 ≠ 0 GOTO A3 Y ← Y + 1 GOTO E [A3] X1 ← X1 - 1 X2 ← X2 - 1 GOTO A1
Ítem d
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle menor(x_1, x_2) = \begin{cases} 1 & \mbox{si } x_1 < x_2 \\ 0 & \mbox{si } x_1 \ge x_2 \\ \end{cases} }
Solución
[A1] IF X2 ≠ 0 GOTO A2 GOTO E [A2] IF X1 ≠ 0 GOTO A3 Y ← Y + 1 GOTO E [A3] X1 ← X1 - 1 X2 ← X2 - 1 GOTO A1
Ejercicio 3
Mostrar que el lenguaje Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mathcal{S}} es minimal, en el sentido que ninguna de las instrucciones
V ← V + 1
,
V ← V - 1
y
IF V ≠ 0 GOTO A
pueden eliminarse del lenguaje sin perder expresividad.
Solución
Ejercicio 4
Escribir en Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mathcal{S}} programas que calculen las siguientes funciones.
Además, pueden utilizarse las macros
GOTO A
,
V ← k
y
V1 ← V2
.
Ítem a
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle producto(x_1, x_2) = x_1 \cdot x_2} (usando suma como macro)
Solución
Z1 ← X1 [A1] IF Z1 ≠ 0 GOTO A2 GOTO E [A2] Y ← Y + X2 Z1 ← Z1 - 1 GOTO A1
Ítem b
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle potencia(x_1, x_2) = x_1^{x_2}} (usando producto como macro)
Solución
Z1 ← X2 Y ← 1 [A1] IF Z1 ≠ 0 GOTO A2 GOTO E [A2] Y ← Y * X1 Z1 ← Z1 - 1 GOTO A1
Ejercicio 5
Demostrar que el lenguaje Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mathcal{S}} cumple las siguientes propiedades:
Ítem a
Las siguientes funciones son computables:
- la función sucesor Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle suc: I\!\!N \to I\!\!N, suc(x) = x + 1}
- las proyecciones Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle u^n_i: I\!\!N^n \to I\!\!N, u^n_i(x_1, \dots, x_n) = x_i} (para Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle i} tal que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle i \le i \le n)} .
- las funciones constantes Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle c_k: I\!\!N \to I\!\!N, c_k(x) = k} (para cualquier Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle k \in I\!\!N} ).
Solución
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle suc(x)\,\!}
Y ← X1 + 1
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle u^n_i(x_1, \dots, x_n)\,\!}
Y ← Xi
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle c_k(x)\,\!}
Y ← k
Ítem b
Si Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f, g_1, \dots, g_k\,\!} son computables con Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Dom(f) \subseteq I\!\!N^k} y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Dom(g_i) \subseteq I\!\!N^r} para todo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle i \in \{1, \dots, k\}} , entonces la composición Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle h\,\!} es computable:
¿Cuál es el dominio de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle h\,\!} ?
Nota: hay un pequeño error en el enunciado, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle h\,\!} es computable sólo si
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Dom(f) \supseteq Img(g_1) \times \dots \times Img(g_k)}
Solución
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Dom(h) = \bigcap_{0 < i \le k} Dom(g_1)}
Ejercicio 6
Usando las macros vistas en clase, escribir programas en Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mathcal{S}} que computen las siguientes funciones:
Ítem a
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(x) =\,\!} el mayor número natural Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle n\,\!} tal que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 2n \le x\,\!}
Solución
[A1] Z1 ← Z1 + 2 Z2 ← Z1 > X1 IF Z2 ≠ 0 GOTO E Y ← Y + 1 GOTO A1
Ítem b
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle P(x_1, x_2) = \begin{cases} 1 & \mbox{si } x_2 \mbox{ es multiplo de } x_1 \\ 0 & \mbox{sino} \\ \end{cases}\,\!}
Solución
IF Z2 = 0 GOTO A2 // si Z2 = 0 entonces es múltiplo de X1 // voy a A2 y como Z1 = X2 = 0 devuelvo 1 [A1] Z1 ← Z1 + X1 // Z1 guarda los múltiplos de X1 Z2 ← Z1 < X2 IF Z2 ≠ 0 GOTO A1 [A2] Y ← Y + 1 // se tiene Z1 = k * X1 >= X2 Z3 ← Z1 = X2 IF Z3 ≠ 0 GOTO E Y ← Y - 1
Ejercicio 7
Escribir un programa que compute el mínimo común múltiplo y otro que compute el máximo común divisor entre dos números naturales. Se puede utilizar cualquier macro vista en clase.
Solución
mcm: N x N -> N Y ← X1 [A] Z ← multiplo(Y, X2) IF Z ≠ 0 GOTO E Y ← Y + X1 // Y = X1, 2X1, 3X1.... GOTO A
MCD : N x N -> N Y ← X1 Z2 ← X2 [A] IF Z2 = 0 GOTO E [B] Z3 ← mayor(Y,Z2) IF Z3 ≠ 0 GOTO C Z2 ← Z2 - Y GOTO A [C] Y ← Y - Z2 GOTO A
IDEA: ALGORITMO DE EUCLIDES ORIGINAL
MCD(a,b) = while (b > 0) { if (a > b) then a <- a-b else b <- b-a } return a
Ejercicio 8
Sean Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle g: I\!\!N^{n+1} \to I\!\!N, s, t: I\!\!N \to I\!\!N} funciones computables. Usando las macros vistas en clase, escribir programas que computen las siguientes funciones:
Ítem a
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f_1(x_1, \dots, x_n, y) = \mbox{max}\{g(x_1, \dots, x_n, i): 0 \le i \le y\}}
Solución
[A1] Z2 ← g(X1, ..., Xn, Z1) Z3 ← Z2 < Y IF Z3 ≠ 0 GOTO A2 Y ← Z2 [A2] Z1 ← Z1 + 1 Z4 ← Z1 < Xn+1 IF Z4 ≠ 0 GOTO A1
Ítem a
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f_2(x_1, \dots, x_n, y) = \begin{cases} \mbox{max}\{g(x_1, \dots, x_n, i): s(y) \le i \le t(y)\} & \mbox{si } s(y) \le t(y) \\ 0 & \mbox{sino} \\ \end{cases} }
Solución
Z1 ← s(Xn+1) Z5 ← t(Xn+1) Z6 ← Z1 > Z5 IF Z6 ≠ 0 GOTO E [A1] Z2 ← g(X1, ..., Xn, Z1) Z3 ← Z2 < Y IF Z3 ≠ 0 GOTO A2 Y ← Z2 [A2] Z1 ← Z1 + 1 Z4 ← Z1 < Z5 IF Z4 ≠ 0 GOTO A1