Diferencia entre revisiones de «Práctica 3: Cuantificadores (Algoritmos I)»

De Cuba-Wiki
 
(No se muestran 5 ediciones intermedias de 2 usuarios)
Línea 7: Línea 7:
# (<math>\forall j \in [0..|s|)) s_j == x </math>
# (<math>\forall j \in [0..|s|)) s_j == x </math>
# (<math>\exists x \in r, x\ mod\ 2 == 0)(\forall j \in [0..|s|)) s_j == x </math>
# (<math>\exists x \in r, x\ mod\ 2 == 0)(\forall j \in [0..|s|)) s_j == x </math>
# <math> ( |s|>5 \land a<b-1 \land (\forall j \in [a..b)) 2 * s_j == s_{j+1})</math>
# <math> ( |s|>5 \land a < b-1 \land (\forall j \in [a..b)) 2 * s_j == s_{j+1})</math>




Línea 64: Línea 64:
otras formas:  
otras formas:  
-utilizar un aux ultimo que sea algo asi como cabeza(invertir(l:[T]))
-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])
Línea 75: Línea 74:
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).
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 = (<math>\forall</math>i <math> \leftarrow</math> [0..|x|/2]) <math>x_{i-1}==x_{|x|-i}</math>
''capicua''(x: [T]): Bool = (<math>\forall</math>i <math> \leftarrow</math> [0..|x|) ) <math>x_i==x_{|x|-i-1}</math>




Línea 81: Línea 80:


''esPrefijo''(x,y: [T]): Bool = (<math>\exists</math> i <math>\leftarrow</math> [0..|y|-1]) x==[<math>y_i</math>| j <math>\leftarrow</math> [0..i] ]
''esPrefijo''(x,y: [T]): Bool = (<math>\exists</math> i <math>\leftarrow</math> [0..|y|-1]) x==[<math>y_i</math>| j <math>\leftarrow</math> [0..i] ]
otra forma:
(|b| > |a| <math>\wedge</math> (<math>\forall i \leftarrow</math> [0..|a|) ) <math>a_i==b_i</math>);


3. ''estaOrdenada'', que determina si la secuencia está ordenada de menor a mayor.
3. ''estaOrdenada'', que determina si la secuencia está ordenada de menor a mayor.
Línea 116: Línea 119:


''sinRepetidos''(x: [T]): Bool = (<math>\forall</math> i,j <math>\leftarrow</math> [0..|x|-1], i <math>\neq</math>j) <math>x_i \neq x_j </math>
''sinRepetidos''(x: [T]): Bool = (<math>\forall</math> i,j <math>\leftarrow</math> [0..|x|-1], i <math>\neq</math>j) <math>x_i \neq x_j </math>
otra forma:
(<math>\forall</math> i <math>\leftarrow</math> [0..|x|-1]), <math>x_i \not\in x_{[0..i)}) </math>
otra más:
(<math>\forall</math> e <math>\leftarrow</math> x, cuenta(e, x) == 1)




Línea 144: Línea 151:
''enTresPartesPrima''(x: [<math>\mathbb{Z}]</math>): Bool = ( estaOrdenada(x) <math> \land (\forall</math> a <math>\leftarrow</math> x) <math> (0 \geq a  \ \land \ a \leq 2 </math> ) )
''enTresPartesPrima''(x: [<math>\mathbb{Z}]</math>): Bool = ( estaOrdenada(x) <math> \land (\forall</math> a <math>\leftarrow</math> x) <math> (0 \geq a  \ \land \ a \leq 2 </math> ) )


===Ejercicio 4===
1- "Todos los naturales menores a 10 que cumplen P, cumplen Q":


===Ejercicio 4===
aux a: Bool (<math>\forall x \in</math> [0..10)) (<math>P(x) \wedge Q(x)</math>)
 
Esta mal porque no queremos que para todos, todos cumplan P y Q, sino que cuando P sea verdadero, Q tambien lo sea:
 
aux a: Bool (<math>\forall x \in</math> [0..10))(<math>P(x) \Rightarrow Q(x)</math>)
 
2- "No hay ningún natural menor a 10 que cumpla P y Q":
 
aux c: Bool = <math>(\neg ( \exists x \in [0..10) P(x)  \wedge \neg ( \exists x \in [0..10) Q(x))</math>
 
Pero esto diría que ninguno en s cumple P y ninguno en s cumple Q.
En su lugar deberíamos poner:
 
aux c: Bool = <math>\neg ( \exists x \in [0..10) ) P(x) \wedge Q(x)</math>;

Revisión actual - 18:27 29 ago 2016

Ejercicio 1

Determinar cuales de las variables que aparecen en las siguientes expresiones aparecen libres y cuales ligadas.

  1. (
  2. (
  3. (
  4. (
  5. (


Respuestas: Recordemos que las variables ligadas son aquellas que son variables de selector y están al alcance del mismo.

  1. x.
  2. x e y.
  3. j
  4. j
  5. x y j
  6. j

Ejercicio 2

Escriba los siguientes predicados en lenguaje de especificación:

a) aux suc, que corresponde al sucesor de x.

b) aux suma, que corresponda a la suma entre x e y.

c) aux producto, que corresponde al producto entre x e y.

d) aux cuadrado: Bool, que sea verdadero sii x es un número cuadrado.

e) aux primo: Bool, que sea verdadero sii x es primo.

f) aux coprimos: Bool, que sea verdadero sii x e y son coprimos.

g) aux divisoresGrandes: Bool, que sea verdadero sii todos los divisores de x, sin contar el uno, son mayores que y.

h) aux mayorPrimo, que represente el mayor primo que divide a x.

i) aux mcm, que represente el mínimo común múltiplo entre x e y.

j) aux mcd, que represente el máximo común divisor entre x e y.


Respuestas:

a) aux suc = x + 1;

b) aux suma = x + y;

c) aux producto = x * y;

d) aux cuadrado: Bool = (x 0 ( y [0..x]) y*y == x);

e)aux primo: Bool = |[ y | y [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 coprimos: Bool == |[ z | z [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 divisoresGrandes: Bool = ( z [ t | t [2..|x|], x mod t == 0]) z > y

h) aux mayorPrimo = otras formas: -utilizar un aux ultimo que sea algo asi como cabeza(invertir(l:[T]))

i) aux mcm = cab([ z | z [0..|x*y|], z \ mod \ x == 0, z \ mod \ y == 0])

j) aux mcd =

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 = (i [0..|x|) )


2. esPrefijo, que determina si una secuencia es prefijo de otra.

esPrefijo(x,y: [T]): Bool = ( i [0..|y|-1]) x==[| j [0..i] ]

otra forma: (|b| > |a| ( [0..|a|) ) );


3. estaOrdenada, que determina si la secuencia está ordenada de menor a mayor.

estaOrdenada(x: [Int]): Bool = ( i,j [0..|x|-1], i<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) otra forma: ( i [0..|x|-1]), otra más: ( e x, cuenta(e, x) == 1)


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) ) )

Ejercicio 4

1- "Todos los naturales menores a 10 que cumplen P, cumplen Q":

aux a: Bool ( [0..10)) ()

Esta mal porque no queremos que para todos, todos cumplan P y Q, sino que cuando P sea verdadero, Q tambien lo sea:

aux a: Bool ( [0..10))()

2- "No hay ningún natural menor a 10 que cumpla P y Q":

aux c: Bool =

Pero esto diría que ninguno en s cumple P y ninguno en s cumple Q. En su lugar deberíamos poner:

aux c: Bool = ;