Diferencia entre revisiones de «Práctica 3: Cuantificadores (Algoritmos I)»
Línea 62: | Línea 62: | ||
h) aux mayorPrimo<math>(x: \mathbb{Z}): \mathbb{Z}</math> = | h) aux mayorPrimo<math>(x: \mathbb{Z}): \mathbb{Z}</math> = | ||
<math>[y | y \leftarrow [0..|x|], primo(y), x \ mod \ y == 0 ]_{|[ y | y \leftarrow [0..|x|], \ primo(y), x \ mod \ y == 0]|-1}</math> | <math>[y | y \leftarrow [0..|x|], primo(y), x \ mod \ y == 0 ]_{|[ y | y \leftarrow [0..|x|], \ primo(y), x \ mod \ y == 0]|-1}</math> | ||
otras formas: | |||
-utilizar un aux ultimo que sea algo asi como cabeza(invertir(l:[T])) | |||
-acum(y | s: <math>\mathbb{Z}</math> = Indef, y <math>\leftarrow</math> [1..abs(x)], x mod y == 0); | |||
i) aux mcm<math>(x,y: \mathbb{Z}): \mathbb{Z}</math> = cab([ z | z <math>\leftarrow</math> [0..|x*y|], z \ mod \ x == 0, z \ mod \ y == 0]) | i) aux mcm<math>(x,y: \mathbb{Z}): \mathbb{Z}</math> = cab([ z | z <math>\leftarrow</math> [0..|x*y|], z \ mod \ x == 0, z \ mod \ y == 0]) |
Revisión del 12:50 11 abr 2010
Ejercicio 1
Determinar cuales de las variables que aparecen en las siguientes expresiones aparecen libres y cuales ligadas.
- (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 \forall x \in [0..n)) x+y==z }
- (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 \forall x \in [0..n), y \in [0..m)) x+y==z }
- (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 \forall j \in [0..|s|)) s_j == 0 }
- (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 \forall j \in [0..|s|)) s_j == x }
- (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 \exists x \in r, x\ mod\ 2 == 0)(\forall j \in [0..|s|)) s_j == x }
- 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 ( |s|>5 \land a<b-1 \land (\forall j \in [a..b)) 2 * s_j == s_{j+1})}
Respuestas:
Recordemos que las variables ligadas son aquellas que son variables de selector y están al alcance del mismo.
- x.
- x e y.
- j
- j
- x y j
- j
Ejercicio 2
Escriba los siguientes predicados en lenguaje de especificación:
a) aux sucError 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 (x: \mathbb{Z}): \mathbb{Z}} , que corresponde al sucesor de x.
b) aux sumaError 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 (x,y: \mathbb{R}): \mathbb{R}} , que corresponda a la suma entre x e y.
c) aux productoError 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 (x, y: \mathbb{R}): \mathbb{R}} , que corresponde al producto entre x e y.
d) aux cuadradoError 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 (x: \mathbb{Z})} : Bool, que sea verdadero sii x es un número cuadrado.
e) aux primoError 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 (x: \mathbb{Z})} : Bool, que sea verdadero sii x es primo.
f) aux coprimosError 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 (x,y: \mathbb{Z})} : Bool, que sea verdadero sii x e y son coprimos.
g) aux divisoresGrandesError 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 (x, y : \mathbb{Z})} : Bool, que sea verdadero sii todos los divisores de x, sin contar el uno, son mayores que y.
h) aux mayorPrimoError 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 (x: \mathbb{Z}): \mathbb{Z}} , que represente el mayor primo que divide a x.
i) aux mcmError 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 (x,y: \mathbb{Z}): \mathbb{Z}} , que represente el mínimo común múltiplo entre x e y.
j) aux mcdError 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 (x,y: \mathbb{Z}): \mathbb{Z}} , que represente el máximo común divisor entre x e y.
Respuestas:
a) aux suc 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 (x: \mathbb{Z}): \mathbb{Z}} = x + 1;
b) aux suma 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 (x,y: \mathbb{R}): \mathbb{R}} = x + y;
c) aux productoError 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 (x, y: \mathbb{R}): \mathbb{R}} = x * y;
d) aux cuadradoError 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 (x: \mathbb{Z})} : Bool = (x 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 \geq} 0 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 \wedge} (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 \exists} 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 \leftarrow} [0..x]) y*y == x);
e)aux primoError 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 (x: \mathbb{Z})} : Bool = |[ y | 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 \leftarrow} [1..|x|], x mod y == 0]| == 2 (Recordemos que un número es primo si tiene exactamente dos divisores positivos: el 1 y su valor absoluto)
f) aux coprimosError 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 (x,y: \mathbb{Z})} : Bool == |[ z | z 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 \leftarrow} [1..x], x mod z==0, y mod z == 0]| == 1 (Dos números son coprimos si tienen un único divisor positivo en común: el uno)
g) aux divisoresGrandesError 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 (x,y : \mathbb{Z})} : Bool = (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 \forall} z 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 \leftarrow} [ t | t 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 \leftarrow} [2..|x|], x mod t == 0]) z > y
h) aux mayorPrimoError 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 (x: \mathbb{Z}): \mathbb{Z}} = 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 [y | y \leftarrow [0..|x|], primo(y), x \ mod \ y == 0 ]_{|[ y | y \leftarrow [0..|x|], \ primo(y), x \ mod \ y == 0]|-1}} otras formas: -utilizar un aux ultimo que sea algo asi como cabeza(invertir(l:[T])) -acum(y | s: 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 \mathbb{Z}} = Indef, 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 \leftarrow} [1..abs(x)], x mod y == 0);
i) aux mcmError 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 (x,y: \mathbb{Z}): \mathbb{Z}} = cab([ z | z 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 \leftarrow} [0..|x*y|], z \ mod \ x == 0, z \ mod \ y == 0])
j) aux mcdError 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 (x,y: \mathbb{Z}): \mathbb{Z}} = 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 [ z | z \leftarrow [0..|x|], x \ mod \ z == 0, y \ mod \ z == 0 ]_{[ z | z \leftarrow [0..|x|], x \ mod \ z == 0, y \ mod \ z == 0 ] - 1}}
Ejercicio 3
Escriba las siguientes funciones auxiliares sobre secuencias de enteros, aclarando los tipos de los parámetros que recibe y devuelve:
1. capicua, que determina si una secuencia es capicúa. (Por ejemplo, [0,2,1,2,0] es capicúa y [0,2,1,4,0] no).
capicua(x: [T]): Bool = (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 \forall} i 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 \leftarrow} [0..|x|/2]) 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 x_{i-1}==x_{|x|-i}}
2. esPrefijo, que determina si una secuencia es prefijo de otra.
esPrefijo(x,y: [T]): Bool = (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 \exists} i 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 \leftarrow} [0..|y|-1]) x==[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 y_i} | j 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 \leftarrow} [0..i] ]
3. estaOrdenada, que determina si la secuencia está ordenada de menor a mayor.
estaOrdenada(x: [Int]): Bool = (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 \forall} i,j 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 \leftarrow} [0..|x|-1], i<j) 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 x_i < x_j}
4. todosPrimos, que determina si todos los elementos de la secuencia son números primos.
todosPrimos(x: []): Bool = ( t x) primo(t)
(primos la definimos en el ejercicio 2.5)
5. todosIguales, que determina si todos los elementos de la secuencia son iguales.
todosIguales(x: [T]): Bool = ( a, b x) a==b
6. hayUnoParQueDivideAlResto, que determina si hay un elemento par en la secuencia que divide al resto.
hayUnoParQueDivideAlResto(x: []): Bool = ( a x, a mod 2 == 0) ( b x) b mod a == 0
7. hayUnoEnPosicionParQueDivideAlResto, que determina si hay un elemento en una posición par de la secuencia que divide al resto.
hayUnoEnPosicionParQueDivideAlResto(x: []): Bool =
( i [0..|x|-1], i mod 2 == 0)( a x)
8. sinRepetidos, que determina si la secuencia no tiene repetidos.
sinRepetidos(x: [T]): Bool = ( i,j [0..|x|-1], i j)
9. sinMasDeNApariciones, que determina si en la secuencia, ningún elemento aparece más de n veces.
sinMasDeNApariciones(x: [T]): Bool = ( a x) | [ b | b x, b==a ] | n
10. otroMayorADerecha, que determina si todo elemento de la secuencia, salvo el último, tiene otro mayor a su derecha.
otroMayorADerecha(x: []): Bool = ( i [0..|x|-2])
11. todoEsMultiplo, que determina si todo elemento de la secuencia es múltiplo de alg¶un otro.
todoEsMultiplo(x: []): Bool = ( a x)( b x) b mod a == 0
12. enTresPartes, que determina si en la secuencia aparecen (de izquierda a derecha) primero 0s, después 1s y por último 2s. Por ejemplo [0; 0; 1; 1; 1; 1; 2] cumple con enTresPartes, pero [0; 1; 3; 0] o [0; 0; 0; 1; 1] no.
¿Cómo modificaría la expresión para que se admitan cero apariciones de 0s, 1s y 2s (es decir, para que por ejemplo [0; 0; 0; 1; 1] o [ ] sí cumplan nTresPartes?
enTresPartes(x: [): Bool = ( estaOrdenada(x) )
Pero si queremos que no sea estrictamente necesaria la pertenencia de al menos un 0, un 1 y un 2, podemos modificarlo de la siguiente manera:
enTresPartesPrima(x: [): Bool = ( estaOrdenada(x) a x) ) )