Práctica 2: Secuencias (Algoritmos I)

Ejercicio 1

Evaluar las siguientes expresiones:

a) |[4,3,1]|
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 cons(\pi , [2,3,5,7,11])}
c) $indice([0..3],3)$
d) $conc([2,3],[5,7,11])$
e) $cab(cola([5..8]))$
f) $sub([2,3,5,7,11],0,3)$
g) $en(\pi ,[2,3,5,7,11])$
h) $sub([2,3,5,7,11],3,2)$
i) $en(1,[1..5])$
j) $sub([2,3,5,7,11],0,65536)$

Respuestas:

a) 3
b) $[\pi ,2,3,5,7,11]$
c) 3
d) [2,3,5,7,11]
e) 6
f) [2,3,5,7]
g) False
h) [ ]
i) True
j) [ ] (Según el apunte de especificación, todos los casos en que no se cumple 0 <= d <= h < |a| equivalen a la secuencia vacía)

Ejercicio 2

¿Cuáles de las siguientes igualdades sobre variables de tipo Lista son válidas?

a) |x|= |cola(x)| + 1

b) en(3,x) = en(3,y)

c) x = sub(x,0,|x|-1)

d) conc(const(3,x),y) = const(3,conc(x,y))

e) x = cons (cab(x),cola(x))

f) indice(x,0) = cab(x)

g) en(i,x) = cab(sub(x,i,i))

h) cola(x) = sub(x,1,|x|-1)

En los casos incorrectos, ¿puede dar condiciones sobre las listas en cuestión para que lo sean?

Respuestas:

a) Válida
b) La validez depende de x e y. En general la igual no vale, pero si el 3 pertenece a ambas lista, o no pertenece a ninguna, la igualdad se cumple
c) Válida
d) Válida
e) Válida
f) Válida
g) No es válida en General. De hecho el miembro izquierdo de la igualdad es de tipo Bool, y el izquierdo es del tipo de los elementos de x. La única posibilidad de que sean iguales es que los elementos de x sean Bool. Pero en tal caso no está definida la función en para este llamado: en(3,x). Por lo tanto para ninguna lista puede ser válido
h) Válida

Ejercicio 3

Describir informalmente las siguientes listas definidas por comprensión y dar sus primeros elementos. Para mejorar la lectura, en algunos casos se han utilizado listas auxiliares.

a) [x| x $\leftarrow$ [0..5]]
b) [x+1| x $\leftarrow$[0..5]]
c) [(x,x+1)| x $\leftarrow$[0..15], x mod 3 = 0]
d) [(x,y)| x $\leftarrow$[0..1], y $\leftarrow$ [0..1]]
e) [[]| x $\leftarrow$[[],[0],[0,1],[0,1,2]]]
f) [ (y,divisores(y)) | y $\leftarrow$ [2..5]] donde

aux divisores$(y:\mathbb {Z} )$: $[\mathbb {Z} ]$ = [x| x $\leftarrow$ [2..x-1], y mod x = 0]
g) [ (u,consec(u)) | u $\leftarrow$ [True,False] ] donde

aux consec(v: Bool): [Bool] = [ w | w $\leftarrow$ [True, False], v $\rightarrow$ w ]

h) concat([ suman10para(n) | n $\leftarrow$ [0..10]]) donde

aux suman10para$(n:\mathbb {Z} )$ : $[\mathbb {Z} ]$ = [ 10 $\cdot$ n + m | m $\leftarrow$ [0..9], n+m=10 ]

i) agregar2digitos([]) donde

aux agregar2digitos$(xs:[\mathbb {Z} ])$: $[[\mathbb {Z} ]]$ = concat([ agregar1digito(ys) | ys $\leftarrow$ agregar1digito(xs)])

aux agregar1digito$(xs:[\mathbb {Z} ])$: $[[\mathbb {Z} ]]$ = [ conc(xs,[x]) | x $\leftarrow$ [0..9] ]

Aclaración: La función auxiliar concat$(x:[[\mathbb {Z} ]]):[\mathbb {Z} ]$ es análoga a la función conc, pero concatena varias listas, o sea que por ejemplo concat( [ [0, 1], [2, 3] ] ) = [0, 1, 2, 3] y concat( [ [0], [2, 4], [6] ] ) = [0, 2, 4, 6].

Respuestas:

a) [0..5]

b) [1..6]

c) [(0,1) , (3,4) , (6,7) , (9,10) , (12,13) , (15,16)]

d) [ (0,0) , (0,1) , (1,0) , (1,1)] (La idea de este punto es trabajar con varios selectores. Simplemente hay que recordar que cada vez que el primer selector toma un valor antes de pasar al siguiente, el segundo selector tiene que haber recorrido todos sus valores posibles. Ejemplo: [(x,y)| x $\leftarrow$[0,1], y $\leftarrow$ [6..9]] = [ (0,6) , (0,7) , (0,8) , (0,9) , (1,6) , (1,7) , (1,8) , (1,9)])

e) [ [] , [] , [] , [] ]

f) [ (2,[]) , (3,[]) , (4,[2]) , (5,[])] (Notar que en el auxiliar divisores se toman los divisores que no son 1 ni el mismo número)

g) [ (True , [True]) , (False , [True,False]) ]

h) [ 19 , 28 , 37, 46 , 55 , 64 , 73, 82 , 91 , 100 ]

i) [ [0,0] , [0,1] , [0,2] , [0,3] , [0,4] , [0,5] , [0,6] , ............ [9,5] , [9,6] , [9,7] , [9,8] , [9,9]]

Ejercicio 4

Evaluar las siguientes expresiones:

a) acum(r+1 | r:$\mathbb {Z}$=0 , e $\leftarrow$ [1..10] , e mod 3 = 0)
b) acum(r+e | r:$\mathbb {Z}$=-1, e $\leftarrow$ [10..1])=-1
c) eval([1,2,-1], 4)

aux eval$(p:[\mathbb {Z} ],x:\mathbb {Z} ):\mathbb {Z}$ = acum(r * x + e | r: $\mathbb {Z}$= 0, e $\leftarrow$p)

Respuestas:

Recordemos el mecanismo del acum:

En un acum tenemos la siguiente sintaxis:

acum( expresión | inicialización, selectores, condicion)

• ¿Qué inicia la inicialización? Inicia la variable que vamos a llamar acumulador. Esta variable va a ir tomando distintos valores, y el último que toma es el que devuelve el acum.
• El selector, como en las secuencias por comprensión está formado por una variable selectora y una secuencia.
• Quizás no nos interesan todos los elementos de la secuencia del selector. La condición sirve, justamente, para poner alguna condición en particular que tengan que cumplir los elementos de la secuencia del selector que van a usarse. Desde luego, si no hay ninguna condición, entonces la variable del selector, pasa por todos los valores de la secuencia.
• La expresión es algo que se evalúa una vez que la variable del selector toma un valor que cumpla la condición. Este valor será guardado en el acumulador, y la variable del selector toma un nuevo valor, y vuelve a evaluarse la expresión y guardarse en el acumulador, y así sucesivamente, hasta que la variable del selector no puede tomar ningún valor. Cuando esto sucede el acum nos devuelve el último valor del acumulador.

a) 3.

Seguimiento a modo de ejemplo:

• r=0 (así empieza el acumulador, que en este caso es r, y lo sabemos por la inicialización)
• La variable del selector (para este ejemplo, e) toma el valor 1. Me pregunto ¿cumple la condición? NO. Entonces lo ignoro y paso al siguiente valor posible de e.
• Ahora e toma valor 2. ¿Cumple la condición? NO. Paso al siguiente valor de e.
• Ahora e toma valor 3. ¿Cumple la condición? SI. Entonces evalúo la expresión r+1, para el valor actual de r y e. Esto da 1 y lo guardo en r. AHORA vale r=1 y paso al siguiente valor del selector.
• Ahora e toma valor 4. ¿Cumple la condición? NO. Paso al siguiente valor de e.
• Ahora e toma valor 5. ¿Cumple la condición? NO. Paso al siguiente valor de e.
• Ahora e toma valor 6. ¿Cumple la condición? SI. Evalúo la expresión r+1 con el valor actual de r y e. Este valor lo guardo en r. Entonces AHORA vale r=2. Paso al siguiente valor de e.
• Ahora e toma valor 7. ¿Cumple la condición? NO. Paso al siguiente valor de e.
• Ahora e toma valor 8. ¿Cumple la condición? NO. Paso al siguiente valor de e.
• Ahora e toma valor 9. ¿Cumple la condición? SI. Evalúo la expresión r+1 con los actuales valores de r y e, y como siempre, lo guardo en el acumulador r. Es decir que AHORA r=3. Paso al siguiente valor de e.
• Ahora e toma valor 10. ¿Cumple la condición? NO. Paso al siguiente valor de e.
• No tengo siguiente valor de e. Entonces el acum vale el último valor de r. Es decir 3

MORALEJA: el acumulador va renovando su valor en función de distintas cosas. Esto le da un mayor poder expresivo al lenguaje de especificación que lo que veníamos viendo hasta ahora. Sin embargo siempre que pueda evitarse el uso de acum es preferible evitarlo.

b) En el enunciado hay un pequeño error y ya está escrito el resultado. Veamos por qué vale -1.

Seguimiento:

• r=-1 (Por la inicialización sabemos que r es el acumulador y que empieza valiendo -1)
• La variable del selector (en este caso e), toma el primer valor de la secuencia del selector.
• Pero la secuencia del selector es vacía. Es un intervalo cuyo extremo inferior es mayor al superior.
• Por lo tanto se me acabaron los valores posibles (porque no había ninguno!) para e. Y en este caso siempre tengo que devolver el último valor que tomó r. Que es -1

c) 23.

Está escrito con una función auxiliar. Pero ¿quién es este acum? Es:

acum( r*4 + e | r: $\mathbb {Z}$=0, e $\leftarrow$ [1, 2, -1])

porque en este caso x=4 y p=[1,2,-1]

Seguimiento:

• r=0 (Por la inicialización)
• El primer valor que puede tomar e es 1 ¿Cumple la condición? Sí, porque no hay ninguna. Entonces evalúo la expresión r*4 + e para los valores actuales de r y e (es decir 0 y 1 respectivamente). El resultado de esto es 1, y por lo tanto ahora r=1. Pasamos al siguiente valor posible de e.
• Ahora e vale 2. ¿Se cumple la condición? Sí. Evalúo la expresión r*4+e para los valores actuales (e vale 2, y r vale 1). Esto da 6, por lo tanto r=6, a partir de ahora y hasta que r vuelva a cambiar. Pasamos al siguiente valor posible de e.
• Ahora e vale -1. ¿Se cumple la condición? Sí. Evalúo la expresión r*4 + e para los valores actuales de e y r. Es decir para -1 y 6. Esto vale 23, y ahora r=23. Pasamos al siguiente valor de e.
• No hay siguiente valor de e! Entonces mi acum vale el último de los valores que tuvo r. Es decir 23.

Ejercicio 5

Utilizando secuencias definidas por comprensión, definir las siguientes expresiones:

a) Dada una secuencia de enteros s formar la secuencia de los elementos de s que son mayores a 3.

Respuesta:

[ x | 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 \leftarrow} s, x > 3]

b) Dados una secuencia s y un natural n formar la secuencia que queda tras eliminar los primeros n elementos de s.

Respuesta: [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_i} | 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} [n+1,|s|-1]]

c) Dada una secuencia de enteros s formar otra con los mismos elementos, pero con los elementos impares primero y los pares después. El orden relativo de los impares y de los pares entre sí debe ser el mismo que tenían en s.

Respuesta:

[ x | 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 \leftarrow} s, x mod 2 = 1]++[ x | x $\leftarrow$ s, x mod 2 = 0]

d) Dada una secuencia s formar su reverso (la secuencia dada vuelta).

Respuesta:

[ $s_{|s|-i-1}$ | i $\leftarrow$ [0,|s|-1] ]

Ejercicio 6

Escriba la función auxiliar concat que dada una lista de listas de enteros forme la lista que representa la concatenación de todas las listas que conforman la primera (ver Ejercicio 3).

Respuesta:

aux concat$(x:[[\mathbb {Z} ]]):[\mathbb {Z} ]$ = [ z | y $\leftarrow$ x , z $\leftarrow$ y ]

Esta lista agarra una lista que está en x, y guarda los elementos en el mismo orden en la lista resultante, y luego pasa a guardar los de otra, y los de otra, hasta que se acaban las listas en x.

Nótese que NO FUNCIONA si intercambiamos el orden de los selectores. Recordemos que las listas de los selectores se recorren en un orden determinado que es: fijamos la variable del primer selector, recorremos TODOS los valores posibles para la del segundo selector, y luego avanzamos. El proceso termina cuando se recorrieron todos los valores posibles para el primer selector.

Ejercicio 7

Para cada aparición de variable en las siguientes expresiones, indicar si en esa posición la variable está libre o ligada.

a) [ (x,z) | x $\leftarrow$ [0..t] ]

b) [ (x,z) | x $\leftarrow$ [0..z] , z $\leftarrow$ [ y | y $\leftarrow$ [0..10 ] ] ]

c) [ k | x $\leftarrow$ [0..t ] ]

d) [ (a,b,c,d) | a $\leftarrow$ [ b | b $\leftarrow$ [ c | c $\leftarrow$ [0..5], c<d ] ] ]

Respuestas:

Recordemos antes la definición de la teórica de variables ligadas:

Selectores: variable $\leftarrow$ secuencia

Las variables que aparecen en los selectores se llaman ligadas, el resto de las que aparecen en una expresión se llaman libres

Entonces se reduce a elegir aquellas variables que "están siendo señaladas por una flechita". Esto es las variables que son variables de un selector.

a) x está ligada y z no.

b) x está ligada y z está ligada. Y y también está ligada, pero en otro nivel (es decir no es variable en ningún selector en la secuencia por comprensión mayor, pero aparece en la secuencia de un selector como variable ligada.)

c) x está ligada, k y t no.

d) a b y c están ligadas y d no.

Ejercicio 8

Indique el resultado de las siguientes expresiones:

a) $\sum$[1..9]

b) $\sum$[1..1)

c) $\prod$[ pot(2,m) | m $\leftarrow$ [0..3] ]

d) [$\prod$[ pot(i,a) | i $\leftarrow$ [1..2] ] | a $\leftarrow$ [0..1] ]

e) $\sum$[ pot(2,m) | m $\leftarrow$ [0..3] ]

f) $\sum$[ pot(2,-m) | m $\leftarrow$ [0..3] ]

Respuestas:

a) 45 (Resultado de sumar de 1 a 9)

b) 0 (Debido a que la lista [1..1) es vacía)

c) 64

d) [1,2] (hay que mirar con más atención, pero no es difícil)

e) 15

f) 1.875

Ejercicio 9

Escriba expresiones auxiliares (aux) utilizando las funciones $\sum$, $\prod$ y acum que respondan a los siguientes enunciados:

a) La suma de los primeros cinco naturales.

b) La productoria del tercer grupo de k naturales (por ejemplo, si k = 3 sería [6; 7; 8], y si k = 5 sería [10; 11; 12; 13; 14]).

c) Sea N una secuencia con las notas de un alumno. Escriba una expresión que determine su promedio. Modifíquela para que determine su promedio sin tener en cuenta los aplazos..

d) Sea R una secuencia de duplas de enteros, donde cada elemento describe los goles a favor y en contra (respectivamente) de los partidos del último torneo de un equipo. Escriba una expresión que determine la diferencia de gol que el equipo obtuvo en ese torneo..

e) Una secuencia que contenga cada una de las sumas parciales de potencias negativas de dos, hasta alcanzar los k elementos. La secuencia debe comenzar así: $[{\frac {1}{2}},{\frac {1}{2}}+{\frac {1}{4}},{\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}},..]$

f) Dada una secuencia de enteros a, defina una expresión que describa la secuencia de productorias parciales de a. Por ejemplo si a es [1, 3, 6] su expresión debe determinar la secuencia [1, 3, 18].

g) Dada una secuencia de enteros a, defina una expresión que determine el valor del máximo elemento en a.

a) $\sum$[0..4]

b) $\prod$[2k..3k-1]

c) $\sum [N_{i}*|N|^{-1}|i\leftarrow [0..|N|-1]]$

d) $\sum$ [ prm(R_i) - sgd(R_i) | i $\leftarrow$ [0..|R|-1] ]

e) [ $\sum$[pot(2,-i) | i $\leftarrow$ [1..n] | n $\leftarrow$] [1..k] ]

f) [ $\prod$[ $a_{i}$ | i $\leftarrow$ [0..j] ] | j $\leftarrow$ [0..|a|-1] ]

g) acum($a_{i}$ | r: $\mathbb {Z} =a_{0}$, i $\leftarrow$ [2..|a|-1], $a_{i}\geq r$ )