lunes, 1 de septiembre de 2008

Introducción a las Estructuras de Datos (I)

CHenry [chenry@lab.matcom.uh.cu]

En este primer articulo expondremos las bases para poder entender en realidad que es son las estructuras de datos y como son definidas matemáticamente y en algunos casos su uso en la vida práctica. Veremos la importancia que pueden representar en la resolución de algunos problemas el uso de estructuras de datos algo más avanzadas que los arreglos sin quitarle ninguna importancia a estos. En resumen serán introducidos los términos básicos para entender el lenguaje de las ED.

1.1. Definiciones principales.

Dado un problema de la vida real, abordar su solución por la vía computacional será nuestro objetivo. Para ello, dado un conjunto de valores (entrada) se necesita conocer cual es la solución del problema, expresada mediante un conjunto de valores resultantes (salida). Necesitamos entonces conocer qué es un algoritmo y cómo se concibe.

Definición 1:

Se conoce como un algoritmo a una secuencia finita de instrucciones, que son ejecutadas con esfuerzos finitos en un tiempo finito, que recibe un conjunto de valores como entrada y produce un conjunto de valores como salida.

Otra forma de definir un algoritmo es como sigue:
• Secuencia de pasos computacionales que transforma una entrada en una salida (efecto “caja negra”).
• Una herramienta computacional para resolver un determinado problema, en el cual debe estar bien especificada la relación entre la entrada y la salida. El algoritmo materializa (efectúa) dicha relación.
Para solucionar un problema computacional, seguiremos los siguientes pasos:

Seleccionar un modelo matemático–computacional adecuado para el problema, o lo que se llama representación del modelo la cual consiste en seleccionar las estructuras necesarias para representar los datos y su reconocimiento general.

Concebir con respecto a dicho modelo un algoritmo que de solución al problema o diseño del algoritmo, que consiste en la selección de las operaciones necesarias para transformar los datos, utilizando el conocimiento y, en consecuencia, suministrar una solución correcta del problema.

Programar dicho algoritmo y ejecutar el programa en una computadora, entonces seleccionar estrategias de control adecuadas en la aplicación de las operaciones para que se alcance una solución computacional del problema de manera eficiente.

Definición 2:

Un tipo de dato es una colección de objetos caracterizados por un conjunto de operaciones que satisfacen un conjunto de propiedades específicas.

Ejemplo 1:
Tipo de dato: REAL.
Operaciones: Suma (+), resta (-), multiplicación (*), división (/).
Propiedades:
• En la suma:
a + b = b + a
a + (b + c) = (a + b) + c


• En la multiplicación
a * b = b * a ...

• En la división
a / b solo puede efectuarse si b != d.

Definición 3:

Una estructura de datos es una colección de variables, quizás de diferentes tipos, relacionadas (o conectadas) lógicamente de alguna forma y sobre la que se ha definido un conjunto de operaciones que cumplen determinadas propiedades.

Esta definición sugiere reconocer a una variable, como la estructura de datos más simple. Una estructura de datos es lo que se utiliza para lograr una representación, y finalmente implementación, de un tipo de dato.

Ejemplo 2:
• Pila como tipo de dato, vista en términos de su funcionalidad, se definen sus operaciones propias, como push, pop, top y empty y las propiedades que cumplen las mismas (la estrategia LIFO que define su comportamiento).

• Pila como estructura de datos, vista como soporte de almacenamiento de información.

Si vemos una estructura de datos desde el punto de vista de las operaciones que sobre ella se realizan, o sea desde el punto de vista de su funcionalidad y no de la forma en que es almacenada la información, se llega a la distinción de un nuevo tipo de dato.


Artículos relacionados


No hay comentarios: