Práctica 1 (LyC Verano)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Ejercicio 1[editar]

Sin usar macros, mostrar en Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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 (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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[editar]

     Y ← Y + 1
[A1] IF Y ≠ 0 GOTO A1


Ejercicio 2[editar]

Escribir en Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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[editar]

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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[editar]

[A1] IF X1 ≠ 0 GOTO A2
     IF X2 ≠ 0 GOTO E
     Y ← Y + 1
     GOTO E
[A2] IF X2 ≠ 0 GOTO A3
     GOTO E
[A3] X1 ← X1 - 1
     X2 ← X2 - 1
     GOTO A1

Ítem b[editar]

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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[editar]

     Y ← Y + 1
[A1] IF X1 ≠ 0 GOTO A2
     IF X2 ≠ 0 GOTO E
     Y ← Y - 1
     GOTO E
[A2] IF X2 ≠ 0 GOTO A3
     GOTO E
[A3] X1 ← X1 - 1
     X2 ← X2 - 1
     GOTO A1

Ítem c[editar]

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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[editar]

[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[editar]

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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[editar]

[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[editar]

Escribir en Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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[editar]

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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[editar]

     Z1 ← X1
[A1] IF Z1 ≠ 0 GOTO A2
     GOTO E
[A2] Y ← Y + X2
     Z1 ← Z1 - 1
     GOTO A1

Ítem b[editar]

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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[editar]

     Z1 ← X2
     Y ← 1
[A1] IF Z1 ≠ 0 GOTO A2
     GOTO E
[A2] Y ← Y * X1
     Z1 ← Z1 - 1
     GOTO A1


Ejercicio 4[editar]

Demostrar que las siguientes funciones son computables:

  • la función sucesor Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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 (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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 (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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 (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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 (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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 (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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[editar]

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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 (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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 (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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


Ejercicio 5[editar]

Usando las macros vistas en clase, escribir programas en Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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[editar]

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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 (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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 (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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[editar]

[A1] Z1 ← Z1 + 2
     Z2 ← Z1 > X1
     IF Z2 ≠ 0 GOTO E
     Y ← Y + 1
     GOTO A1

Ítem b[editar]

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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[editar]

     IF X2 = 0 GOTO A2 // si X2 = 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 6[editar]

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[editar]

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle MCM:\ \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}}

     Y ← X1
[A]  Z ← multiplo(Y, X2)
     IF Z ≠ 0 GOTO E
     Y ← Y + X1   // Y = X1, 2X1, 3X1....
     GOTO A

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle MCD:\ \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{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 7[editar]

Mostrar que el lenguaje Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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[editar]

Pistas:

  • Para la primera probar por inducción que no importa las instrucciones que ponga el valor de salida siempre será 0.
  • Para la segunda ver más abajo.
  • Para la tercera probar que cualquier función que haga va a estar acotada por el tamaño del programa asi que f(x) = x no puede hacerse (por ejemplo).

Caso 2: Sin resta[editar]

Versión preliminar de la demostración, needs cleanup.

En general, supongo P un programa, v1,...,vk las variables que aparecen en la guarda de los k IFs de P, y l la longitud de P.

Lema 1: Supongamos <i1,t1> tiene como sucesor a <i2,t2>. Sea t1' un estado tal que es vi = 0 en t1 sii vi = 0 en t1' y también que vi > 0 en t1 sii vi > 0 en t1'. Entonces <i1,t1'> tiene como suc. a <i2,t2'>. Dem: Es bastante facil de ver. Si i1 es V <- V + 1 o V <- V - 1, la siguiente instrucción es i2 independientemente del estado. Si i1 es IF V !=0 GOTO A, como t1 y t1' coinciden en el resultado de la evaluación de V en el if, el sucesor es i2 en ambos casos.

Lema 2: Si P ejecuta l+1 pasos y ninguna de las vi cambia (donde cambia es que pasa a cero si era distinta de cero, o pasa a ser distinta de cero si era cero), P se cuelga. Dem: Es facil ver que en l+1 pasos se tiene que repetir al menos una instrucción de P. Digamos que es la número i1. Entonces la ejecución que tenemos es:

...<i1, t1> <i2,t2>....<il+1 = i1, tl+1>...

y sabemos que ninguna de las vi cambió durante la ejecución. Pero entonces, por el lema 1, la siguiente instrucción a ij es ij+1 (para todo j entre 1 y l) sin importar cuál es el estado. Eso significa que se establece un ciclo infinito y el programa se cuelga.

Teo: Sea P sin la instrucción V <- V - 1. Si P termina, ejecuta como mucho n.k instrucciones. Dem: Como P termina, por el lema 2 en l pasos tiene que cambiar alguna de las vi. Como no hay resta, cada vi sólo puede cambiar de cero a distinto de cero. Si en l.k pasos el programa no terminó, las k variables de los ifs de P tienen que haber cambiado a un valor distinto de cero y de ahí en más no pueden volver a cambiar, con lo cual el programa termina en ese punto o se cuelga.

Ejercicio 8[editar]

Sean Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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[editar]

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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[editar]

[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 b[editar]

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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[editar]

     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


Ejercicio Extra 1[editar]

Si Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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 (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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 (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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 (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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 (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle h\,\!} es computable:

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle h(x_1, \dots, x_r) = f(g_1(x_1, \dots, x_r), \dots, g_k(x_1, \dots, x_r))\,\!} .

¿Cuál es el dominio de Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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 (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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 (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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[editar]

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): 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)}