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

Materiales de clase de la asignatura de interés para el grupo de mañanas (curso 23-24).

Ricardo J. Rodríguez

Contenido de la página

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)

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)

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)

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

Lección 4. TAD genéricos

Lección 5. TAD fundamentales

Tema II: Tipos de datos lineales

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

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

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

Lección 9. TAD cola genérica

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

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 (grupo de tarde)
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