Diseño de estructuras de datos Código:  75.613    :  6
Consulta de los datos generales   Descripción   La asignatura en el conjunto del plan de estudios   Campos profesionales en el que se proyecta   Conocimientos previos   Objetivos y competencias   Contenidos   Consulta de los recursos de aprendizaje de los que dispone la asignatura   Recursos de aprendizaje y herramientas de apoyo   Informaciones sobre la evaluación en la UOC   Consulta del modelo de evaluación  
Este es el plan docente de la asignatura para el segundo semestre del curso 2023-2024. 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.

Amunt

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 en 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.

Amunt

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.

Amunt

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.

Amunt

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.

Amunt

 La asignatura se estructura en ocho módulos (el módulo 8 de los materiales no se estudia):

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 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 búsqueda
  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

(Este módulo no se estudia)

  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, ...).

Amunt

Data Structures Library Web
3. Contenedores secuenciales PDF
5. Colas con prioridad PDF
7. Árboles de búsqueda PDF
2. Complejidad algorítmica PDF
9. Bibliotecas de colecciones PDF
4. Árboles PDF
8. Grafos PDF
1. Tipos abstractos de datos PDF
6. El TAD Tabla PDF

Amunt

Los módulos didácticos constituyen la parte más importante de los materiales de la asignatura. Estos materiales los podéis descargar en formato PDF desde el apartado Recursos del aula.

Para realizar las Prácticas, la asignatura se apoya en una librería de tipos abstractos de datos que ofrece una jerarquía con las estructuras de datos más usuales. Podéis descargar esta librería de TADs desde el aula virtual, dentro del apartado de Recursos.

Igualmente, dispondréis de ejemplos de PEC de semestres anteriores en este mismo espacio de Recursos. Para resolver de vuestras dudas en programación Java o el uso de la librería, disponéis de un Laboratorio de Java de Diseño de Estructuras de Datos.

Amunt

El proceso de evaluación se fundamenta en el trabajo personal de cada estudiante y presupone la autenticidad de la autoría y la originalidad de los ejercicios realizados.

La falta de autenticidad en la autoría o de originalidad de las pruebas de evaluación; la copia o el plagio; el intento fraudulento de obtener un resultado académico mejor; la colaboración, el encubrimiento o el favorecimiento de la copia, o la utilización de material o dispositivos no autorizados durante la evaluación, entre otras, son conductas irregulares que pueden tener consecuencias académicas y disciplinarias graves.

Por un lado, si se detecta alguna de estas conductas irregulares, puede comportar el suspenso (D/0) en las actividades evaluables que se definan en el plan docente –incluidas las pruebas finales– o en la calificación final de la asignatura, ya sea porque se han utilizado materiales o dispositivos no autorizados durante las pruebas, como redes sociales o buscadores de información en internet, porque se han copiado fragmentos de texto de una fuente externa (internet, apuntes, libros, artículos, trabajos o pruebas del resto de estudiantes, etc.) sin la correspondiente citación, o porque se ha practicado cualquier otra conducta irregular.

Por el otro, y de acuerdo con las normativas académicas, las conductas irregulares en la evaluación, además de comportar el suspenso de la asignatura, pueden dar lugar a la incoación de un procedimiento disciplinario y a la aplicación, si procede, de la sanción que corresponda.

Amunt

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.

 
 

Amunt