Estructuras de Datos y Algoritmos (EDA)

Un curso sobre Tipos Abstractos de Datos

Cambio de horario

sin comentarios

El miércoles 7 de diciembre tendrá horario de lunes, por tanto habrá clase de EDA.

Written by Javier Campos

December 2nd, 2016 at 11:08 am

Posted in Anuncios

Vídeos sobre algoritmos de ordenación

sin comentarios

Written by Javier Campos

November 29th, 2016 at 2:29 am

Modificación del quicksort para conseguir coste O(n log n) en el caso peor

sin comentarios

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.

selection_is_linear

Written by admin

November 29th, 2016 at 1:14 am

Posted in Material, curiosidades

Uso de colas con prioridad para acelerar alguna fase de otros algoritmos

sin comentarios

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:

monticulos_y_dijkstra

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:

Dijkstra usando cola con prioridades

(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

Written by admin

November 29th, 2016 at 12:08 am

Posted in Material

Sobre la implementación de montículos

sin comentarios

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.

dynamic_heap

Written by Javier Campos

November 28th, 2016 at 11:39 am

Posted in cosas de clase

Enrutamiento de direcciones IP

sin comentarios

patriciaUna de las formas de almacenar la información sobre las direcciones IP en los nodos que hacen función de enrutamiento en internet es la estructura de datos Patricia.

Consultando el Patricia en un nodo de enrutamiento, es posible rechazar un dominio como no válido (si no está almacenado en el Patricia) o como válido, y en este caso, bien aceptarlo (si ya se ha alcanzado el dominio buscado) o redirigir la petición HTTP al siguiente nodo.

Éste es el artículo en el que se propuso por vez primera (en 1991) el Patricia para este uso.

En esta página podéis encontrar un simulador y algunas explicaciones.

En este artículo, una comparativa del uso de Patricia frente al uso de tablas hash (las veremos más adelante).

Y en estas transparencias (desde la nº 142 a la nº 150), algunas ideas sobre la implementación de un Patricia.

Written by Javier Campos

November 22nd, 2016 at 12:17 am

Cambio de horario

sin comentarios

El jueves 3 de noviembre tendrá horario de martes, por tanto habrá clase de EDA.

Written by Javier Campos

October 28th, 2016 at 10:04 am

Posted in Anuncios

Para pasar un rato durante las fiestas del Pilar…

sin comentarios

binky

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.

Written by Javier Campos

October 4th, 2016 at 10:00 am

Sobre las prácticas de esta asignatura

sin comentarios

Como regla general, la nota de prácticas en esta asignatura no se guarda de un curso para el siguiente.

Written by Javier Campos

September 26th, 2016 at 3:09 pm

Posted in Anuncios, Prácticas

Presentación de la asignatura (curso 2016-17)

sin comentarios

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)

Written by Javier Campos

September 12th, 2016 at 6:13 pm

Posted in Anuncios