Estructura de Datos (resumen)

Efraín Buenrostro Chávez

UNIDAD 1 Introducción a las estructuras de datos
Tipos de datos
Un tipo de datos es una colección de valores.
Utilizando distintos criterios, podemos clasificar los tipos de datos de Pascal:
-Según si modifican su valor en ejecución: constantes (const) y variables (var).
-Según su composición:
1. Elementales:
a) Predefinidos: enteros (integer), lógicos (boolean), caracteres (char), reales (real).
b) Definidos por el usuario: enumerados y subrangos.
2. Estructurados:
a) Predefinidos: matrices (array), cadena de caracteres (string), registros (record), ficheros (file), ficheros de texto (text), conjuntos (set), punteros (pointer) y objetos (object).
b) Definidos por el usuario: procedimientos (procedure, function) y otros (TADs).
-Según la naturaleza de los valores: numéricos (integer, real) y caracteres (char, string).
-Según su almacenamiento en memoria (¿Cómo? y ¿Dónde?): estáticos (simples y estructurados) y dinámicos (punteros, variables dinámicas).
-Según su ordenación: ordinales (integer, boolean, char, enumerados, subrango) y escalares (integer, boolean, char, real).
TIPOS DE DATOS ABSTRACTOS
Una abstracción es la simplificación de un objeto o de un proceso de la realidad en la que sólo se consideran los aspectos más relevantes. La abstracción se utiliza por los programadores para dar sencillez de expresión al algoritmo.
La abstracción tiene dos puntos de vista en programación:
La abstracción funcional:
- Permite dotar a la aplicación de operaciones que no están definidas en el lenguaje en el que se está trabajando.
- Se corresponden con el mecanismo del subprograma (acción que se realiza y argumentos a través de los cuales toma información y devuelve resultados).
- Es irrelevante cómo realiza la acción y no importa su tiempo de ejecución.
Las abstracciones de datos (= Clase):
- Permiten utilizar nuevos tipos de datos que se definirán especificando sus posibles valores y las operaciones que los manipulan.
- Cada operación constituye una abstracción funcional.

Un tipo abstracto de datos (TAD) es un tipo definido por el usuario que: a) Tiene un conjunto de valores y un conjunto de operaciones. b) Cumple con los principios de abstracción, ocultación de la información y se puede manejar sin conocer la representación interna.
Es decir, los TADs ponen a disposición del programador un conjunto de objetos junto con sus operaciones básicas que son independientes de la implementación elegida.

Modularidad
En programación modular, y más específicamente en programación orientada a objetos, se denomina Modularidad a la propiedad que permite subdividir una aplicación en partes más pequeñas (llamadas módulos), cada una de las cuales debe ser tan independiente como sea posible de la aplicación en sí y de las restantes partes. Estos módulos que se puedan compilar por separado, pero que tienen conexiones con otros módulos. Al igual que la encapsulación, los lenguajes soportan la Modularidad de diversas formas.
Según Bertrand Meyer "El acto de particionar un programa en componentes individuales para reducir su complejidad en algún grado. A pesar de particionar un programa es útil por esta razón, una justificación más poderosa para particionar un programa es que crea una serie de límites bien definidos y documentados en el programa. Estos límites, o interfaces, son muy valiosos en la comprensión del programa".
Por su parte Bárbara Liskov establece que "modularización consiste en dividir un programa en módulos que pueden ser compilados de forma separada, pero que tienen conexiones con otros módulos".



Manejo de memoria
El problema con la memoria estática de memoria es que siempre se reserva antes de conocer los datos concretos del problema y esto origina reservar siempre un máximo de memoria que en la mayoría de las veces no se va a necesitar.

Memoria dinámica:
La reserva de memoria dinámica se hace en tiempo de ejecución después de leer los datos y de conocer el tamaño exacto del problema. Como consecuencia se adapta mucho mejor a las necesidades en cada caso.
El sitio donde se almacenan los objetos se denominan en ingles heap o free store traducido como montículo o memoria libre, y el sitio preciso donde se encuentre depende del compilador y el tipo de puntero utilizado. La creación y destrucción de los objetos está en manos del programador a través de los operadores new y delete.
En C# las variables que se declaran son punteros y se pasan eficientemente con referencia, tampoco es necesario considerar la liberación de la memoria puesto que framework se encarga de liberar todas las referencias que no se estén utilizando y compactar la memoria para mejorar el rendimiento.

Memoria Estática
La forma más fácil de almacenar el contenido de una variable en memoria en tiempo de ejecución es en memoria estática o permanente a lo largo de toda la ejecución del programa.

Ventajas de utilizar memoria dinámica vs memoria estática
La memoria dinámica sirve para que los programadores se adapten siempre al tamaño del problema que tienen que resolver sin desperdiciar recursos de memoria y esto se traduce en una mayor eficiencia en la ejecución de los programas, las ventajas de utilizar memoria dinámica se valoran mejor en comparación con la utilización de la reserva de la memoria estática, como se muestra en el siguiente cuadro.


UNIDAD 2 Recursividad
Recurrencia, recursión o recursividad es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente círculo sin fin en esta definición:
Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (< N) del mismo problema y se conozca la solución explícita a las instancias más simples, lo que se conoce como casos base, se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas.
Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva o recurrente.
Generalmente, si la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de un tamaño menor que N. De esta forma, al ir reduciendo progresivamente la complejidad del problema que resolver, llegará un momento en que su resolución sea más o menos trivial (o, al menos, suficientemente manejable como para resolverlo de forma no recursiva). En esa situación diremos que estamos ante un caso base de la recursividad.

Las claves para construir un subprograma recurrente son:
Cada llamada recurrente se debería definir sobre un problema de menor complejidad (algo más fácil de resolver).
Ha de existir al menos un caso base para evitar que la recurrencia sea infinita.
Es frecuente que los algoritmos recurrentes sean más ineficientes en tiempo que los iterativos aunque suelen ser mucho más breves en espacio.


UNIDAD 3 Estructuras lineales
Estructuras lineales
Las estructuras lineales de datos se caracterizan porque sus elementos están en secuencia, relacionados en forma lineal, uno luego del otro. Cada elemento de la estructura puede estar conformado por uno o varios sub-elementos o campos que pueden pertenecer a cualquier tipo de dato, pero que normalmente son tipos básicos. Una estructura lineal de datos os lista está conformada por ninguno, uno o varios elementos que tienen una relación dónde existe un primer elemento, seguido de un segundo elemento y así sucesivamente hasta llegar al último. El valor contenido en los elementos pueden ser el mismo o diferente. En estas estructuras se realizan operaciones de agregar y/o eliminar elementos a la lista según un criterio particular.
Pila
Una pila es un subtipo de las listas donde el acceso está restringido a un solo extremos de la lista, en este caso al tope de la misma. Un ejemplo de esta estructura es una pila de bandejas de un restaurante de comida rápida (self service) o una pila de platos. Las operaciones básicas sobre una pila son: crearla, destruirla, agregar un nuevo elemento, suprimir un elemento, consultar el elemento del tope y verificar si está vacía.

Cola
Una cola es otro subtipo de las listas donde el acceso está restringido a los extremos de la lista, es decir al inicio y al fin de la misma. Un ejemplo de esta estructura es una cola de personas en un restaurante de comida rápida (self service) ejemplo, se tiene que cualquier cliente del restaurante, al llegar entra a la fila de clientes que van a comer en el mismo por el final de la fila. Las operaciones básicas son: creación, destrucción, inserción al final de un nuevo elemento, eliminación del inicio de un elemento, consultar que elemento está al inicio y cual al final, y verificar si la cola está vacía.

Dipolo
Esta estructura equivale a dos colas colocadas una en un sentido y la otra en sentido contrario, por ello las operaciones de inserción y eliminación se pueden realizar por ambos extremos. Dos casos especiales se pueden tener, el dipolo de entrada restringida donde sólo se puede insertar por un extremo y eliminar por ambos, y el dipolo de salida restringida, donde se puede insertar por ambos extremos y sólo se puede suprimir por un extremo. Se llamará a estos extremos como izquierdo (izq) y derecho (der).

Lista
La lista es el tipo más general de estructura lineal donde las inserciones y eliminaciones se hacen en cualquier punto de la lista, por ello se debe especificar donde se requiere que se haga la operación. Sus operaciones básicas son: creación, destrucción, inserción, eliminación, consulta y verificación de lista vacía.


UNIDAD 4 Estructuras no lineales
Grafo
Es un conjunto de puntos y un conjunto de líneas, cada una de las cuales une un punto con otro. Los puntos se llaman nodos o vértices de un grafo y las líneas se llaman aristas o arcos.

Nodo
Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él.

Aristas
Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.

Aristas Adyacentes: Se dice que dos aristas son adyacentes si coinciden en el mismo vértice.
Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.
Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.
Cruce: Son dos aristas que cruzan en un punto.

Vértices
Son los puntos o nodos con los que está conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.

Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.
Vértice Aislado: Es un vértice de grado cero.
Vértice Terminal: Es un vértice de grado 1.

Clasificación de los grafos

Dirigidos
Cada arco está representado por un par ordenado de vértices, de forma que representan dos arcos diferentes.

No dirigidos
En este el par de vértices que representa un arco no está ordenado




Tipos de grafos
Grafo regular: Aquel con el mismo grado en todos los vértices.

Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto

Grafo completo: Aquel con una arista entre cada par de vértices

Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados.

Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.

Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro

Grafos conexos: Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: "un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une".

Grafos dirigidos (bigrafo): A un grafo dirigido se le puede definir como un grafo que contiene aristas dirigidas, como en el siguiente caso.


UNIDAD 5 Métodos de ordenamiento

Ordenamiento interno
Los algoritmos de ordenamiento interno son aquellos que son manejados usando la memoria primaria, es decir la memoria de trabajo o memoria RAM. A estos algoritmos se les conoce porque su uso es con listas simples, los datos son de un solo tipo y se ordenan mientras se esté trabajando con la lista de forma preliminar, es decir; usando la lista, ya sea que los datos se inserten, o que se inicialicen.

Entre los algoritmos de ordenamiento interno tenemos:
Ordenamiento de Burbuja
El método de la burbuja es una comparación lineal con cada uno de los elementos, el elemento que sea menor contra el que se está comparado intercambiaran posiciones. Este método no es recomendado para grandes comparaciones, ya que es un proceso muy lento y requiere de una gran cantidad de Memoria RAM.

Ordenamiento Shell
Esta forma de ordenación es muy parecida a la ordenación con burbuja. La diferencia es que no es una comparación lineal, sino que trabaja con una segmentación entre los datos. Por lo tanto es un buen método, pero no el mejor para implementarlos en grandes arreglos.

Ordenamiento Quick Sort
El ordenamiento rápido (quicksort en inglés) es un algoritmo creado por el científico británico en computación C. A. R. Hoare basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

Ordenamiento Radix
El ordenamiento Radix (radix sort en inglés) es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y, especialmente, números en punto flotante especialmente formateados, radix sort no está limitado sólo a los enteros.




Ordenamiento externo

Los algoritmos de ordenamiento externo son aquellos que para su uso utiliza la memoria secundaria, es decir disco duro. Estos algoritmos se usan cuando se tienen registros y/o archivos, ya que su uso es para el manejo de datos ya sean del mismo tipo o distinto tipo y estos pueden quedar almacenados ya ordenados.

Entre los algoritmos de ordenamiento externo se encuentran:
Intercalación Simple
El método de ordenación por mezcla directa es probablemente el más utilizado por su fácil comprensión. La idea central de este algoritmo consiste en la realización sucesiva de una partición y una fusión que produce secuencias ordenadas de longitud cada vez mayor.

Ordenamiento Merge
Este método de llama mezcla porque combina dos o más secuencias en una sola secuencia ordenada por medio de la selección repetida de los componentes accesibles en ese momento. Un arreglo individual puede usarse en lugar de dos secuencias si se considera como de doble extremo. En este caso se tomaran elementos de los dos extremos del arreglo para hacer la mezcla.

Método de Hash
En este método se requiere que los elementos estén ordenados. El método consiste en asignar el índice a cada elemento mediante una transformación del elemento, esto se hace mediante una función de conversión llamada función hash. Hay diferentes funciones para transformar el elemento y el número obtenido es el índice del elemento.


UNIDAD 6 Métodos de búsqueda
La búsqueda es la operación más importante en el procesamiento de información, ya que permite recuperar datos previamente almacenados. El resultado de una búsqueda puede ser un éxito, si se encuentra la información o un fracaso, si no la encuentra.

La búsqueda se puede aplicar sobre elementos previamente ordenados o sobre elementos desordenados, en el primer caso la búsqueda es más fácil, en cambio en el segundo se dificulta un poco más el proceso, sobre todo cuando de se trata de encontrar una cantidad de elementos similares.

Secuencial
El método de búsqueda secuencial externa consiste en revisar el archivo elemento por elemento hasta encontrar el dato que se está buscando, o hasta llegar al final del archivo. Este método de búsqueda se puede aplicar a archivos ordenadas o desordenadas. Si la búsqueda se aplica a un archivo desordenado y el elemento que se está buscando existe más de una vez, el proceso de búsqueda debe continuar hasta que se llegue al fin del archivo.

Binaria
El método de búsqueda binaria externa utiliza el mismo principio que la búsqueda binaria interna. Divide el total de elementos del archivo en dos, comparando el elemento buscado con el central, en caso de no ser iguales se determina si el elemento buscado es menor o mayor al central, para determinar si la búsqueda continua del lado izquierdo (menor) o derecho (mayor) del central, repitiendo el mismo proceso de división y comparación, hasta encontrar el elemento buscado o que la división ya no sea posible. El archivo debe estar ordenado y se debe conocer el número de elementos del mismo para aplicar este método.

Hash
El método de búsqueda hash o por transformación de clave aumenta la velocidad de búsqueda sin necesidad de que los elementos estén previamente ordenados, comparándolo con los métodos anteriores. Además tiene la ventaja de que el tiempo de búsqueda es independiente del número de elementos de la estructura que los almacena.

Este método permite que el acceso a los datos sea por una llave que indica directamente la posición donde están guardados los datos que se buscan. Prácticamente trabaja con una función que transforma la llave o dato clave en una dirección (índice) dentro de la estructura y que en ocasiones puede generar una colisión, que se define como una misma dirección para dos o más claves distintas.


UNIDAD 7 Análisis de los algoritmos

El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes.

A la hora de realizar un análisis teórico de algoritmos es común calcular su complejidad en un sentido asintótico, es decir, para un tamaño de entrada suficientemente grande. La cota superior asintótica, y las notaciones omega (cota inferior) y theta (caso promedio) se usan con esa finalidad. Por ejemplo, la búsqueda binaria decimos que se ejecuta en una cantidad de pasos proporcional a un logaritmo, en O(log(n)), coloquialmente "en tiempo logarítmico". Normalmente las estimaciones asintóticas se utilizan porque diferentes implementaciones del mismo algoritmo no tienen por qué tener la misma eficiencia. No obstante la eficiencia de dos implementaciones "razonables" cualesquiera de un algoritmo dado está relacionada por una constante multiplicativa llamada constante oculta.

La medida exacta (no asintótica) de la eficiencia a veces puede ser computada pero para ello suele hacer falta aceptar supuestos acerca de la implementación concreta del algoritmo, llamada modelo de computación. Un modelo de computación puede definirse en términos de un ordenador abstracto, como la Máquina de Turing, y/o postulando que ciertas operaciones se ejecutan en una unidad de tiempo. Por ejemplo, si al conjunto ordenado al que aplicamos una búsqueda binaria tiene 'n' elementos, y podemos garantizar que una única búsqueda binaria puede realizarse en un tiempo unitario, entonces se requieren como mucho log2 N + 1 unidades de tiempo para devolver una respuesta.

Las medidas exactas de eficiencia son útiles para quienes verdaderamente implementan y usan algoritmos, porque tienen más precisión y así les permite saber cuánto tiempo pueden suponer que tomará la ejecución. Para algunas personas, como los desarrolladores de videojuegos, una constante oculta puede significar la diferencia entre éxito y fracaso.

Las estimaciones de tiempo dependen de cómo definamos un paso. Para que el análisis tenga sentido, debemos garantizar que el tiempo requerido para realizar un paso se encuentre acotado superiormente por una constante. Hay que mantenerse precavido en este terreno; por ejemplo, algunos análisis cuentan con que la suma de dos números se hace en un paso. Este supuesto puede no estar garantizado en ciertos contextos. Si por ejemplo los números involucrados en la computación pueden ser arbitrariamente grandes, dejamos de poder asumir que la adición requiere un tiempo constante (usando papel y lápiz, compara el tiempo que necesitas para sumar dos enteros de 2 dígitos cada uno y el necesario para hacerlo con enteros de 1000 dígitos).


Concepto de complejidad de algoritmos.

La mayoría de los problemas que se plantean en la actualidad se pueden resolver con algoritmos que difieren en su eficiencia. Dicha diferencia puede ser irrelevante cuando el número de datos es pequeño pero cuando la cantidad de datos es mayor la diferencia crece. La complejidad de un algoritmo o complejidad computacional, estudia los recursos y esfuerzos requeridos durante el cálculo para resolver un problema los cuales se dividen en: tiempo de ejecución y espacio en memoria. El factor tiempo, por lo general es más importante que el factor espacio, pero existen algoritmos que ofrecen el peor de los casos en un menor tiempo que el mejor de los casos, lo cual no es la mejor de las soluciones.

El factor tiempo de ejecución de un algoritmo depende de la cantidad de datos que se quieren procesar.

Aritmética de la notación O.

La notación asintótica "O" (grande) se utiliza para hacer referencia a la velocidad de crecimiento de los valores de una función, es decir, su utilidad radica en encontrar un límite superior del tiempo de ejecución de un algoritmo buscando el peor caso.

La definición de esta notación es la siguiente:
f(n) y g(n) funciones que representan enteros no negativos a números reales. Se dice que f(n) es O(g(n)) si y solo si hay una constante real c>0 y un entero constante n0>=1 tal que f(n)= n0.

Nota: el orden de magnitud de una función es el orden del término de la función más grande respecto de n.

La notación asintótica "O" grande se utiliza para especificar una cota inferior para la velocidad de crecimiento de T(n), y significa que existe una constante c tal que T(n) es mayor o igual a c(g(n)) para un número infinito de valores n.

Regla para la notación O

Definición: (O)T(n) es O(f(n)) si existen las constantes positivas c y n0 tales que n >= n0 se verifica T(n)