Introducción a las Estructuras de Datos (Parte 3)

CHenry [chenry@lab.matcom.uh.cu]

Algunas reflexiones a la hora de concebir los axiomas necesarios para definir un TDA.

El estado de un cierto objeto queda establecido por las variables que lo definen. Ellas deben estar encapsuladas en el objeto y nunca deberá ser pública la posibilidad de cambiar el estado de las mismas, lo cual debe siempre hacerse a través de métodos y/o propiedades. Por tanto, un cambio en el estado del objeto, generalmente puede alcanzarse alterando el valor de alguna(s) de sus variables, lo cual solo puede hacerse mediante la aplicación de algún operador. En consecuencia, tras aplicar dicho operador siempre se deberá verificar el cumplimiento de determinadas condiciones que definen a qué estado debe pasar ese objeto tras aplicar dicho operador. Esto queda reflejado mediante uno o más axiomas, por tanto, cada vez que la aplicación de un operador implique un cambio de estado en el objeto, se hace necesario establecer un axioma para los fines antes expuestos. No siempre el estado de un objeto depende estrictamente de sus variables, puede depender también del estado de otro objeto al que el hace referencia. El conjunto de axiomas que verifica la integridad del estado de un objeto, esta formado por los axiomas particulares inherentes a su TDA, más los definidos en el TDA del objeto referenciado, o sea, que a lo mejor hay axiomas que no estoy poniendo en la definición del TDA en cuestión porque ya están recogidos en la definición del TDA al cual se hace referencia.

Ejemplo 8:
En el TDA Colección, tras la devolución de un enumerador por un determinado operador (por ejemplo, el operador GetEnumerator que está presente en todas las colecciones por ser todas enumerables) no es necesaria la existencia de un axioma que verifique que el enumerador recorrió toda la colección, ya que esto es algo inherente a la axiomática del TDA donde se definió el enumerador. En este caso es necesario que no hayan cambios en el estado de la colección, o sea que el operador no haga que la colección cambie de estado, podemos decir que tras la aplicación del mismo, la colección va del estado actual a ese propio estado, lo cual queda garantizado por los axiomas del enumerador y de la propia colección, quien debe garantizar que todo lo que devuelva el enumerador esta dentro de la colección.

Ejemplo 9:
¿Qué sentido tiene definir un botón si no está metido en una ventana? El TDA botón es dependiente de la existencia del TDA ventana.

Ejemplo 10:
Las herramientas gráficas están condicionadas por la existencia de una superficie gráfica, dígase control gráfico, impresora, etc.

Tipos de Datos Abstractos y Programación Orientada a Objetos.

Computacionalmente en el modelo orientado a objetos se trabaja con clases, y estas no son más que tipos de datos abstractos con una implementación parcial o total de sus especificaciones. Toda clase que se programe tiene que tener al menos todas las operaciones del TDA que la describe. Cada operación del TDA tiene que estar reflejada en la clase a través de métodos y atributos. Los axiomas y las precondiciones tienen que seguirse cumpliendo por tanto deben quedar reflejadas en la implementación de los métodos. Según Bertrand Meyer, una clase es una implementación total o parcial de un Tipo de Dato Abstracto.

Lista

Una Lista es un contenedor de objetos que pueden ser insertados, eliminados y accedidos de manera flexible y no estricta como las pilas y las colas. Matemáticamente una lista es una secuencia de objetos de un tipo específico que puede ser representada de la forma:
a1, a2, ..., an

Donde n >= 0 es la longitud de la lista (cantidad de elementos). Los elementos se encuentran ordenados según su posición en la lista. La posición del elemento ai es i.
Las operaciones definidas para una Lista son las siguientes:
• insert: inserta un elemento en una posición dada.
• remove: remueve el elemento que está en una posición dada.
• item: devuelve el elemento que está en una posición dada.
• total: devuelve la cantidad de elementos de la lista.
• locate: devuelve la posición de un elemento en la lista. De no estar el elemento devuelve el total de la lista incrementado en 1.

Su definición axiomática es:
Lista

Tipo LIST[G] // lista de elementos genericos.
Funciones
    insert: LIST[G] x INTEGER x G -> LIST[G]
    remove: LIST[G] x INTEGER -> LIST[G]
    item: LIST[G] x INTEGER -> G
    new: LIST[G]
    total: LIST[G] => INTEGER
    locate: LIST[G] x G => INTEGER
Axiomas:
    total(new) = 0: al construir la lista, está vacía.
    total(insert(L, i, x)) = total(L) + 1: al insertar un elemento, el total de elementos aumenta en 1.
    remove(insert(L, i, x), i) = L: si se inserta un elemento y a continuación se elimina, la lista queda como antes.
    insert(insert(L, i, x), j+1, y) = insert(insert(L, j, y), i, x): si i <= j el orden de los elementos en la lista no está determinado por el orden en que se realizaron las inserciones, sino por las posiciones donde se hicieron.
    item(insert(L, i, x), i) = x: si se inserta un elemento en la posición i-ésima de la lista y a continuación se pregunta por el elemento de esa misma posición, tiene que ser el que se insertó.
    item(L, j) = item(remove(L, i), j) si j < i al quitar un elemento en la posición i no se afecta la posición de los elementos en las posiciones de la 1 a la i-1, en caso de existir (j>1).
    item(L, j) = item(remove(L, i), j -1): si j > i al quitar un elemento en la posición i disminuye en 1 la posición de los elementos en las posiciones i+1 en adelante.
    locate(L, x) = min i {item(L, i) = x or i = total(L) + 1}: devuelve la primera posición de la lista donde se encuentre el elemento, si no está en la lista, devuelve total +1.

Precondiciones:
insert(L: LIST[G], i: INTEGER, x: G): 1 <= i <= total(L) + 1
remove(L: LIST[G], i: INTEGER): 1 <= i <= total(L)
item(L: LIST[G], i: INTEGER): 1 <= i <= total(L)

Un axioma es redundante cuando desde otro puedo demostrarlo a él. Dos conjuntos de axiomas diferentes son válidos para definir un mismo tipo de dato abstracto, siempre y cuando ambos conjuntos, describan lo mismo.
Las listas, al igual que los TDAs anteriores, pueden ser implementadas con:
• Arreglos.
• Nodos enlazables.

Un axioma es redundante cuando puede ser demostrado a partir de otro. Dos conjuntos de axiomas diferentes son válidos para definir un mismo tipo de dato abstracto, siempre y cuando ambos describan lo mismo.
Como propuesta de estudio individual, se puede mostrar que los axiomas siguientes pueden ser demostrados a partir de los axiomas anteriores.
• item(L, j) = item(insert(L, i, x), j) si j < i al insertar un elemento en la posición i no se afecta la posición de los elementos en las posiciones de la 1 a la i-1, en caso de existir (j>1).
• item(L, j) = item(insert(L, i, x), j+1) si j >= i al insertar un elemento en la posición i aumenta en 1 la posición de los elementos en las posiciones i en adelante.

Artículos relacionados