Publicado el Miércoles 19 de abril de 2006 a las 20:48:06 por anomalia
Lecturas
Tipos Abstractos De Datos
La abstracción es un mecanismo fundamental para la comprensión de fenómenos o situaciones que implican gran cantidad de detalles. La idea de abstracción es uno de los conceptos más potentes en el proceso de resolución de problemas. Se entiende por abstracción la capacidad de manejar un objeto (tema o idea) como un concepto general, sin considerar la enorme cantidad de detalles que pueden estar asociados con dicho objeto. Sin abstracción no sería posible manejar, ni siquiera entender, la gran complejidad de ciertos problemas. Por ejemplo, sería inimaginable pensar en el presidente de una gran multinacional que viese la empresa en términos de cada trabajador individual o de cada uno de los objetos que fabrica, en vez de departamentos especializados. El proceso de abstracción presenta dos aspectos complementarios:
1. descartar los aspectos relevantes del objeto. 2. ignorar aspectos irrelevantes del mismo (la irrelevancia depende del nivel de abstracción, ya que si se pasa a niveles más concretos, es posible que ciertos aspectos pasen a ser relevantes).
Se puede decir que la abstracción permite estudiar los fenómenos complejos siguiendo un método jerárquico, es decir, por sucesivos niveles de detalle. Generalmente, se sigue un sentido descendente, desde los niveles más generales a los niveles más concretos.
Los programas son objetos complejos que pueden contener varios miles de instrucciones, cada una de las cuales puede dar lugar a un error del programa y que, por lo tanto, necesitan mecanismos de definición que eviten en la medida de lo posible que el programador cometa errores. Así, los lenguajes de programación de alto nivel permiten al programador abstraerse del sin fin de detalles de los lenguajes ensambladores y permiten trabajar de manera independiente respecto a las máquinas sobre las que finalmente se hará funcionar el programa.
En el proceso de programación se puede extender el concepto de abstracción tanto a las acciones, mediante la llamada abstracción procedural (uso de procedimientos), como a los datos, mediante los llamados tipos abstractos de datos.
La idea de programación procedural aparece ya en los primeros lenguajes de alto nivel (Fortran y Cobol) a través de la utilización de subrutinas. La aparición de la llamada programación estructurada profundiza más en la descomposición del programa en procedimientos. Los procedimientos permiten generalizar el concepto de operador, de manera que el programador es libre de definirse sus propios operadores y aplicarlos sobre datos que no tienen porque ser necesariamente simples, como hacen habitualmente los constructores de expresiones de los lenguajes de programación.
Los procedimientos permiten encapsular partes de un algoritmo (modularizar), localizando en una sección del programa aquellas proposiciones relacionadas con cierto aspecto del mismo. De forma que, la abstracción procedural destaca qué hace el procedimiento ignorando cómo lo hace. El programador, como usuario de un procedimiento, sólo necesita conocer la especificación de la abstracción (el qué), limitándose a usar el procedimiento con los datos apropiados. Por lo tanto, la abstracción produce un ocultamiento de información.
La aplicación a los datos de las ideas de abstracción y de ocultación de información ha tardado más tiempo en producirse. El concepto de tipo abstracto de datos, propuesto hacia 1974 por John Guttag y otros, vino a desarrollar este aspecto. Análogamente a los procedimientos, los llamados tipos abstractos de datos constituyen un mecanismo que permite generalizar y encapsular los aspectos relevantes sobre la información (datos) que maneja el programa.
Hay que tener en cuenta que no se deben confundir los conceptos de tipo de datos, estructura de datos y tipo abstracto de datos. Todos ellos constituyen diferentes niveles en el proceso de abstracción referida a los datos.
Los datos son las propiedades o atributos (cualidades o cantidades) sobre hechos u objetos que procesa el ordenador. El tipo de datos, en un lenguaje de programación, define el conjunto de valores que una determinada variable puede tomar, así como las operaciones básicas sobre dicho conjunto. Los tipos de datos pueden variar de un lenguaje a otro, tanto los tipos simples como los mecanismos para crear tipos compuestos. Los tipos de datos constituyen un primer nivel de abstracción, ya que no se tiene en cuenta cómo se representa realmente la información sobre la memoria de la máquina. Para el usuario, el proceso de representación es invisible. El programador no manipula directamente las cadenas de bits que constituyen los datos, sino que hace uso de las operaciones previstas para cada tipo de datos.
Por ejemplo: el tipo simple entero (integer en Pascal e int en C) define un conjunto de valores enteros comprendidos en un determinado intervalo. (en el caso de Pascal por la constante MAXINT), para los que están definidas las operaciones suma, resta, multiplicación y división entera (entre otras). De esta manera al escribirse los programas independientemente de la representación última de los datos en la memoria, si cambiase, por ejemplo, la forma de representar la información en los ordenadores (si por ejemplo, dejaran de trabajar en base dos y pasaran a base tres), los programas escritos en lenguajes de alto nivel sólo necesitarían ser recompilados para ejecutarse correctamente en las nuevas máquinas.
La memoria del ordenador es una estructura unidimensional (secuencia de elementos) formada por celdas iguales que pueden almacenar números binarios con un número fijo de cifras (bits). Cada tipo de datos tiene asociada una función de transformación que permite pasar los datos del formato en que se manejan en un programa al formato de la memoria y viceversa. De manera que cambiar la representación en memoria de los datos sólo implica modificar la función de transformación, el programador no ve afectado para nada su trabajo, que se encuentra en un nivel superior de abstracción.
Los tipos de datos que un programador utiliza en un lenguaje de alto nivel suelen ser de dos tipos: predefinidos por el lenguaje y definidos por el usuario. Esta última posibilidad contribuye a elevar el nivel del lenguaje, pues permite definir tipos de datos más próximos al problema que se desea resolver. Además, la posibilidad de especificar tipos estructurados introduce la idea de genericidad. El lenguaje suministra constructores genéricos de tipos mediante los cuales el programador puede definir tipos concretos. Sin embargo, al programador no se le permite definir cuáles son las operaciones permitidas para los nuevos tipos de datos.
En general, los lenguajes suministran unas operaciones predefinidas muy generales que, en la mayoría de los casos, no resultan las más apropiadas para el nuevo tipo.
Supóngase, por ejemplo, la definición de un tipo de datos para manipular fechas del calendario, una posible definición en Pascal sería:
type fecha = record dia: 1..31; mes: 1..12; anyo: 1900..2100; end;
Se pueden definir variables del nuevo tipo:
var f1, f2: fecha;
También se pueden definir procedimientos que operen sobre valores de este tipo, pero, sin embargo, no se puede impedir que se generen valores que no tienen sentido, teniendo en cuenta la idea del programador. Por ejemplo, hacer:
f1.dia:=30; f1.mes:=2; (dia 30 de febrero)
o bien:
f1.dia := 5*f2.mes;
La explicación última a estos hechos es que los lenguajes de programación como Pascal no permiten definir tipos en el sentido estricto, sino tan sólo representar unos tipos con otros. Se utilizan tipos previamente definidos (en última instancia los predefinidos en el lenguaje) para definir otros nuevos, lo que hace que las operaciones asociadas con los tipos originales sean heredadas por los nuevos tipos. El concepto de tipo abstracto de datos viene a clarificar esta situación.
Entre el nivel de los tipos de datos y el nivel de los tipos abstractos nos encontramos con las llamadas estructuras de datos. Las estructuras de datos son conjuntos de variables, quizás de tipos distintos, relacionadas (conectadas) entre sí de diversas formas y las operaciones definidas sobre esa agrupación. Ejemplos de estructuras de datos las podemos encontrar en muchos ámbitos, desde las matemáticas (estructuras algebraicas: grupo, anillo o cuerpo) hasta el mundo de los negocios (estructura de una empresa). Los elementos de una estructura de datos dependen del lenguaje de programación a través de los tipos de datos que los definen. Sin embargo, la estructura en sí, que está definida por el tipo de relación entre los elementos, no depende del lenguaje de programación empleado.
Las estructuras de datos se caracterizan por el tipo de los elementos de la estructura, las relaciones definidas sobre los elementos y las operaciones permitidas sobre la estructura. Operaciones típicas sobre estructuras de datos suelen ser: acceder a los elementos (por la posición que ocupan o por la información que contienen), buscar elementos, insertar o borrar elementos, modificar las relaciones entre los elementos, etc...
Al nivel de las estructuras de datos, ya no tienen relevancia las operaciones que se puedan realizar sobre los componentes individuales de la misma, solamente la tienen las operaciones que implican a la estructura globalmente.
En el nivel más alto de abstracción estarían los tipos abstractos de datos, estos se pueden ver como modelos matemáticos sobre los que se definen una serie de operaciones. El tipo abstracto de datos (en adelante TAD) es una colección de valores y operaciones que se definen mediante una especificación que es independiente de cualquier representación. Para representar el modelo matemático básico de un TAD se emplean estructuras de datos y las operaciones definidas en el modelo se representan mediante procedimientos. Por ejemplo, se podría definir el TAD número complejo como un objeto con dos componentes que son números reales y sobre el que se define las operaciones suma y producto de números complejos. En una definición de este tipo no importa si en un programa concreto se utiliza una estructura tipo registro con dos campos para representar los datos o bien una estructura tipo array con dos elementos. Desde el punto de vista formal ese tipo de información es irrelevante. Así mismo, no es necesario conocer cómo se realizan las operaciones definidas formalmente, sólo importa qué hacen para poder usarlas correctamente.
