Información general

Describe información de interés para los estudiantes de la asignatura.

Ricardo J. Rodríguez
Contenido de la página

Guía Docente oficial

La guía docente de esta asignatura está disponible en este enlace.

Objetivos

El alumno deberá, tras cursar esta asignatura, poder enfocar el diseño de una estructura de datos de forma abstracta, pensando primero en las operaciones y comportamientos observables por los usuarios de la misma y, más tarde, en los detalles de realización (representación de datos e implementación de operaciones). Deberá poder especificar rigurosamente dicho comportamiento observable sin mencionar las decisiones de implementación. Deberá conocer las familias básicas de soluciones algorítmicas y de estructuración de datos para familias de problemas y ser capaz de identificar un problema aparentemente nuevo con alguna de esas familias.

Objetivo general

  • Proporcionar nuevos elementos que permitan superar las limitaciones del diseño descendente para el diseño de programas de media y gran escala;
  • Estas limitaciones se traducen esencialmente en dos necesidades:
    1. Modularizar el diseño de los programas facilitando el desarrollo independiente de cada módulo, y
    2. Proporcionar nuevos mecanismos que permitan razonar sobre la corrección de programas en los que utilicemos datos estructurados;
  • La respuesta a estas necesidades la proporciona el diseño con TAD’s (tipos abstractos de datos).

Objetivos concretos

Aprender a:

  • Definir tipos abstractos de datos (TAD’s) independientemente de su implementación.
  • Implementar TAD’s en un lenguaje de programación modular.
  • Implementar y utilizar algunos TAD’s fundamentales, como pilas, colas, listas, árboles de búsqueda, tablas hash y grafos.
  • Comparar distintas alternativas de implementación de TAD’s con respecto al tiempo de ejecución de algoritmos y al uso de la memoria.
  • Afrontar el diseño modular de programas de tamaño medio identificando, definiendo e implementando los TAD’s necesarios.
  • Aplicar los esquemas algorítmicos básicos (como dividir para vencer, búsqueda con retroceso, voracidad…) a la resolución de problemas.

Programa

  1. Programación con Tipos Abstractos de Datos.
  2. Tipos de datos lineales.
  3. Tipos de datos arborescentes.
  4. Tipos de datos funcionales.
  5. Introducción a los grafos.
  6. Introducción a los esquemas algorítmicos.

Bibliografía

  • Bibliografía básica

    • Data Structures and Algorithm Analysis in C++, M.A. Weiss, 4th Edition, Pearson/Addison Wesley, 2013.
    • Fundamentos de Estructuras de Datos. Soluciones en Ada, Java y C++, Z.J. Hernández y otros, Thomson, 2005.
    • Data Structures and Algorithm Analysis in C++, C.A. Shaffer, 3rd Edition, Dover Publications, 2011.
    • Apuntes de Estructuras de datos y algoritmos, J. Campos, 2da ed., v4, 2022.

  • Biblografía sobre C++

    • The C++ Programming Language, B. Stroustrup, 4th Edition, Addison-Wesley, 2013.

  • Ejercicios

    • Estructura de datos y algoritmos. Ejercicios y problemas resueltos, N. Martí Oliet, Y. Ortega Mallén, J.A. Verdejo López, Pearson Prentice Hall, 2003.
    • Estructura de datos. Libro de problemas, L. Joyanes, I. Zahonero, M. Fernández y L. Sánchez, McGraw Hill, 1999.

  • Bibliografía complementaria

    • Estructuras de datos. Especificación, diseño e implementación, X. Franch, 3a edición, Ediciones UPC, 2001.
    • Handbook of Data Structures and Applications, D.P. Mehta y S. Sahni, Chapman & Hall/CRC, 2005