Estructuras de Datos y Algoritmos (EDA)

Las colas con prioridad (y por tanto la estructura de datos montículo con la que se representan en memoria) se utilizan a menudo para mejorar la eficiencia de algoritmos en los que iterativamente se precisa conocer el mínimo (o máximo) de un conjunto de valores y eliminarlo del conjunto. Ejemplo:

Si utilizamos una cola con prioridades (montículo), añadiéndole una operación de reducción de clave, el algoritmo anterior queda de la siguiente forma:

(Detalles: en la asignatura Algoritmia Básica, de la Especialidad en Computación)

———

Por supuesto, la utilidad del algoritmo anterior se obtiene si n es grande.

Se han publicado en la página de material adicional más enunciados de ejercicios de los Temas I y II (especificación e implementación de TADs lineales).

Se recuerda que (como dice la Guía Docente de la asignatura):

La dedicación del estudiante para alcanzar los resultados de aprendizaje en esta asignatura se estima en 157 horas distribuidas del siguiente modo:

• 49 horas, aproximadamente, de actividades presenciales (clases teóricas, de problemas y prácticas en laboratorio)
• 41 horas de trabajo de programación en equipos de 2 personas para desarrollar los programas propuestos en las prácticas de laboratorio
• 61 horas de estudio personal efectivo (estudio de apuntes y textos, resolución de problemas, preparación clases y prácticas, desarrollo de programas)
• 6 horas de examen final de teoría escrito y de prácticas en laboratorio

Si bien la lección no está incluida en el programa de la asignatura, dado que en la clase de hoy (grupo de mañanas) ha surgido el tema al comparar la versión recursiva del recorrido en preorden de un árbol binario con la versión iterativa que utiliza una pila auxiliar, se incluye aquí un texto que trata la transformación de algoritmos recursivos en iterativos.

Pdf descargable aquí.

Haz clic en el cuadro negro de arriba para que empiece…

Directamente desde la Universidad de Stanford. Recomendable además leer el documento sobre “punteros y memoria” de la misma Universidad.

El quicksort, tal y como aparece en los libros, tiene un coste asintótico cuadrático en el caso peor.

No obstante, existe una modificación no trivial del quicksort que sí consigue un coste asintótico O(n logn). Consiste en elegir la mediana como el pivote que se utiliza para la partición del vector en dos trozos, en cada llamada recursiva del quicksort.

El cálculo de la mediana de los n datos de un vector es un caso particular del conocido como problema de selección, consistente en calcular el estadístico de orden k de esos datos (es decir, el dato que ocuparía la posición k en el supuesto en que se ordenasen los datos de menor a mayor). Si n es impar, la mediana sería el estadístico de orden (n+1)/2; si por el contrario n es par, hay dos medianas que son los estadísticos de orden n/2 y n/2 + 1.

Como decía, se conoce un algoritmo de coste asintótico lineal en el caso peor para el problema de selección y, por tanto, para el cálculo de la mediana. Os lo incluyo aquí debajo, extraído del libro Introducion to Algorithms, de Cormen, Leiserson, Rivest y Stein.

Los montículos se utilizan a menudo para mejorar la eficiencia de algoritmos en los que iterativamente se precisa conocer el mínimo (o máximo) de un conjunto cambiante de valores. Ejemplo:

Detalles: aquí (transparencias 26 a 37).

———

Por supuesto, utilidad de lo anterior: si n es grande.

Están disponibles las soluciones de los ejercicios de clase de los días 13 y 16 de diciembre.

Los árboles AVL no son la única forma de conseguir árboles binarios de búsqueda cuya altura sea de orden logarítmico en el número de nodos. Una alternativa bastante conocida son los árboles rojinegros. Se incluyen a continuación unas transparencias explicativas tomadas de una asignatura optativa del plan en extinción y más abajo un enlace a un applet.

El applet que ya conocéis de árboles AVL permite también hacer pruebas con un árbol rojinegro (seleccionando “RB” en el menú de la derecha del applet).

En la zona de acceso restringido de esta web (acceso con usuario y clave comunicados en clase) están disponibles algunas páginas de documentación sobre árboles AVL:

• 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).

Mañana martes y también el viernes serán clases de problemas. Los enunciados están disponibles aquí.