Estructuras de Datos y Algoritmos (EDA)

Directamente desde la Universidad de Stanford.

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

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

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.

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.

Haz clic en la imagen 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.

Atención: se ha corregido un detalle de codificación C++ en las transparencias del apéndice de la lección 8 (implementación de la operación vacía) y en la lección 9 (implementación de la operación vacía de pilas y colas). Se ha añadido además la implementación de alguna operación más (anyadirPrimero en el apéndice de la lección 8 y apilar en la lección 9), para ilustrar la creación de nuevos datos dinámicos.

Tenéis un par de ejemplos no triviales de utilización del TAD pila en este enlace.

Una alternativa a los árboles AVL para construir árboles binarios de búsqueda de altura logarítmica en el número de nodos son los árboles rojinegros.

Aquí tenéis unas transparencias bastante autocontenidas (acceso restringido, acceder con usuario y clave habituales):

Y el capítulo de un libro con una implementación “top-down”: en C++, y en Java (acceso restringido, acceder con usuario y clave habituales).

Si bien la lección no está incluida en el programa de la asignatura, se incluye aquí un texto que trata la transformación de algoritmos recursivos en iterativos.
[issuu width=420 height=297 embedBackground=%23000000 backgroundColor=%23222222 documentId=121105155255-44efe93b155e49a6a28f9f29874148d6 name=recursivo_a_iterativo username=javier.campos tag=algoritmos unit=px v=2]
Pdf descargable aquí (autor: Javier Campos).

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.