Archive for the ‘Material’ Category
Lectura avanzada: transformación de algoritmos recursivos en iterativos
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.
[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í.
Llévate un Binky para tus días de fiesta
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.
Modificación del quicksort para conseguir coste O(n log n) en el caso peor
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.
A vueltas con los montículos
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.
| n | 10 | 100 | 1000 | 10000 | 100000 | 1000000 |
| n log n | 30 | 600 | 10000 | 130000 | 1600000 | 19000000 |
| n2 | 100 | 10000 | 1000000 | 100000000 | 10000000000 | 1000000000000 |
Soluciones de ejercicios
Están disponibles las soluciones de los ejercicios de clase de los días 13 y 16 de diciembre.
Árboles rojinegros
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).
Material sobre AVL’s
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 el viernes: clases de problemas
Mañana martes y también el viernes serán clases de problemas. Los enunciados están disponibles aquí.
Soluciones de ejercicios
Próximos lunes 28 y martes 29: clases de problemas
Las hojas de ejercicios se pondrán en las páginas de material de los grupos de mañana y tarde.