1.1 Concepto y terminología1.1 Concepto y terminología

Tipos de Tipos de DDatos atos colección de valores + operaciones colección de valores + operaciones Enteros, reales, booleanos, caracteresEnteros, reales, booleanos, caracteres Enumerados, subrangoEnumerados, subrango Son opacosSon opacos

Tipos EstructuradosTipos Estructurados genericidad genericidad Riesgo de crear valores sin semánticaRiesgo de crear valores sin semántica

Tipos de Datos Abstractos (TDA)Tipos de Datos Abstractos (TDA) Tipos de datos creados por el programador, que deben ser Tipos de datos creados por el programador, que deben ser

opacosopacos

1.1 Concepto y terminología1.1 Concepto y terminología

Tipos de Tipos de DDatos atos AAbstractos:bstractos: Colección de valores + operacionesColección de valores + operaciones Se definen mediante una especificación, que es Se definen mediante una especificación, que es

independiente de cualquier representación (abstracción)independiente de cualquier representación (abstracción) Acceso a los valores limitado al uso de las operaciones Acceso a los valores limitado al uso de las operaciones

(interfaz con el usuario limitada)(interfaz con el usuario limitada) Establecida la interfaz, el programador elige la Establecida la interfaz, el programador elige la

representación adecuada (implementación)representación adecuada (implementación) Los usuarios del TDA sólo conocen su nombre y la Los usuarios del TDA sólo conocen su nombre y la

especificación de las operacionesespecificación de las operaciones Cambios en la representación no afectarán al resto de Cambios en la representación no afectarán al resto de

programasprogramas

1.1 Concepto y terminología1.1 Concepto y terminología

Tipos de Tipos de DDatos atos AAbstractos:bstractos: El lenguaje de programación trata a los TDA’s de igual El lenguaje de programación trata a los TDA’s de igual

forma que a sus propios tipos de datos, es decir, como forma que a sus propios tipos de datos, es decir, como tipos opacos:tipos opacos: Privacidad de la representaciónPrivacidad de la representación ProtecciónProtección

Para que esto sea posible, la implementación deberá Para que esto sea posible, la implementación deberá realizarse en un ámbito de declaración inaccesible al realizarse en un ámbito de declaración inaccesible al resto de los programasresto de los programas

1.1 Concepto y terminología1.1 Concepto y terminología

Tipos de Tipos de DDatos atos AAbstractos:bstractos: El conjunto de operaciones ha de permitir generar cualquier El conjunto de operaciones ha de permitir generar cualquier

valor del tipovalor del tipo Existen dos piezas de documentación bien diferenciadas:Existen dos piezas de documentación bien diferenciadas:

Especificación del TDAEspecificación del TDA. Es lo . Es lo únicoúnico que conoce el usuario que conoce el usuario del TDA. Consiste en el nombre del TDA y la especificación de del TDA. Consiste en el nombre del TDA y la especificación de las operaciones. Tienen parte sintáctica y parte semánticalas operaciones. Tienen parte sintáctica y parte semántica

Implementación del TDAImplementación del TDA. Conocida sólo por el programador . Conocida sólo por el programador del TDA. Se realiza en un lenguaje de programación concreto. del TDA. Se realiza en un lenguaje de programación concreto. Consiste en la representación del tipo y en la realización de Consiste en la representación del tipo y en la realización de las operacioneslas operaciones

1.1 Concepto y terminología1.1 Concepto y terminología

Tipos de datos abstractos:Tipos de datos abstractos: Se destacan los detalles (normalmente pocos) del Se destacan los detalles (normalmente pocos) del

comportamiento observable del tipocomportamiento observable del tipo, que, que es estable es estable.. Se ocultan los detalles (normalmente numerosos) de la Se ocultan los detalles (normalmente numerosos) de la

implementaciónimplementación, que es , que es propensa a cambiospropensa a cambios..

1.2 Clasificación de Tipos de Datos Abstractos1.2 Clasificación de Tipos de Datos Abstractos

Tipos de Tipos de DDatos atos AAbstractos simples:bstractos simples: Cambian su valor pero no su estructura Cambian su valor pero no su estructura espacio de espacio de

almacenamiento constantealmacenamiento constante Enteros, reales, booleanos, carácter, enumerado, Enteros, reales, booleanos, carácter, enumerado,

subrango, etc.subrango, etc.

Tipos de Tipos de DDatos atos AAbstractos contenedores:bstractos contenedores: Cambian su valor y estructura (colecciones de elementos Cambian su valor y estructura (colecciones de elementos

de número variable) de número variable) espacio de almacenamiento variable espacio de almacenamiento variable Listas, colas, pilas, árboles, grafos, conjuntos, etc.Listas, colas, pilas, árboles, grafos, conjuntos, etc.

1.2 Clasificación de Tipos de Datos Abstractos1.2 Clasificación de Tipos de Datos Abstractos

Tipos de datos abstractos inmutables:Tipos de datos abstractos inmutables: Sus casos no pueden modificarse (se crean y destruyen, Sus casos no pueden modificarse (se crean y destruyen,

pero no existen operaciones de modificación)pero no existen operaciones de modificación) Representación inmutable o mutableRepresentación inmutable o mutable

Tipos de datos abstractos mutableTipos de datos abstractos mutabless:: Sus casos pueden modificarse (existen operaciones de Sus casos pueden modificarse (existen operaciones de

modificación)modificación) Representación mutableRepresentación mutable

1.3 Especificación de Tipos de Datos Abstractos1.3 Especificación de Tipos de Datos Abstractos

ImplementaciónImplementacióndel TDAdel TDA

RepresentaciónRepresentaciónelegidaelegida

RepresentaciónRepresentaciónde las operacionesde las operaciones ++

EspecificaciónEspecificaciónUsuarioUsuario ImplementadorImplementador

TDA TDA Colección de valores + Operaciones Colección de valores + Operaciones

1.3 Especificación de Tipos de Datos Abstractos1.3 Especificación de Tipos de Datos Abstractos

Especificaciones informales:Especificaciones informales: Predomina el lenguaje natural Predomina el lenguaje natural Poco precisas y breves Poco precisas y breves ambigüedad ambigüedad Sencillas de escribir, leer y entenderSencillas de escribir, leer y entender

Especificaciones formales:Especificaciones formales: Lenguaje alLenguaje alggeebbraico raico verificación formal de programas verificación formal de programas Precisas y brevesPrecisas y breves Pueden resultar más complejas de escribir, leer y entenderPueden resultar más complejas de escribir, leer y entender

1.3.1 Especificaciones informales1.3.1 Especificaciones informales

CabeceraCabecera: Aparece el nombre de las operaciones.: Aparece el nombre de las operaciones. DescripciónDescripción: Se describe de forma general en qué consiste la : Se describe de forma general en qué consiste la

abstracción, sin decir nada acerca de la implementación. Los casos abstracción, sin decir nada acerca de la implementación. Los casos del TDA pueden describirse en términos de otros tipos para los cuales del TDA pueden describirse en términos de otros tipos para los cuales se espera que el lector de la especificación esté más familiarizado. Se se espera que el lector de la especificación esté más familiarizado. Se pueden utilizar gráficos y abstracciones matemáticas. Se puede incluir pueden utilizar gráficos y abstracciones matemáticas. Se puede incluir en la descripción si el TDA es mutable o inmutableen la descripción si el TDA es mutable o inmutable

Especificación de las operacionesEspecificación de las operaciones: Para la especificación de una : Para la especificación de una abstracción operacional seguiremos el siguiente modelo:abstracción operacional seguiremos el siguiente modelo:

nombre de la operación (entrada) devuelve (salida)nombre de la operación (entrada) devuelve (salida) requerimientos: Esta cláusula muestra las restricciones de usorequerimientos: Esta cláusula muestra las restricciones de uso

modifica: Esta cláusula identifica las entradas que van a ser modificadasmodifica: Esta cláusula identifica las entradas que van a ser modificadas

efecto: Esta cláusula define el comportamientoefecto: Esta cláusula define el comportamiento

1.3.1 Especificaciones informales1.3.1 Especificaciones informales

Observamos los siguientes componentes:Observamos los siguientes componentes: CabeceraCabecera: Es la información sintáctica. Se indica el nombre de la operación y el : Es la información sintáctica. Se indica el nombre de la operación y el

número, orden y tipos de sus entradas y salidas. Deben darse nombres para las número, orden y tipos de sus entradas y salidas. Deben darse nombres para las entradas y pueden darse para las salidasentradas y pueden darse para las salidas

CuerpoCuerpo: Es la información semántica. Consta de las siguientes cláusulas:: Es la información semántica. Consta de las siguientes cláusulas: RequerimientosRequerimientos: Restringen el dominio del procedimiento o función. Cuando introducimos : Restringen el dominio del procedimiento o función. Cuando introducimos

requerimientos, obtenemos una abstracción operacional parcial (en caso contario se dice requerimientos, obtenemos una abstracción operacional parcial (en caso contario se dice que la abstracción es total). El que use la abstracción es el responsable de que los que la abstracción es total). El que use la abstracción es el responsable de que los requerimientos se cumplan; si estos no se cumplen, los resultados pueden ser requerimientos se cumplan; si estos no se cumplen, los resultados pueden ser impredecibles. Si la abstracción es total, la cláusula de requerimientos puede omitirse. Se impredecibles. Si la abstracción es total, la cláusula de requerimientos puede omitirse. Se supone como requerimiento implícito (y por tanto no tiene que ser explicitado en la cláusula supone como requerimiento implícito (y por tanto no tiene que ser explicitado en la cláusula de requerimientos) que las entradas que figuran en la lista de parámetros de la abstracción de requerimientos) que las entradas que figuran en la lista de parámetros de la abstracción han sido correctamente construidas mediante algún constructor del tipohan sido correctamente construidas mediante algún constructor del tipo

ModificaModifica: Indica los argumentos de entrada que cambian de valor tras una llamada a la : Indica los argumentos de entrada que cambian de valor tras una llamada a la abstracción operacionalabstracción operacional

EfectoEfecto: Se indica el efecto que se produce al ejecutar la operación para las entradas que : Se indica el efecto que se produce al ejecutar la operación para las entradas que cumplen los requerimientos. Debe definir qué salidas son producidas y también qué cumplen los requerimientos. Debe definir qué salidas son producidas y también qué modificaciones son hechas en la lista de entradas de la cláusula modifica. La cláusula modificaciones son hechas en la lista de entradas de la cláusula modifica. La cláusula efecto se escribe bajo la asumpción de que se satisface la cláusula requerimientos, y no se efecto se escribe bajo la asumpción de que se satisface la cláusula requerimientos, y no se dice nada sobre el efecto de la abstracción cuando dicha cláusula no se satisfacedice nada sobre el efecto de la abstracción cuando dicha cláusula no se satisface

1.3 Especificación de Tipos de Datos Abstractos1.3 Especificación de Tipos de Datos Abstractos

El usuario de la abstracción es el responsable de El usuario de la abstracción es el responsable de que se cumplan los requerimientosque se cumplan los requerimientos

Implementaciones robustas: se autoprotegen frente Implementaciones robustas: se autoprotegen frente a valores inconsistentesa valores inconsistentes

Mecanismos de protección frente a errores:Mecanismos de protección frente a errores: Manejo de excepcionesManejo de excepciones Parámetros de salida de error en cada operaciónParámetros de salida de error en cada operación

Puesto que las especificaciones son independientes Puesto que las especificaciones son independientes de las implementaciones, existen requerimientos de de las implementaciones, existen requerimientos de uso (información adicional de cara al usuario)uso (información adicional de cara al usuario)