Este es el plan docente de la asignatura para el primer semestre del curso 2024-2025. Podéis consultar si la asignatura se ofrece este semestre en el espacio del campus Más UOC / La universidad / Planes de estudios). Una vez empiece la docencia, tenéis que consultarlo en el aula. El plan docente puede estar sujeto a cambios.
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:
Los objetivosde esta asignaturason los siguientes:
Conocer en profundidadlas estructuras de datosmás habitualespara representarla informaciónde una aplicación enmemoria.
Sabercalcularla eficienciaespacial ytemporal de unaestructura de datosy comparardiferentes alternativas.
Sercapaz de identificarla estructura de datosutilizada enun programa yentender su funcionamiento.
Conocerlas libreríasde componentesmás habitualespara representarestructuras de datos.
Saberimplementar un programaque utiliceestructurasde datos utilizandolas posibilidades que ofrecela programación orientada aobjetos ylas libreríasdisponibles.
Saberproponerla estructura de datosmás apropiada parauna aplicación concretateniendoen cuenta suscaracterísticas.
Las competenciastransversalesdel Gradoque se desarrollan enesta asignatura son:
Uso yaplicación de las TICen el ámbito académicoy profesional.
Capacidad parainnovar ygenerar nuevasideas.
Las competenciasespecíficasdel Gradoque se desarrollan enesta asignatura son:
Capacidadpara analizarun problemaen el nivelde abstracciónadecuado a cadasituacióny aplicar lashabilidades yconocimientos adquiridospara resolverlo.
Capacidadpara diseñar y construiraplicaciones informáticasmediante técnicas dedesarrollo, integración y reutilización.
Capacidadpara proponery evaluardiferentes alternativastecnológicaspara resolver un problemaconcreto.
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 la Java Collections Framework
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 la Java Collections Framework
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 la Java Collections Framework
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, ...).
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.
Ponderación de las calificaciones
Opción para superar la asignatura: 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.