Algoritmos y Estructuras de Datos

Departamento de Computación
Guı́a Práctica 2 Facultad de Ciencias Exactas y Naturales
Especificación de problemas Universidad de Buenos Aires
Primer Cuatrimestre 2026

2.1. Predicados y Auxiliares

Ejercicio 1. Nombrar los siguientes predicados sobre enteros:

a) pred ????(x : Z) { (∃c : Z) (c > 0 ∧ c ∗ c = x) }

b) pred ????(x : Z) { (∀n : Z) (1 < n < x →L x mód n ̸= 0) }

Ejercicio 2. Escriba los siguientes predicados sobre números enteros en lenguaje de especificación:

a) pred divide(x, y : Z) que sea verdadero si y sólo si x divide a y (es decir, el resto es 0).
b) pred sonCoprimos(x, y : Z) que sea verdadero si y sólo si x e y son coprimos.
c) pred mayorPrimoQueDivide(x : Z, y : Z) que sea verdadero si y es el mayor primo que divide a x.

Ejercicio 3. Nombre los siguientes predicados auxiliares sobre secuencias de enteros:

a) pred ????(s : seq⟨Z⟩) { (∀i : Z) (0 ≤ i < |s| →L s[i] ≥ 0) }

b) pred ????(s : seq⟨Z⟩) { (∀i : Z) (0 ≤ i < |s| →L (∀j : Z) (0 ≤ j < |s| ∧ i ̸= j →L s[i] ̸= s[j])) }

Ejercicio 4. Escriba los siguientes predicados auxiliares sobre secuencias de enteros, aclarando los tipos de los parámetros
que recibe:
a) pred pertenece(. . .) que determina si un elemento pertenece a una secuencia.
b) pred esPrefijo(. . .) que determina si una secuencia es prefijo de otra.
c) pred estáOrdenada(. . .) que determina si la secuencia está ordenada de menor a mayor.
d) pred primosEnPosicionesPares(. . .) que determina si todos los números primos están en posiciones pares.
e) pred hayUnoPrimoQueDivideAlResto(. . .) que determina si hay un elemento primo en la secuencia que divide a todos
los otros elementos de la secuencia.
f) pred 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 enTresPartes)?

Ejercicio 5. Escribir una auxiliar que

a) Sume 10 a un entero.
b) “Devuelva” el mayor elemento de una tupla de 3 enteros.
c) “Devuelva” el dı́gito menos significativo de un entero.

Ejercicio 6. Sea s una secuencia de elementos de tipo Z. Escribir una auxiliar utilizando sumatoria y productoria que:
a) Cuente la cantidad de veces que aparece el elemento e de tipo Z en la secuencia s.
b) Sume los elementos en las posiciones pares de la secuencia s.
c) Sume los elementos mayores a 0 contenidos en la secuencia s.
d) Sume los inversos multiplicativos ( x1 ) de los elementos contenidos en la secuencia s distintos a 0.

1
2.2. Análisis de especificación
Ejercicio 7. Las siguientes especificaciones no son correctas. Indicar por qué y corregirlas para que describan correctamente
el problema.

a) proc progresionGeometricaFactor2() Indica si la secuencia l representa una progresión geométrica factor 2. Es decir,
si cada elemento de la secuencia es el doble del elemento anterior.
proc progresionGeometricaFactor2(in l : seq⟨Z⟩) : bool {
requiere { T rue }
asegura { res = T rue ↔ (∀i : Z) (0 ≤ i < |l| →L l[i] = 2 ∗ l[i − 1]) }
}

b) proc mı́nimo() Devuelve en res el menor elemento de l.

proc mı́nimo(in l : seq⟨Z⟩) : Z {
requiere { T rue }
asegura { (∀y : Z) ((y ∈ l ∧ y ̸= x) → y > res) }
}

Ejercicio 8. Para los siguientes problemas, dar todas las soluciones posibles a las entradas dadas:

a) proc indiceDelMaximo(in l : seq⟨R⟩) : Z {

requiere { |l| > 0 }
asegura { 0 ≤ res < |l| ∧L (∀i : Z) (0 ≤ i < |l| →L l[i] ≤ l[res]) }
}

i) l = ⟨1, 2, 3, 4⟩
ii) l = ⟨15.5, −18, 4.215, 15.5, −1⟩
iii) l = ⟨0, 0, 0, 0, 0, 0⟩

b) proc indiceDelPrimerM;aximo(in l : seq⟨R⟩) : Z {

requiere { |l| > 0 }
asegura { 0 ≤ res < |l| ∧L (∀i : Z) (0 ≤ i < |l| →L (l[i] < l[res] ∨ (l[i] = l[res] ∧ i ≥ res))) }
}

i) l = ⟨1, 2, 3, 4⟩
ii) l = ⟨15.5, −18, 4.215, 15.5, −1⟩
iii) l = ⟨0, 0, 0, 0, 0, 0⟩

c) ¿Para qué valores de entrada indiceDelPrimerMaximo y indiceDelMaximo tienen necesariamente la misma salida?

Ejercicio 9. Sea f : R × R → R definida como:


2 × b si a < 0
f (a, b) =
b − 1 en otro caso

Indicar cuáles de las siguientes especificaciones son correctas para el problema de calcular f (a, b). Para aquellas que no
lo son, indicar por qué.

a) proc f(in a, b : R) : R {
requiere { T rue }
asegura { (a < 0 ∧ res = 2 × b) ∧ (a ≥ 0 ∧ res = b − 1) }
}

b) proc f(in a, b : R) : R {

2
 requiere { T rue }
asegura { (a < 0 ∧ res = 2 × b) ∨ (a ≥ 0 ∧ res = b − 1) }
}

c) proc f(in a, b : R) : R {
requiere { T rue }
asegura { (a < 0 → res = 2 × b) ∨ (a ≥ 0 → res = b − 1) }
}

d) proc f(in a, b : R) : R {
requiere { T rue }
asegura { res = IfThenElse(a < 0, 2 × b, b − 1) }
}

Ejercicio 10. Considerar la siguiente especificación, junto con un algoritmo que dado x devuelve x2 .
proc unoMasGrande(in x : R) : R {
requiere { T rue }
asegura { res > x }
}

a) ¿Qué devuelve el algoritmo si recibe x = 3? ¿El resultado hace verdadera la postcondición de unoMasGrande?
b) ¿Qué sucede para las entradas x = 0,5, x = 1, x = −0,2 y x = −7?
c) Teniendo en cuenta lo respondido en los puntos anteriores, escribir una precondición para unoMasGrande, de manera
tal que el algoritmo cumpla con la especificación

2.3. Relación de fuerza

Ejercicio 11. Sean x y res variables de tipo R. Considerar los siguientes predicados:
P1: {x ≤ 0} Q1: {res ≥ x2 }
P2: {x ≤ 10} Q2: {res ≥ 0}
P3: {x ≤ −10} Q3: {res = x2 }

a) Indicar la relación de fuerza entre P1, P2 y P3

b) Indicar la relación de fuerza entre Q1, Q2 y Q3
c) Escribir 2 programas que cumplan con la siguiente especificación:
proc hagoAlgo(in x : R) : R {
requiere { x ≤ 0 }
asegura { res ≥ x2 }
}

d) Sea A un algoritmo que cumple con la especificación del ı́tem anterior. Decidir si necesariamente cumple las siguientes
especificaciones:
i) requiere { x ≤ −10 }, asegura { res ≥ x2 }
ii) requiere { x ≤ 10 }, asegura { res ≥ x2 }
iii) requiere { x ≤ 0 }, asegura { res ≥ 0 }
iv) requiere { x ≤ 0 }, asegura { res = x2 }
v) requiere { x ≤ −10 }, asegura { res ≥ 0 }
vi) requiere { x ≤ 10 }, asegura { res = x2 }
e) ¿Qué conclusión pueden sacar? ¿Qué debe cumplirse con respecto a las precondiciones y postcondiciones para que sea
seguro reemplazar la especificación?

3
Ejercicio 12. Considerar las siguientes dos especificaciones, junto con un algoritmo a que satisface la especificación de p2.
proc p1(in x : R, in n : Z) : Z {
requiere { x ̸= 0 }
asegura { xn − 1 < res ≤ xn }
}
proc p2(in x : R, in n : Z) : Z {
requiere { n ≤ 0 → x ̸= 0 }
asegura { res = ⌊xn ⌋ }
}

a) Dados valores de x y n que hacen verdadera la precondición de p1, demostrar que hacen también verdadera la precondición
de p2.
b) Ahora, dados estos valores de x y n, supongamos que se ejecuta a: llegamos a un valor de res que hace verdadera la
postcondición de p2. ¿Será también verdadera la postcondición de p1 con este valor de res?
c) ¿Podemos concluir que a satisface la especificación de p1?

2.4. Especificación de problemas

Ejercicio 13. Especificar los siguientes problemas:
a) Dado un entero, decidir si es par
b) Dado un entero n y otro m, decidir si n es un múltiplo de m
c) Dado un entero, listar todos sus divisores positivos (sin duplicados)
d) Dado un entero positivo, obtener su descomposición en factores primos. Devolver una secuencia de tuplas (p, e), donde p
es un factor primo y e es su exponente, ordenada en forma creciente con respecto a p

Ejercicio 14. Especificar los siguientes problemas sobre secuencias:

a) Dadas dos secuencias s y t, decidir si s está incluida en t, es decir, si todos los elementos de s aparecen en t en igual o
mayor cantidad
b) Dadas dos secuencias s y t, devolver su intersección, es decir, una secuencia con todos los elementos que aparecen en
ambas. Si un mismo elemento tiene repetidos, la secuencia retornada debe contener la cantidad mı́nima de apariciones
del elemento en s y en t.
c) Dada una secuencia de números enteros, devolver aquel que divida a más elementos de la secuencia. El elemento tiene
que pertenecer a la secuencia original. Si existe más de un elemento que cumple esta propiedad, devolver alguno de ellos.
d) Dada una secuencia de secuencias de enteros l, devolver una secuencia de l que contenga el máximo valor. Por ejemplo,
si l = ⟨⟨2, 3, 5⟩, ⟨8, 1⟩, ⟨2, 8, 4, 3⟩⟩, devolver ⟨8, 1⟩ o ⟨2, 8, 4, 3⟩.
e) Dada una secuencia l con todos sus elementos distintos, devolver la secuencia de partes, es decir, la secuencia de todas
las secuencias incluidas en l, cada una con sus elementos en el mismo orden en que aparecen en l.

Ejercicio 15. Dados dos enteros a y b, se necesita calcular su suma y retornarla en un entero c. ¿Cúales de las siguientes
especificaciones son correctas para este problema? Para las que no lo son, indicar por qué.

a) proc sumar(inout a, b, c : Z) {
requiere { T rue }
asegura { a + b = c }
}

b) proc sumar(in a, b : Z, inout c : Z) {

requiere { T rue }
asegura { c = a + b }
}

4
c) proc sumar(inout a, b : Z, inout c : Z) {
requiere { a = A0 ∧ b = B0 }
asegura { a = A0 ∧ b = B0 ∧ c = a + b }
}

Ejercicio 16. Dada una secuencia l, se desea sacar su primer elemento y devolverlo. Decidir cúales de estas especificaciones
son correctas. Para las que no lo son, indicar por qué y justificar con ejemplos.

a) proc tomarPrimero(inout l : seq⟨Z⟩) : Z {

requiere { |l| > 0 }
asegura { res = head(l) }
}

b) proc tomarPrimero(inout l : seq⟨Z⟩) : Z {

requiere { |l| > 0 ∧ l = L0 }
asegura { res = head(L0 ) }
}

c) proc tomarPrimero(inout l : seq⟨Z⟩) : Z {

requiere { |l| > 0 }
asegura { res = head(L0 ) ∧ |l| = |L0 | − 1 }
}

d) proc tomarPrimero(inout l : seq⟨Z⟩) : Z {

requiere { |l| > 0 ∧ l = L0 }
asegura { res = head(L0 ) ∧ l = tail(L0 ) }
}

Ejercicio 17. Dada una secuencia de enteros, se requiere multiplicar por 2 aquéllos valores que se encuentran en posiciones
pares. Indicar por qué son incorrectas las siguientes especificaciones y proponer una alternativa correcta.

a) proc duplicarPares(inout l : seq⟨Z⟩) {

requiere { l = L0 }
asegura {
|l| = |L0 | ∧
(∀i : Z) (0 ≤ i < |l| ∧ i mód 2 = 0 →L l[i] = 2 × L0 [i])
}
}

b) proc duplicarPares(inout l : seq⟨Z⟩) {

requiere { l = L0 }
asegura {
(∀i : Z) (0 ≤ i < |l| ∧ i mód 2 ̸= 0 →L l[i] = L0 [i]) ∧
(∀i : Z) (0 ≤ i < |l| ∧ i mód 2 = 0 →L l[i] = 2 × L0 [i])
}
}

c) proc duplicarPares(inout l : seq⟨Z⟩) : seq⟨Z⟩ {

asegura {
|l| = |res| ∧
(∀i : Z) (0 ≤ i < |l| ∧ i mód 2 ̸= 0 →L res[i] = l[i]) ∧
(∀i : Z) (0 ≤ i < |l| ∧ i mód 2 = 0 →L res[i] = 2 × l[i])

5
 }
}

Ejercicio 18. Especificar los siguientes problemas de modificación de secuencias:

a) proc reemplazarParesPorSiguiente(inout l : seq⟨Z⟩) que reemplaza los elementos pares de la secuencia por el siguiente.
Por ejemplo dada la secuencia ⟨2, 7, 4⟩ deberı́a devolver ⟨3, 7, 5⟩
b) proc primosHermanos(inout l : seq⟨Z⟩), que dada una secuencia de enteros mayores a dos, reemplaza dichos valores por
el número primo menor más cercano. Por ejemplo, si l = ⟨6, 5, 9, 14⟩, luego de aplicar primosHermanos(l), l = ⟨5, 3, 7, 13⟩
c) proc reemplazar(inout l : seq⟨char⟩, in a, b : char), que reemplaza todas las apariciones de a en l por b
d) proc limpiarDuplicados(inout l : seq⟨char⟩) : seq⟨char⟩, que elimina los elementos duplicados de l dejando sólo su
primera aparición (en el orden original). Devuelve además una secuencia con todas las apariciones eliminadas (en cualquier
orden)

2.5. Especificación sobre conjuntos y diccionarios

Ejercicio 19. Dado un conjunto de enteros, se espera que el siguiente predicado sea Verdadero cuando todos sus elementos
son mayores a 0. Indicar por qué son incorrectas las siguientes especificaciones y proponer una valida.

a) pred sonTodosPositivos(c : Conjunto⟨Z⟩) { (∀i : Z) (0 ≤ i < |c| → c[i] > 0) }

b) pred sonTodosPositivos(c : Conjunto⟨Z⟩) { (∀e : Z) (e ∈ c ↔ e > 0) }
c) pred sonTodosPositivos(c : Conjunto⟨Z⟩) { res = T rue ↔ (∀e : Z) (e ∈ c → e > 0) }

Ejercicio 20. Especificar los siguientes procedimientos:

a) proc sacarImpares(inout c : Conjunto⟨Z⟩) Que saca los elementos impares del conjunto c
b) proc devolverAlgunoMenor(inout c : Conjunto⟨Z⟩, in e : Z) : Z Que devuelve un entero perteneciente a c que sea menor
que e. En caso de no existir, se agrega el elemento (e-1) al conjunto c y se devuelve dicho elemento.
Por ejemplo, devolverAlgunoMenor({4, 3, 10}, 5) puede devolver tanto el 3 como 4 y deja al conjunto como esta. Por otro
lado, que devolverAlgunoMenor({4, 3, 10}, 2) cambia el conjunto a {4, 3, 1, 10} y devuelve 1.

Ejercicio 21. Dado un diccionario, se espera que el siguiente predicado sea Verdadero cuando no hay valores iguales para
distintas claves. Indicar por qué son incorrectas las siguientes especificaciones y proponer una valida.

a) pred noHayValoresRepetidos(d : Diccionario⟨K, V ⟩) { (∀c1 : K) (c1 ∈ d ∧L (∀c2 : K) (d[c1 ] ̸= d[c2 ])) }

b) pred noHayValoresRepetidos(d : Diccionario⟨K, V ⟩) { (∀c1 : K) (c1 ∈ d →L (∀c2 : K) (c2 ∈ d →L c1 ̸= c2 )) }
c) pred noHayValoresRepetidos(d : Diccionario⟨K, V ⟩) { (∀c1 : K) (c1 ∈ d →L (∀c2 : K) (c2 ∈ d →L d[c1 ] ̸= d[c2 ])) }

Ejercicio 22. Dado el siguiente procedimiento:

proc valorMasGrande(d : Diccionario⟨Z, Z⟩) : Z

a) Especificarlo, considerando que recibe un diccionario con tanto claves como valores números positivos, y da como resultado
el valor más grande asociado a alguna clave del diccionario.
b) ¿La solución propuesta permite que la entrada sea un diccionario vacı́o? Modifiquela para que, en dicho caso, devuelva
-1.

Ejercicio 23. En nuestro lenguaje de especificación contamos con dos funciones útiles llamadas setKey y delKey, las cuales
funcionan como detalla el apunte. Suponer que no existen dichas funciones y especificar los siguientes procedimientos:
a) proc eliminarClave(inout d : Diccionario⟨K, V ⟩, in c : K) Que hace d = delKey(D0 , c)
b) proc agregarOModificarSiExiste(inout d : Diccionario⟨K, V ⟩, in c : K, in e : V ) Que hace d = setKey(D0 , c, e)

6
Ejercicio 24. Dado el siguiente procedimiento:

proc modificarMayores(inout d : Diccionario⟨Z, Z⟩, in umbral : Z, in v : Z)

a) Especificarlo, considerando que cambia el valor de todas las claves de d que superen el umbral por el valor v, dejando las
otras como estan.
Por ejemplo,
Umbral = 10, v = 100
D0 = {3 → 2, 6 → 12, 20 → 0, 9 → 1, 32 → 5, 10 → −2}
d = {3 → 2, 6 → 12, 20 → 100, 9 → 1, 32 → 100, 10 → −2}
b) Para este problema es incorrecto utilizar setKey. Explique por qué y corrija su especificación en caso de haberlo usado.
c) ¿Qué habrı́a que agregar para que, a parte de modificar d, devuelva el conjunto de todas las claves cuyos valores fueron
modificados? Es decir, {20, 32} en el ejemplo dado.

2.6. Ejercicios de parciales anteriores

Ejercicio 25. Especificar los siguientes problemas. En todos los casos es recomendable ayudarse escribiendo predicados y
funciones auxiliares.

a) Se desea especificar el problema reemplazarNúmerosPerfectos, que dada una secuencia de enteros devuelve la secuencia
pero con los valores que se corresponden con números perfectos reemplazados por el ı́ndice donde se encuentran. Se llama
números perfectos a aquellos naturales mayores a cero que son iguales a la suma de sus divisores positivos propios (divi-
sores incluyendo al 1 y sin incluir al propio número). Por ejemplo, reemplazarN úmerosP erf ectos([0, 3, 9, 6, 4, 28, 7]) =
[0, 3, 9, 3, 4, 5, 7], donde los únicos números reemplazados son el 6 y el 28 porque son los únicos números perfectos de la
secuencia.
b) Se desea especificar el problema ordenarYBuscarMayor que dada una secuencia s de enteros (que puede tener repetidos)
ordena dicha secuencia en orden creciente de valor absoluto y devuelve el valor del máximo elemento. Por ejemplo,

ordenarY BuscarM ayor([1, 4, 3, 5, 6, 2, 7]) = [1, 2, 3, 4, 5, 6, 7], 7

ordenarY BuscarM ayor([1, −2, 2, 5, 1, 4, −2, −10]) = [1, 1, −2, −2, 2, 4, 5, −10], 5
ordenarY BuscarM ayor([−10, −3, −7, −9]) = [−3, −7, −9, −10], −3

c) Se desea especificar el problema primosEnCero que dada una secuencia s de enteros devuelve la secuencia pero con los
valores que se encuentran en posiciones correspondientes a un número primo reemplazados por 0. Por ejemplo,

primosEnCero([0, 1, 2, 3, 4, 5, 6]) = [0, 1, 0, 0, 4, 0, 6]

primosEnCero([5, 7, −2, 13, −9, 1]) = [5, 7, 0, 0, −9, 0]

d) Se desea especificar el problema positivosAumentados que dada una secuencia s de enteros devuelve la secuencia pero con
los valores positivos reemplazados por su valor multiplicado por la posición en que se encuentra.

positivosAumentados([0, 1, 2, 3, 4, 5]) = [0, 1, 4, 9, 16, 25]

positivosAumentados([−2, −1, 5, 3, 0, −4, 7]) = [−2, −1, 10, 9, 0, −4, 42]

e) Se desea especificar el problema procesarPrefijos que dada una secuencia s de palabras y una palabra p, remueve todas
las palabras de s que no tengan como prefijo a p y además retorna la longitud de la palabra más larga que tiene de
prefijo a p. Por ejemplo, dados: s = ["casa", "calamar", "banco", "recuperatorio", "aprobar", "cansado"] y p
= "ca" un posible valor para la secuencia s luego de aplicar procesarPrefijos(s, p) puede ser ["casa", "calamar",
"cansado"] y el valor devuelto será 7.