Estructuras de datos


Datos

Este es un tema denso, pero fundamental a la hora del manejo de datos. Un conjunto de datos aislado y desordenado de nada sirve. ¿Te imaginas un diccionario en el que todas las palabras estuviesen desordenadas? Aunque nos diera de forma exacta el significado de cada palabra, un diccionario así, de nada serviría.

La organización y estructura de datos es, por tanto, algo fundamental a la hora de hacer uso de los mismos. En el ejemplo anterior, un diccionario contiene miles de palabras y la ordenación alfabética es una ordenación válida y útil. Pero si en vez de contener miles de entradas contuviera unas pocas, por ejemplo, las relativas a países, lo mismo convenía ordenarlos por continentes y dentro de los mismos alfabéticamente. La forma de ordenar unos datos influye a la hora de tener acceso a los mismos.

Una estructura de datos es una colección de datos organizada. En este sentido, un dato puede ser tan simple como un número entero, o tan complejo, como una matriz de números.

Las estructuras pueden ser contiguas, seguidas unas de otras (cadenas, arrays (vectores, matrices, o arrays multidmensionales), registros) o enlazadas, los datos no están contiguos en la memoria. También pueden ser estáticas, cuando el tamaño ocupado en la memoria no puede modificarse, o dinámicas, cuando pueden cambiar de tamaño.

Las estructuras dinámicas se representan por un tipo de dato denominado puntero, que es el dato que indica la posición en la memoria de otro dato.

El objeto de la programación está relacionada con la obtención de un algoritmo que resuelva los problemas de la forma más eficiente posible. Para saber si hemos resuelto el problema de una forma eficiente, debemos conocer la complejidad algorítmica.

Determinar la complejidad de un algoritmo no es tarea sencilla. Está relacionada con el número de operaciones elementales que es preciso realizar. Según el grado del polinomio, así será la complejidad, existiendo lineales, cuadrados, cubicos, etc. Cuando aumenta el grado, aumenta notablemente el número de operaciones, y por tanto el tiempo de resolverlo. Por tanto, es importante estimar la complejidad de un algoritmo.

La recursión es una forma de hallar la solución de un problema mediante soluciones de pequeñas instancias del problema. Un algoritmo recursivo es un algoritmo que expresa la solución de un problema llamándose a sí mismo (llamada recursiva o recurrente). El Teorema maestro se usa para determinar la complejidad de un algoritmo.


1. Estructuras de datos

- Lectura: Instituto de Robótica - U. de Valencia. Estructuras de datos (pdf)




2. Archivos y bases de datos

- Lectura: Instituto de Robótica - U. de Valencia. Archivos y bases de datos (pdf)



3. Complejidad de los algoritmos

- Lectura: Instituto de Robótica - U. de Valencia. Algoritmos y su complejidad (pdf)




4. Teorema maestro

- Lectura: Wikipedia. Teorema maestro
- Presentación: Marcelo Arenas. El Teorema Maestro




Algoritmos

0 comentarios:

Publicar un comentario