Estructuración de datos y aplicación en Ingeniería de Sistemas

Introducción

La mayor parte de la información útil en la práctica, no aparece en forma de datos simples aislada de otro tipo de datos, al contrario, aparece de forma estructurada y organizada. Las enciclopedias, diccionarios, revistas, libros en general, son colecciones de datos que serían complejos por no decir imposibles de leer si no hicieran parte de una organización lógica con determinadas reglas.

El agrupar la información y poner en ella una estructura facilita su acceso, administración y hace aún más importante y relevante su contenido. Por ello la importancia de la escogencia de una estructura de datos frente a otra, ya que en el momento de la programación es decisivo el algoritmo a utilizarse para la resolución de determinado problema recordando siempre la ecuación:

"PROGRAMACION = ESTRUCTURA DE DATOS + ALGORITMOS"

En el desarrollo de este ensayo, tendremos la oportunidad de ver las ventajas de estructurar la información de acuerdo a reglas básicas establecidas. Se presentará la forma de catalogación de los datos en estructuras estáticas y dinámicas, así como las estructuras no lineales y estudiaremos la teoría de colecciones de objetos denominada Grafos. .

Concepto de datos estructurados

Un dato simple no supone ningún tipo de estructura diferente a los bits, no obstante se presentan algunas operaciones propias de cada tipo que les da de alguna manera una caracterización. Una estructura de datos se define como una colección de datos de tipo simple que se caracteriza por su organización y las operaciones que se efectúan entre ellos. Esto significa que formalmente podremos expresar mediante un conjunto de reglas, las operaciones y relaciones que se pueden ejecutar sobre los datos.

Un dato de tipo estructurado es una Entidad con un identificador que se constituye por datos de otro tipo de acuerdo con las reglas que definen las estructuras de datos, como por ejemplo: una cadena se forma con una sucesión de caracteres, una [1]matriz se forma por datos simples organizados en filas y columnas y, un archivo se compone de registros y los anteriores por campos que se componen de datos simples.

Figura 1 – Arreglo Matricial

Estructuras de datos estáticas

Arreglo

Es una colección ordenada y homogénea de elementos del mismo tipo y agrupados bajo el mismo nombre de una variable. Los arreglos son utilizados como contenedores que almacenan tipos de datos que se relacionan entre si, como por ejemplo los números reales y los números enteros, entre otros.

Hay tres tipos de arreglos, los Unidimensionales (vectores), los bidimensionales (matrices) y los de tres o más dimensiones (multidimensionales).

Arreglos Unidimensionales

Un arreglo unidimensional conocidos como vectores requieren de subíndice para direccionarse.

Arreglo Bidimensional

Arreglo bidimensional o matriz requiere de los dos índices para el acceso a los datos.

Arreglo Multidimensional

Es un dato de tipo estructurado el cual se compone por n dimensiones y es necesario, para hacer referencia a cada componente, la utilización de n índices, uno para cada dimensión.

Características de un arreglo

• Dimensión, es la longitud y/o cantidad total de datos que lo conforman.

• Indización, indica la posición de cada uno de los elementos dentro de la estructura.

• Tipo, define el tipo de datos que se almacenarán en el arreglo. Cuando no se sabe con seguridad si los datos serán del mismo tipo para todas las posiciones se utiliza la clase [2]Object.

Vectores

Son estructuras estáticas de datos que permiten agrupar datos de un mismo tipo, llamadas también arreglos unidimensionales.

Representación Gráfica

Los vectores se presentan en forma de fila o columna de la siguiente manera:

Figura 2 -[3]Representación Gráfica – Vectores

ESTRUCTURA DINÁMICAS DE DATOS

Las estructuras de datos dinámicas son una colección de elementos denominados nodos en donde la estructura puede aumentar o disminuir durante la ejecución de un programa. Las estructuras de datos dinámicas están clasificadas en:

PRIMERA CLASIFICACIÓN

• Estructuras de datos dinámicas lineales, como lo son las listas enlazadas, las colas, las pilas, las listas dobles, las listas circulares

SEGUNDA CLASIFICACIÓN

• Estructuras de datos no lineales, como lo son los árboles y los grafos

ESTRUCTURAS DE DATOS DINÁMICAS LINEALES

Las estructuras de datos dinámicas lineales están conformadas por las listas, las cuales a su vez son una colección de elementos organizados en forma secuencial que pueden disminuir o aumentar el número de elementos que las integra, esto mediante las operaciones con nodos que pueden ser insertar y/o eliminar.

Listas Enlazadas

Son estructuras dinámicas de datos compuestas por un conjunto de elementos del mismo tipo denominados nodos e interconectados entre sí a través de una o más referencias.

Representación gráfica de Nodo

La representación gráfica de Nodo es un rectángulo conformado por dos campos como mínimo:

• Dato (información), puede ser uno o varios campos

• Referencia, que es el enlace al siguiente [4]nodo

Figura 3 – Representación Gráfica de Nodo

El dato puede ser informativo: código, identificación, dirección, nombres, apellidos, teléfono, correo, etc., en [5]Java corresponden a datos de tipo "int, char, long, doublé"; objetcts tipo String.

Figura 4 – Datos dento de Nodo – Lista

La referencia puede tomas únicamente dos valores únicamente: null (sin direccionamiento) o, la referencia del segundo nodo.

La referencia es también conocida como enlace, link, sigue¿iente nodos, próximo, sig.

Figura 5 – Analogía Dato – Referencia

Tipos de Listas Enlazadas

Una lista enlazada es una secuencia de nodos interconectados entre si y pueden ser de los siguientes tipos:

• Enlazadas simples.

• Doblemente enlazadas.

• Enlazadas y circulares.

• Enlazadas doblemente circulares

Representación Gráfica de una Lista

En la siguiente figura se evidencia la interconexión o enlace del primer nodo con el segundo, el segundo con el tercero y así continúa hasta el último nodo.

Ya que el último nodo no tiene enlace alguno hacia otro nodo, se le da el valor de null, el cual se puede representar: (.) punto, (^) circunflejo, () línea inclinada o, el símbolo de tierra en electrónica.

Figura 6- [6]Simbolo Tierra

Representación de [7]null en un nodo

Figura 7 – Representación null en un nodo

Representación de la Referencia:

Figura 8 – [8]La Referencia de un nodo

Operaciones entre listas enlazadas

Entre listas enlazadas se pueden realizar las siguientes operaciones:

• Recorrido, consiste en visitar los nodos que conforman la lista

• Inserción, consiste en anexar un nodos a la lista de nodos

• Eliminar, consiste en la eliminación de un nodo que pertenece a la lista

• Busqueda, consiste en visitar cada nodo tomando al campo de referencia como el enlace al nuevo nodo a visitar y para realizar la búsqueda es necesario recorrer desde el prier hasta el último nodo

Estructuras dinámicas de datos no lineales

Las estructuras dinámicas de datos no lineales están conformadas por árboles y grafos. A continuación abordaremos los fundamentos de teoría de árboles, más adelante entraremos en detalle con la descripción y teoría de [9]Grafos.

Árboles

Un árbol es una estructura de datos no lineal con jerarquía aplicada a una colección de objetos llamados nodos, en donde uno de ellos se conoce como raíz y de él se genera una relación de parentesco entre los otros nodos dando lugar a los términos padre, hijo, etc. Puesto en otras palabras, un árbol es una colección de nodos interconectados por aristas.

Características de los árboles

• Son estructuras de datos no-lineales, ya que a cada elemento le pueden seguir varios nodos (elementos).

• Es una estructura jerárquica que se aplica sobre una colección de elementos de nombre "nodos", en donde uno de ellos es llamado raíz.

• La jerarquía representada en la relación de parentesco entre los nodos es de padre, hijo, hermano, antecesor, sucesor, ancestro, etc.

• Se utiliza en la representación de fórmula matemáticas, secciones de un libro, numeración de capítulos, organización de información y árboles genealógicos.

• Son jerárquicos ya que sus componentes están a diferente nivel.

• Son dinámicas porque su tamaño, contenido y forma pueden cambiar durante la ejecución, ya que el árbol puede ser vacío, con una raíz y sub árboles.

A continuación se presenta algunas de las representaciones gráficas de los árboles:

Representación de árbol mediante diagrama de Venn

Figura 9 – [10]Diagrama de Venn

Representación de árbol Mediante círculos y flechas (nodo y aristas)

Figura 10 – Nodos y Aristas

Representación de árbol Mediante paréntesis anidados

Figura 11 – Paréntesis anidados

Representación de árbol Mediante Nodos

Elementos de un árbol

Figura 12 – Elementos de un árbol

• Raíz: Nodo que no presenta antecesor

• Rama: [11]arista que conecta dos nodos

• Antecesor: un nodo X es el antecesor de un nodo Y si por las ramas de X se puede llegar a Y.

• Sucesor: un nodos A es sucesor de un nodo B si por las ramas de A se puede llegar a B.

• Grado de un nodos: número de descendientes directos de un nodo.

• Grado del árbol: el mayor grado entre los nodos que lo componen.

• Nodo interno: el que al menos tiene un nodo hijo o descendiente.

• Nodo hoja (externo): no tiene descendientes o nodo hijo, es grado 0.

• Descendiente directo: hijo

• Descendientes: hijo, nieto, bisnieto…

• Subárbol: árbol conformado por un nodos y descendientes

• Padre: antecesor inmediato de un nodo

• Hijo; descendientes inmediatos.

• Descendiente de un nodo: cualquier sucesor de cualquier nodo.

• Hermano de un nodo: otro nodo al que le corresponde el mismo padre.

• Generación: conjunto de nodos los cuales tienen profundidad igual.

• Hoja: nodo sin sucesores, sin hijos.

• Rama: es cualquier camino presente en el árbol

Arbol Binario

Es un conjunto de elementos que puede estar vacío ó estar formado por una raíz con dos árboles binarios disjuntos llamados subárbol izquierdo y subárbol derecho respecto a la raíz. Sus aplicaciones son variadas debido a que se les puede usar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.

Representaciónes de árbol binario en la memoria

• Representación gráfica de un nodo de un árbol

Figura 13 – [12]Nodo de un árbol

• Representación mediante nodos

Figura 14 – Mediante nodos

Operaciones de un árbol

• Recorrer árbol

• Preorden

• Inorden

• Postorden

• Inserción nodo

Grafos

Estructura de datos no lineal que se utiliza para representar las relaciones no siempre jerárquicas entre objetos de datos.

La teoría de los grafos estudia las propiedades de colección de objetos a los que se les llama nodos o vértices conectados por vínculos denominados enlaces, los cuales a su vez, puede no tener ninguna orientación.

En la siguiente figura, los círculos corresponden a los nodos o vértices y las líneas que los unen o enlaces son las [13]aristas.

Figura 15 – Grafo

Un grafo es un par G = (V, E), donde:

• V es un conjunto de puntos de nombre nodos

• E es un conjunto de pares de nodos de nombre enlaces o arcos

• Un enlace {n,m} se puede denotar nm

Generalmente los grafos se clasifican en dirigidos y no dirigidos, dependiendo de si las aristas están orientadas o no y entre grafos con etiquetas o no en función de si las aristas tienen o no tienen información asociada.

Algunas Aplicaciones de los Grafos

• En Internet, al visitar una página y hacer click en algún enlace, visto como grafo, los vértices son los sitios y sus aristas son los enlaces.

• Con la teoría de Grafos es posible resolver problemas planteados en síntesis de circuitos secuenciales, contadores o sistemas de apertura.

• Los Grafos pueden ser útiles en la modelación de trayectos en rutas de buses por calles de una ciudad para obtener rutas óptimas aplicando algoritmos como el [14]Algoritmo de Floyd

• En administración de proyectos se utiliza la técnica de PERT en la que se modelan utilizando grafos se optimizan los tiempos para concretar actividades.

Grafos Dirigidos

Los elementos tienen asociada una dirección

Figura 16 – Grafos Dirigidos – No Dirigidos

El conjunto de vértices es V = { A, B, C, D, E }

Grafos no dirigidos

Figura 17 – Grafos – Aristas – Arcos

La arista es un par de vértices (v,w) si el par está ordenado se dice que el grafo es dirigido o dígrafo.

Adyacencia

Se dice que un vértice es adyacente a otro si existe una arista que los una y la adyacencia puede ser:

• Adyacencia desde

• Adyacencia hasta

Figura 18 – Grafos – Adyacencia

• Los vértices A y B son adyacentes, A es adyacente a B y B es adyacente a C y C es adyacente a D

Camino

Secuencia de vértices que cada uno es adyacente al anterior.

Figura 19 – Grafos – Camino

Camino Simple

Si al partir de cualquier vértice se puede recorrer la estructura del grafo sin repetir algún vértice, arco o arista. Es el grafo cuyos vértices son todos distintos excluyendo posiblemente el primero y el último, por ej., iniciando de D hasta E o partiendo de E hasta D.

Peso o Costo

Las aristas pueden conectar datosy uno de ellos puede ser el peso o costo asociado a esa arista para determinar el costo de recorrer el camino.

Figura 20 – Grafos – Peso o costo

Longitud del camino

Es el número de aristas con que cuenta el grafo. Por ej., del vértice A al F hay dos aristas.

Coste de un camino

La suma de los pesos de sus aristas. Por e., el costo para llegar del vértice A al F puede ser:

7 + 9 = 16 o 1 + 2 + 9 = 12

Es de anotar que a veces el camino m[as corto no es el m[as económico.

Tipos de grafos

Como hemos visto un grafo es un conjunto de nodos unidos por arcos que tienen posiblemente una dirección y se clasifican en:

• Grafos Dirigidos detallados anteriormente

• Grafo No dirigidos detallados anteriormente

• Grafos regulares

Se presentan cuando todos los vértices presentan el mismo grado y el grado de un vértice corresponden al número de aristas que inciden en el mismo vértice:

Figura 21 – Grafo Regular

• Grafos cíclicos

Si un vértice llega al mismo vértice el grafo es cíclico.

Figura 22 – Grafo Cíclico

Conclusiones

La asignatura aporta al ingeniero la capacidad para desarrollar ideas lógicas y a identificar el proceso de desarrollo de aplicaciones enfocado en la resolución de problemas.

Los conceptos de arreglos nos permite ubicar y clasificar los tipos de datos con el objeto de definir variables que nos permiten almacenar números fijos de datos de acuerdo a lineamientos de estructuras de datos estáticas o por lo contrario, cuando se necesita almacenar cantidades de datos no determinadas nos podemos basar en lineamientos de estructuras de datos dinámicas.

Los datos se encuentran generalmente catalogados jerárquicamente, sin embargo a través de los conceptos de árbol podemos estructurar y nombrar cada jerarquía haciendo aprovechando la organización ya establecida para definir una organización detallada donde confluyen capacidades cada vez más grande de datos, lo que nos lleva al concepto de BIG DATA, en donde si bien existen catalogadas grandes cantidades de información, la administración, catalogación y gestión se hacen perentorias, ya que la información es el tesoro más grande para cualquier empresa, corporación o individualidad.

Bibliografía

Title: Fundamentos de programacio´n Author: Corbi´ Bellot, Antonio Date: 1999 eBook Academic Collection (EBSCOhost) – AIU

CAIRÓ, O. & Guardati, S. (2006). Estructuras de Datos. Tercera edición.McGraw-Hill.

VILLALOBOS, JORGE, Introducción a las Estructuras de Datos, Prentice Hall. 2008

http://ece.uprm.edu/~jrosado/oldexams/4102/calc/Matrices.htm – Matrices Complejas, consulta realizada Octubre 07 de 2014

KRUSE. Robert L Estructuras de datos y programas. Editorial: Prentice Hall (México).

http://www.monografias.com/trabajos10/esda/esda, Estructuras de Datos, consultado Obtubre 07 de 2014

Autor:

Angel Alberto Echeverry Castano

NOMBRE DEL CURSO: DATA & INFORMATION STRUCTURE

FECHA: Marzo 27 de 2014LUGAR: Bogotá D.C., Colombia

ATLANTIC INTERNATIONAL UNIVERSITY

[1] Matriz: Arreglo rectangular de números y su tamaño está dado por m x n donde m =fila y n = columna

[2] Object: elemento de programación Java utilizado para almacenar en las posiciones de un arreglo el tipo de dato que se necesite.

[3] Regresentación Gráfica de Vectores – Filas – Columnas

[4] Nodo: Colección de datos simples y su referencia hacia otro nodo

[5] Java – Lenguaje de programación estructurado con base en objetos

[6] Simbolo Tierra – En electrónica este símbolo significa que el circuito está aterrizado

[7] Null: representa ausencia de valor – fin de lista

[8] Referencia de nodo: la representación de la referencia de un nodo es una flecha

[9] Grafos: Estructuras de datos no lineal representada para representar relaciones no jerárquicas entre objetos de datos

[10] Diagrama de Venn: esquemas de graficación utilizados en la teoría de conjuntos

[11] Arista: línea o flecha que interconecta dos nodos representados en un árbol

[12] Nodo de un árbol – representación gráfica en memoria

[13] Arista: línea o flecha que referencian dos nodos en un grafo

[14] Algoritmo de Floyd: algoritmo de análisis sobre grafos que permite encontrar el camino mínimo en grafos dirigidos ponderados