Material de clase del grupo de mañanas (2022-23)
- 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)
Tema I: Programación con Tipos Abstractos de Datos (TAD)
Lectura obligatoria: Tema I de los apuntes, Anexo 6 de los apuntes (sintaxis de especificaciones y pseudocódigo). 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
- 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: El 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: Implementación dinámica de pilas
- Lección 9: El TAD cola genérica
- Lección 10: El TAD diccionario. Implementación con listas enlazadas ordenadas
- Diapositivas (esquema)
- Diapositivas (detalles implementación)
- Costes representación estática versus dinámica con lista.
- Codificación en C++ (fragmento)
- Enunciados de ejercicios para casa y para clases de problemas:
- Para el viernes 14 de octubre (y el 21): hoja 1 de ejercicios (especificación de TAD/implementación de TAD lineales)
- Para ir haciendo en casa: hoja 2 de ejercicios (más especificación de TAD/implementación de TAD lineales).
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 (tries): sección 5.6 del libro de Z.J. Hernández et al. la bibliografía.
- Lección 11: Introducción a los árboles
- Lección 12: Árboles binarios
- Lección 13: Árboles binarios de búsqueda (ABB)
- Diapositivas
- Un applet. Si no te funciona en línea, puedes descargarlo de aquí y ejecutarlo localmente.
-
Esta visualización (sacada de http://algs4.cs.princeton.edu/32bst/) muestra el resultado de insertar 255 claves en un ABB, en orden aleatorio. Se muestran el nº de claves (N), el máximo nº de nodos en un camino de la raíz a una hoja (max), el nº medio de nodos en un camino de la raíz a una hoja (avg), y el nº medio de nodos en un camino de la raíz a una hoja en un ABB perfectamente equilibrado con las mismas claves (opt). ( Resultado final.)
- Lección 14: Árboles AVL
- Diapositivas
- Apéndice a las diapositivas
- Tabla resumen de costes de implementaciones de diccionarios
Un archivo Flash ( acceso restringido, en todos estos casos: usuario/clave = eda/tad)- Un applet (si no te funciona en línea, puedes descargarlo de aquí y ejecutarlo localmente; si tampoco, 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).
- Lección 15: Árboles n-arios
- Lección 16: Árboles n-arios de búsqueda
- Diapositivas
- Un applet (si no te funciona en línea, puedes descargarlo de aquí y ejecutarlo localmente; si tampoco, puedes probar con esta versión anterior )
- Otro visualizador (JavaScript+HTML5)
- Un visualizador para árboles B+. Otro
- Páginas sobre árboles B del libro de Joyanes et al. (1999) de la bibliografía (acceso restringido)
- Páginas sobre árboles B del libro de Weiss (2000) de la bibliografía (acceso restringido)
- Páginas sobre árboles B en el 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. Otro applet (stringology -> trie ; si no te funciona en línea, puedes descargarlo de aquí y ejecutarlo localmente; si tampoco, puedes probar con esta versión anterior)
- Otro visualizador (JavaScript+HTML5)
- Otro
- 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 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, puedes probar con esta versión anterior )
- Un applet del heapsort (acceso restringido)
- Comparación práctica de velocidades de métodos de ordenación: un applet, otro applet
- Enunciados de ejercicios para casa y para clases de problemas
- Para el viernes 11 de noviembre: Hoja 3 de ejercicios (sobre árboles binarios)
- Para el viernes 18 de noviembre: Hoja 4 de ejercicios (árboles binarios de búsqueda)
- Para el viernes 25 de noviembre: Hoja 5 de ejercicios (árboles n-arios)
- Para el viernes 2 de diciembre y siguiente: Hoja 6 de ejercicios (tries y montículos)
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 (on-line), o capítulo sobre tablas hash del libro de Mehta y Sahni, de la bibliografía (acceso restringido).
- Lección 19: El 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)
- Lección 20: Tablas multidimensionales
Enunciados de ejercicios de repaso:
- Para el viernes 16 de diciembre y martes 20: Hoja 7 de ejercicios (repaso).