(Segundo parcial)(2013)(-Ejercicio 1 parte 1)

(Segundo parcial)(2013)(-Ejercicio 1 parte 1)

de Nicolas Gerardo Perez Alano -
Número de respuestas: 3

Yo pense este ejercicio de otra forma a como fue resuelto. Considero que no esta mal ya que algunos aspectos que en los procedimientos tiene en cuenta, yo con Pre-condiciones me adelanto para que esos casos no se den. Y con los otros procedimientos se solucione estos aspectos antes de invocar estos con pre-condiciones. 

 PROCEDURE insertar (d:Dominio; r:Rango; VAR t:TablaInyectiva); (* Inserta la correspondencia d:r creando una nueva entrada en la tabla t o actualizando la correspondiente al elemento d, si existiera (para mantener la funcionalidad). Además, si hay una correspondencia d':r en t, la borra para mantener la propiedad de inyectividad *)

 PROCEDURE borrar (d:Dominio; VAR t:TablaInyectiva); (* Si estaDefinida(d,t) borra la correspondencia correspondiente a d en la tabla t; en caso contrario la operación no tiene efecto sobre t *)

 Solución mia:

 (*PRE: NOT estaDefinida(d,t)*)

(*PRE: no hay una correspondencia d':r en t *)

PROCEDURE insertar (d:Dominio; r:Rango; VAR t:TablaInyectiva);

(* Inserta la correspondencia d:r creando una nueva entrada en la tabla t *)

 

(* PRE: estaDefinida(d,t) *)

PROCEDURE borrar (d:Dominio; VAR t:TablaInyectiva);

(* Borra la correspondencia correspondiente a d en la tabla t *)

 

La pregunta en si es ¿Se toma como valida mi resolucion? muchas gracias

 

En respuesta a Nicolas Gerardo Perez Alano

Re: (Segundo parcial)(2013)(-Ejercicio 1 parte 1)

de Lorena Etcheverry -

Hola Nicolás

tengo idea de que ya contesté un mensaje similar a este, pero no logro encontrarlo.

Tu solución tiene un problema y es que como precondición de Insertar solicitás que no haya una correspondencia d':r en t.

¿Cómo implementarías este chequeo?

Si el único predicado que tenés disponible es estaDefinida esto implicaría que se satisfaga la siguiente condición, la cual no se puede controlar si el dominio D es no acotado.

\forall d' \epsilon D \neg estaDefinida(d',r)

Tu solución es válida pero tiene una desventaja, y es que en ambas operaciones es necesario chequear la precondición antes de la invocación, y por lo tanto la solución es menos eficiente en tiempo de ejecución que las vistas en clase, aunque es del mismo orden.

Por ejemplo, el peor caso para insertar (suponiendo una implementación como lista encadenada ordenada) se da cuando el elemento a insertar debería ser el último de la lista y no está. En ese caso se recorre toda la lista una vez al llamar a estaDefinida y luego se va a recorrer otra vez más dentro de insertar para encontrar la posición donde debe insertarse.  Esto hace que el tiempo del peor caso se 2*n, siendo n la cantidad de parejas en la tabla. La solución vista en clase recorre la lista una sola vez, por lo tanto su tiempo de ejecución es n. Ambas soluciones son O(n).

slds

Lorena