Ver el código de «Final 1C/2013 2 (Algoritmos II)»

{{Back|Algoritmos y Estructuras de Datos II}}
'''Esteban Feuerstein y Fernando Schapachnik'''

Copia textual del final.

Para considerarse aprobado deben estar bien al menos 3 ejercicios.

== Ejercicio 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.
#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 <math>x^2 + y^2 = z^2</math>)

 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

#Analice la complejidad del algoritmo anterior.
#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:
#Una función recursiva a la cola, ¿siempre puede transformarse en iterativa?
#¿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:

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