Algoritmos y Estructuras de Datos (VJ1215)
Curso 2022/2023
Algoritmos y Estructuras de Datos (VJ1215)
Curso 2022/2023
Horas de clases presenciales: 4 (2 teoría + 2 prácticas)
Horas de trabajo no presencial: 6
En clase de teoría nos basaremos en los siguientes apartados de los capítulos 6 "Priority Queues (Heaps)" y 7 "Sorting" del libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss:
Estas animaciones te pueden ayudar a entender este tema:
Animación de un Min-Heap de David Galles.
Animación de Heapsort de David Galles.
Animación Binary Heap + Priority Queue de Jakub Melezinek.
Si no te gusta el libro recomendado arriba o necesitas un texto en castellano, puedes recurrir a los siguientes textos alternativos para entender este tema:
Los siguientes apartados de los capítulos 6 "La API de Colecciones" y 21 "Una cola con prioridad: el montículo binario" del libro "Estructuras de datos en Java" (2013) de M. A. Weiss:
deleteMinbuildHeap: construcción de un montículo en tiempo linealdecreaseKey y mergeEl siguiente apartado del capítulo 13 "Ordenación" del libro "TADs, estructuras de datos y resolución de problemas con C++" (2006) de L. R. Nyhoff:
De las transparencias que acompañan al libro "Algorithm Design" de Jon Kleinberg y Éva Tardos preparadas por Kevin Wayne te pueden interesar estas:
Heapify demo (el algoritmo para construir un montículo con n datos en tiempo O(n) se denomina "Heapify" o "buildHeap" dependiendo del autor; no lo confundas con "Heapsort")
Clase de teoría TE1 20/10
Clase de prácticas LA2 y LA4 25/10, LA1 y LA3 27/10
Este es un ejercicio práctico sobre el algoritmo de Huffman, explicado previamente en clase de teoría y que también nos sirve como primer ejemplo de algoritmo voraz en el tema 5.1. En su implementación haremos uso de estructuras de datos que hemos estudiado en temas anteriores. Concretamente, vamos a ver una aplicación conjunta de árboles binarios (diferentes de los árboles binarios de búsqueda), colas de prioridad y diccionarios.
En temas anteriores hemos puesto el énfasis en aprender a realizar
nuestras propias implementaciones de Tipos Abstractos de Datos. En las
prácticas de este tema vamos a poner el énfasis en aprender a utilizar
implementaciones estándar. Por ello, para trabajar con colas de
prioridad y diccionarios, recurriremos esta vez a las
clases priority_queue y map de la Biblioteca
de Plantillas Estándar de C++ (Standard Template Library,
conocida como STL).
Recurso opcional La página History of the Standard Template Library de la Wikipedia describe el origen de la STL.
Ayuda con C++
La STL incluye
contenedores
que proporcionan
implementaciones genéricas
de los Tipos Abstractos de Datos más importantes (en el ejercicio 6 del tema 3 ya viste
un primer ejemplo de utilización de queue):
stack)
queue)
list con listas enlazadas
y
vector con vectores)
set con árboles de búsqueda y unordered_set con tablas de dispersión)
multiset con árboles de búsqueda y unordered_multiset con tablas de dispersión)
map
con árboles de búsqueda
y unordered_map
con tablas de dispersión)
priority_queue)
Para conocer lo que vas a necesitar en esta práctica, mira los siguientes ejemplos. En ellos no se trata de ilustrar exhaustivamente todo lo que se puede hacer con esas clases, sino las operaciones más importantes. Compílalos, ejecútalos, y trata de entender todo lo que sucede. Puedes consultar al profesor las dudas que tengas. Haz las modificaciones que se sugieren en el código y cualquier otra que consideres conveniente.
priority_queue con enteros Clase de teoría TE1 20/10
priority_queue con objetos Clase de teoría TE1 20/10
priority_queue con punteros Clase de teoría TE1 20/10
string
pair
map
Con esas herramientas, la práctica consiste en lo siguiente: completa
la implementación de la clase Huffman que puedes encontrar en
este fichero
Huffman.h, añadiendo
en Huffman.cpp lo necesario para que funcione este
ejemplo de uso
TestHuffman.cpp
y produzca una salida análoga a
esta TestHuffman.salida
(no necesariamente la misma). Para ello, tu implementación debe
ofrecer los tres métodos públicos que se enumeran a continuación.
Un constructor
Huffman(const vector< pair<char, float> > &)
al que se le pasará una tabla de caracteres a codificar junto con
sus frecuencias. Esa tabla es un vector de pares. Consulta este
ejemplo de uso de pair
para conocer eso.
El constructor, aplicando el algoritmo de Huffman,
debe construir el árbol de Huffman, contando con los atributos
previstos en
Huffman.h. Esos
atributos se han elegido para poder realizar eficientemente los dos
métodos de codificación y decodificación que se piden a
continuación: en el método codificar entraremos por
las hojas y nos moveremos hacia el padre hasta la raíz, y en el
método decodificar entraremos por la raíz y nos
moveremos hacia los hijos hasta una hoja.
Para entrar al árbol de Huffman por la raíz en el
método decodificar, disponemos del
atributo raiz, con el que ya has aprendido a trabajar
en el tema 3.
Para entrar al árbol de Huffman por las hojas en el
método codificar, disponemos del
atributo hojas, que es un diccionario en el que cada
carácter del albabeto será la clave con la que acceder a su
correspondiente nodo hoja. El constructor que crea el árbol de
Huffman se debe encargar también de insertar esos datos en ese
diccionario. Para ello, consulta
este ejemplo de uso
de map.
Esta descripción de la Wikipedia, en su primera lista numerada, te puede ayudar a recordar el algoritmo de Huffman.
Un método
string codificar(const string &) const;
que reciba una cadena de caracteres a codificar y devuelva, en forma de cadena de ceros y unos, el resultado de codificarla empleando el árbol de Huffman obtenido en el constructor. Se lanzará una excepción si el mensaje contiene algún carácter que no estaba en la tabla de carácteres y frecuencias inicial.
Esta descripción de la Wikipedia, en su segunda lista numerada, te puede ayudar a recordar lo que debes hacer para codificar un símbolo. Debes aplicar eso repetidamente, con cada carácter del mensaje a codificar.
Ayuda con C++ Si intentas
utilizar hojas[] en ese método, verás que el
compilador te dice que no puedes utilizar ahí un método que no
es const. Lo puedes resolver utilizando hojas.at().
Un método
string decodificar(const string &) const;
que reciba una cadena de ceros y unos resultante de una codificación previa (no hace falta comprobar que es así) y devuelva el resultado de decodificarla empleando el mismo árbol de Huffman.
Esta descripción de la Wikipedia, en su tercera lista numerada, indica cómo decodificar un mensaje formado por un solo símbolo. Debes aplicar eso repetidamente, hasta decodificar el mensaje completo.
Recursos opcionales
No es un objetivo de esta práctica obtener verdaderas
secuencias de bits, nos conformamos con trabajar con
cadenas de ceros y unos. Opcionalmente, si sientes
curiosidad por cómo convertir esas cadenas en secuencias
de bits, mira este
ejemplo: BitsEmpaquetados.cpp.
Otra posibilidad en C++, más simple, es emplear la
clase bitset,
por
ejemplo: EjemploBitset.cpp.
Clase de teoría TE1 27/10
En el ejercicio 6 del tema 2 comparaste el coste temporal de cuatro implementaciones con estructuras de datos lineales para soportar las siguientes operaciones básicas del TAD Cola de Prioridad:
Añade ahora a ese estudio comparativo tres estructuras de datos más:
El TAD Cola de Prioridad de Doble Fin, que se introdujo en la segunda semana de prácticas del tema 2 (ejercicio 3), se caracteriza por las siguientes operaciones básicas:
Piensa cómo añadir las operaciones eliminarMáximo y consultarMáximo a cada una de las tres nuevas estructuras de datos del apartado a y cuál es el coste temporal en cada caso. ¿Cuál de esas tres soluciones elegirías para soportar las cinco operaciones?
Clase de teoría TE1 03/11
Analiza el coste temporal del siguiente algoritmo de ordenación con cada una de las 7 estructuras de datos consideradas en el ejercicio 2.a para implementar la cola de prioridad:
void ordenar(vector<int> & v) {
ColaDePrioridad cp;
for (int dato : v)
cp.insertar(dato);
int i = 0;
while (cp.talla() > 0) {
v[i] = cp.consultarMínimo();
i = i + 1;
cp.eliminarMínimo();
}
}
Utilizando la
animación
de un Min-Heap de David Galles, compara lo que sucede al insertar
los enteros entre 31 y 1 en orden decreciente empleando la operación
de inserción con lo que sucede al emplear (con su
botón BuildHeap) el algoritmo de construcción de
montículos en tiempo lineal, para ayudarte a entender la diferencia
entre utilizar ese algoritmo y realizar n operaciones de
inserción.
Clase de teoría TE1 03/11
Analiza el
coste temporal del siguiente algoritmo de ordenación si
la clase ColaDePrioridad se implementa con
un montículo binario y en el constructor
de ColaDePrioridad se emplea el algoritmo
de construcción de montículos binarios en tiempo lineal
para inicializar el montículo con los datos que contiene
el vector:
void ordenar(vector<int> & v) {
ColaDePrioridad cp(v);
int i = 0;
while (cp.talla() > 0) {
v[i] = cp.consultarMínimo();
i = i + 1;
cp.eliminarMínimo();
}
}
Clase de teoría TE1 03/11
Para ver cómo funciona el algoritmo de ordenación Heapsort, utiliza la animación de Heapsort de David Galles, hasta entender lo que hace.
Supongamos que debes implementar una variante del TAD Cola de Prioridad que permita realizar las siguientes operaciones:
void insertar(float); void eliminarMinimo(); float consultarMinimo() const; void mezclar(const ColaDePrioridad &);
El objetivo de la cuarta operación es mezclar dos colas de prioridad.
Si cp1 y cp2 son dos colas de prioridad, tras ejecutar
cp1.mezclar(cp2) la cola de prioridad cp1 debe
contener todos los elementos que contenían previamente
cp1 y cp2, mientras que
cp2 no debe modificarse.
Sabemos que las tres primeras operaciones se pueden realizar eficientemente si la estructura de datos empleada para representar internamente la cola de prioridad es un montículo binario. Explica cómo implementarías la cuarta operación con esa estructura de datos. Tu solución debe ser eficiente. Expresa en notación O el tiempo de ejecución en el peor caso de tu solución al mezclar dos colas de prioridad de talla n.
Hemos presentado un algoritmo que permite construir un montículo en tiempo O(n) a partir de n datos iniciales dados. El algoritmo no consiste en hacer n operaciones de inserción, lo cual costaría O(n log n), sino en hacer algo diferente.
¿Sería posible diseñar un algoritmo que, análogamente, a partir de n datos iniciales cualesquiera, construyese en tiempo O(n) un árbol binario de búsqueda o un árbol AVL de talla n con un dato en cada nodo?
¿Cómo podemos cambiar (disminuir o aumentar) la prioridad de un elemento en un montículo binario si sabemos su posición, es decir, si no necesitamos buscarlo? ¿Cuál es el coste temporal en el mejor y en el peor caso de la operación?
¿Qué habría que hacer y cuál sería el coste temporal si no conociésemos la posición del dato y primero tuviésemos que buscarlo en el montículo?
¿Qué harías para que en una cola de prioridad, implementada con un montículo binario, se siga un orden FIFO al eliminar el mínimo cuando hay un empate entre elementos con la mínima prioridad?
Dados dos montículos binarios, ambos de talla n, tienes que comprobar si contienen los mismos datos. Los puedes modificar. Explica cómo lo comprobarías, analiza el coste temporal en el mejor y en el peor caso de tu solución, e indica cuándo se dan ambos casos.
Opcionalmente, en las evaluaciones de cursos anteriores puedes encontrar más ejercicios de este tema si quieres seguir practicando.