Estructuras de Datos y Algoritmos (EDA)

Un curso sobre Tipos Abstractos de Datos

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

Resultado de la segunda convocatoria del curso 2015-16

sin comentarios

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.

Written by Javier Campos

September 12th, 2016 at 6:11 pm

Posted in Anuncios, examen

Segunda convocatoria

sin comentarios

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

Written by Javier Campos

May 20th, 2016 at 12:24 pm

Posted in Anuncios, examen

Resultado de la primera convocatoria del curso 2015-16

sin comentarios

Se han publicado en Moodle, en la sección de información general, las notas y la solución del examen escrito de la primera convocatoria del curso 2015-2016.

Las revisiones del examen se atenderán los siguientes días (se debe consultar la solución con antelación):

• Ejercicio 1 con Javier Campos (Despacho 1.12) el lunes 15 y el martes 16, de 10:00 a 12:00.
• Ejercicios 2 y 3 con Yolanda Villate (Despacho 0.06) el lunes 15, de 11:30 a 13:30 y de 16:00 a 18:00.

Written by Javier Campos

February 12th, 2016 at 1:36 pm

Posted in Anuncios, examen