INTRODUCCION A LA ESTRUCTURA DE DATOS

1.1. CONCEPTOS GENERALES

Como ya sabemos, las computadoras 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 una 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.

Ejemplo: Supongamos que nos enfrentamos a un problema como este: Una empresa que cuenta con 150 empleados, desea establecer una estadística sobre los salarios de sus empleados, y quiere saber cual es el salario promedio, y también cuantos de sus empleados gana entre $1250.00 y $2500.00.

Si tomamos la decisión de tratar este tipo de problemas con datos simples, pronto nos percataríamos del enorme desperdicio de tiempo, almacenamiento y velocidad. Es por eso que para situaciones de este tipo la mejor solución son los datos estructurados.

1.1.1.¿Qué es una estructura de datos?

·         Estructura de Datos describe el conjunto de operaciones que legalmente pueden aplicarse a los elementos de datos.

·         Es una especificación de como almacenar y recuperar datos, tal que sea :

o    Fácil de aprender

o    Conveniente de usar

o    A prueba de idiotas

o    Completamente genérica

o    Independiente del lenguaje

o    Eficiente al ejecutar

·         Estructura de Datos es una definición funcional donde se especifica las operaciones que están permitidas. Esta funcionalidad puede ser aclarada a través de axiomas.

·         Estructura de Datos es una interfase y múltiples implementaciones

·         Estructura de Datos es una colección de datos que pueden ser caracterizados por su organización y las operaciones que se definen en ella.

DEFINICION FORMAL

Se trata de un conjunto de variables de un determinado tipo agrupadas y organizadas de alguna manera para representar un comportamiento. Lo que se pretende con las estructuras de datos es facilitar un esquema lógico para manipular los datos en función del problema que haya que tratar y el algoritmo para resolverlo. En algunos casos la dificultad para resolver un problema radica en escoger la estructura de datos adecuada. Y, en general, la elección del algoritmo y de las estructuras de datos que manipulará estarán muy relacionadas.

Según su comportamiento durante la ejecución del programa distinguimos estructuras de datos:

- Estáticas: su tamaño en memoria es fijo. Ejemplo: arrays.
- Dinámicas: su tamaño en memoria es variable. Ejemplo: listas enlazadas con punteros, ficheros, etc.

Las estructuras de datos que trataremos aquí son los arrays, las pilas y las colas, los árboles, y algunas variantes de estas estructuras. La tabla que se encuentra al comienzo de esta página agrupa todas las estructuras de datos que emplearán los algoritmos explicados en esta web.

1.1.2. ¿Qué es un algoritmo?

Un algoritmo es una lista bien definida, ordenada y finita de operaciones que permite hallar la solución a un problema. Dado un estado inicial y una entrada, a través de pasos sucesivos y bien definidos se llega a un estado final, obteniendo una solución.

Podemos encontrar muchas definiciones de algoritmo en los textos de programación, todas ellas muy similares:

·         Conjunto ordenado y finito de pasos que permite hallar la solución de un problema.

·         Una secuencia de pasos que conducen a la realización de una tarea.

·         Descripción exacta de la secuencia en que se ha de realizar un conjunto de actividades tendientes a resolver un determinado tipo de problema o procedimiento.

·         Conjunto de sentencias / instrucciones en lenguaje nativo, los cuales expresan la lógica de un programa.

·         Es un sistema por el cual se llega a una solución, teniendo en cuenta que debe de ser definido, finito y preciso.

·         Toda receta, proceso, rutina, método, procedimiento, técnica, formula que resuelven un determinado problema.

·         Conjunto de instrucciones concretas y detalladas mediante el cual se consigue una acción determinada.

·         Conjunto de reglas que permiten obtener un resultado determinado a partir de ciertas reglas definidas.

·         Descripción precisa de una sucesión de instrucciones que permite llevar a cabo un trabajo en un número finito de pasos.

·         Un conjunto de símbolos y procedimientos usados en la realización de un cálculo.

Las definiciones mas completas o formales:

·         Secuencia finita de instrucciones, reglas o pasos que describen de forma precisa las operaciones de un ordenador debe realizar para llevar a cabo un tarea en un tiempo mas finito. [Donald E. Knuth, 1968]

·         Descripcion de un esquema de comportamiento expresado mediante un reportorio finito de acciones y de informaciones elementales, identificadas, bien comprendidas y realizables a priori. Este repertorio se denomica lexico [Pierre Scholl, 1988]

·         Un algoritmo es un conjunto finito de pasos definidos, estructurados en el tiempo y formulados con base a un conjunto finito de reglas no ambiguas, que proveen un procedimiento para dar la solución o indicar la falta de esta a un problema en un tiempo determinado. [Rodolfo Quispe-Otazu, 2004]

Características:

Las características fundamentales que debe cumplir todo algoritmo son:

·         Ser definido: Sin ambigüedad, cada paso del algoritmo debe indicar la acción a realizar sin criterios de interpretación.

·         Ser finito: Un número específico y numerable de pasos debe componer al algoritmo, el cual deberá finalizar al completarlos.

·         Tener cero o más entradas: Datos son proporcionados a un algoritmo como insumo (o estos son generados de alguna forma) para llevar a cabo las operaciones que comprende.

·         Tener una o más salidas: Debe siempre devolver un resultado; de nada sirve un algoritmo que hace algo y nunca sabemos que fue. El devolver un resultado no debe ser considerado como únicamente “verlos” en forma impresa o en pantalla, como ocurre con las computadoras. Existen muchos otros mecanismos susceptibles de programación que no cuentan con una salida de resultados de esta forma. Por salida de resultados debe entenderse todo medio o canal por el cual es posible apreciar los efectos de las acciones del algoritmo.

·         Efectividad: El tiempo y esfuerzo por cada paso realizado debe ser preciso, no usando nada más ni nada menos que aquello que se requiera para y en su ejecución.

 1.1.3. Estudio de Algoritmos

·         Las ciencias de la computación son quienes estudian los algoritmos, interesadas en :

o    Máquinas que ejecutan algoritmos

o    Lenguajes que describen algoritmos

o    Fundamentos de los algoritmos

o    Análisis de los algoritmos

§ Tiempo de computación

§ Espacio de computación

·         Un algoritmo es un conjunto finito de instrucciones, el cuál, si se ejecuta, realiza una tarea particular, y debe satisfacer los siguientes criterios :

o    input : cero o más cantidades, las que son provistas externamente.

o    output : al menos una cantidad es producida.

o    ambiguedad : cada instrucción debe ser clara y no ambigua.

o    finitud : en todos los casos el algoritmo debe terminar, luego de un número finito de etapas.

o    efectividad : toda instruccion debe ser posible.

·         Un programa, no es un algoritmo, y puede no cumplir con el criterio de finitud.

1.1.4. Estudio de Datos

·         Las ciencias de la computación son quienes estudian los datos, interesadas en :

o    Máquinas que almacenan datos

o    Lenguajes que describen manipulación de datos

o    Fundamentos de refinamientos de datos, a partir de datos primitivos

o    Análisis de estructuras para representar datos

§ Representación de los datos

§ Algoritmos que operan sobre la estructura

·         Tipo de dato : la clase de datos que una variable puede guardar, por ejemplo, integer

·         Objeto de dato : un conjunto de elementos, por ejemplo, D = { ..., -3, -2, -1, 0, +1, +2, +3, ... }

·         Estructura de dato : describe los conjuntos de objetos de datos y como se relacionan, por ejemplo, arreglos

    TIEMPO DE EJECUCION DE UN PROGRAMA

 El análisis de la eficiencia de un algoritmo estudia el tiempo que tarda un algoritmo en ejecutarse y la memoria que requiere.

El gasto en tiempo y en espacio son normalmente factores contrapuestos. Muchas veces se puede mejorar el tiempo de ejecución a costa de incrementar el espacio ocupado por el algoritmo.

 El tiempo de ejecución se mide contando el número de pasos de programa.

 

1. Los comentarios y las instrucciones de declaración no son pasos de programa.

2. Las expresiones y las instrucciones de asignación son un paso de programa. 

·         Si las expresiones contienen llamadas a funciones al número de pasos se le suma el número de pasos de la función. Si la llamada a la función tiene paso de parámetros por valor hay que tener en cuenta las asignaciones a estos parámetros. Si la función es recursiva deben considerarse también las variables locales, ya que deben ser almacenadas en la pila del sistema.

·         Si las expresiones manejan tipos compuestos (por ejemplo vectores) el número de pasos depende del tamaño de los datos.

3. Las instrucciones de iteración.

·         La ejecución de la parte de control cuenta como el número de pasos de la expresión que debe ser evaluada.

·         El número de pasos necesarios para ejecutar el cuerpo del bucle debe multiplicarse por el número de veces que se ejecuta el bucle.

4. Instrucciones de selección. La ejecución de la parte de control cuenta como el número de pasos de la expresión que debe ser evaluada. Se consideraran las diversas alternativas al contar el número de pasos total del programa.

5. La instrucción de retorno return cuenta como el numero de pasos de la expresión que debe ser evaluada.

 

Tiempo de ejecución:

Se denomina Tiempo de ejecución (Runtime en inglés) al intervalo de tiempo en el que un programa de computadora se ejecuta en un sistema operativo. Este tiempo se inicia con la puesta en memoria principal del programa, por lo que el sistema operativo comienza a ejecutar sus instrucciones. El intervalo finaliza en el momento en que éste envía al sistema operativo la señal de terminación, sea ésta una terminación normal, en que el programa tuvo la posibilidad de concluir sus instrucciones satisfactoriamente, o una terminación anormal, en el que el programa produjo algún error y el sistema debió forzar su finalización.

Suele decirse también que un programa se encuentra "corriendo" mientras está siendo ejecutado.

En tiempo de ejecución pueden darse errores inesperados llamados runtime errors, que pueden ser controlados a través de mecanismos llamados manejos de excepciones.

Este término suele emplearse, en oposición a tiempo de compilación, para indicar si una acción o hecho sucede en uno u otro tiempo.

Tiempo de compilación:

Se denomina tiempo de compilación (compile-time en inglés) al intervalo de tiempo en el que un compilador compila código escrito en un lenguaje de programación a una forma de código ejecutable por una máquina.

El compilador normalmente realiza un chequeo de sintaxis, que incluye entre otros un chequeo de tipos y ejecución de reglas de ámbito, seguido de un análisis semántico, que se compone de procesos como el enlazado estático, la instanciación de plantillas y la optimización del código generado. El enlazado dinámico se realiza normalmente después del tiempo de compilación, bien en tiempo de ejecución o antes de éste, por medio de un cargador de programas. El chequeo de límites de arras normalmente no se hace en tiempo de compilación.

Este término suele emplearse, en oposición a tiempo de ejecución, para indicar si una acción o hecho sucede en uno u otro tiempo.

 

El tiempo de compilación no sucede en los lenguajes interpretados debido a que éstos no necesitan compilarse. En dichos lenguajes, ciertas acciones típicas de la compilación como es la comprobación de la sintaxis se realizan antes de comenzar a ejecutar el código, pero no es propiamente una compilación.