Estructuras de Datos y Algoritmos (EDA)

Lectura adicional: árboles de juego y estrategia minimax.

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.

Se ha publicado en la página de material adicional un documento con más ejercicios de los Temas I y II (especificación e implementación de TAD’s lineales).

Una alternativa a los árboles AVL son los árboles rojinegros.

Aquí tenéis unas transparencias bastante autocontenidas:

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

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 pre-orden 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.
[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.

En clase lo dije bien pero en la transparencia y en el fichero de pseudocódigo correspondiente estaba mal…

Código correcto de la función “posterior” (de comparación de fechas):

función posterior(f1,f2:fecha) devuelve booleano
principio
  devuelve not( iguales(f1,f2)  or  anterior(f1,f2) )
fin

Ya está corregido en las transparencias (transp. nº 12) y en el fichero de pseudocódigo (pág. 2).

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