Final 1C/2013 2 (Algoritmos II)

Plantilla:Back Esteban Feuerstein y Fernando Schapachnik

Copia textual del final.

Para considerarse aprobado deben estar bien al menos 3 ejercicios.

Ejercicio 1

1. El invariante de representación suele escribirse de manera formal y eso permite utilizarlo para una serie de cosas. Si se escribiese en castellano, ¿cuáles de esas cosas se podrían seguir haciendo y cuáles no? Justifique.
2. Si el invariante de un tipo resultase programable, ¿lo haría? ¿para qué lo usaría? Justifique.

Ejercicio 2

El siguiente algoritmo, dado un array A determina si el mismo contiene 3 elementos x, y, z que forman una terna pitagórica (es decir, tales que $x^{2}+y^{2}=z^{2}$)

FIND-PITNUM(a)
1 for i = 1 to length[a] do
2   for j = 1 to length[a] do
3     for k = 1 to length[a] do
4       if a[i]^2 + a[j]^2 = a[k]^2 then
5         return true
6 return false

1. Analice la complejidad del algoritmo anterior.
2. Proponer un algoritmo diferente y analizar su complejidad, que debe ser estrictamente menor que el algoritmo anterior. Para elaborar su solución puede utilizar la siguiente función:

EXACT-SUM2(A, n, x)
1  i <- n
2  j <- 1
3  while j < i do
4    if A[i]^2 + A[j]^2 = x then
5      return true
6    else
7      if a[i]^2 + a[j]^2 < x then
8        j <- j + 1
9      else
10       i <- i - 1
11 return false

Ejercicio 3

Responda y justifique:

1. Una función recursiva a la cola, ¿siempre puede transformarse en iterativa?
2. ¿Y una función con recursión múltiple?

Ejercicio 4

A continuación se muestran unos breves enunciados junto a fragmentos de su especificación como TADs. Indicar si dichos fragmentos son correctos o presentan errores, y si es así, cuáles y por qué.

1. En un frasco aislado en un laboratorio se cuenta con una cantidad de hielo, que al ser sometido a calor se transforma en agua, a razón de un dm^2 por caloría. Como el frasco está aislado, ésa es la única transformación posible.

TAD frasco
generadores:
    nuevo_frasco: tamaño -> frasco
observadores:
    volumen_hielo: frasco -> nat
    volumen_agua:  frasco -> nat
operaciones:
    aportar_calorías: frasco x nat -> frasco
    disminuir_hielo: frasco x nat -> frasco
    incrementar_agua: frasco x nat -> frasco
Fin TAD

2. Una bolita se desplaza sobre una recta a medida que recibe impulsos. Los impulsos se miden en kilos, y la relación entre ambos es que por cada kilo la bolita avanza dos metros.

[...]
observadores:
    posición: bolita -> nat
operaciones:
    empujar: bolita x nat i x distancia d -> bolita {d = 2i}
[...]

3. Se desea modelar una pila que siempre permite aplicar la operación top(), pero indica cuándo no hay ningún elemento válido.

observadores:
    top: pila -> <elem, bool>

4. Ídem anterior:

    top: pila -> indicador
    hay_elem?: indicador -> bool
    elem: pila x indicador i -> elem {hay_elem?(i)}

Ejercicio 5

Supongamos que extendemos el TAD Diccionario agregándole una operación RestricciónDeRango(x,y) con x <= y, que elimina del diccionario todos los valores que son mayores que y o menores que x. Por ejemplo, si las claves son reales, luego de una operación RestriccionDeRango(x, y) el diccionario contendría solamente las claves en el intervalo cerrado [x, y]. Proponga una estructura de datos para implementar eficientemente tanto las operaciones tradicionales de diccionario como la nueva operación, considerando los siguientes casos:

1. Se puede asumir que x e y están en el diccionario.
2. No se puede asumir que x e y están en el diccionario.