Departamento de Ciencias de la Computación
e Inteligencia Artificial
Universidad de Granada
Escuela Técnica Superior de Ingeniería Informática
C/ Periodista Daniel Saucedo Aranda s/n, 18071 Granada, España
ESTRUCTURAS DE DATOS
Ingeniería Informática
Primer curso
Segundo cuatrimestre
Número de Créditos: 6T + 1.5P
Profesores: Teoria: Joaquín Fdez-Valdivia.
Tutorias: L (10-14, 16-18), X (11-13, 16-17) (Despacho 12 del Depto. de Ciencias de la Computación e I.A. (Cuarta planta)
PROGRAMA DE TEORÍA:
Módulo 1.- Introducción a la eficiencia de algoritmos.
Eficiencia y complejidad en tiempo y espacio.
Cotas de eficiencia.
Caso peor, caso promedio y análisis amortizado
Cálculo del tiempo de ejecución de un algoritmo.
Módulo 2.- Tipos de datos abstractos
Abstracción en Programación
Abstracción Funcional
Abstracción de datos
Tipos de datos abstractos (TDA)
Especificación. Tipos abstracto y representado
Implementación. TDA en C++.
Ejemplos de TDA
Vector Dinámico
Vector Disperso
Conjunto
Módulo 3.- TDA Lineales.
Especificación e implementación de:
Tipo Pila
Tipo Cola
Tipo Lista
Tipo Cola con prioridad
Módulo 4.- Generalización: Plantillas.
Introducción. Abstracción por parametrización.
Funciones patrón.
Clases patrón.
TDA Lineales con plantillas.
Módulo 5.- Estructuras de datos no lineales: Árboles
Conceptos fundamentales
Arboles generales
Arboles binarios
Recorridos sobre árboles
Heaps. Arboles Parcialmente ordenados
Arboles binarios de búsqueda. Arboles AVL
Otros tipos de árboles
Módulo 6.- Abstracción por iteración.
Contenedores e iteradores.
Iteración en C++.
Ejemplos: Tipo Conjunto y tipo Diccionario.
Módulo 7.- La Standard Template Library (STL) en C++
Contenedores básicos
Contenedores complejos
Módulo 8.- Tablas Hash
Tablas Hash abiertas
Tablas Hash cerradas. Resolucion de colisiones.
Módulo 9.- Grafos
Grafos dirigidos y no dirigidos. Conceptos fundamentales.
Recorridos en profundidad y anchura
TDA Grafo.
PROGRAMA DE PRÁCTICAS:
Se desarrollarán bajo el S.O. linux.
Eficiencia de algoritmos. Con diversos ejemplos analizar la eficiencia teórica vs. eficiencia empírica.
Construcción de TDAs básicos;
Uso e Implementación de TDAs lineales.
Uso e Implementación de TDAs no lineales.
Uso de las STL en ejemplos simples.
Todas las clases se llevarán a cabo en el laboratorio.
BIBLIOGRAFÍA:
Aho, A.V., Hopcroft, J.E., Ullman, J.A. (1987). Data Structures and Algorithms. Addison-Wesley.
Austern, M.H. (1999). Generic programming and the STL. Addison-Wesley.
Budd, T. (1998). data structures in C++ using the STL. Addison-Wesley.
Cline, M. Girou, M., Lomow, M. (1998). C++ FAQ (Second Edition). Addison-Wesley.
Deitel y Deitel, C++ How to program. Cuarta Edición (2003). Prentice Hall.
Eckel, B. Thinking in C++ (2ª edición) (2000). Prentice-Hall.
Fdez-Valdivia, J., Garrido, A., Garcia-Silvente, M. (1998). Estructuras de Datos. Ediciones Gala.
Ford, W. and Topp, W. (1996). Data Structures with C++ Prentice-Hall.
Garrido A., Fdez-Valdivia, J. (2006) Abstracción y Estructuras de Datos en C++. Delta publicaciones
Garrido A. (2005), Fundamentos de programación en C++. Delta publicaciones.
Gilberg, R.F., Forouzan, B.A. (2001). Data structures: A pseudocode approach with C++. Brooks/Cole.
Josuttis, N.M. (1999). The C++ Standard Library: A Tutorial and Reference. Addison-Wesley.
Koenig, A., Moo, B.E. (2000). Accelerated C++: Practical programming by example. Addison-Wesley.
Musser, D.R. Saini, A. (1996) STL Tutorial and reference guide. Addison-Wesley.
Robson, R. (2000) Using the STL (2nd ed.) Springer Verlag.
Sedgewick, R. (1990). Algorithms in C++. Addison-Wesley.
Stroustrup B. (2002). El lenguaje de Programación C++. Edicion Especial. Addison-Wesley.
Weiss, M.A. (2000). Estructuras de datos en Java. Addison-Wesley.
MÉTODO DE EVALUACIÓN:
Junio:
Un examen al final del cuatrimestre (80%).
Prácticas a realizar a lo largo del cuatrimestre (20%).
Se podrán sacar puntos adicionales con trabajos a realizar a lo largo del cuatrimestre.
Septiembre:
Un examen escrito (parte teórica (80%) y parte práctica (20%))..
Las notas de prácticas de Junio se guardarán para la convocatoria de Septiembre.
RECOMENDACIONES AL ALUMNO:
Se requiere una perfecta coordinacion en el estudio con la asignatura Metodologia de la Programación II, tanto a nivel teórico como práctico.