Estructuras de Datos y Algoritmos (EDA)

Un curso sobre Tipos Abstractos de Datos

Resultado de la primera convocatoria del curso 2016-17

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 primera convocatoria del curso 2016-2017.

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 martes 21 de 11:30 a 13:30, y el jueves 23 de 16:00 a 18:00.
  • Ejercicio 2 con Javier Campos (Despacho 1.12), el viernes 24 de 11:00 a 13:00.

Written by Javier Campos

February 20th, 2017 at 12:59 pm

Posted in Anuncios, examen

Convocatoria de febrero de 2017

sin comentarios

Primera convocatoria de evaluación del curso 2016-17:

  • Examen escrito (teoría y problemas): 06-02-2017, 10:00 h., aulas A06 y A07 del edificio Ada Byron.
  • Examen de laboratorio: 06-02-2017, 16:00 h., laboratorio L0.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

December 16th, 2016 at 12:42 pm

Posted in Anuncios, examen

Encuestas sobre la docencia

sin comentarios

Desde el 13 de diciembre hasta el 13 de enero se pueden responder las encuestas sobre la docencia.

Son muy importantes para facilitar la mejora, año a año, de la asignatura.

Te pedimos unos minutos para responderlas: http://encuestas.unizar.es/

Written by Javier Campos

December 12th, 2016 at 11:24 am

Posted in Anuncios

Lenguajes de programación (cronograma, listado y cervezas)

sin comentarios

Written by Javier Campos

December 2nd, 2016 at 12:53 pm

Posted in curiosidades

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