Pda- tipos estructurados de datos

PDAFundamentos de Programación

Estructura de Datos

Fundamentos de Programación

1

Fundamentos de Programación

2.6 Tipos estructurados

Hasta ahora los ejemplos que hemos presentado han tenido por ob-jetivo mostrar el procedimiento para derivar programas, a partir de su especificación. Pero los datos sobre los cuales se ha trabajado han sido de tipos básicos: bool, nat, enteros(excepto los reales). Pero en el desarrollo de software comercial los tipos de datos básicos no son suficientes, por ello es necesario ampliar nuestro repertorio de ti-pos. Por ejemplo, un tipo de dato usado en los ejemplos, pero de manera restringida, han sido los vectores. Hemos sido cuidadosos de no hacer asignación alguna sobre elementos de vector, la pregunta es ¿cuál es el inconveniente quesurge? Responderemos dicha pregun-ta con un ejemplo muy sencillo, dada la siguiente especificación, deseamos hallar su pmd:
Profesor: Alejandro Bello R.
Fundamentos de Programación

2

Fundamentos de Programación

{¿pmd?} a(a(2)):= 1
{a(a(2)) = 1}

Por definición: pmd(“a(a(2)):= 1”, a(a(2)) = 1) = (1 = 1) = T luego {T} a(a(2)):= 1
{a(a(2)) = 1}

Profesor: Alejandro Bello R.Fundamentos de Programación

3

Fundamentos de Programación

Dándole una interpretación a lo obtenido, esto significa que no hay condición alguna que se debe imponer a cualquier arreglo de ente-ros, siempre que se haga la asignación a(a(2)):= 1, la postcondición siempre se cumplirá. Dicho de otro modo, no importa cómo es el arreglo de enteros, después de la asignación la postcondición siem-preserá cierta. Esto no es así, lo demostraremos con un contra ejem-plo:si inicialmente a(2) = 2, la asignación se produce sobre la según-da componente pero la postcondición pregunta sobre la primera, que puede tener cualquier valor, por lo que concluimos que el pmd halla-do es incorrecto. ¿Qué podemos decir? Nuestra definición de ins-trucción de asignación es incorrecta o incompleta. No es así, estáclaro que estos nuevos tipos de datos deben formalizarse de manera que toda la teoría axiomática que hemos presentado para los tipos de datos básicos, también funcione para estos tipos estructu-rados.
Profesor: Alejandro Bello R.
Fundamentos de Programación

4

Fundamentos de Programación

A mediados de la década del 70 se introdujo el concepto de tipo abstracto de dato, que define no sóloel conjunto de valores que confor-man el tipo de dato, sino también las operaciones que se pueden a-plicar sobre él, cuyas propiedades expresadas en ecuaciones determi-naran inequívocamente su comportamiento. Intuitivamente nos guiaremos del método de razonamiento empleado para los tipos de datos básicos. En ellos se pueden destacar los siguientes puntos:
–Contiene un conjunto de operacionesaplicables al tipo de dato en cuestión. –Las operaciones poseen un conjunto de propiedades algebraicas que nos permite calcular el resultado de una operación.

Profesor: Alejandro Bello R.

Fundamentos de Programación

5

Fundamentos de Programación

–El nivel de abstracción es tal, que permite tratar los elementos del tipo, sus operaciones y sus propiedades independientemente de cómo estánimplementados. Por ejemplo en Pascal dentro de los números enteros siempre se tiene que 2 + 2 = 4, independien-temente de sí se ha implementado internamente en la memoria de la computadora usado binario, modulo2, complemento a uno, etc. La respuesta esperada siempre será la misma.

Estas mismas características exigiremos de los nuevos tipos de datos y para cubrir estos puntos procederemos de lasiguiente manera. Ante un tipo nuevo lo primero que haremos es darle un nombre junto con los tipos auxiliares que necesite, a continuación daremos nombre a las operaciones que se vayan considerando necesarias, y por últimos describiremos las propiedades que estas cumplen

Profesor: Alejandro Bello R.

Fundamentos de Programación

6

Fundamentos de Programación

Para hacer esto,...