Descripción de la asignatura
Examen de Febrero de 2007. Enunciado [pdf] y Solución [pdf]
Examen de Septiembre de 2007. Enunciado [pdf] y Solución [pdf]
Examen de Diciembre de 2007. Enunciado [pdf] y Solución [pdf]
Examen de Febrero de 2008. Enunciado [pdf] y Solución [pdf]
Examen de Septiembre de 2008. Enunciado [pdf] y Solución [pdf]
Programa de la asignatura en [pdf]
Año académico: 2008/09
Centro: Escuela Politécnica Superior
Estudios: Ingeniería Técnica en Informática de Sistemas
Asignatura: Estructuras de Datos y Algoritmos
Ciclo: 1º
Curso: 2º
Cuatrimestre: 1º
Carácter: Troncal
Créditos teóricos: 4,5 (Horas Semanales: 3)
Créditos prácticos: 4,5 (Horas Semanales: 3)
Profesor/es: Antonio Corral Liria y Francisco Guil Reyes.
Área: Lenguajes y Sistemas Informáticos
OBJETIVOS GENERALES
Con esta asignatura se pretenden conseguir los siguientes objetivos principales:
• Valorar la importancia de la programación con Tipos Abstractos de Datos (TAD) como base del diseño modular, diferenciando los conceptos de especificación e implementación de un TAD.
• Estudiar y realizar las implementaciones de los TAD a partir de su especificación, utilizando el paradigma de la POO y, en concreto, el lenguaje de programación C++ y las STL.
• Conocer las estructuras de datos fundamentales y los algoritmos principales que se utilizan para su manipulación. Todo ello, extendiendo los conocimientos adquiridos en la asignatura de Metodología de la Programación cursada en primer curso.
• Tener la capacidad de elección de la estructura de datos adecuada para cada tipo de problema, y los algoritmos más eficientes que la gestionan.
• Saber decidir entre dos o más algoritmos similares aplicados a una misma estructura de datos sobre la base de la eficiencia de cada uno de ellos.
• Aprender a combinar diferentes estructuras de datos para resolver problemas complejos.
CONOCIMIENTOS PREVIOS RECOMENTADOS
Haber cursado y superado las asignaturas troncales de primer curso: Introducción a la Programación y Metodología de la Programación.
TEMARIO
PROGRAMA DE TEORÍA:
TEMA 1 Tipos Abstractos de Datos (3 horas)
1.1 Estructuras de datos
1.2 Tipos Abstractos de Datos (TAD)
1.3 Especificación algebraica de un TAD
1.4 TAD genéricos
1.5 Paso de la especificación a la implementación de TAD
1.6 Implementación de TAD: La librería estándar de plantillas (STL)
TEMA 2 Contenedores e Iteradores (2 horas)
2.1 Contenedor simple
2.2 Tablas
2.3 Contenedores asociativos
2.4 Iteradores
TEMA 3 TAD Lineales (10 horas)
3.1 Análisis de algoritmos aplicado a las estructuras de datos
3.2 Concepto y especificación de estructura lineal
3.3 El TAD Stack (pila)
3.4 El TAD Queue (cola)
3.5 El TAD Vector (vector)
3.6 El TAD List (lista(
3.7 El TAD Sequence (secuencia)
TEMA 4 El TAD Tree (12 horas)
4.1 Conceptos y terminología básica. TAD Tree
4.2 Árbol binario (BinaryTree). Especificación e implementación
4.3 Recorridos sobre árboles binarios
4.4 Árboles binarios de búsqueda (BinarySearchTree)
4.5 TAD PriorityQueue y Heaps
4.6 Árboles binarios de búsqueda equilibrados: AVLTree y Red-Black Tree (RBTree)
4.7 Árboles de búsqueda multicamino: B Tree
TEMA 5 El TAD Graph (12 horas)
5.1 Conceptos y terminología básica. TAD Graph
5.2 Especificación e implementación de grafos
5.3 Recorridos sobre grafos
5.4 Conectividad
5.5 Ordenación topológica
5.6 Caminos de coste mínimo sobre grafos
5.7 Árbol de recubrimiento de coste mínimo
TEMA 6 El TAD Dictionary (6 horas)
6.1 Conceptos y terminología básica. TAD Dictionary
6.2 Especificación e implementación
6.3 Tabla dispersa
6.4 Función de dispersión
6.5 Resolución de colisiones
6.6 Aspectos de la implementación
6.4 Contenedores asociativos. set y map
PROGRAMA DE PRÁCTICAS DE LABORATORIO:
Las prácticas de laboratorio consistirán en la realización de ejercicios relacionados con las estructuras de datos y algoritmos estudiados en el temario teórico utilizando el lenguaje de programación C++. Además, se realizará un supuesto práctico donde se hará uso de varias estructuras de datos y algoritmos explicados en clase. Además, para poder seguir la asignatura es recomendable haber cursado y/o aprobado las asignaturas: Introducción a la Programación y Metodología de la Programación, ambas de primer curso de ITIS.
Práctica I. Aspectos generales de programación en C++ (6 horas)
Práctica II. TAD lineales (9 horas)
Práctica III. TAD Tree (12 horas)
Práctica IV. TAD Graph (12 horas)
Práctica V. TAD Dictionary. Tablas Hash (6 horas)
BIBLIOGRAFÍA
Bibliografía Básica
Zenón José Hernández Figueroa y otros. Fundamentos de estructuras de datos. Soluciones en Ada, Java y C++. Thomson. 2005.
Larry R. Nyhoff. TADs, estructuras de datos y resolución de problemas con C++. Pearson-Prentice-Hall. 2005.
Luis Joyanes Aguilar, Lucas Sánchez García, Ignacio Zahonero Martínez. Estructuras de datos en C++. McGraw-Hill. 2007.
Elliot B. Koffman, Paul A.T. Wolfgang. Objects, abstraction, data structures and design using C++. John Wiley & Sons, Inc. 2003.
Bibliografía Complementaria
Osvaldo Cairó, Silvia Guardati. Estructuras de datos. McGraw-Hill. 2006.
Román Martínez, Elda Quiroga. Estructuras de datos. Referencia práctica con orientación a objetos. Thomson-Learning. 2002.
Narciso Martí Oliet, Yolanda Ortega Mallén, José A. Verdejo López. Estructuras de datos y métodos algorítmicos. Ejercicios resueltos. Pearson-Prentice-Hall. 2004.
Luis Joyanes Aguilar, Matilde Fernández Azuela, Lucas Sánchez García, Ignacio Zahonero Martínez. Estructuras de datos en C (Serie Schaum). McGraw-Hill. 2005.
John Lewis, Joseph Chase. Estructuras de datos con Java. Diseño de estructuras y algoritmos. Pearson-Addison-Wesley. 2006.
Adam Drozdek. Data structures and algorithms in C++. Thomson. 2005.
Michael T. Goodrich, Roberto Tamassia, David M. Mount. Data structures and algorithms in C++. John Wiley & Sons, Inc. 2003.
Mark Allen Weiss. Data structures and problem solving using C++. Addison-Wesley. 2000.
Fco. Javier Ceballos. Programación orientada a objetos con C++. Ra-Ma. 2003.
EVALUACIÓN
CONVOCATORIA DE FEBRERO
Para aprobar la asignatura en esta convocatoria, el alumno deberá aprobar el examen y cada una de las pruebas prácticas de forma independiente. El alumno deberá también asistir obligatoriamente a las clases de laboratorio. Las prácticas serán individuales o en parejas como máximo. Durante el cuatrimestre se realizarán varias pruebas prácticas usando el lenguaje de programación C++. Una vez finalizada cada práctica, se citarán rigurosamente a los grupos para que dichos miembros defiendan la práctica ante el profesor en horas de tutorías o en las clases de prácticas (al final de las sesiones).
Calificación Final: Examen teórico-práctico (evaluado sobre 10 puntos), que constituye el 100% de la nota final, ya que dicha prueba consta de una parte teórica y una parte práctica (ejercicios teóricos y de implementación). Cada parte debe de aprobarse separadamente.
Pruebas de prácticas: Será necesario superar las pruebas de prácticas para poder aprobar la asignatura.
RESTO DE CONVOCATORIAS
Para aprobar la asignatura en estas convocatorias, se realizará un único examen escrito teórico-práctico con una valoración máxima de 10 puntos, debiéndose de aprobar la parte teórica y la parte práctica de forma separada. A los alumnos que hubieran superado las prácticas se les conservarán para sucesivas convocatorias.