Cap I, ABSTRACCION DE DATOS.pdf
-
Upload
pamela-vasquez-costales -
Category
Documents
-
view
599 -
download
6
Transcript of Cap I, ABSTRACCION DE DATOS.pdf
FACULTAD DE INGENIERÍA
ESCUELA DE INGENIERÍA EN SISTEMAS Y COMPUTACIÓN
ESTRUCTURA DE DATOS
Pamela Vásquez Costales
ABSTRACCIÓN DE DATOS
Objetivos
O Entender en qué consiste el proceso de abstracción.
O Describir la técnica de la abstracción de datos para el diseño de estructuras de datos.
O Comprender qué es una estructura de datos.
Objetivos
O Entender el diseño de una estructura de datos a través de una especificación lógica.
O Ubicar los niveles de abstracción al programar.
O Identificar los beneficios de utilizar la abstracción de datos como estrategia de trabajo en el desarrollo de software.
¿Qué es una abstracción?
Una abstracción es un proceso mental, mediante el cual se extraen los rasgos esenciales de algo para representarlos
por medio de un lenguaje gráfico o escrito. Puesto que es un proceso
mental, la abstracción es una acción subjetiva y creativa, esto es, depende del contexto psicológico de la persona
que la realiza.
Por ejemplo, se dice que algunas de las pinturas de Picasso son abstractas, no porque sean difíciles de entender, sino
porque a través de ciertos trazos simples, y de acuerdo con su criterio mental, el pintor plasmó los rasgos
esenciales de ese algo real que trataba de representar por medio de un lenguaje
gráfico.
En la vida cotidiana, continuamente se hacen abstracciones, por ejemplo
cuando describimos a una persona:
"Reconocerán al profesor Garay por su enorme nariz, su barba y sus anteojos;
además, es muy alto, y tiene un carácter muy amigable".
Cuando hacemos un mapa para describir cómo se llega al rancho donde
será el día de campo, extraemos los rasgos importantes del camino:
"Al llegar al cruce donde está una piedra gigantesca, das vuelta a la
derecha y verás un árbol lleno de flores rojas; ahí encontrarás la entrada al
rancho".
¿Por qué es importante la abstracción?
Aunque la gente realiza cotidianamente el proceso de abstracción, debe
convertirse en una habilidad para quien estudie una carrera relacionada
con la computación.
La capacidad de modelar una realidad por medio de herramientas computacionales requiere
necesariamente de hacer continuas abstracciones, por lo que es vital
conocer metodologías que desarrollen esta habilidad.
¿Qué es la abstracción de datos?
La abstracción de datos es una técnica o metodología que permite diseñar
estructuras de datos.
Consiste, básicamente, en representar bajo ciertos lineamientos de formato las
características esenciales de una estructura de datos. Este proceso de
diseño se olvida de los detalles específicos de implementación de los
datos, razón por la cual se trata de una abstracción.
¿Qué es una estructura de datos?
Cualquier colección o grupo de datos organizados de tal forma que tengan asociados un conjunto de operaciones para poder manipularlos, se dice que conforma una estructura de datos.
Por ejemplo, cualquier lenguaje de alto nivel provee típicamente de tipos de datos estructurados o estructuras de
datos predefinidas, como los arreglos o los registros. Un arreglo es un conjunto
de datos, todos del mismo tipo, con una organización lineal y con métodos
claros de acceso a través de sus subíndices.
Las operaciones tradicionales sobre los arreglos incluyen la comparación, la
asignación, la escritura, etc.
En un nivel más bajo, podría verse a los números enteros como estructuras de datos: se componen de un grupo de
dígitos y tienen asociadas operaciones como sumar, restar y multiplicar, entre
otras.
¿Qué es un Tipo de Dato Abstracto (TDA)?
La técnica de la abstracción de datos establece que al diseñar una nueva
estructura de datos, ésta pasa a ser un Tipo de Dato Abstracto (TDA), que podrá implementarse en cualquier lenguaje y aplicarse en cualquier
concepto.
Por lo tanto, al usar la metodología de la abstracción de datos se diseñarán TDA, siguiendo los lineamientos para hacer
una especificación lógica o abstracta del mismo TDA.
¿En qué consiste la especificación lógica de un TDA?
La especificación lógica de un TDA es un documento en el que se plasma la abstracción realizada al diseñar una
estructura de datos.
Dicho documento pasará a ser el mapa o plano mediante el cual se construirá (implementará) la estructura de datos y en el que se definirán claramente las
reglas en las que podrá usarse (aplicarse) el TDA.
El documento de la especificación lógica de un TDA consiste de los
siguientes cuatro puntos:
1. Elementos que conformarán la estructura de datos.
En este punto se describe el tipo de los datos individuales que guardará la estructura. Por ejemplo, números
enteros, caracteres, fechas, registros con los datos de un empleado, etc.
2. Tipo de organización en que se guardarán los elementos.
Existen solamente cuatro tipos de organización para los datos en la
estructura, la cual deberá tener alguna de las siguientes organizaciones:
O Lineal: Si hay una relación de uno a uno entre los elementos.
O Jerárquica: Si hay una relación de uno a muchos entre los elementos.
O Red: Si hay una relación de muchos a muchos entre los elementos.
O Sin relación: Si no hay relaciones entre los elementos.
Las relaciones entre los elementos se dan, por ejemplo, cuando existe algún
motivo para que un elemento esté antes o después que otro.
3. Dominio de la estructura.
Este punto es opcional, y en él se describirá la capacidad de la estructura en cuanto al rango posible de datos por
guardar.
4. Descripción de las operaciones de la estructura.
Cada operación relacionada con la estructura debe describirse con los
siguientes puntos:
O Nombre de la operación.
O Descripción breve de su utilidad.
O Datos de entrada a la operación.
O Datos que genera como salida la operación.
O Precondicion: Condición que deberá cumplirse antes de utilizar la operación para que se realice sin problemas.
O Postcondición: Condición en que queda el TDA después de ejecutar la operación.
Definir claramente la especificación lógica del TDA facilita posteriormente la
construcción y aplicación de la estructura de datos.
¿Cuáles son los niveles de abstracción de datos?
Al aplicar la abstracción de datos se pueden definir tres niveles de trabajo:
1. Nivel Lógico o Abstracto
2. Nivel Físico o de Implementación
3. Nivel de Aplicación o de Uso
1. Nivel lógico o abstracto
Correspondería a la especificación lógica del TDA que se describió anteriormente. En este nivel se define abstractamente la estructura de datos y las operaciones relacionadas con ella. La descripción que
se obtenga en este nivel debe ser independiente del lenguaje de
programación en el que se implemento o usará la estructura.
2. Nivel físico o de implementación
En este nivel se decide el lenguaje de programación en que se implementará la
estructura, qué tipos de datos ya definidos servirán para representarla y, finalmente, bajo estas consideraciones, se implementa como un módulo a cada
una de las operaciones del TDA.
Este nivel toma el diseño que se ha realizado a nivel lógico y siguiendo al pie de la letra las especificaciones de cada operación construye la estructura que posteriormente se usará en el nivel
aplicación.
3. En el nivel aplicación o de uso el programador usará el TDA para resolver determinada aplicación. El uso del TDA se limita a llamar las operaciones sobre la estructura que se requiera cuidando siempre de cumplir con las reglas de
cada operación especificadas en el nivel lógico.
¿Cómo distinguir los niveles de abstracción?
Una analogía podría hacerse al comparar este proceso con el que se realiza al construir una casa, vea la
siguiente figura:
Esto significa que quien implementa el TDA no debe estar influenciado por la aplicación que tendrá la estructura y
quien use la estructura no tiene porqué saber cómo se implementaron sus
operaciones.
Entonces, se dice que la forma en que se almacenan los datos en la estructura es independiente de su aplicación y que para el usuario programador permanece
oculto cómo se implementaron las operaciones del TDA.
Esto, sin lugar a dudas, simplifica la labor del usuario del TDA, pues se
olvida de detalles de programación al basar su trabajo sólo del diseño lógico
del propio TDA. Adicionalmente, el implementador del TDA, podrá hacer
cambios o mejoras a su implementación, respetando la
especificación lógica y sin afectar en lo más mínimo las aplicaciones
desarrolladas.
¿Que es la independencia de datos y el ocultamiento de información?
Se observa que hay una independencia marcada entre el nivel físico y el nivel
de aplicación del TDA, con el nivel lógico como intermediario, ver figura:
Primero se trabaja en el nivel lógico al pedirle a un arquitecto que diseñe el
plano; el arquitecto hace una abstracción y plasma en el papel los
rasgos principales de la casa por construir. Además, especifica
claramente medidas y condiciones de construcción y de uso. Una vez
aprobado el diseño, se procede en el nivel físico, que correspondería a la
construcción.
Los albañiles seguirán paso a paso las especificaciones dadas en el plano (diseño en nivel lógico) y no tienen
porque preguntar para qué se utilizará cada uno de los espacios construidos
Además utilizarán el material más apropiado para cada situación. Una vez que la construcción esté terminada lle-gará su dueño para habitarla dándole el
uso correspondiente a cada espacio (nivel aplicación).
El dueño al utilizar la casa no necesita saber cómo se hizo con qué materiales o quiénes la construyeron; sin embargo le será útil conocer algunas medidas o
condicionen de construcción que se representan en el plano (nivel lógico).
De la misma forma, cuando se desea aplicar la abstracción de datos en el
desarrollo de software que requiere de una estructura de datos, se debe
comenzar con el diseño a nivel lógico del TDA, continuar con su
implementación y finalmente con su uso en el desarrollo de la aplicación
correspondiente.
En este proceso podrán intervenir tres personas: el diseñador del TDA, un
programador a nivel físico y un programador a nivel aplicación. Cuando el mismo programador trabaje en los
niveles físico y de aplicación, debe tener en cuenta la regla de no invadir los
niveles, respetando el nivel lógico que es intermediario.
¿Qué ventajas ofrece utilizar la técnica de abstracción de datos?
Seguir la regla de los tres niveles de abstracción redunda en un mejor
desarrollo de software. La técnica obliga a diseñar modularmente y, como
consecuencia, se tiene una implementación más clara,
documentada y de fácil mantenimiento.
Adicionalmente, gracias a la inde-pendencia de datos y al ocultamiento de información, se pueden crear paquetes como unidades de software reutilizable, con lo que se obtienen estructuras de
datos genéricas.
Quien utiliza un TDA se limita a llamar las operaciones, cuidando solamente de
cumplir con las especificaciones del diseño lógico, lo que facilita y hace más
rápido el desarrollo de aplicaciones, pues no es necesario manejar los detalles físicos de la estructura.
Quien utiliza un TDA se limita a llamar las operaciones, cuidando solamente de
cumplir con las especificaciones del diseño lógico, lo que facilita y hace más
rápido el desarrollo de aplicaciones, pues no es necesario manejar los detalles físicos de la estructura.
Con base en este diseño lógico, se puede pasar a la implementación del n TDA (nivel físico) para posteriormente
utilizarlo (nivel de aplicación) y resolver el problema factorial eficientemente.
EJERCICIOS CAPÍTULO I
1. Defina los siguientes conceptos: O Abstracción
O Abstracción de datos
O Especificación lógica
O Nivel de abstracción
O Independencia de niveles
O Precondición
O Postcondición
O Módulo
O Abstracción modular