Actividad 9. Tabla de análisis blackboard lógica y programación estructurada PDF

Preview

Summary

Download Actividad 9. Tabla de análisis blackboard lógica y programación estructurada PDF

Description

Eleme ntos / Aspect os

Caracte rísticas

Ventaja s

Estructuras de datos Lista enlazada

Tablas de hash

Tiene un nombre de variable único que representa a cada elemento dentro de él y estos elementos son diferenciados por un índice. Los elementos dentro del array son guardados en posiciones de memoria de forma continua.

La lista enlazada es una estructura de datos dinámica cuyos nodos suelen ser normalmente registros y que tienen un tamaño fijo.

- Las matrices ayudan en la optimización del código. Podemos almacenar una gran cantidad de valores en una sola matriz escribiendo un pequeño fragmento de código en lugar de declarar cada variable por separado. - Las matrices son fáciles de

- Las listas son dinámicas, es decir, se pueden almacenar en ellas tantos elementos como se necesiten, siempre y cuando haya espacio suficiente en la memoria de la computadora. - Al insertar un elemento en la lista, la operación tiene un

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 generada usando el nombre, número de cuenta o id. - Una tabla hash tiene como principal ventaja que el acceso a los datos suele ser muy rápido si se cumplen las siguientes condiciones: - Una razón de ocupación no muy elevada (a partir del 75% de ocupación se producen demasiadas

Array

Pilas

Colas

Arboles

Una pila (stack en inglés) es una lista ordenada o estructura de datos que permite almacenar y recuperar datos, siendo el modo de acceso a sus elementos de tipo LIFO (del inglés Last In, First Out, «último en entrar, primero en salir»).

Una cola (también llamada fila) es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pull por el otro.

En este caso no existe el problema de tener que fijar el tamaño máximo de la pila, es decir, no se necesita saber la cantidad de elementos que va a contener. Esto se debe a que al ser implementada s a base de punteros, se va tomando memoria a

- Las colas son útiles cuando los consumidores múltiples comparten un determinado proceso. - Las colas pueden conducir a espacios vacíos en la estructura de datos. - Las colas de datos son un método rápido de comunicación

Un árbol es una estructura (posiblemente no lineal) de datos compuesta de nodos, vértices y aristas que es acíclica. Un árbol que no tiene ningún nodo se llama árbol vacío o nulo. Un árbol que no está vacío consta de un nodo raíz y potencialment e muchos niveles de nodos adicionales que forman una jerarquía. - El número de accesos al árbol es menor que en una lista enlazada. - Por ejemplo, en un árbol lleno que tenga n nodos el camino más largo que hay que recorrer es log2(n+1).

Desven tajas

usar, ya que muchos algoritmos, como las técnicas de búsqueda y clasificación, la búsqueda de valores máximos y mínimos, la inversión se puede implementar fácilmente utilizando matrices. - La complejidad de tiempo para acceder a cualquier elemento de una matriz es O (1), es decir, se necesita una cantidad constante de tiempo para acceder a un elemento. - Las matrices utilizan índices para identificar sus elementos.

tiempo constante independiente mente de la posición en la que se inserte, solo se debe crear el nodo y modificar los enlaces de los mismos. - Al eliminar un elemento sucede lo mismo que se mencionó en el punto anterior.

- El tamaño de una matriz es fijo. Una vez que la memoria se asigna a una matriz, no se puede aumentar ni disminuir. Esto

El acceso a un elemento es más lento, debido a que la información no está en posiciones contiguas en la memoria de la

colisiones y la tabla se vuelve ineficiente). - Una función resumen que distribuya uniformemente las claves. Si la función está mal diseñada, se producirán muchas colisiones. - Otra ventaja, es que están implementada s usando algoritmos de hashing que los hace muy rápidos (aunque las listas asociativas son más fáciles de crear y manipular). - Comparada con otras estructuras de arreglos asociadas, las tablas hash son más útiles cuando se almacenan grandes cantidades de información. - Su principal inconveniente es que se trata de una estructura estática fija y al implementar cualquier

medida que se cargan los datos, si no hay más memoria disponible no se ingresan más datos.

entre procesos. - Las colas son flexibles, que requieren no comunicacione s de programación. - Algunos trabajos tienen restricciones de rendimiento y no pueden manejar todas las entradas, por lo que las entradas de datos son repartidas por múltiples trabajos.

El inconveniente de esta implementació n es que es necesario fijar de antemano el número

- La implementació n de las colas de prioridad es costosa en algunas implementacio nes. - Si se mantiene la

- Las búsquedas son más eficientes cuando el árbol está equilibrado - Un árbol equilibrado es aquel en el

Ejempl o

evita que almacenemos datos extra en caso de que queramos. Estas matrices de tamaño fijo se denominan matrices estáticas. - Asignar menos memoria de la necesaria a una matriz conduce a la pérdida de datos. - Una sola matriz no puede almacenar valores de diferentes tipos de datos, es decir, una matriz es de naturaleza homogénea. - Las operaciones de eliminación e inserción en matrices son muy difíciles de implementar, ya que almacenan datos en ubicaciones de memoria contiguas. elementos.

computadora, por lo que no se puede acceder a un elemento con base en su posición cómo se hace en los arreglos.

Otro ejemplo, definir una array de dos dimensiones

Las listas son comunes en la vida diaria: listas de

otra operación el coste es muy elevado. - Dificultad para recorrer todos los elementos. Se suelen emplear listas o colecciones (Collection usadas en .net) para procesar la totalidad de los elementos. Desaprovecha miento de la memoria. Si se reserva espacio para todos los posibles elementos, se consume más memoria de la necesaria; se suele resolver reservando espacio únicamente para punteros a los elementos. - Las tablas hash almacenan la información en posiciones seudoaleatorias, así que el acceso ordenado a su contenido es bastante lento. Es uno de los medios más eficientes para implementar el

máximo de elementos que puede contener la pila, MAX_ELEM, y por lo tanto al apilar un elemento es necesario controlar que no se inserte un elemento si la pila está llena.

En la programación de sistemas (para

lista desordenada, la inserción queda constante, pero la eliminación y la búsqueda exigen una búsqueda lineal. - Si se escoge ordenar la lista, entonces es la inserción la operación que requiere una búsqueda lineal a cambio del coste constante de la consulta, mientras que en la eliminación depende de la representación concreta de la lista.

Su utilización es infinita, sobre todo en

que las ramas izquierda y derecha de cada nodo tienen aproximadame nte la misma altura (el árbol lleno sería el árbol equilibrado perfecto con todos los nodos con subárboles izq y dch de la misma altura) - Si los nodos que se van insertando en el árbol aparecen en orden aleatorio el árbol tenderá a ser equilibrado

Un ejemplo de estructura de árbol es el sistema de

¿Cómo se aplica en la progra mación estruct urada?

(también llamado matriz o tabla) de 3 filas y cuatro columnas de cadenas. Definir tabla como Cadenas; Dimensión tabla[3,4];

alumnos, listas de clientes, listas de espera, listas de distribución de correo, etc.

TDA Diccionario.

registrar llamadas a subprogramas y recuperar los datos anteriores, o recuperar los parámetros).

Los arreglos se pueden aplicar para cuando necesitemos guardar datos para luego llamarlos dentro del mismo programa.

Las listas son estructuras de datos muy útiles para los casos en los que se quiere almacenar información de la que no se conoce su tamaño con antelación.

Se emplea en la implementació n de la tabla de símbolos de un compilador.

Se aplican en la recuperación de elementos en orden inverso al que fueron colocados (en un depósito, una pila de contenedores, sillas, etc.).

aquellos problemas que tienen un componente de simulación de procesos, por ejemplo la simulación de una cola formada frente a un cajero automático. Las colas de prioridad se aplican cuando las solicitudes deben procesarse en el orden de prioridad y no en el orden de llegada.

directorios y ficheros en el disco, en este caso se considera que los ficheros son hojas y los directorios ramas.

Pueden almacenar sus nodos en forma jerárquica y no en forma lineal como las Listas Ligadas, Colas, Pilas, etc....