2.1 Los
tipos de datos abstractos.
Uno de los
puntos más cruciales asociados con el diseño de un nuevo sistema involucra la
gestión de la complejidad del proceso de diseño.
Habitualmente
los buenos diseñadores emplean alguna forma de abstracción como herramienta
para tratar esta complejidad.
¿Abstracción?
Capacidad
intelectual de considerar una entidad aislándola de cualquier ejemplar
específico de esa entidad. Ejemplo: los diseñadores de hardware que pretenden
diseñar una computadora, se preocupan de la funcionalidad de los circuitos
integrados que piensan usar, no del funcionamiento de los transistores que se
encuentran en esos circuitos integrados.
El
desarrollo de un sistema informático también se ve simplificado en gran medida
mediante el uso de abstracciones en el proceso de diseño.
¿Abstracción en un sistema informático?
Supone
especificar la funcionalidad de un sistema informático en términos generales de
alto nivel.
Una vez que
puede ser demostrado que esta especificación abstracta del sistema es correcta
es posible añadir más detalles, para finalmente conducir a una descripción
detallada de ¨bajo nivel¨ del sistema informático en términos que son
directamente implementados usando la sintaxis de un lenguaje de programación
dado. En cada paso de este proceso el diseñador debe verificar que el detalle
adicional añadido al diseño del sistema es correcto. La ventaja de este enfoque
está en que limita la complejidad con la que se debe tratar en cualquier paso
del proceso de diseño. Esto permite al diseñador concentrarse en el conjunto
del diseño del sistema sin tener que enfrascarse en detalles de implementación.
Mientras
avanza el proceso de diseño los distintos tipos de datos necesarios, así como
las operaciones que deben ser ejecutados con estos datos se van revelando.
En este
momento puede ser utilizado un tipo especial de abstracción conocido como abstracción
de datos. Esto implica una descripción abstracta o lógica, tanto de los
datos requeridos por el sistema informático como de las operaciones que pueden
ser ejecutadas con esos datos.
El uso de la
abstracción de datos durante el desarrollo del software permite al diseñador
concentrase en cómo son usados los datos en el sistema para resolver el
problema que le ocupa, sin tener que preocuparse de cómo los datos son
representados y tratados en la memoria del computador.
Las clases
representan abstracciones de entidades que son utilizadas en la solución de problemas
concretos. A ellas se llega mediante el proceso de abstracción del problema a
resolver, identificando atributos y responsabilidades mediante los métodos de
análisis y diseño orientado a objetos que deben ser conocidos.
Cuando se presentó el modelo de programación orientada a objetos se
habló de clases, objetos, encapsulamiento, y generalización, es necesario que
recuerdes todo ello pues son conceptos que seguiremos utilizando a lo largo de
este semestre, para ello puedes utilizar el libro “Thinking in C++” de Bruce Eckel, lee los capítulos del 1 al 5, en ellos podrás ampliar tus
conocimientos acerca de la POO y el lenguaje C++. Este libro será utilizado
como bibliografía auxiliar durante este tema.
Al crear
clases que pueden ser instanciadas estamos concretando determinada abstracción
que nos es necesaria para dar solución a determinado problema, esto está
relacionado con el concepto de Tipo de Dato
Abstracto, así como con el de Estructura
de Datos, estos conceptos serán vistos más adelante, primero
el de Tipo de Dato Abstracto y luego el de Estructura de Datos.
Definición 1. Tipo de Dato Abstracto (TAD).
Un tipo de dato abstracto (TAD) es un modelo matemático compuesto por una colección de operaciones definidas sobre un conjunto de datos para el modelo.
Si nos remontamos a las primeras clases del semestre anterior veremos que esto es en cierta forma similar a la definición de clases, de hecho las clases se utilizan para representar a los TADs en los lenguajes de programación orientados a objetos.
Un TAD se
caracteriza por:
1. Exportar un tipo (una clase lo
es)
2. Definir un conjunto de
operaciones para la manipulación (la interfase, el conjunto de métodos tanto
públicos como protegidos que pueden ser utilizados)
3. Utilizar la interfase como único
mecanismo de acceso a la estructura de datos (encapsular, esconder el cómo)
Ejemplos de
tipos de datos abstractos son los números enteros, los números complejos, las
matrices, etc. En la asignatura nos encargaremos de definir las propiedades de
determinados TAD como las listas (y sus variantes), árboles, grafos y otros muy
utilizados en la solución de problemas y con un comportamiento conocido.
Veamos como
se puede definir el TAD entero:
TAD Entero es
Una secuencia de dígitos que opcionalmente
presentan
como prefijo un signo + o -. A esta
secuencia le damos el
nombre de n.
Suma( Entero k )
Crea un nuevo entero resultado de la suma de
n y k.
Resta( Entero k )
Crea un nuevo entero resultado de la resta de n y k.
Multiplicar( Entero k )
Crea un nuevo entero resultado de la multiplicación n y k
Dividir( Entero k )
Crea un nuevo entero resultado de la división
de n y k
Resto( Entero k )
Crea un nuevo entero resultado, el resto la
división de n y k
Obtener(
)
Devuelve a n
Poner( Entero k )
Pone en n el valor de k.
FIN
Figura 1. El TAD Número Entero.
Esta descripción es la especificación para el TAD Entero, note que la
descripción de las operaciones se realizan con palabras, estas operaciones no
están ligadas a ningún lenguaje de programación en particular, hacerlo
significa poner un poco de “azúcar sintáctica” en ellos, en C++ por ejemplo las
operaciones Suma, Resta, Multiplicar y Dividir pueden ser representadas
mediante los operadores +, -, * y / utilizando la redefinición de estos. Definir de esta forma a los TADs nos lleva a libre elección
del lenguaje de programación y nos hace libres también de escoger una
implementación arbitraria para cualquier TAD, en dependencia de las
posibilidades y recursos que el lenguaje escogido nos brinde.
Una clase es
una representación real o concreta de un TAD, por lo tanto puede proporcionar
los detalles de implementación para la estructura de datos y las operaciones
que definimos. En una clase los atributos representan a la estructura de
datos utilizada y los métodos a las operaciones.
El término tipo de datos se refiere a la
implementación del modelo matemático especificado por un TAD. Un tipo de dato es
la representación informática de un TAD.
El término Estructura de Datos se refiere a una
colección de variables en memoria que están relacionadas de alguna forma
específica.
Recordemos
también la existencia de clases abstractas que nos proporcionan la forma de
escribir determinada interfase sin proporcionar la forma en que esta será
implementada en su totalidad. Estas clases abstractas pueden ser utilizadas
para representar también a TADs, aunque el grado de completitud nos impedirá
utilizarlas, recuerde que no se pueden crear instancias de las clases
abstractas.
Otro ejemplo
de TAD es el TAD Conjunto, con las operaciones de intersección, unión,
diferencia y pertenencia al conjunto.
TDA
Conjunto es
Datos
Una colección de elementos
del mismo tipo. La llamaremos A
Operaciones
Constructor
Crea un nuevo conjunto, lo crea vacío.
Conjunto
Unión( Conjunto B )
Crea un nuevo
conjunto. Coloca en el conjunto a los elementos de A y de B, sin repetir
elementos.
Conjunto Intersección( Conjunto B )
Crea un nuevo
conjunto. Coloca en el conjunto a los elementos de A que pertenecen a B.
Lógico Pertenece( Tipo x )
Devuelve verdadero
si x esta en la colección.
...
FIN
Figura 2. El TAD Conjunto.
En la Definición 1
de TAD no se menciona cómo ni dónde son almacenados los datos, ni el tipo a
que estos pertenecen, sólo nos da un modelo para la manipulación que se
llevara a cabo con ellos. Un elemento importante a incluir con las operaciones
son las precondiciones que estas necesitan y las poscondiciones que generan la
ejecución de determinada operación. En una notación más formal de un TAD se
representan mediante axiomas.
Para
describir el comportamiento de un tipo de datos se necesita que las
descripciones no tengan ambigüedades ni sobre-especificaciones, y tengan un
alto nivel de completitud y precisión, como es el caso de los TADs presentados.
Una
implementación del TAD es una traducción a un lenguaje de programación de las
operaciones definidas para él, en el caso que nos ocupa escribimos una clase,
en esta se escoge una estructura de datos para la representación del TAD, por
lo que para un mismo TAD podemos tener varias implementaciones. En este curso
por ejemplo tendremos versiones del TAD Lista utilizando arreglos y listas
enlazadas.
Otro elemento a destacar en la definición de
un TAD es que esta contiene un conjunto de operaciones que es mínimo, pero que
puede no ser el único. Existen operaciones que pueden ser representadas
mediante otras y algunas que no pueden ser descompuestas, que se pueden
considerar “atómicas”.
Podemos
proporcionar una implementación del TAD Conjunto donde almacenemos los
elementos que pertenecen al conjunto en un arreglo, esta implementación utiliza
a una estructura de datos,
esta no es más que una colección de variables sobre la que se han implementado
las operaciones definidas para el TAD y que permite finalmente la
implementación de un tipo de dato (a través de una clase).
La
utilización de una estructura de datos en particular puede generar algunas
operaciones nuevas. Por ejemplo si la implementación del conjunto se realiza
utilizando un arreglo tiene sentido las operaciones Lleno y Vacío, para verificar que se pueden poner más elementos en el conjunto, pues la
cantidad de elementos en este estará determinado por tamaño del arreglo al ser
declarado o creado.
Para saber mas:
No hay comentarios.:
Publicar un comentario