Unidad de Aprendizaje
"Estructuras de Datos"
18-19/2 Enero - Junio 2019
ESCOM IPN - ISC Plan 2009
18-19/2 Enero - Junio 2019
ESCOM IPN - ISC Plan 2009
20 % Ejercicios (Escritos, programas, y simulaciones)*
50 % Practicas**
30 % Evaluaciones en clase (Escritas y/o prácticas)*
*Individuales
**En equipo
Con la implementación del TAD Pila en C, (estática y dinámica) implementar un programa que valide y evalué una expresión infija p.g. A*((B+D)/C)+E^A. El programa mostrará el resultado de pasar la expresión a posfija y finalmente la evaluación de la expresión.
Con la implementación del TAD Cola en C, (estática, estática circular y dinámica) resolver los programas que realizan las siguientes tres simulaciones: simulación de la atención de clientes en un supermercado, simulación de la ejecución de procesos en el sistema operativo y simulación de la atención en un banco con prioridades.
Con la implementación del TAD lista realizar la implementación de una tabla hash abierta, capaz de soportar el almacenamiento de palabras y sus definiciones (Diccionario de palabras).
Programar en ANSI C la implementación recursiva del término n de la serie de Fibonacci y Tribonacci, así como la implementación recursiva de las Torres de Hanoi para n discos.
Programar en ANSI C la solución por backtraking al problema de las N-Reinas, el cuál consiste en colocar n reinas en un tablero de ajedrez de tamaño N*N de forma la reinas no se amenacen según las normas del ajedrez.
Con la implementación del TAD árbol binario y la implementación de las reglas el ABB, construir un árbol AVLcapaz de almacenar palabras y sus definiciones (Diccionario de palabras).
Presentación de la Unidad de Aprendizaje (Introducción, unidades tematicas, formato de las evaluaciónes, tareas, practicas y acuerdos).
La abstracción es una operación intelectual que ignora selectivamente partes de un todo para facilitar su comprensión, en computación pudiendose hacer una abtracción por Parametrización y una por Especificación. Se pueden realizar tres abstracciones distintas: Abstracción Procedimental, Abstracción de Iteración y Abstracción de Datos; esta última puede a su vez abstraer Tipos de datos simples, Tipos de datos definidos por el programador y TAD's. Un Tipo Abstracto de Dato (TAD) es una entidad abstracta formada por un conjunto de datos organizados en cierta estructura y una colección de operaciones asociadas especificados formalmente.
Uno de los conceptos más útiles en computación es la pila o stack, esta es una estructura, en la que los elementos se añaden y se remueven por un solo extremo; este extremo es llamado “tope” de la pila. A las pilas se les llama también listas LIFO (last-in first-out) o listas “ultimo en entrar, primero en salir”. Hablamos de una Estructura de datos estática cuando se le asigna una cantidad fija de memoria para esa estructura antes de la ejecución del programa. En el caso del TAD Pila, nos bastara para su implementación en C, el empleo de arreglos estáticos de elementos. Hablamos de una Estructura de datos dinámica cuando se le asigna memoria a medida que es necesitada, durante la ejecución del programa. En el caso de el TAD Pila su implementación dinámica en C deberá de realizarse con ayuda de las funciones de memoria dinámica malloc() & free(). Una de las aplicaciones clásicas del TAD Pila es la evaluación de expresiones infijas. En la solución de este problema el TAD Pila se emplea para la validación de paréntesis, la conversión a postfijo y la evaluación de una expresión postfija.
Uno de los conceptos más abundantes en la vida cotidiana es la cola (Queue). Una COLA es otro tipo especial de Lista en el cual: los elementos se insertan en un extremo (el final) y la supresiones tienen lugar en el otro extremo (frente). A las colas se les llama también Listas FIFO (first in first out) o Listas (primero en entrar, primero en salir). Son ampliamente utilizadas para gestionar recursos por parte del sistema operativo, gestionar peticiones de servicio y otro tipo de procesos de sistemas gestores de bases de datos.
Las listas son la generalización de los dos TAD’s anteriores (Pila y Cola): mientras que en una pila y en una cola las operaciones sólo afectan a un extremo de la secuencia, en una lista se puede insertar un elemento en cualquier posición, y borrar y consultar cualquier elemento. Una lista es: una colección de 0 o más elementos de un mismo tipo y sus elementos están colocados uno detrás de otro a cada elemento de una lista se conoce con el nombre de NODO. Las listas son mucho más flexibles que los arreglos ya que permiten trabajo “dinámico” con un grupo de elementos.
Una tabla hash o mapa hash es una estructura de datos que asocia llaves o claves con valores. La operación principal que soporta de manera eficiente es la búsqueda: permite el acceso a los elementos almacenados a partir de una clave de este. Funciona transformando la clave con una función hash en un hash, un número que la tabla hash utiliza para localizar el valor deseado.
La recursividad es un recurso muy poderoso que permite expresar soluciones simples y naturales a ciertos tipos de problemas. Es importante considerar que no todos los problemas son naturalmente recursivos. Un objeto recursivo es aquel que aparece en la definición de si mismo, así como el que se llama a sí mismo.
Backtracking (vuelta atrás) es una estrategia para encontrar soluciones a problemas que satisfacen restricciones. El principio de backtracking (vuelta atrás) se suele aplicar en la resolución de un gran número de problemas, muy especialmente en juegos y problemas de optimización. El backtraking realiza una búsqueda exhaustiva y sistemática en el espacio de soluciones del problema. Se utilizan para resolver problemas para los que no existe un algoritmo eficiente para resolverlos.
Un árbol binario es una estructura de datos de tipo árbol en donde cada uno de los nodos del árbol puede tener 0, 1, ó 2 subárboles llamados de acuerdo a su caso como: Si el nodo raíz tiene 0 relaciones se llama hoja, si el nodo raíz tiene 1 relación a la izquierda, el segundo elemento de la relación es el subárbol izquierdo, si el nodo raíz tiene 1 relación a la derecha, el segundo elemento de la relación es el subárbol derecho.
Un árbol binario de búsqueda es un tipo especial de árbol binario cuya principal característica es que la información se almacena en los nodos cuidando mantener cierto orden. En un ABB sus nodos también son ABB y contienen información ordenada de tal manera que todos los elementos a la izquierda de la raíz son menores a la raíz y todos los elementos a la derecha de la raíz son mayores a la raíz.
Un árbol AVL es un Árbol Binario de Búsqueda al que se le añade una condición de equilibrio, la cual dice que: “Para todo nodo la altura de sus subárboles izquierdo y derecho pueden diferir a lo sumo en 1”. Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O(log n).
Un árbol rojo-negro es un árbol binario de búsqueda en el que cada nodo tiene un atributo de color cuyo valor es rojo o negro. Es un tipo especial de árbol para organizar información compuesta por datos comparables (por ejemplo, números). En los árboles rojo-negro las hojas no son relevantes y no contienen datos. En los árboles rojo-negro, como en todos los árboles binarios de búsqueda, es posible moverse ordenadamente a través de los elementos de forma eficiente si hay forma de localizar el padre de cualquier nodo. El tiempo de desplazarse desde la raíz hasta una hoja a través de un árbol equilibrado que tiene la mínima altura posible es de O(log n).
El montículo es una estructura de datos basada en un árbol binario que soporta solamente 3 operaciones: conocer la cima del montículo y eliminar el elemento de la cima y agregar un nuevo elemento. Los montículos máximos tienen la característica de que cada nodo padre tiene un valor mayor que el de cualquiera de sus nodos hijos, mientras que, en los montículos mínimos, el valor del nodo padre es siempre menor al de sus nodos hijos. Un árbol cumple la condición de montículo si satisface dicha condición y además es un árbol binario casi completo. Un árbol binario es completo cuando todos los niveles están llenos, con la excepción del último, que se llena desde la izquierda hacia la derecha.
En las ciencias de la computación, los árboles-B o B-árboles son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Al igual que los árboles binarios de búsqueda, son árboles balanceados de búsqueda, pero cada nodo puede poseer más de dos hijos.1 Los árboles B mantienen los datos ordenados y las inserciones y eliminaciones se realizan en tiempo logarítmico amortizado.
Un árbol de segmento es una estructura de datos en forma de árbol para guardar intervalos o segmentos. Permite consultar cuál de los segmentos guardados contiene un punto. Este es, en principio, una estructura estática; es decir, su contenido no puede ser modificado una vez que su estructura es construida. Un árbol de segmento para un conjunto I de n intervalos usa O(n log n) de memoria de almacenamiento y puede construirse en un tiempo O(n log n). Los árboles de segmento soportan búsqueda para todos los intervalos que contienen un punto de consulta en O (log n + k), k el número de intervalos o segmentos recuperados. Algunas aplicaciones del árbol de segmento son vistas en las áreas de la geometría computacional y en los sistemas de información geográfica. El árbol de segmentos puede generalizarse para espacios multidimensionales.
Un trie es una estructura de datos de tipo árbol que permite la recuperación de información. La información almacenada en un trie es un conjunto de claves, donde una clave es una secuencia de símbolos pertenecientes a un alfabeto. Las claves son almacenadas en las hojas del árbol y los nodos internos son pasarelas para guiar la búsqueda. El árbol se estructura de forma que cada letra de la clave se sitúa en un nodo de forma que los hijos de un nodo representan las distintas posibilidades de símbolos diferentes que pueden continuar al símbolo representado por el nodo padre. Por tanto la búsqueda en un trie se hace de forma similar a como se hacen las búsquedas en un diccionario.
En matemáticas y ciencias de la computación, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto. La búsqueda en anchura (BFS Breadth First Search) es un algoritmo para recorrer o buscar elementos en un grafo (usado frecuentemente sobre árboles). Intuitivamente, se comienza en un nodo y se exploran todos los vecinos de este nodo. A continuación para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol. Una Búsqueda en profundidad (DFS - Depth First Search) es un algoritmo que permite recorrer todos los nodos de un grafo de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, regresa (Backtracking), de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado.