Vídeos sobre algoritmos de ordenación
Hay varios vídeos ilustrando los diferentes métodos de ordenación en la red.
Aquí podéis ver uno de ellos que muestra 15 métodos distintos de ordenación en 6 minutos.
Aquí hay otros de “bailarines ordenándose”:
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.
Uso de colas con prioridad para acelerar alguna fase de otros algoritmos
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.
| n | 10 | 100 | 1000 | 10000 | 100000 | 1000000 |
| n log n | 30 | 600 | 10000 | 130000 | 1600000 | 19000000 |
| n2 | 100 | 10000 | 1000000 | 100000000 | 10000000000 | 1000000000000 |
Sobre la implementación de montículos
La implementación habitual (vista en clase, transparencia 16) de un montículo es estática, es decir, basada en almacenar el árbol en un vector, por niveles, desde la raíz hacia abajo y de izquierda a derecha para cada nivel.
Lógicamente, esa implementación plantea el típico problema (en representaciones estáticas) de saturación cuando la capacidad del vector se completa.
Hay una solución para ese problema. Se basa en tener un vector de punteros a vectores de datos en el que inicialmente sólo se usa el primer puntero a vector, y apunta a un montículo almacenado como el visto en clase (en el vector, por niveles de arriba a abajo y de izquierda a derecha). Cuando ese primer vector de datos se llena, se usa el siguiente puntero a vector para apuntar a un nuevo vector en el que se guardará el siguiente nivel del montículo. Si ese nivel también se llena, se genera espacio para un nuevo nivel (puntero a un nuevo vector), etcétera.
Está explicado en esta página.
Cambio de horario
El jueves 3 de noviembre tendrá horario de martes, por tanto habrá clase de EDA.
Para pasar un rato durante las fiestas del Pilar…
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.
Sobre las prácticas de esta asignatura
Como regla general, la nota de prácticas en esta asignatura no se guarda de un curso para el siguiente.
Presentación de la asignatura (curso 2016-17)
La presentación de la asignatura para el curso 2016-17 es el próximo lunes 19 de septiembre con los siguientes horarios:
- grupo de mañana: 9:00 horas, aula A01 (edificio Ada Byron)
- grupo de tarde: 15:00 horas, aula A11 (edificio Ada Byron)
Resultado de la segunda convocatoria del curso 2015-16
Se han publicado en la sección de información general de Moodle las notas y una solución del examen escrito de EDA correspondientes a la segunda convocatoria del curso 2015-2016.
Las revisiones del examen se atenderán (se debe consultar la solución del examen con antelación):
• Ejercicio 1 con Yolanda Villate (Despacho 0.06), el jueves 15 de 16:00 a 18:00.
• Ejercicios 2 y 3 con Javier Campos (Despacho 1.12), el jueves 15 de 10:00 a 12:00.
Segunda convocatoria
Segunda convocatoria de evaluación del curso 2015-16:
- Examen escrito: 5 de septiembre de 2016 a las 10:00 horas. Aula 19 del Edificio Torres Quevedo.
- Examen de laboratorio: 6 de septiembre de 2016 a las 16:00 horas. Laboratorio L.0.04 del Edificio Ada Byron.
Estarán exentos de hacer el examen de laboratorio quienes hayan superado las prácticas realizadas durante el curso.
Se recuerda que en los exámenes de la asignatura no está permitido el uso de libros, apuntes, la red de comunicaciones, dispositivos de almacenamiento externo, ni el uso de instrumentos electrónicos (teléfonos móviles, calculadoras, portátiles, tabletas, etc.). Por ello, siguiendo recomendaciones textuales de la Universidad de Zaragoza, se establece: “la prohibición de acceder a los exámenes portando cualquier dispositivo móvil, activado o no, ya que podría ser utilizado en cualquier momento de la evaluación como herramienta para prácticas fraudulentas. Esto es, se entenderá que si un estudiante porta un dispositivo móvil dentro del aula de exámenes, es como si tuviera una herramienta fraudulenta y será expulsado del aula con los efectos académicos correspondientes.”