Material de clase (grupo mañanas, curso 24-25)

Apuntes y chuletas de la asignatura

• Apuntes
• Chuleta con la notación para escribir especificaciones (última versión: 2020-09-21). English version (optional for international students)
• Chuleta con la notación algorítmica (pseudocódigo) que se utilizará en clase (última versión: 2018-10-18). English version (optional for international students)

Hojas de problemas (ejercicios)

1. Especificación e implementación de TAD lineales (solución)

2. Más especificación e implementación de TAD lineales (solución)

3. Árboles binarios (solución)

4. Árboles binarios de búsqueda (solución)

5. Árboles n-arios (solución)

6. Tries (solución)

7. Tablas multidimensionales (solución)

8. Ejercicios de repaso (solución)

Presentación de la asignatura

• Diapositivas

Tema I: Programación con Tipos Abstractos de Datos (TAD)

Lectura obligatoria: Tema I y Anexo 6 (sintaxis de especificaciones y pseudocódigo) de los apuntes. Lectura optativa: secciones 1.1 y 1.2 del capítulo 1 del libro de Z.J. Hernández et al. de la bibliografía.

Lección 1. Tipos Abstractos de Datos (TAD)

• Diapositivas
• Definición de TAD
• TAD bool y nat (signaturas)
• TAD conjunto de caracteres
• Ejercicio de la tabla de frecuencias
• Ventajas de la programación con TAD
• Conferencia de Barbara Liskov, creadora de los TAD, sobre TAD y modularidad (Barbara Liskov, Premio Turing 2008)

Lección 2. Especificación de TAD

• Diapositivas
• Características generales
• Ejemplo de especificación algebraica
• Otro ejemplo de especificación algebraica
• Especificación no formal
• Chuleta de la sintaxis de especificación no formal
• Ejemplos: conjuntos de caracteres, fechas, tablas de frecuencias, pilas (genéricas; de genericidad ya hablaremos)
• Otro ejemplo: TAD PilaDelimitadores (código fuente)

Lección 3. Implementación de TAD

• Diapositivas
• Características de una buena implementación
• Implementación modular de TAD
• Chuleta del pseudocódigo que emplearemos (en clase y en exámenes). English version (optional for international students)
• Codificación en C++
• Ejemplos: fechas, conjuntos de caracteres, tabla de frecuencias
• Otro ejemplo: TAD PilaDelimitadores (código fuente)

Lección 4. TAD genéricos

• Diapositivas
• Sacos genéricos en C++
• Otro ejemplo: TAD Pila genérica (implementación estática) (código fuente)

Lección 5. TAD fundamentales

• Diapositivas
• Ejemplo de interfaz de un módulo de conjuntos genéricos
• Sobre el iterador para una agenda (práctica 1)
• Ejemplo de clase: TAD HypatiaX (enunciado)

Tema II: Tipos de datos lineales

Lección 6. TAD pila genérica. Definición e implementación estática

• Diapositivas
• Especificación
• Implementación estática
• Otros TADs de interés: TAD conjunto genérico (implementación estática), TAD lista genérica (implementación estática)
• Ejemplo de clase: TAD HypatiaX (solución)

Lección 7. Datos puntero y estructuras dinámicas de datos

• Diapositivas
• Vídeo de “binky” (Universidad de Stanford). Documento sobre “punteros y memoria” de la misma Universidad

Lección 8. TAD pila genérica. Definición e implementación dinámica

• Diapositivas
• Implementación en pseudocódigo
• Codificación en C++
• Ejemplos de aplicación

Lección 9. TAD cola genérica

• Diapositivas
• Especificación
• Una implementación estática (circular)
• Implementación dinámica en pseudocódigo
• Codificación en C++ (fragmento)
• Ejemplos de aplicación

Lección 10. TAD diccionario. Implementación con listas enlazadas ordenadas

• Diapositivas
• Costes representación estática versus dinámica con lista.
• Codificación en C++ (fragmento)

Tema III: Tipos de datos arborescentes

Lectura obligatoria: Tema III de los apuntes. Lectura optativa: capítulos 4 y 6 del libro de M.A. Weiss de la bibliografía. Para la lección 17: sección 5.6 del libro de Z.J. Hernández et al. de la bibliografía.

Lección 11. Introducción a los árboles

• Diapositivas

Lección 12. Árboles binarios

• Diapositivas

Lección 13. Árboles Binarios de Búsqueda (ABB)

• Diapositivas
• Applet de Java (si no te funciona en línea, prueba a descargarlo y ejecutarlo localmente)

Lección 14. Árboles AVL

• Diapositivas
• Tabla resumen de costes de implementaciones de diccionarios
• Applet de Java (si no te funciona en línea, prueba a descargarlo de aquí y ejecutarlo localmente; si tampoco te funciona, puedes probar con esta versión anterior)
• Otro visualizador (JavaScript + HTML5)
• Una implementación en lenguaje Ada basada en los apuntes de clase
• Capítulos sobre AVL en algunos libros (acceso restringido):
  • del libro de X. Franch citado en la bibliografía,
  • del libro de Z.J. Hernández et al. citado en la bibliografía,
  • del libro Algorithms and Data Structures (2004) de N. Wirth (libro completo publicado en este enlace) de la bibliografía.

Lección 15. Árboles n-arios

• Diapositivas

Lección 16. Árboles n-arios de búsqueda

• Diapositivas
• Applet de Java (si no te funciona en línea, prueba a descargarlo de aquí y ejecutarlo localmente; si tampoco te funciona, puedes probar con esta versión anterior)
• Otro visualizador (JavaScript + HTML5)
• Un visualizador para árboles B+. Otro visualizador.
• Páginas sobre árboles B en algunos libros (acceso restringido):
  • del libro de Joyanes et al. (1999) de la bibliografía.
  • del libro de Weiss (2000) de la bibliografía (acceso restringido)
  • capítulo 10 del libro de C. A. Shaffer de la bibliografía (on-line)

Lección 17. Árboles lexicográficos (o tries)

• Diapositivas
• Un applet de Java. Otro applet de Java (stringology -> trie; si no te funciona en línea, prueba a descargarlo de aquí y ejecutarlo localmente; si tampoco te funciona, puedes probar con esta versión anterior)
• Otro visualizador (JavaScript + HTML5)
• Otro visualizador
• Capítulo sobre Tries del libro de Mehta y Sahni (2005) de la bibliografía (acceso restringido)
• Una implementación nodo-vector y otra nodo-lista (ambas en lenguaje Ada).
• Una variante mejorada: PATRICIA

Lección 18. Colas con prioridad, montículos y el heapsort

• Diapositivas
• Un enlace externo sobre implementaciones de montículos y variantes
• Una idea para una implementación dinámica. Pero, recordad, la implementación habitual es ESTÁTICA.
• Un visualizador (JavaScript + HTML5)
• Un applet de Java para visualizar montículos de máximos o de mínimos (si no te funciona en línea, puedes descargarlo de aquí y ejecutarlo localmente; si tampoco te funciona, puedes probar con esta versión anterior)
• Un applet de Java del heapsort (acceso restringido)
• Comparación práctica de velocidades de métodos de ordenación: un applet, otro applet

Tema IV: Tipos de datos funcionales

Lectura obligatoria: Lección 19 de los apuntes. Lectura optativa: sección 9.4 del libro de C. A. Shaffer de la bibliografía (recurso en línea), o capítulo sobre tablas hash del libro de Mehta y Sahni, de la bibliografía (acceso restringido).

Lección 19. TAD tabla y las tablas dispersas (hash)

• Diapositivas
• Material de clase de la profesora Elvira Mayordomo (curso 03-04)
• Animaciones:
  • Resolución de colisiones por encadenamiento (en zonas de desbordamiento)
  • Recolocación en el mismo vector soporte. Otra animación

Lección 20. Tablas multidimensionales

• Diapositivas