UNIDAD 1 TIPOS DE DATOS ABSTRACTOS

Contenidos	Página
1.1 Tipos de datos abstractos (TDA)	1
1.2 Modularidad	6
1.3 Uso de TDA	6
1.4 Manejo de memoria estática	7
1.4.1. Ejemplo	7
1.5 Manejo de memoria dinámica	10

Introducción.

Las computadoras como ya sabemos, fueron diseñadas o ideadas como una herramienta mediante la cual podemos realizar operaciones de cálculo complicadas en un lapso de mínimo tiempo. Pero la mayoría de las aplicaciones de este fantástico invento del hombre, son las de almacenamiento y acceso de grandes cantidades de información.

La información que se procesa en la computadora es un conjunto de datos, que pueden ser simples o estructurados. Los datos simples son aquellos que ocupan sólo un localidad de memoria, mientras que los estructurados son un conjunto de casillas de memoria a las cuales hacemos referencia mediante un identificador único.

Debido a que por lo general tenemos que tratar con conjuntos de datos y no con datos simples (enteros, reales, booleanos, etc.) que por sí solos no nos dicen nada, ni nos sirven de mucho, es necesario tratar con estructuras de datos adecuadas a cada necesidad.

Las estructuras de datos son una colección de datos cuya organización se caracteriza por las funciones de acceso que se usan para almacenar y acceder a elementos individuales de datos.

Una estructura de datos se caracteriza por lo siguiente:

-Pueden descomponerse en los elementos que la forman.

-La manera en que se colocan los elementos dentro de la estructura afectará la forma en que se realicen los accesos a cada elemento.

-La colocación de los elementos y la manera en que se accede a ellos puede ser encapsulada.

1.1. Tipos de Datos Abstractos (TDA)

Qué es un TDA? Según los libros:

• “Un TDA es un modelo matemático con una colección de operaciones definidas sobre el modelo” (Aho, Hoperoft y Ullman. “Fundamental Structures of Computer Science”, 1981).

• “Una clase de objetos definida por una especificación independiente de la representación“ (Guttag “Abstract Data Type and development of data structures “ ACM . Vol 20-6, 1977)

• “Es un tipo de dato definido por el usuario a través de una especificación y una implementación de los objetos abstractos”. (Rowe , “types” ACM sigplan, Vol 16-1, 1980).

· Un TDA es un tipo de dato definido por el programador que se puede manipular de un modo similar a los tipos de datos definidos por el sistema.

. Un TDA es el elemento básico de la abstracción de datos. Su desarrollo es independiente del lenguaje de programación utilizado, aunque este puede aportar mecanismos que faciliten su realización.

Algunos lenguajes de programación tienen características que nos permiten ampliar el lenguaje añadiendo sus propios tipos de datos. Un tipo de dato definido por el programador se denomina tipo abstracto de datos (TAD) para diferenciarlo  del tipo fundamental (predefinido) de datos.

El término abstracto se refiere al medio en que un programador abstrae algunos conceptos de programación creando un nuevo tipo de dato.

Por ejemplo, en Java, el tipo Punto, que representa las coordenadas x,y  de un sistema de coordenadas rectangulares, no existe. Sin embargo, es posible implementar el tipo abstracto de datos, considerando los valores que se almacenan en las variables y qué operaciones están disponibles para manipular estas variables.

En esencia, un tipo abstracto es un tipo de dato que consta de datos (estructuras de datos propias) y operaciones que se pueden realizar sobre ellos. Un TAD se compone de estructuras de datos y los procedimientos o funciones que manipulan esas estructuras de datos.

Un tipo abstracto de datos puede definirse mediante la ecuación:

TA D = Representación (datos) + Operaciones (funciones y procedimientos)

La estructura de un tipo abstracto de dato (clase), desde un punto de vista global, se compone de la interfaz y de la implementación.

Las estructuras de datos reales elegidas para almacenar la representación de un tipo abstracto de datos son invisibles a los usuarios o clientes. Los algoritmos utilizados para implementar cada una de las operaciones de los TAD están encapsuladas dentro de los propios TAD. La característica de ocultamiento de la información significa que los  objetos tienen interfaces públicas. Sin embargo, las representaciones e implementaciones de esas interfaces son privadas.

Estructura de un tipo abstracto de datos (TAD)

En un TDA existen dos elementos diferenciados:

- La Interfaz de utilización

- La representación

A la hora de utilizar el TDA, la representación debe permanecer oculta. Solo podremos utilizar las operaciones del tipo para trabajar con sus elementos.

Para construir un tipo abstracto debemos:

1. Exponer una definición del tipo.

2. Definir las operaciones (funciones y procedimientos) que permitan operar con instancias de ese tipo.

3. Ocultar la representación de los elementos del tipo de modo que sólo se pueda actuar sobre ellos con las operaciones proporcionadas.

4. Poder hacer instancias múltiples del tipo.

Tipos básicos de operaciones en un TDA

· Constructores: Crean una nueva instancia del tipo.

· Transformación: Cambian el valor de uno o más elementos de una instancia del tipo.

· Observación: Nos permiten observar el valor de uno o varios elementos de una instancia sin modificarlos.

· Iteradores: Nos permiten procesar todos los componentes en un TDA de forma secuencial.

Ventajas de los tipos abstractos de datos.

Un tipo abstracto de datos es un modelo (estructura) con un número de operaciones que afectan a ese modelo. Los tipos abstractos de datos proporcionan numerosos beneficios al programador, que se pueden resumir en los siguientes:

1. Permiten una mejor conceptualización y modelización del mundo real. Mejoran la representación y la comprensibilidad. Clarifican los objetos basados en estructuras y comportamientos comunes.

2. Mejoran la robustez del sistema. Si hay características subyacentes en los lenguajes, permiten la especificación del tipo de cada variable. Los tipos abstractos de datos permiten la comprobación de tipos para evitar errores de tipo en tiempo de ejecución.

3. Mejoran el rendimiento (prestaciones). Para sistemas tipeados (tipificados), el conocimiento de los objetos permite la optimización de tiempo de compilación.

4. Separan la implementación de la especificación. Permiten la modificación y la mejora de la implementación sin afectar la interfaz pública del tipo abstracto de dato.

5. Permiten la extensibilidad del sistema. Los componentes de software reutilizables son más fáciles de crear y mantener.

6. Recogen mejor la semántica del tipo. Los tipos abstractos de datos agrupan o  localizan las operaciones y la representación de atributos.

Un programa que maneja un TAD lo hace teniendo en cuenta las operaciones o la funcionalidad que tiene, sin interesarse por la representación física de los datos. Es decir, los usuarios de un TAD se comunican con éste a partir de la interfaz que ofrece el TAD mediante funciones de acceso. Podría cambiarse la implementación del tipo de dato sin afectar al programa que usa el TAD ya que para el programa está oculta.

Clasificación de los TDA.

·          Tipos de Datos Abstractos simples:

·          Cambian su valor pero no su estructura ® espacio de almacenamiento constante

·          Enteros, reales, booleanos, carácter, enumerado, subrango, etc.

·          Tipos de Datos Abstractos contenedores:

·          Cambian su valor y estructura (colecciones de elementos de número variable) ® espacio de almacenamiento variable

·          Listas, colas, pilas, árboles, grafos, conjuntos, etc.

·           

·          Tipos de datos abstractos inmutables:

·          Sus casos no pueden modificarse (se crean y destruyen, pero no existen operaciones de modificación)

·          Representación inmutable o mutable

·          Tipos de datos abstractos mutables:

·          Sus casos pueden modificarse (existen operaciones de modificación)

·          Representación mutable

Implementación de los TAD.

Las unidades de programación de lenguajes que pueden implementar un TAD reciben distintos nombres:

Modula-2          módulo

Ada                  paquete

C++                 clase

Java                 clase

En estos lenguajes se definen la especificación del TAD, que declara las operaciones y los datos, y la implementación, que muestra el código fuente de las operaciones, que permanece oculto al exterior del módulo.

ESPECIFICACIÓN DE LOS TAD.

El objetivo de la especificación es describir el comportamiento del TAD; consta de dos partes, la descripción matemática del conjunto de datos y la de las operaciones  definidas en ciertos elementos de ese conjunto de datos.

La especificación del TAD puede tener un enfoque informal, que describe los datos y las operaciones relacionadas en lenguaje natural. Otro enfoque mas riguroso, la especificación formal, supone suministrar un conjunto de axiomas que describen las operaciones en su aspecto sintáctico y semántico.

La especificación informal de un TAD tiene como objetivo describir los datos del tipo y las operaciones según la funcionalidad que tienen. No sigue normas rígidas al hacer la especificación, simplemente indica, de forma comprensible, la acción que realiza cada operación.

Especificación de un TDA

Es la descripción formal del tipo de dato que representa a una entidad a través de sus propiedades y su comportamiento. Dos niveles:

1) Especificación Sintáctica:

¿Qué hace? Especificación de las entidades y sus propiedades (interfaz)

Definir el nombre de las entidades abstractas.

Definir el nombre de las operaciones indicando el dominio (argumentos) y el codominio o rango (los valores de retorno)

Especificación Semántica:

¿Cómo lo hace? Descripción de la representación del objeto (estructura de los datos) y desarrollo de las operaciones.

• Definir el significado de cada operación usando los símbolos definidos en la especificación sintáctica.

1.2. Modularidad.

La modularidad descompone un programa en un pequeño número de abstracciones independientes unas de otras pero fáciles de conectar entre sí. Un módulo se caracteriza principalmente por su interfaz y su implementación. La programación modular sigue el criterio de ocultación de información: si no se necesita algún tipo de información, no se debe tener acceso a ella.

La modularidad es un aspecto muy importante en los TDA, ya que es el reflejo de la independencia de la especificación y la implementación. Es la demostración de que un TDA puede funcionar con diferentes implementaciones. Además de esto, la programación modular ofrece otras ventajas como por ejemplo un mejor reparto de trabajo y una detección

La modularización de un programa utiliza la noción de tipo abstracto de dato (TAD) siempre que sea posible. Si el lenguaje de programación soporta los tipos que desea el usuario y el conjunto de operaciones sobre cada tipo, se obtiene un nuevo tipo de dato denominado TAD.

1.3.        Uso de TDA.

Ejemplos:

Una calculadora es un ejemplo de un TDA que maneja objetos de cantidades numéricas y las operaciones aritméticas sobre dichas cantidades.

Usa el sistema decimal para las cantidades y realiza operaciones de suma, resta, multiplicación, etc. Sin embargo, ¿Sabes cómo una calculadora representa las cantidades internamente? ¿En  binario? ¿Decimal? , ¿Palitos? ó ¿piedritas?.  NO!, no lo sabemos y tampoco nos hace falta para usar la calculadora.

Un sistema de numeración es un ejemplo de un tipo de dato abstracto que representa el concepto de cantidad. 

Los siguientes son ejemplos de sistemas de numeración:

Romano: I, V, X, L, C, D, M;

Decimal: 0, 1, 2, 3,…., 9;

Maya: . .. … __ _._

Las características más importantes son:

- “crear una protección de las entidades representadas”, es decir:

Oculta la representación e implementación de la entidad y sus operaciones. Nosotros no sabemos como la calculadora representa las cantidades ni como realiza la  operación de sumar.

-Sólo se manipulan a través de sus operaciones.

Nosotros solo podemos realizar las operaciones que la calculadora le permite realizar y nada más.

¿Cómo logramos crear dicha protección?. Según la ecuación de Wirth definimos un programa asi:

Programa = Datos + Algoritmos

Si podemos separar e identificar en un algoritmo las instrucciones que manipulan los datos de las instrucciones que indican control, entonces podemos reescribir la ecuación como:

Programa = Datos + Algoritmos-Datos + Algoritmo-Control

Donde TDA = Datos + Algoritmos-Datos, y por tanto la ecuación queda así:

Programa = TDA + Algoritmo de Control

Ventajas de uso de un TDA

• Herramienta para resolver problemas (nivel de abstracción)

• Independencia entre la forma de representar la información y la solución del problema →portabilidad de la solución.

• Favorece la especificación, verificación y depuración de programas.

• Contribuye a la flexibilidad de los cambios.

1.4 Manejo de memoria estática

Las Estructuras de datos Estáticos son aquéllas en las que el tamaño ocupado en memoria se define antes de que el programa se ejecute y no pude modificarse dicho tamaño durante la ejecución del programa. Arreglos, Registros, archivos y cadenas.

Ejemplo: Arreglos Unidimensionales

Un arreglo unidimensional es un tipo de datos estructurado que está formado de una colección finita y ordenada de datos del mismo tipo. Es la estructura natural para modelar listas de elementos iguales.

El tipo de acceso a los arreglos unidimensionales es el acceso directo, es decir, podemos acceder a cualquier elemento del arreglo sin tener que consultar a elementos anteriores o posteriores, esto mediante el uso de un índice para cada elemento del arreglo que nos da su posición relativa.

Para implementar arreglos unidimensionales se debe reservar espacio en memoria, y se debe proporcionar la dirección base del arreglo, la cota superior y la inferior.

REPRESENTACION EN MEMORIA

Los arreglos se representan en memoria de la forma siguiente:

x : array[1..5] of integer

Para establecer el rango del arreglo (número total de elementos) que componen el arreglo se utiliza la siguiente fórmula:

RANGO = Ls - (Li+1)

donde:

ls = Límite superior del arreglo

li = Límite inferior del arreglo               

Para calcular la dirección de memoria de un elemento dentro de un arreglo se usa la siguiente fórmula:

A[i] = base(A) + [(i-li) * w]

donde :

A = Identificador único del arreglo

i = Indice del elemento

li = Límite inferior

w = Número de bytes tipo componente

Si el arreglo en el cual estamos trabajando tiene un índice numerativo utilizaremos las siguientes fórmulas:

RANGO = ord (ls) - (ord (li)+1)

A[i] = base (A) + [ord (i) - ord (li) * w]

Operaciones Con Arreglos.

Las operaciones en arreglos pueden clasificarse de la siguiente forma:

• Lectura

• Escritura

• Asignación

• Actualización

• Ordenación

• Búsqueda

a) LECTURA

Este proceso consiste en leer un dato de un arreglo y asignar un valor a cada uno de sus componentes.

La lectura se realiza de la siguiente manera:

para i desde 1 hasta N haz

x<--arreglo[i]

b) ESCRITURA

Consiste en asignarle un valor a cada elemento del arreglo.

La escritura se realiza de la siguiente manera:

para i desde 1 hasta N haz

arreglo[i]<--x

c) ASIGNACION

No es posible asignar directamente un valor a todo el arreglo, por lo que se realiza de la manera siguiente:

para i desde 1 hasta N haz

arreglo[i]<--algún_valor

d) ACTUALIZACION

Dentro de esta operación se encuentran las operaciones de eliminar, insertar y modificar datos. Para realizar este tipo de operaciones se debe tomar en cuenta si el arreglo está o no ordenado.

Cuando un arreglo esta desordenado primeramente se tiene que llevar a cabo la búsqueda del elemento y posteriormente se realizara la operación correspondiente ya sea inserción, eliminación o modificación. Por otro lado si el arreglo esta ordenado se realiza el recorrido buscando la posición correspondiente según el tipo de ordenamiento que tenga el arreglo para realizar las operaciones.

Veamos un ejemplo de inserción en arreglos ordenados:

1.- Insertar.

//Este algoritmo inserta un elemento y en un arreglo unidimensional que se encuentra ordenado de forma creciente. La capacidad máxima del arreglo es de 100 elementos. N indica el número actual de elementos de V

//POS e I son variables de tipo entero

Si (N < 100) entonces

            Llamar al algoritmo Busca_Secuencial_Ordenado con V,N, Y y POS

Si POS > 0 entonces  // El elemento fue encontrado en el arreglo

                        Escribir “el elemento ya existe”

Si No

                        Hacer N = N+1

                        POS = POS * -1

                        Repetir con I desde N hasta POS + 1

                                   Hacer V[I] = V [I-1]

                        Fin-Repetir

                        Hacer V[POS] = Y

            Fin-SI

Si No

            Escribir “No hay espacio en el arreglo”

Fin-SI

1.5  Manejo de memoria dinámica

Las Estructuras de datos Dinámicas no tienen las limitaciones o restricciones en el tamaño de memoria ocupada que son propias de las estructuras estáticas. Mediante el uso de un tipo de datos específico denominado puntero, es posible construir estructuras de datos dinámicas que son soportadas por la mayoría de los lenguajes.  Listas, árboles y grafos.