Estructuras de Datos y Algoritmos (EDA)

Un curso sobre Tipos Abstractos de Datos

Archive for the ‘Material’ Category

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

without comments

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

without comments

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

Para pasar un rato durante las fiestas del Pilar…

without comments

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

Corrección de un detalle de C++ en alguna transparencia

without comments

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.

Written by Javier Campos

October 8th, 2015 at 12:08 pm

Ejemplos de uso del TAD pila

without comments

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

Written by Javier Campos

October 5th, 2015 at 10:03 am

Árboles rojinegros: una alternativa a los AVL

without comments

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

Rojinegros

Un applet para probarlos: aquí (seleccionar “Red-black tree” en el menú de arriba).

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

Written by admin

November 18th, 2014 at 9:35 am

Posted in Material

Lectura avanzada: transformación de algoritmos recursivos en iterativos

without comments

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.

Pdf descargable aquí (autor: Javier Campos).

Written by admin

November 7th, 2014 at 12:40 pm

Posted in Material, curiosidades

Diviértete con Binky en estas fiestas del Pilar

without comments

binky

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.

Written by Javier Campos

October 6th, 2014 at 11:03 am

Posted in Material, curiosidades

Árboles de juego

without comments

Written by Javier Campos

December 12th, 2013 at 11:28 am

Posted in Material, curiosidades

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

without comments

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 Javier Campos

November 19th, 2013 at 11:11 am

Posted in Material, curiosidades