PrOGRAMACION ESTRUCTURADA

Guía de Estudio: Estructuras de Datos y Tipos de Datos Abstractos

Resumen de Conceptos

Estructuras de Datos

Las estructuras de datos son formas fundamentales de organizar y almacenar información en la informática. Influyen en la eficiencia de los algoritmos y, por ende, en la rapidez y funcionalidad de los programas.

Tipos de Estructuras de Datos:

Arrays (Arreglos): Colecciones de elementos del mismo tipo en memoria contigua, accesibles por un índice.
Ventajas: Acceso directo y eficiente a los elementos.
Desventajas: Tamaño fijo, ineficiencia al insertar o eliminar elementos.
Listas Enlazadas: Secuencias de nodos, donde cada nodo contiene un valor y una referencia al siguiente nodo.
Ventajas: Tamaño dinámico, inserciones y eliminaciones eficientes.
Desventajas: Acceso secuencial, ineficiencia al buscar elementos específicos.
Pilas (Stacks): Siguen el principio LIFO (último en entrar, primero en salir).
Ventajas: Útiles para la gestión de memoria, evaluación de expresiones, backtracking.
Colas (Queues): Siguen el principio FIFO (primero en entrar, primero en salir).
Ventajas: Útiles para la programación concurrente, algoritmos de grafos.
Árboles: Estructuras jerárquicas con nodos conectados por enlaces.
Ventajas: Representación eficiente de relaciones jerárquicas.
Tipos: Árboles binarios, árboles B, etc.
Grafos: Conjuntos de nodos (vértices) conectados por aristas.
Ventajas: Representación de redes, relaciones, rutas.
Tipos: Dirigidos, no dirigidos, ponderados.
Tablas Hash: Implementan matrices asociativas, mapeando claves a valores.
Ventajas: Búsqueda, inserción y eliminación eficientes.
Desventajas: Posibilidad de colisiones.

Tipos de Datos Abstractos (TDA)

Un TDA es un modelo que define un conjunto de datos y operaciones que se pueden realizar sobre ellos, sin especificar cómo se implementan.

Ventajas de los TDA:

Abstracción: Ocultan la implementación y muestran solo la interfaz.
Reutilización: Pueden ser utilizados en diferentes programas.
Modularidad: Facilitan la organización y estructuración del código.
Flexibilidad: La implementación puede cambiarse sin afectar a los programas que lo utilizan.

Ejemplos de TDA:

Listas
Pilas
Colas
Árboles
Grafos

Manejo de Memoria

Memoria Estática: Asignada en tiempo de compilación, con tamaño fijo.
Memoria Dinámica: Asignada en tiempo de ejecución, con tamaño variable.
Referencias y Punteros: Permiten el acceso indirecto a la memoria.
Recolección de Basura: Libera automáticamente la memoria no utilizada.

Hilos de Programación

Definición: Unidad más pequeña de un programa que se puede programar para su ejecución independiente.
Creación: Se crean mediante APIs específicas del lenguaje o del sistema operativo.
Sincronización: Esencial para evitar condiciones de carrera al acceder a recursos compartidos.
Comunicación: Permite a los hilos coordinarse y trabajar de manera eficiente.
Ventajas del Multiprocesamiento: Mayor rapidez, mejor respuesta, capacidad para realizar tareas en paralelo.
Problemas Típicos: Competencia y deadlock.

Cuestionario

Responda las siguientes preguntas en 2-3 oraciones cada una:

¿Cuál es la principal diferencia entre una pila y una cola en términos de cómo se agregan y se eliminan los elementos?
¿Por qué las listas enlazadas son más eficientes para insertar y eliminar elementos en comparación con los arrays?
Describa cómo una tabla hash utiliza una función hash para mapear claves a valores.
¿Cuál es la ventaja de utilizar un árbol B sobre un árbol binario en sistemas donde la información se almacena en discos?
¿Por qué es importante la sincronización de hilos en la programación concurrente?
¿Qué problema puede ocurrir cuando dos hilos intentan acceder al mismo recurso compartido simultáneamente?
¿Cuál es la diferencia entre memoria estática y dinámica en términos de cuándo se asigna y si su tamaño puede cambiar?
¿Cómo facilitan las referencias y los punteros el manejo de memoria dinámica?
Explique el concepto de recolección de basura y su importancia en la gestión de memoria.
Menciona al menos tres ventajas del multiprocesamiento en la programación.

Clave de Respuestas

En una pila, los elementos se agregan y eliminan por el mismo extremo (LIFO), mientras que en una cola, los elementos se agregan por un extremo y se eliminan por el otro (FIFO).
Las listas enlazadas no requieren memoria contigua, lo que facilita la inserción y eliminación de elementos sin necesidad de desplazar otros elementos como en un array.
Una tabla hash utiliza una función hash para convertir una clave en un índice dentro de un array. Este índice determina dónde se almacena el valor asociado a la clave.
Los árboles B minimizan los accesos a disco al tener múltiples hijos por nodo, lo que reduce la altura del árbol y agiliza las búsquedas en grandes conjuntos de datos.
La sincronización de hilos evita condiciones de carrera al asegurar que solo un hilo pueda acceder a un recurso compartido a la vez, manteniendo la consistencia de los datos.
Cuando dos hilos intentan acceder al mismo recurso compartido simultáneamente, pueden ocurrir condiciones de carrera, lo que lleva a resultados inesperados y errores en el programa.
La memoria estática se asigna en tiempo de compilación y tiene un tamaño fijo, mientras que la memoria dinámica se asigna en tiempo de ejecución y su tamaño puede cambiar durante la ejecución del programa.
Las referencias y los punteros permiten el acceso indirecto a la memoria dinámica, facilitando la manipulación de datos sin necesidad de copiarlos o moverlos en la memoria.
La recolección de basura es un proceso automático que libera la memoria que ya no está siendo utilizada por el programa, evitando fugas de memoria y mejorando la eficiencia.
Las ventajas del multiprocesamiento incluyen mayor rapidez en la ejecución de tareas, mejor respuesta en aplicaciones interactivas y la capacidad de realizar tareas en paralelo.

Preguntas de Ensayo

Compare y contraste las ventajas y desventajas de los arrays y las listas enlazadas como estructuras de datos.
Explique cómo los principios de encapsulación, abstracción y modularidad se aplican al diseño de Tipos de Datos Abstractos (TDA).
Analice los desafíos y las estrategias para la sincronización de hilos en la programación concurrente, incluyendo ejemplos de problemas comunes como la competencia y el deadlock.
Describa el papel de la recolección de basura en la gestión de memoria, discutiendo sus beneficios y cómo funciona en la práctica.
Elija dos estructuras de datos diferentes (por ejemplo, árbol y grafo) y explique cómo se pueden utilizar para modelar y resolver un problema del mundo real.

Glosario de Términos Clave

Array (Arreglo): Colección de elementos del mismo tipo, almacenados en memoria contigua y accesibles por un índice.
Lista Enlazada: Estructura de datos lineal que consiste en una secuencia de nodos, cada uno conteniendo un valor y una referencia al siguiente nodo.
Pila (Stack): Estructura de datos LIFO (último en entrar, primero en salir) que admite operaciones como push (agregar) y pop (eliminar).
Cola (Queue): Estructura de datos FIFO (primero en entrar, primero en salir) que admite operaciones como enqueue (agregar) y dequeue (eliminar).
Árbol: Estructura de datos jerárquica que consiste en nodos conectados por enlaces, con un nodo raíz y subárboles.
Grafo: Estructura de datos que consiste en un conjunto de nodos (vértices) conectados por aristas, representando relaciones entre entidades.
Tabla Hash: Estructura de datos que utiliza una función hash para mapear claves a valores, permitiendo un acceso eficiente a los datos.
Tipo de Datos Abstracto (TDA): Modelo matemático que define un conjunto de datos y operaciones sobre esos datos, sin especificar la implementación.
Memoria Estática: Memoria asignada en tiempo de compilación con un tamaño fijo.
Memoria Dinámica: Memoria asignada en tiempo de ejecución, con un tamaño que puede variar durante la ejecución del programa.
Referencia: Variable que almacena la dirección de memoria de otra variable, permitiendo el acceso indirecto a los datos.
Puntero: Variable que almacena una dirección de memoria, utilizada para acceder a datos de forma indirecta.
Recolección de Basura: Proceso automático que libera la memoria que ya no está siendo utilizada por el programa.
Hilo (Thread): Unidad más pequeña de un programa que se puede programar para su ejecución independiente.
Sincronización de Hilos: Mecanismos para coordinar el acceso a recursos compartidos entre múltiples hilos, evitando condiciones de carrera.
Comunicación entre Hilos: Mecanismos para que los hilos intercambien información y se coordinen durante la ejecución.
Competencia (Race Condition): Situación en la que múltiples hilos intentan acceder y modificar un recurso compartido al mismo tiempo, lo que puede llevar a resultados inesperados.
Deadlock: Situación en la que dos o más hilos se bloquean mutuamente al esperar recursos que el otro hilo tiene, impidiendo que ninguno progrese.