Algoritmia para Problemas Difíciles

Para cada una de las estructuras de datos que estamos viendo en clase, existen variantes y generalizaciones con diversas utilidades.

Por ejemplo, una idea basada en las listas skip es la de los grafos skip:

• explicación en Wikipedia
• artículo original
• otro artículo sobre sus ventajas

Está disponible en la página de material la hoja 6 de ejercicios sobre estructuras de datos aleatorizadas.

Se ha dejado en la página de material, más información sobre árboles splay, listas skip y árboles treap.

Está disponible en la página de material la hoja 5 de ejercicios sobre análisis amortizado. Son ejercicios sobre los árboles splay que veremos hoy en clase.

Hoy se abre el plazo para realizar las encuestas de evaluación de la enseñanza y de la labor docente del profesorado. En este curso se ha eliminado el uso de papel como soporte. Toda la información sobre el tema está en la página:

http://encuestas.unizar.es/

Las encuestas pueden realizarse bien desde un computador, en la página:

https://janovas.unizar.es/atenea/ate100bienvenida.xhtml

o bien desde un teléfono móvil, accediendo a la página de Unizar y siguiendo la banderola correspondiente.

Vuestra participación es muy importante para ayudarnos a mejorar.

El jueves 12 de diciembre tiene horario de lunes.

El tema de implementación de conjuntos disjuntos, y su análisis amortizado, está tratado en el capítulo 21 del libro de Cormen et al. de la bibliografía.

Además, podéis consultar:

• Notas de clase de una asignatura del M.I.T.
• Vídeo de una clase de la Universidad de California en Berkeley.

Está disponible el enunciado de la práctica 2. La fecha de entrega es hasta una semana antes de la fecha del examen.

Está disponible en la página de material la hoja 4 de ejercicios sobre análisis amortizado. Los primeros cinco ejercicios de la hoja son ya realizables con la información dada hoy en clase. El resto lo serán con la información dada en las próximas dos horas de clase.

La fecha de entrega es hasta el 20 de diciembre.

En las próximas horas hablaremos en clase sobre análisis amortizado.

Podéis encontrar algunas clases interesantes sobre este tema en internet. Por ejemplo:

• Prof. Charles Leiserson, M.I.T. (coautor del libro de Cormen et al. de la bibliografía): “Amortized Algorithms, Table Doubling, Potential Method“.
• Prof. Jonathan Shewchuk, University of California at Berkeley: “Amortized Analysis“.