Diseño de estructuras de datos Código:  75.613    Créditos:  6
Consulta de los datos generales   Descripción   La asignatura en el conjunto del plan de estudios   Campos profesionales en que se proyecta   Conocimientos previos   Objetivos y competencias   Contenidos   Consulta de los materiales que dispone la asignatura   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 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.

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

 

Amunt

Material Soporte
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

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.

Amunt