Documentación de la Biblioteca de Estructuras de Datos Avanzadas (página 2)

Aplicaciones:

• Las colas de prioridad se aplican cuando las solicitudes deben procesarse en el orden de prioridad y no en el orden de llegada.

• Una aplicación de las colas de prioridad es la planificación de los trabajos o procesos en un sistema informático multiusuario. Un planteamiento simple consiste en utilizar una cola para atender a los trabajos con una filosofía de que el primero en llegar es el primero en ser atendido. Este planteamiento no funciona bien cuando trabajos cortos quedan "atrapados" en la cola detrás de trabajos largos en ejecución, generalmente es mejor dejar que los trabajos cortos se ejecuten primero.

• Gestión de los procesos en un sistema operativo. Los procesos no se ejecutan uno tras otro en base a su orden de llegada. Algunos procesos deben tener prioridad (por su mayor importancia, por su menor duración, etc.) sobre otros.

• Implementación de algoritmos voraces, los cuales proporcionan soluciones globales a problemas basándose en decisiones tomadas sólo con información local. La determinación de la mejor opción local suele basarse en una cola de prioridad.

• Algunos algoritmos sobre grafos, como la obtención de caminos o árboles de expansión de mínimo coste, son ejemplos representativos de algoritmos voraces basados en colas de prioridad.

• Implementaciones eficientes de algoritmos de simulación de sucesos discretos. En estas, el avance del tiempo no se gestiona incrementando un reloj unidad a unidad, sino incrementado sucesivamente el reloj al instante del siguiente suceso.

3.1.1 Cola de prioridad utilizando arreglos.

Definición 3.2:

La implementación más sencilla que puede llevarse a cabo es utilizar un arreglo lineal. Al igual que en la lista, a estas operaciones se les pueden agregar otras.

Por ejemplo si se implementa la cola utilizando arreglos se puede añadir una operación que nos indique cuando la misma está llena, en caso de que se quisiera adicionar más elementos habría que reservar más espacio en la memoria de la computadora. (4)

Seudocódigo:

3.1.2 Cola de prioridad utilizando listas enlazadas.

Definición 3.3:

Al igual que para la pila las implementaciones de Cola pueden ser obtenidas utilizando algunas implementaciones del TDA Lista, así como con la utilización de nodos enlazados, para esta variante la clase puede utilizar un nodo frente y un nodo fondo.

Seudocódigo:

3.2 Cola de amigos.

Una Cola de Amigos se comporta de manera similar a una Cola de Prioridad, con la particularidad de que en la misma para insertar un elemento se busca el primer elemento amigo partiendo desde el frente de la cola y se coloca delante él.

3.2.1 Cola de Amigos utilizando arreglos.

Definición 3.4:

La implementación más sencilla que puede llevarse a cabo es utilizar un arreglo lineal. Al igual que en la lista, a estas operaciones se les pueden agregar otras. Por ejemplo si se implementa la cola utilizando arreglos se puede añadir una operación que indique cuando la misma está llena. En caso de que se quisiera adicionar nuevos elementos habría que reservar más espacio en la memoria de la computadora.(3)

Seudocódigo:

3.2.2 Cola de Amigos utilizando listas enlazadas.

Definición 3.5:

Al igual que en la pila, las implementaciones de una cola pueden ser obtenidas utilizando algunas implementaciones del TDA Lista, así como con la utilización de nodos enlazados, para esta variante la clase puede utilizar un nodo frente y un nodo fondo.

Seudocódigo:

3.3 Observaciones Generales sobre los TDA Colas.

Al igual que con las pilas, la mejor implementación depende de la situación particular. Si se conocen de antemano el número de elementos entonces lo ideal es una implementación por arreglos. En otro caso se recomienda el uso de la lista enlazada.(8)

Implementar el TDA Cola supone añadir elementos en un extremo de la lista durante una operación Adicionar, y quitarlos del otro extremo de la lista durante al operación Extraer. Esto garantiza que los elementos son accedidos en orden FIFO.

CAPÍTULO 4

Estructura de datos: Tabla Hash

Durante este capítulo se manifestará el concepto de la estructura de datos: tabla hash y de algunas de sus estrategias para la resolución de colisiones, simultáneamente se exponen las ventajas y las desventajas de cada una, así como las aplicaciones que tienen en la vida práctica, además de mostrar el seudocódigo. Lo mencionado anteriormente permite tener un mejor conocimiento de este tipo de estructura de datos y saber en un problema determinado cual es la más óptima para darle solución al mismo.

¿Qué es una tabla hash?

Una tabla hash, mapa hash o tabla de dispersión es una estructura de datos que está formada por las combinaciones de llaves o claves con valores organizados en "sectores de almacenamiento", para permitir realizar una búsqueda rápida. Constituye un TDA especial para la manipulación y almacenamiento de la información en la memoria secundaria de la computadora.

Una tabla hash se construye con tres elementos básicos.

• Una estructura de acceso directo, como un arreglo, capaz de almacenar N cantidad de elementos.

• Una función de dispersión que permita a partir de la clave obtener el índice donde estará almacenado el dato asociado a esa clave y cuyo dominio sea el espacio de claves y su imagen (o rango) los números naturales.

• Una función de resolución de colisiones. (5)

Figura 4.1 Representación gráfica de una Tabla Hash.

La operación principal que soporta de manera eficiente es la búsqueda, que permite el acceso a los elementos (por ejemplo: teléfono y dirección) almacenados a partir de una clave generada (por ejemplo: usando el nombre o número de cuenta). Funciona transformando a través de una función de dispersión, la clave en un índice, que no es más que un número que la tabla hash utiliza para localizar el valor deseado.

Las operaciones básicas implementadas en las Tablas Hash son:

• Insertar (clave, elemento), inserta un elemento en un índice de la tabla hash generado por una función de dispersión dado una clave.

• Buscar (clave), busca el elemento que se encuentra almacenado en el índice de la tabla hash generado por una función de dispersión dado una clave.

• Eliminar (clave), elimina el elemento que se encuentra almacenado en el índice de la tabla hash generado por una función de dispersión dado una clave.

Es inevitable que claves diferentes lleguen a producir el mismo resultado de la función de dispersión y esto constituye un problema.

Figura 4.2 Representación gráfica de una colisión.

Pero existen estrategias que tratan de resolver este problema de mejor o peor manera, tal es el caso de la:

• Resolución de colisiones por dispersión Abierta (o externa).

• Resolución de colisiones por dispersión Cerrada (o interna).

Ventajas:

• Una tabla hash tiene como principal ventaja que el acceso a los datos suele ser muy rápido si se cumplen las siguientes condiciones:

• Una razón de ocupación no muy elevada (a partir del 75% de ocupación se producen demasiadas colisiones y la tabla se vuelve ineficiente).

• Una función resumen que distribuya uniformemente las claves. Si la función está mal diseñada, se producirán muchas colisiones.

• Otra ventaja, es que están implementadas usando algoritmos de hashing que los hace muy rápidos (aunque las listas asociativas son más fáciles de crear y manipular).

• Comparada con otras estructuras de arreglos asociadas, las tablas hash son más útiles cuando se almacenan grandes cantidades de información.

Desventajas:

• Su principal inconveniente es que se trata de una estructura estática fija y al implementar cualquier otra operación el coste es muy elevado.

• Dificultad para recorrer todos los elementos. Se suelen emplear listas o colecciones (Collection usadas en .net) para procesar la totalidad de los elementos.

• Desaprovechamiento de la memoria. Si se reserva espacio para todos los posibles elementos, se consume más memoria de la necesaria; se suele resolver reservando espacio únicamente para punteros a los elementos.

• Las tablas hash almacenan la información en posiciones seudo-aleatorias, así que el acceso ordenado a su contenido es bastante lento.

Aplicaciones:

• Es uno de los medios más eficientes para implementar el TDA Diccionario.

• Se emplea en la implementación de la tabla de símbolos de un compilador.

4.1 Resolución de colisiones por dispersión abierta.

Definición 3.1:

Una de las estrategias más simples de resolución de colisiones, denominada dispersión abierta, se basa en colocar en una lista enlazada todos los elementos que se dispersan en el mismo hueco. Así todos los elementos almacenados en una lista enlazada tendrán la misma clave. En este caso los huecos de la tabla dispersa no almacenan ya elementos, sino punteros a listas enlazadas asignadas dinámicamente que almacenan todos los elementos que se dispersan en ese hueco, como se muestra en la figura 4.2. Esta estrategia se extiende fácilmente para permitir cualquier estructura de datos dinámica, no solo listas enlazadas. Téngase en cuenta que con la dispersión abierta el número de elementos que pueden ser almacenados solo está limitado por la cantidad de memoria disponible.

Figura 4.3 Representación gráfica de la resolución de colisiones por dispersión abierta en una tabla hash.

Ventajas:

• El número de elementos que pueden ser almacenados solo está limitado por la cantidad de memoria disponible en la computadora.

Seudocódigo:

4.2 Resolución de colisiones por dispersión cerrada.

Definición 3.2:

En la dispersión cerrada todos los elementos se almacenan en la propia tabla dispersa. En este caso, las colisiones se resuelven calculando una secuencia de huecos de dispersión. Esta secuencia es examinada o explorada sucesivamente hasta que se encuentra un hueco en la tabla dispersa vacío en el caso de Insertar, o se encuentre el elemento deseado en el caso de Buscar o Eliminar.

Figura 4.4 Representación gráfica de la resolución de colisiones por dispersión cerrada en una tabla hash.

Ventajas:

• La ventaja de este enfoque es que evita el uso de punteros. La memoria que se ahorra al no almacenar puteros puede utilizarse para construir una tabla dispersa más grande si es necesario. De este modo, utilizando la misma cantidad de memoria se puede construir una tabla dispersa mayor, que potencialmente conduce a menos colisiones y por lo tanto, a unas operaciones más rápidas del TDA Diccionario.

• Evita el uso de una segunda estructura de datos.

Desventajas:

• Usa un espacio fijo para el almacenamiento de los elementos, por lo que limita el tamaño de los conjuntos.

• Se pueden llegar a producir colisiones en cadena.

• Necesidad de ampliar el espacio de la tabla si el volumen de datos almacenados crece. Se trata de una operación costosa.

Seudocódigo:

4.3 Observaciones Generales sobre la estructura de datos: Tabla Hash.

4.3.1 Función de dispersión.

Las propiedades más importantes de una buena función de dispersión son:

• Que pueda ser calculada muy rápidamente (que solo se requieran unas pocas operaciones simples).

• Y que al mismo tiempo se minimicen las colisiones.

Con el fin de minimizar las colisiones, una función de dispersión no debería de mostrar un sesgo hacia ningún hueco en particular de la tabla dispersa. Idealmente, una función de dispersión tendrá la propiedad de que cada clave tiene la misma probabilidad de dispersarse en cualquiera de los huecos de la tabla dispersa.

Para cada uno de los métodos de dispersión expuestos a continuación se asume que:

K: representa una clave arbitraria.

M: representa el tamaño de la tabla hash.

N: representa el número de elementos almacenados en la tabla hash.

H: representa a la función de dispersión.

H (K): representa el índice o el valor de dispersión calculado por la función de dispersión H cuando se le suministró la clave K.

DISPERSION ABIERTA

• Método de la División:

Las funciones de dispersión que hacen uso del método de la división generan los valores de dispersión calculando el resto de K dividido entre M:

• Método de la Multiplicación:

Aunque el método de la división tiene las ventajas de ser simple y fácil de usar, su sensibilidad a la elección de M puede ser demasiado restrictiva.

La principal ventaja del método de la multiplicación es que la elección de M no es crítica, de hecho, M se escoge a menudo como una potencia de 2 en las implementaciones con aritmética de coma fija.

Las funciones de dispersión que hacen uso del método de la multiplicación generan valores de dispersión en dos pasos:

Primero se calcula la parte decimal del producto de K y cierta constante real A, donde: 0 < A < 1.

Este resultado es entonces multiplicado por M antes de aplicarle la función de truncado para obtener el valor de dispersión:

Obsérvese que K*A – [K*A] obtiene la parte decimal del número real K*A. Dado que la parte decimal es mayor o igual que 0 y menor que 1, los valores de dispersión son enteros en el rango 0, 1, …, M -1. Una elección para A que habitualmente hace un buen trabajo al distribuir las claves por toda la tabla dispersa es la inversa de la razón áurea.

El método de la multiplicación exhibe cierto número de agradables características matemáticas. Debido a que los valores de dispersión dependen de todos los bits de la clave, las permutaciones de una clave no tienen mayor probabilidad de colisión por cualquier otro par de claves. Además las claves como «ptr1» y «ptr2» son muy similares y por tanto tienen valores de claves transformados que se encuentran numéricamente cercanos uno al otro pero producirán valores de dispersión que están ampliamente separados.

DISPERSION CERRADA

En la dispersión cerrada, las funciones de dispersión habituales comentadas anteriormente son modificadas para utilizar tanto una clave, como un número de ensayo al calcular un valor de dispersión. Esta información adicional se utiliza para construir la secuencia de exploración. Más concretamente, en la dispersión cerrada, las funciones de dispersión son aplicaciones:

Y producen la secuencia de exploración:

Debido a que la tabla contiene M huecos, a lo sumo puede haber M valores distintos en una secuencia de exploración. Téngase en cuenta, sin embargo, que para una secuencia de exploración dada se permite la posibilidad de que H (K, i) = H (K, j) para i ? j. Por tanto, es posible que una secuencia de exploración contenga más de M valores.

Insertar un elemento utilizando dispersión cerrada conlleva sondear la tabla dispersa utilizando la secuencia de exploración calculada hasta que se encuentre un hueco vacío en el arreglo, o bien se cumplan algunos criterios de parada.

• Exploración Lineal:

Esta es una de las estrategias de exploración más simples de implementar, sin embargo, su rendimiento tiende a decaer rápidamente conforme aumenta el factor de carga.

El estudio de la exploración lineal es también instructivo debido a que es fácil demostrar con este enfoque las condiciones patológicas que pueden surgir cuando se utiliza la dispersión cerrada.

El empleo de la exploración lineal conduce a un problema conocido como agrupamiento, donde los elementos tienden a juntarse o agruparse en la tabla dispersa de tal forma que solo pueden ser accedidos por medio de una larga secuencia de exploración. Esto proviene del hecho de que tras aparecer un pequeño grupo en la tabla dispersa, se convierte en «objetivo» de las colisiones durante las inserciones subsiguientes.

Se ha observado que la secuencia de exploración en la exploración lineal está completamente determinada por el valor de dispersión inicial y dado que hay M posibles de estos, el número de secuencias de exploración distintas es M. Este hecho junto con los problemas de agrupamiento conspira para hacer que la exploración lineal sea una pobre aproximación a la dispersión uniforme cuando N se acerca a M.

• Exploración Cuadrática:

Esta es una extensión simple de la exploración lineal en la que uno de los argumentos suministrados a la operación mod es una función cuadrática del número de ensayo. Más concretamente, dada cualquier función de dispersión ordinaria H´, una función de dispersión que utilice dispersión cuadrática puede construirse utilizando:

Dado que el argumento izquierdo de la operación mod en la ecuación es una función no lineal del número de ensayo, las secuencias de exploración no pueden ser generadas a partir de otras secuencias de exploración por medio de simples desplazamientos cíclicos. Esto elimina el problema del agrupamiento primario y tiende a hacer que la exploración cuadrática funcione mejor que la exploración lineal. No obstante, como con la exploración lineal, el ensayo inicial H (K, 0) determina toda la secuencia de exploración y el número de secuencias de exploración distintas es M. Así el agrupamiento secundario es todavía un problema, y la exploración cuadrática solo ofrece una buena aproximación a la dispersión uniforme si M es grande comparado con N.

4.3.2 Desbordamiento de la tabla.

Hasta este punto se ha asumido que el tamaño M de la tabla dispersa será siempre suficientemente grande como para acomodar los conjuntos de datos con los que se está trabajando. En la práctica sin embargo, se debe considerar la posibilidad de una inserción en una tabla llena (un desbordamiento en la tabla). Si se está utilizando dispersión abierta, este no es habitualmente un problema dado que el tamaño total de las cadenas solo está limitado por la cantidad de memoria disponible de la zona libre. Así se restringe la exposición al desbordamiento de las tablas en la dispersión cerrada.

Se considerarán dos técnicas que evitan el problema del desbordamiento de la tabla asignando memoria adicional. En ambos casos, es mejor no esperar hasta que la tabla esté completamente llena antes de asignar más memoria; en su lugar, la memoria será asignada cuando el factor de carga a supere cierto umbral que se denotará con a.

• Expansión de la tabla:

El planteamiento más simple para tratar el desbordamiento de las tablas consiste en asignar una tabla más grande cuando una inserción produzca que el factor de carga exceda y trasladar el contenido de la tabla antigua a la nueva.

Emplear esta técnica con las tablas dispersas se complica por el hecho de que el resultado de las funciones de dispersión depende del tamaño de la tabla. Esto significa que después de expandir (o contraer) la tabla, todos los elementos necesitan ser «re- dispersados» en la nueva tabla. Los costes adicionales debidos a la re-dispersión tienden a hacer que este método sea demasiado lento.

• Dispersión extensible:

La dispersión extensible limita los costes adicionales debido a la re-dispersión dividiendo la tabla dispersa en bloques. El proceso de dispersión se ejecuta entonces en dos pasos:

Primero se comprueban los bits de menor orden de una clave para determinar en que bloque será almacenado un elemento (todos los elementos de un bloque dado tendrán idénticos bits de menor orden), entonces el elemento se dispersa en un hueco particular de ese bloque utilizando los métodos comentados anteriormente. Las direcciones de estos bloques se almacenan en una tabla directorio, tal y como se muestra en la figura 4.5. Además con la tabla se almacena un valor b, que es el número de bits de menor orden a utilizar durante el primer paso del proceso de dispersión.

Si el tamaño de los bloques se mantiene relativamente pequeño, el enfoque de dispersión extensible reducirá enormemente los costes adicionales debidos a la re-dispersión. Desde luego, esto se hace a expensas del tiempo adicional que se consume comparando los bits de orden inferior de la tabla directorio durante el primer paso del proceso de dispersión.

Figura 4.5 Diagrama de la estructura de datos utilizada en la dispersión extensible.

CAPÍTULO 5

Estructura de datos: DCEL

En este capítulo se muestra el concepto de la estructura de datos DCEL, conjuntamente se exponen sus ventajas, así como las aplicaciones que tiene en la vida práctica, además de mostrar el seudocódigo de alguna de sus operaciones.

Definición 3.1:

DCEL son las siglas inglesas de Lista de Lados Doblemente Enlazados. La estructura DCEL está formada por tres colecciones de registros:

• Lista de vértices: Un registro para un vértice v, que almacena las coordenadas de v y un puntero a una arista arbitraria con origen en v.

• Lista de aristas: Un registro para una arista a, que almacena un puntero al vértice origen, un puntero a su arista gemela, un puntero a la cara en la que se encuentra, un puntero a la arista siguiente y otro a la anterior, todos ellos orientados en el sentido anti horario.

• Lista de caras: Un registro para una cara c, almacena un puntero a un lado exterior a la cara y otro a uno interior. Se puede ver que es necesario aplicar una determinada orientación a las aristas, ya que se habla de medios-lados orientados, de esta forma una arista podría considerarse interna a una cara si está orientada en sentido anti horario con respecto a la cara.

Figura 5.1 Representación gráfica de DCEL.

Ventajas:

• Eficiente a la hora de obtener las siguientes características:

• Aristas que conforman una cara.

• Aristas que inciden en un vértice.

• Caras adyacentes a una cara determinada.

Aplicaciones:

• Se puede utilizar para almacenar eficazmente información geométrica y topológica sobre superficies bidimensionales.

• Además, estas estructuras pueden almacenar otras informaciones no necesariamente topológicas, sino colores.

• Se emplean en la representación de grafos planares.

• Para calcular la intersección (o unión) de polígonos simples.

• DCEL se utiliza además para almacenar el Diagrama de Voronoi.

Seudocódigo:

5.1- Observaciones Generales sobre la estructura de datos DCEL.

La lista de lados doblemente enlazados (DCEL) es una estructura clásica de la geometría computacional que permite almacenar cualquier grafo plano. Es una lista de segmentos orientados. Para cada segmento se guardan apuntadores a sus dos vértices V1 y V2, apuntadores al primer segmento vecino que se encuentran girando alrededor de cada uno de los vértices en sentido anti horario A1 y A2, opcionalmente puede contener un apuntador a cada una de las caras que comparten el segmento C1 y C2. Como ha de almacenar una triangulación restringida, un atributo adicional indica si el segmento es requerido o no.

La estructura de datos DCEL se emplea para almacenar el Diagrama de Voronoi. Un Diagrama de Voronoi de un conjunto de puntos en el plano, no es más que la subdivisión del mismo en regiones formadas por los lugares más próximos a cada uno de los puntos.

Son muchas las utilidades de los Diagramas de Voronoi entre las cuales se encuentran:

• Posicionamiento de torretas en telefonía móvil. La región de Voronoi de cada una de las torretas determinaría qué teléfonos deberían realizar la conexión a través de la misma.

• Control aéreo. El Diagrama de Voronoi de cada centro de control, determinaría la zona del espacio aéreo a controlar por dicha estación.

• Distribución de servicios públicos (hospitales, centros comerciales…) La ubicación de dichos establecimientos "debería ser" (al menos teóricamente) la que tenga la mayor área de región de Voronoi con respecto al resto de establecimientos del mismo tipo, para así aumentar la hipotética clientela. Como comentario a este último caso, se podría realizar una serie de modificaciones al planteamiento: por ejemplo en el caso de la ubicación de los hospitales. A un determinado enfermo siempre le interesaría acudir al hospital más cercano a su domicilio según la distancia euclídea. Para saber a cual acudir no tendría más que mirar el Diagrama de Voronoi de los puntos que indican la posición de los hospitales y comprobar en que región se encuentra su casa. Ahora bien, también podría ser interesante considerar a ciertos hospitales como más cercanos si tienen, por ejemplo, mejor acceso (autopista…) o si tienen un mayor número de camas. En este caso cada uno de los puntos (hospitales en este caso) puede tener asignado un determinado "peso", con lo que el Diagrama de Voronoi de la nube de hospitales podría cambiar notablemente al llevarse una mayor zona de influencia (cercanía) el hospital con más peso.

Coclusiones

El objetivo por el cual se realizó la presente documentación de la Biblioteca de Estructuras de Datos Avanzadas, fue la de establecer un material de apoyo y consulta para los estudiantes de Ingeniería en Informática y de Sistemas o de cualquier otra área afín, en la cual se imparta la materia de Estructura de Datos.

Cada estructura de datos ofrece ventajas y desventajas en relación a su simplicidad y eficiencia para la realización de cada operación. Una vez que se haya terminado de revisar detenidamente este material, el usuario será capaz de establecer estructuras de datos lógicas que permitan hacer un uso más eficiente del espacio ocupado en la memoria de la computadora, de minimizar los tiempos de acceso, así como de lograr formas más efectivas de inserción y eliminación de los datos en estructuras de almacenamiento, para lograr una solución óptima.

Glosario de Términos y siglas

A

Apilar: operación en la que un elemento de datos se coloca en el lugar apuntado por el puntero de la pila, y la dirección en el puntero de la pila se ajusta por el tamaño de los datos de partida.

Arreglo: o como también se le conoce: vector, array, o alineación, en programación no es más que un conjunto o agrupación de variables del mismo tipo cuyo acceso se realiza por índices. Se almacenan en forma contigua en la memoria RAM y son referenciados con un nombre común y una posición relativa.

D

Desapilar: operación en la que un elemento de datos en la ubicación actual apuntada por el puntero de la pila es eliminado, y el puntero de la pila se ajusta por el tamaño de los datos de partida.

E

Estructura de datos: son colecciones de variables, no necesariamente del mismo tipo, relacionadas entre sí de alguna forma, sobre la que se han implementado las operaciones definidas para el TDA y que permite finalmente la implementación de un tipo de dato (a través de una clase).

F

Función hash: es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor (por ejemplo un subconjunto de los números naturales). Una buena función de dispersión es una que experimenta pocas colisiones en el conjunto esperado de entrada; es decir que se podrán identificar unívocamente las entradas.

S

Seudocódigo: se utiliza para expresar los algoritmos en una forma que sea independiente de cualquier lenguaje de programación. El prefijo seudo se usa para resaltar que no se pretende que este código sea compilado y ejecutado en una computadora. La razón para usar seudocódigo es que permite transmitir en términos generales las ideas básicas de un algoritmo. Una vez que los programadores entienden el algoritmo que está siendo expresado por el seudocódigo, pueden implementarlo en el lenguaje de programación de su elección.

T

Tabla de símbolos: es una forma concreta del TDA Diccionario que utilizan los compiladores para mantener los distintos trozos de información simbólica que deben accederse cuando se genera un código ejecutable.

Tipo de dato abstracto (TDA) o Tipo abstracto de datos (TAD): es un modelo matemático compuesto por una colección de operaciones definidas sobre un conjunto de datos para el modelo.

Referencias bibliográficas

1. PROGRAMACIÓN, D. D. T. D. P2. Conferencia #1. Estructuras de Datos Lineales. Los Tipos de Datos Abstractos. El TDA Lista. 2006-2007.

2. P2. CONFERENCIA #2. Estructuras de Datos Lineales. Implementación del TDA Lista utilizando listas enlazadas. . Departamento de Técnicas de Programación ed. curso: 2006-2007.

3. ALGORITMIA.NET de 2008]. Disponible en: http://www.algoritmia.net/articles.php?id=13.

4. P2. CONFERENCIA #3. Estructuras de Datos Lineales.Los TDA Pila y Cola. . Departamento de Técnicas de Programación ed. curso: 2006-2007.

5. COTA, J. M. G. Tutorial de Estructuras de Datos (I). Instituto Tecnológico de La Paz.: de 2008]. Disponible en: http://sistemas.itlp.edu.mx/tutoriales/estru1/index.htm.

6. ALGORITMIA.NET de 2008]. Disponible en: http://www.algoritmia.net/articles.php?id=14.

7. HEILMAN, G. L. Estructuras de datos, algoritmos y programación orientada a objetos. La Habana : Félix Varela, 2003.

8. ALGORITMIA.NET Disponible en: http://www.algoritmia.net/articles.php?id=15.

9. GREGORY, H. Estructuras de datos, algoritmos y programación orientada a objetos. La Habana: Félix Varela, 2003.

10. MICTLAN. Página de entrenamiento para el ACM ICPC de la Universidad Tecnológica de la Mixteca. Diccionarios de 2008]. Disponible en: http://mictlan.utm.mx/html/jaws/html/index.php?page/diccionarios.

11. FERRERA, J. C. Diagramas de Voronoi Facultad de Informática. Universidad Politécnica de Madrid: Disponible en: http://www.dma.fi.upm.es/mabellanas/voronoi/voronoi/voronoi.html.

Autor:

Yulaine Arias Guerra.

Universidad de las Ciencias Informáticas

Ciudad de la Habana, Noviembre del 2012.

"Año 54 de la Revolución".

Universidad de las Ciencias Informáticas.

[1] un dato elemental es la mínima información que se tiene en el sistema.

[2] LIFO es el acrónimo correspondiente a Last In First Out, cuya traduccin literal sería: último en entrar, primero en salir.

[3] Balanceados significa que para cada paréntesis abierto existe uno cerrado en el mismo orden.

[4] FIFO es el acrónimo correspondiente a First In First Out, cuya traducción literal sería: primero en entrar, primero en salir.