| Diseño de estructuras de datos | Código: 75.613 Créditos: 6 |
En esta asignatura se estudian las diversas estrategias de representación de datos en un ordenador y los criterios para evaluarlas. En función del tipo de tratamiento que se tenga que hacer con esta información (tamaño, criterios de acceso, etc.), se puede seleccionar la estrategia que ofrezca un balance óptimo entre el consumo de memoria y el tiempo de manipulación.
Esta asignatura es fundamental dentro del ámbito de la programación, dado que el uso apropiado de estructuras de datos es crítico en cualquier aplicación que maneje grandes volúmenes de información o bien que tenga unos requerimientos de eficiencia muy estrictos.
Las asignaturas previas del ámbito de programación ya introducían algunas estructuras de datos básicos, como por ejemplo listas, pilas, colas o árboles. En esta asignatura se presenta el concepto de tipo abstracto de datos (TAD) como modelo general para describir una estructura de datos y estudiar su eficiencia. Finalmente, el núcleo central de la asignatura consiste en aprender a utilizar adecuadamente cada estructura de datos y saber seleccionar la estructura de datos más adecuada a cada situación.
La asignatura Diseño de Estructuras de Datos se puede cursar como asignatura optativa o bien como parte de los itinerarios de Ingeniería del Software o de Computación.
Sus contenidos están directamente relacionados con las asignaturas obligatorias de programación (Fundamentos de Programación, Prácticas de Programación y Diseño y Programación Orientada a Objetos), donde ya se habían introducido estructuras de datos sencillas. Otras estrategias de representación, como por ejemplo los métodos basados en dispersión, se habían estudiado a la asignatura obligatoria Diseño de Bases de Datos. Finalmente, la asignatura Grafos y Complejidad presenta el concepto de grafo e introduce aspectos de eficiencia de los algoritmos.
El diseño de estructuras de datos es muy importante en el ámbito del desarrollo de software, especialmente en sistemas donde la eficiencia es un factor crítico.
La asignatura requiere disponer de las nociones fundamentales de algorítmica (asignaciones, condicionales, bucles) y de programación utilizando el paradigma imperativo (uso de compiladores y depuradores, uso de un entorno de desarrollo integrado -IDE-, etc.). Además, la asignatura requiere unos buenos conocimientos de programación orientada a objetos, específicamente en lenguaje Java.
Por otro lado, se requieren nociones básicas sobre el cálculo del coste de un algoritmo.
Antes de cursar esta asignatura, es muy recomendable haber cursado previamente las asignaturas básicas y obligatorias siguientes:
- Fundamentos de Programación.
- Prácticas de Programación.
- Diseño y Programación Orientada a Objetos.
- Grafos y Complejidad.
Los objetivos de esta asignatura son los siguientes:
- Conocer en profundidad las estructuras de datos más habituales para representar la información de una aplicación en memoria.
- Saber calcular la eficiencia espacial y temporal de una estructura de datos y comparar diferentes alternativas.
- Ser capaz de identificar la estructura de datos utilizada en un programa y entender su funcionamiento.
- Conocer las librerías de componentes más habituales para representar estructuras de datos.
- Saber implementar un programa que utilice estructuras de datos utilizando las posibilidades que ofrece la programación orientada a objetos y las librerías disponibles.
- Saber proponer la estructura de datos más apropiada para una aplicación concreta teniendo en cuenta sus características.
Las competencias transversales del Grado que se desarrollan en esta asignatura son:
- Uso y aplicación de las TIC en el ámbito académico y profesional.
- Capacidad para innovar y generar nuevas ideas.
Las competencias específicas del Grado que se desarrollan en esta asignatura son:
- Capacidad para analizar un problema en el nivel de abstracción adecuado a cada situación y aplicar las habilidades y conocimientos adquiridos para resolverlo.
- Capacidad para diseñar y construir aplicaciones informáticas mediante técnicas de desarrollo, integración y reutilización.
- Capacidad para proponer y evaluar diferentes alternativas tecnológicas para resolver un problema concreto.
La asignatura se estructura en nueve módulos:
| Módulo | Contenidos | Descripción |
| 1. Tipos Abstractos de Datos | 1. Contenedores 2. Diseño por contrato 3. Desarrollo de una colección de ejemplo 4. Tipos genéricos o paramétricos 5. Biblioteca de colecciones de la asignatura 6. Presentación del resto de módulos | Estudio del concepto de TAD y de aspectos relativos a su definición e implementación en clases mediante una jerarquía. |
| 2. Complejidad algorítmica | 1. Introducción a la complejidad algorítmica 2. Notación asintótica de la complejidad algorítmica 3. Complejidad algorítmica de los tipos abstractos de datos | Descripción de los métodos utilizados para comparar el coste de diferentes programas en términos de tiempos de ejecución o consumo de memoria. |
| 3. Contenedores secuenciales | 1. Pilas 2. Colas 3. Representaciones encadenadas 4. Listas 5. Representaciones con vector: redimensionamiento 6. Los contenedores secuenciales en | Estudio de las colecciones de objetos con acceso secuencial (pilas, colas, listas). |
| 4. Árboles | 1. Árboles generales y binarios. Definiciones y conceptos relacionados 2. Recursividad 3. Árboles generales 4. Árboles binarios 5. Recorridos 6. Un ejemplo de sistema de ficheros | Presentación de las estructuras de datos empleadas para representar relaciones jerárquicas e introducción del concepto de recursividad. |
| 5. Colas con prioridad | 1. El concepto de cola con prioridad 2. Funcionamiento de las colas con prioridad 3. Implementaciones de las colas con prioridad 4. Las colas con prioridad en las bibliotecas JDK 5. Ordenación por montículos: el algoritmo heapsort 6. Ejemplo de uso: algoritmo de Huffman | Estudio del diseño e implementación de colecciones donde el orden de acceso a los elementos depende de su prioridad. |
| 6. El TAD Tabla | 1. Presentación del TAD Tabla 2. Implementación por dispersión del TAD Tabla 3. El TAD Conjunto 4. Ejemplo de aplicación: una tabla de símbolos para un lenguaje modular 5. Las tablas y los conjuntos en | Estudio del concepto de dispersión, presentación del TAD tabla y las estrategias para su implementación. |
| 7. Árboles de busca | 1. Los árboles de búsqueda 2. Implementación de colecciones ordenadas con árboles binarios de búsqueda 3. Árboles multicamino y árboles B 4. Los árboles de búsqueda en | Profundización en el concepto de árbol y sus aplicaciones para representar colecciones ordenadas. |
| 8. Grafos | 1. El concepto de grafo. 2. El tipo abstracto de datos Grafo 3. Interfaces Java para grafos dirigidos y no dirigidos 4. Implementación de grafos 5. Ejemplo de uso: TAD Academia | Revisión del concepto de grafo y descripción de estrategias para implementar diferentes tipos de grafos (dirigidos o no dirigidos, etiquetados o no etiquetados, ...). |
| 9. Bibliotecas de colecciones | 1. Diseño de TAD nuevos usando una biblioteca de colecciones 2. Diseño de bibliotecas de colecciones 3. Bibliotecas de colecciones existentes | Análisis del diseño de nuevos TADs a partir de otros existentes. Estudio de las consideraciones que afectan al diseño de librerías de colecciones y presentación de algunas librerías existentes (Java Collections Framework, Java Data Structure Library, ...). |
| Material | Soporte |
| Data Structures Library | Web |
| 3. Contenedores secuenciales | |
| 5. Colas con prioridad | |
| 7. Árboles de búsqueda | |
| 2. Complejidad algorítmica | |
| 9. Bibliotecas de colecciones | |
| 4. Árboles | |
| 8. Grafos | |
| 1. Tipos abstractos de datos | |
| 6. El TAD Tabla |
|
Esta asignatura solo puede superarse a partir de la evaluación continua (EC), nota que se combina con una nota de prácticas (Pr) para obtener la nota final de la asignatura. No se prevé hacer ninguna prueba de evaluación final. La fórmula de acreditación de la asignatura es la siguiente: EC + Pr. |
Nota final de asignatura = Final Continuada (FC) = EC+Pr
EC = 40%
Pr = 60%
Notas mínimas:
· Pr = 5
· EC = 4
En caso de no conseguir la nota mínima en la Pr, la nota obtenida en la fórmula corresponde a la obtenida en la Pr, o el que indique el modelo de evaluación.