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

• 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:

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

• 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

• Especificación e implementación de:
  • Tipo Pila
  • Tipo Cola
  • Tipo Lista
  • Tipo Cola con prioridad

• Introducción. Abstracción por parametrización.
• Funciones patrón.
• Clases patrón.
• TDA Lineales con plantillas.

• Conceptos fundamentales
• Arboles generales
• Arboles binarios
• Recorridos sobre árboles
• Heaps. Arboles Parcialmente ordenados
• Arboles binarios de búsqueda. Arboles AVL
• Otros tipos de árboles

• Contenedores e iteradores.
• Iteración en C++.
• Ejemplos: Tipo Conjunto y tipo Diccionario.

• Contenedores básicos
• Contenedores complejos

• Tablas Hash abiertas
• Tablas Hash cerradas. Resolucion de colisiones.

• Grafos dirigidos y no dirigidos. Conceptos fundamentales.
• Recorridos en profundidad y anchura
• TDA Grafo.

PROGRAMA DE PRÁCTICAS:

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

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: