Estructuras de Datos y Algoritmos (21417)

Titulación/estudio: Grado en Ingeniería en Informática (3377)
Curso: segundo 
Trimestre: primero
Número de créditos ECTS: 4 créditos
Horas de dedicación del estudiante: 100 horas
Lengua o lenguas de la docencia: catalán
Profesor: Narcís Parés

 

1. Presentación de la asignatura

Estructuras de Datos y Algoritmos forma parte del grupoo de asignaturas del área de Lenguajes de Programación, junto con las asignaturas: Fundamentos de la Programación (de primer curso, durante el 2º y 3er trimestres) y Programación Orientada a Objetos (de segundo curso, durante el 1er trimestre y en paralelo con la nuestra). Si bien estas dos últimas asignaturas del grupoo son comunes a los tres grados (Ingeniería en Informática, Ingeniería en Telemática y Ingeniería en Sistemas Audiovisuales), nuestra asignatura es una especialización sólo para la Ingeniería en Informática. De esta manera, la asignatura parte de la voluntad de empezar a plantear a los alumnos una mentalidad de analistas de problemas y no sólo de programadores. Sin embargo, las  capacidatos y habilidatos de programación de las estructuras de datos y los tipos abstractos de datos son importantes en esta asignatura. 

Esta asignatura presupone haber adquirido unos conocimientos y habilidatos básicas de programación en la asignatura de Fundamentos de la Programación de primer curso. Los dos trimestres de esta asignatura habrán dado un dominio en las  técnicas y tipos elementales de programación y estructuras de control de flujos. En Estructuras de Datos y Algoritmos profundizaremos en estos aspectos concentrándonos en las  formas de estructurar la información utilizada en un programa, en cómo se puede gestionar esta información y en cómo hacerlo para evitar efectos colaterales en la resta del programa. Además veremos cómo se evalúa la implementación óptima, tanto en ocupación de espacio de memoria como en tiempo de ejecución de las  operaciones y algoritmos de gestión de datos. 

Las  estructures elementales que es trataremos serán las  Estructuras Lineales, las  Estructuras en Árbol y las  Estructures Asociativas. La programación de estas estructuras y sus algoritmos se realizará en lenguaje C, que los alumnos ya han aprendido en Fundamentos de la Programación. Además esta asignatura promueve de forma especial la capacidad de analizar un problema desde el punto de vista de la información utilizada y gestionada, y de cómo se puede diseñar y programar la mejor solución en cuanto las  estructuras de datos y sus operaciones de gestión. En este sentido el aprendizaje del alumno irá muy encaminado resolver problemas que presenten escenarios tan cercanos como sea posible a casos reales. 

Las  actividatos de aprendizaje se dividen de la forma siguiente:

- Sesiones de Teoría: el profesorado presenta una serie de conceptos y técnicas, además de ejemplos  de uso. Se espera que los alumnos repasen los apuntes tomados en clase después de la sesión para consolidar estos contenidos.
- Sesiones de Seminario: los alumnos, en grupoos reducidos, resolverán ejercicios que les ayudarán a consolidar los conceptos teóricos y sirven como enlace con los trabajos prácticos. La realización es en solitario y durante la clase. Los profesores supervisarán de cerca estos ejercicios para solucionar cualquier duda y ayudar a los alumnos en la consolidación.
- Sesiones de Prácticas: los alumnos, en equipos de tres, tendrán que resolver aspectos prácticos de resolución de problemas de la asignatura. Básicamente ejercitarán las  técnicas de programación de las estructuras de datos y de las  operaciones de gestión, pero també tendrán que saber analizar la forma más óptima de hacerlo. Estas prácticas se empezarán en aula de ordenadores pero se acabarán fuera de horas de clase dada la intensidad que requieren estos problemas prácticos.
- Ejercicios de Autoevaluación: estos ejercicios pertenecen a una lista accesible desde el aula global para los alumnos, fuera de horas de clase, puedan llevar a cabo un seguimiento de su aprendizaje de cada bloque de la asignatura.

 

2. Prerrequisitos para seguir el itinerario formativo

Esta asignatura requiere los conocimientos y habilidatos adquiridos en la asignatura de Fundamentos de la Programación (de primer curso, durante el 2º y 3er trimestres). Esencialmente, la asignatura presupone que se ha adquirido unos conocimientos y habilidatos básicos de programación que dan un dominio en las técnicas y tipos elementales de programación y estructuras de control de flujo.

 

3. Competencias que se deben lograr

A continuación se detallan las competencias que los alumnos de Estructuras de Datos y Algoritmos tendrán que haber adquirido al finalitar la asignatura. Estas competencias están relacionadas con el análisis, diseño y desarrollo de estructuras de datos y les operaciones para su gestión, en programas de tamaño medio.

Competencias generales

Competencias específicas

Instrumentales CG1: Capacidad de síntesis El alumno tiene que ser capaz de escribir soluciones con los elementos esenciales, de forma simple, elegante y tan eficiente como sea posible. CG2: Capacidad de análisis El alumno tiene que ser capaz de analizar un problema concreto y proponer soluciones adecuadas para resolverlo.   Interpersonales  CG3: Capacidad de comprender necesidatos de terceros en la resolución de problemas El alumno tiene que ser consciente de que como profesional tendrá que analizar y solucionar problemas planteados por terceros y por tanto deberá saber escucharles y entenderlos. CG4: Dialogar y trabajar en equipo El trabajo de un informático rara vez es en solitario dada la complejidad del desarrollo de aplicaciones de gran formato y por eso es importante que el alumno se vaya acostumbrando a trabajar en grupoo.   Sistémicas  CG5: Capacidad de aplicar el conocimiento a la práctica El alumno tiene que ser capaz de aplicar los conocimientos adquiridos en la resolución de problemas concretos, escogiendo la técnica que se ajuste mejor a cada caso. CG6: Interés per la calidad El alumno tiene que mostrar atención en la calidad de su trabajo.

Conocimientos (Saber)  CE1: Conocimiento del concepto de Tipo Abstracto de Datos sus componentes (Conjunto de Soporte e Interfaz o Signatura) y los conceptos que implica (encapsulamiento, independencia de implementación, reutilización, robustez, etc.) y cómo están definidos formalmente (conjunto de operaciones constructoras, conjuntos puros/impuros, etc.)  CE2: Conocimiento de las estructuras de datos básicas. Concretamente: estructures lineales (pilas, colas y listas), estructures en árbol (árboles binarios de búsqueda, árboles balanceados o AVL, árboles parcialmente ordenados), estructuras asociativas (tablas, tablas de hash, tablas con AVLs), colas con prioridad (montículos o heaps).  CE3: Conocimiento de cómo se puede combinar estas estructuras básicas para formar otras más complejas.  CE4: Conocimiento de los algoritmos asociados a las estructuras. Operaciones básicas de gestión (creación, inserción, modificación, eliminación, etc.); Algoritmos de búsqueda, funciones de hash, etc.  CE5: Conocimiento de los conceptos de funciones de complejidad o coste espacial y de ejecución. Esencialmente función del caso peor O().   Habilidatos (Saber hacer)  CE6: Capacidad de análisis y abstracción de les necesidatos estructurales y funcionales de un problema.   CE7: Especificación formal de problemas informáticos, concretamente de sus necesidatos estructurales y de sus necesidatos funcionales.  CE8: Adecuación de las estructuras de datos básicas a ciertos problemas arquetípicos.  CE9: Aplicación de las estrategias elementales de Implementación de los tipos abstractos de datos, optimizando la ocupación en memoria y la complejidad temporal de ejecución.  CE10: Capacidad de comprensión de estructuras de datos nuevas noves y de su aplicación.

 

4. Objetivos de aprendizaje

Esta asignatura quiere, en último término, que el alumno adquiera una primera visión de las tareas asociadas con el analista informático. Es decir, quiere conseguir que un alumno pueda partir de la descripción verbal/textual de un problema a resolver informáticamente y pueda diseñar y desarrollar los Tipos Abstractos de Datos (TADs) que lo resuelven, a partir de los siguientes pasos esenciales: 

* Comprender y especificar formalmente las necesidatos funcionales del problema, es decir, especificar la firma de los TADs (tipos abstractos de datos) necesarios.
* Seleccionar y diseñar las estructuras de datos que se utilizarán en los TADs, optimizando la ocupación en memoria y la complejidad temporal de ejecución.
* Realizar un esquema completo de les estructuras de datos seleccionadas.
* Implementar de forma óptima los TADs diseñados para incorporarlos a la aplicación que resuelve el problema inicial. 

El alumno debe ser capaz, además, de poder entender por sí mismo nuevas estructuras de datos más complejas que vaya encontrando en el futuro y de poderlas incorporar en su repertorio para el análisis y la resolución de problemas. 

Todo esto tiene que enlazar con la filosofía de diseño de programas descendiente de la asignatura previamente realizada (Fundamentos de la Programación) y ha de mostrar los claros vínculos con la asignatura paralela Programación Orientada a Objetos.

 

5. Evaluación

5.1. Criterios generales de evaluación

Siguiendo el espíritu del EEES, se evaluará a los alumnos mediante una fórmula mixta de forma continuada y de forma global final mediante un examen. 

Notas de Seminarios (NS): se irá evaluando a los alumnos a parteir de ejercicios realizados en clase durante las sesiones de seminario. Estos ejercicios aportarán una nota de 0, 0,5 o 1,0. Se hará un promedio de todas las notas de seminario y finalmente se sumará a la nota del examen final. Estos ejercicios de seminario, que se realizarán individualmente en clases reducidas, permitirán a los profesores llevar a cabo un seguimiento más preciso del alumno para conocerlo mejor y poder evaluar con más conocimiento las diversas fases del curso (seminarios, prácticas y examen). 

Notas de Prácticas (NP): los alumnos realizarán 4 prácticas a lo largo del curso, que se empezarán durante la hora de clase y se acabaran fuera de clase. Se realizarán en equipos de 3 alumnos para que aprendan a trabajar en equipo. Se avaluarán para cada entrega que el equipo realice y la nota será la misma para los tres miembros del equipo. La evaluación se hará siempre que la práctica compile correctamente y se ejecute sin errores de sistema. En ese caso, la práctica se avaluará en base a la adecuación de la solución al problema y a los criterios de eficiencia de la solución, claridad y limpieza del código, documentación del código y funcionamiento con los juegos de datos aportados por los profesores. Las 4 prácticas harán media para obtener una nota global de prácticas. 

Nota de Examen (NE): a final de la asignatura, los alumnos realizarán un examen que constará de tres partes: (a) una parte de tipo test que evaluará conceptos generales, (b) una parte con dos cuestiones de respuesta corta y/o de ejercicio de cálculo de funcionamiento de estructuras de datos, y finalmente, (c) un problema largo que evaluará la capacidad de analizar un problema, diseñar las estructuras de datos adecuadas, especificar la solución formalmente y los tipos abstractos de datos con las operaciones de la interfaz y el esquema de las estructuras, y analizando la complejidad en espacio i en tiempo. 

Autoevaluación: El alumno dispondrá de una colección de ejercicios con soluciones para irse autoevaluando a lo largo del curso. Estos ejercicios serán voluntarios y no contarán en la nota final. 

Nota Final (NF): la nota final será calculada de la siguiente forma:

NF = (NE + NS) * 0,4 + NP * 0,6

Donde la media se calcula sólo si: NE >= 5,0 y NP >= 5,0

 

5.2. Concreción de competencias

Competencias a adquirir en la asignatura	Indicador de adquisición	Procedimiento de evaluación	Temporalizació
CE1: Conocimiento del concepto de Tipo Abstracto de Datos sus componentes (Conjunto de Soporte e Interfaz o Signatura) y los conceptos que implica (encapsulamiento, independencia de implementación, reutilización, robustez, etc.) y cómo están definidos formalmente (conjunto de operaciones constructoras, conjuntos puros/impuros, etc.)  CE2: Conocimiento de las estructuras de datos básicas. Concretamente: estructures lineales (pilas, colas y listas), estructures en árbol (árboles binarios de búsqueda, árboles balanceados o AVL, árboles parcialmente ordenados), estructuras asociativas (tablas, tablas de hash, tablas con AVLs), colas con prioridad (montículos o heaps).  CE3: Conocimiento de cómo se puede combinar estas estructuras básicas para formar otras más complejas.	Responder correctamente les preguntes tipo test del examen final.  Responder correctamente les cuestiones cortas del examen final.  Responder correctamente el problema largo del examen final.  Realizar correctamente los problemas y ejercicios propuestos en los seminarios.	Examen final con parte tipo test para conocimientos generales, con cuestiones cortas para profundización particular y con problema largo para visión analítica y capacidad de diseño.   Ejercicios de clase en sesiones de seminario.	Al final del trimestre.    Ejercicios a resolver en sesiones de seminario, aproximadamente en sesiones semanales.
CE4: Conocimiento de los algoritmos asociados a las estructuras. Operaciones básicas de gestión (creación, inserción, modificación, eliminación, etc.); Algoritmos de búsqueda, funciones de hash, etc.  CE5: Conocimiento de los conceptos de funciones de complejidad o coste espacial y de ejecución. Esencialmente función del caso peor O().  CE6: Capacidad de análisis y abstracción de les necesidatos estructurales y funcionales de un problema. CE7: Especificación formal de problemas informáticos, concretamente de sus necesidatos estructurales y de sus necesidatos funcionales.  CE8: Adecuación de las estructuras de datos básicas a ciertos problemas arquetípicos.  CE10: Capacidad de comprensión de estructuras de datos nuevas noves y de su aplicación.	Responder correctamente les preguntes tipo test del examen final.  Responder correctamente les cuestiones cortas del examen final. Responder correctamente el problema largo del examen final.  Realizar correctamente los problemas y ejercicios propuestos en los seminarios.	Examen final con parte tipo test para conocimientos generales, con cuestiones cortas para profundización particular y con problema largo para visión analítica y capacidad de diseño. Ejercicios de clase en sesiones de seminario.	Al final del trimestre.   Ejercicios a resolver en sesiones de seminario, aproximadamente en sesiones semanales.
CE8: Adecuación de las estructuras de datos básicas a ciertos problemas arquetípicos.  CE9: Aplicación de las estrategias elementales de Implementación de los tipos abstractos de datos, optimizando la ocupación en memoria y la complejidad temporal de ejecución.	Realizar correctamente las prácticas.	Corrección de las prácticas.	Prácticas a realizar en sesiones de laboratorio. Aproximadamente una cada dos semanas.

 

 

6. Contenidos

6.1. Bloques de contenido

•-  Bloque de contenido 1: Introducción a los Tipos Abstractos de Datos
•-  Bloque de contenido 2. Estructuras Lineales
•-  Bloque de contenido 3. Estructuras en Árbol
•-  Bloque de contenido 4. Estructures Asociativas
•-  Bloque de contenido 5. Colas con Prioridad y Heaps
•-  Bloque de contenido 6. Análisis de Problemas

6.2. Organización y concreción de los contenidos

Bloque de contenido 1. Introducción a los Tipos Abstractos de Datos

Conceptos	Procedimientos	Actitudes
1. Introducción a las Estructuras de Datos  2. Breve contexto histórico  3. Necesidad de los Tipo Abstractos de Datos  4. Definición de los Tipo Abstractos de Datos  5. Noción de Coste Espacial y Temporal -> Función de Orden de Coste: O()  6. Beneficios de los Tipo Abstractos de Datos	1. Ejemplo de problemas de no utilización de los Tipo Abstractos de Datos.	1. Abstracción  2. Comprensión matemática

Bloque de contenido 2. Estructures Lineales

Conceptos	Procedimientos	Actitudes
1. Aproximación Estructural a les Estructures Lineales  2. Introducción a la Especificación formal de Tipos Abstractos de Datos a partir de las Est. Lineales  3. Implementación de las Est. Lineales  4. Comparativa de las Est. Lineales.	1. Analogía de les Estructures Lineales a funcionamiento de actividades cotidianas  2. Formalización de las operaciones de la interfaz de los tipos abstractos de datos: operaciones constructoras, modificadores y consultores  3.  Implementación estática y dinámica de les Est. Lineales 4. Complejidad en Tiempo y Espacio de les Est. Lineales.	1. Abstracción 2. Análisis

Bloque de contenido 3. Estructuras en Árbol 

Conceptos	Procedimientos	Actitudes
1. Propiedades, terminología y conceptos asociados a los Árboles.  2. Recorridos de Árboles Binarios.  3. Estructuras de Árboles Binarios (AB).  4. Árboles Binarios de Búsqueda (ABB).  5. ABBs Balanceados: Árboles Adelson-Velskii Landis (AVL)  6. Árboles Parcialmente Ordenados (APO)	1. Algoritmos de recorridos de Árboles Binarios.  2. Especificación Formal de AB.  3. Implementación Dinámica de AB.  4. Implementación Estática de AB.  5. Operaciones de balanceo de AVL.  6. Operaciones de inserción, modificación y eliminación.  7. Complejidad en Espacio y Tiempo de los Árboles.	1. Abstracción 2. Análisis

Bloque de contenido 4. Estructuras Asociativas 

Conceptos	Procedimientos	Actitudes
1. Estructuras Asociativas: Tablas  2. Concepto de Clave y relación Clave-Valor, Cerca per Clave, etc.  3. Aproximación de Tablas con Listes: Eficiencia  4. Tablas de Hash: Conceptos, Propiedades, Eficiencia.  6. Fórmulas de Hashing.  7. Gestión de Desbordamiento de Hashing: Encadenamiento, Direccionamiento Abierto, etc.  8. Tablas con AVL: Conceptos, Eficiencia.	1. Especificación Informal: Operaciones Generales  2. Implementación de Tablas de Hash.  3. Implementación de Tablas con AVL.	1. Abstracción 2. Análisis

Bloque de contenido 5. Colas con Prioridad y Heaps 

Conceptos	Procedimientos	Actitudes
1. Diferencias funcionales respecto a la Cola normal.  2. Especificación Informal  3. Funcionamiento a partir de Árboles Parcialmente Ordenados y Completos à Heaps.	1. Operaciones con Árbol Parcialmente Ordenado: Inserciones (Flotación), Consulta, Eliminación (Hundimiento) 2. Implementación Estática a partir de APO con Montículos (Heaps) 3. Algoritmo de búsqueda y ordenación: Heapsort.	1. Abstracción  2. Análisis

 Bloque de contenido 6. Análisis de Problemas 

Conceptos	Procedimientos	Actitudes
1. Comprensión y especificación formal de las necesidades funcionales de un problema.  2. Selección y diseño de las estructuras de datos que se utilizarán en los Tipos Abstractas de Datos, optimizando la ocupación en memoria y la complejidad temporal de execución.  3. Repaso y consolidación del todos los TADs vistos.	1. Especificación formal de la firma de los TADs necesarios.  2. Realizar un esquema completo de las estructures de datos seleccionadas.  3. Implementar de forma óptima los TADs diseñados para incorporarlos a la aplicación que resuelve el problema inicial.	1. Abstracción  2. Análisis

 

 

7. Fuentes de información y recursos didácticos

Recursos de información procedentes de varias fuentes: Biblioteca o de otras; así como de otros recursos docentes necesarios para el proceso de aprendizaje. 
Tratamos de clasificarlos con arreglo a criterios diversos: la tipología del recurso y el grado de incidencia en aprendizaje propuesto en la asignatura. 

7.1. Fuentes de información para el aprendizaje. Bibliografía básica (soporte papel y electrónico) 

- AHO, A.V. y de otros. Data Structures and Algorithms. Addison-Wesley, 1983.
- FRANCH GUTIÉRREZ, X. Estructuras de datos. Especificación, diseño e implementación. Edicions UPC, 1994. 

7.2. Fuentes de información para el aprendizaje. Bibliografía complementaria (soporte papel y electrónico) 

- WEIS, M. Data Structures and Algorithm Analysis in C. Benjamin Cummings, 1993.
- PEÑA, R. Diseño de programas. Prentice Hall, 2a Edició, 1999. 

7.3. Fuentes de información para el aprendizaje. Bibliografía de refuerzo (soporte papel y electrónico) 

- NYHOFF, L. TADs, Estructuras de datos y resolución de problemas con C++ (2ª Edición), Pearson/Prentice Hall, 2005. 

7.4. Recursos didácticos. Material docente de la asignatura 

- Transparencias de la Asignatura en formato Power Point
- Lista de Problemas de la Asignatura 

7.5. Recursos didácticos. Materiales y herramientas de soporte 

- Web de la asignatura donde se recogerán enlaces interesantes, información puntual de enunciados y entrega de prácticas, soluciones de ejercicios, etc.

 

8. Metodología

Desde el punto de vista de contenidos teóricos, cada bloque definido corresponde a un tema nuevo y creciente en complejidad hasta que en el último se encara la resolución de problemas usando todo el material visto anteriormente. 

Cada bloque puede contener varias clases magistrales de introducción de conceptos reforzadas por clases de seminarios en las cuales se realizan ejercicios para consolidar los conceptos en los alumnos. Les clases teóricas, con todos los alumnos, requieren que éstos tomen apuntes y los repasen después de cada clase magistral. Los seminarios, con grupoos reducidos de alumnos, suponen un trabajo individual del alumno durante la hora de clase, durante la cual puede ser asesorado de forma minuciosa por el profesor y así solucionar posibles dudas en el momento en que aparecen. Esto permite que el alumno se enfronte a los problemas por sí mismo pero sin el riesgo de quedarse bloqueado. 

El último bloque está pensado para entrenar a los alumnos en les capacidades analíticas y de diseño estructural de problemas más cercanos a casos reales. 

Al final de los blocs 2, 3, 4 i 5 se realiza una sesión de prácticas donde se plantea la realización de un trabajo práctico en equipos de 3. Estas sesiones sirven para entender el enunciado y solucionar las dudas que puedan aparecer. También sirven para iniciar la realización de estos trabajos prácticos aunque se tendrán que desarrollar plenamente y finalizar como trabajo de los equipos fuera de horas de clase. Se tendrán que programar en lenguaje C, como continuación de la asignatura Fundamentos de la Programación de primer curso. 

Las tres primeras prácticas están más enfocadas a desarrollar las habilidades de programación de los alumnos, aunque también promueven, en parte, el análisis y la abstracción. La última práctica, que será más larga que las otras, promoverá un trabajo más profundo y serio intentando resolver un problema más cercano a un caso real. 

Así, tanto la teoría como el trabajo práctico progresan en paralelo y de forma coordinada.