Estructuras de Datos y Algoritmos (EDA)

Los árboles AVL no son la única forma de conseguir árboles binarios de búsqueda cuya altura sea de orden logarítmico en el número de nodos. Una alternativa bastante conocida son los árboles rojinegros. Se incluyen a continuación unas transparencias explicativas tomadas de una asignatura optativa del plan en extinción y más abajo un enlace a un applet.

El applet que ya conocéis de árboles AVL permite también hacer pruebas con un árbol rojinegro (seleccionando “RB” en el menú de la derecha del applet).

Ya está disponible en la sección de prácticas el enunciado de la práctica 5 (ir a a la sección pinchando aquí). La fecha límite para presentar esta práctica, según las indicaciones dadas en el propio enunciado, será el 09/01/2012 (incluido).

En la zona de acceso restringido de esta web (acceso con usuario y clave comunicados en clase) están disponibles algunas páginas de documentación sobre árboles AVL:

• del libro de X. Franch citado en la bibliografía,
• del libro de Z.J. Hernández et al citado en la bibliografía,
• del libro Algorithms and Data Structures (2004) de N. Wirth (libro completo publicado en este enlace).

Mañana martes y también el viernes serán clases de problemas. Los enunciados están disponibles aquí.

Se ha fijado la fecha para la realización del examen práctico de programación en laboratorio e individual, correspondiente a la primera convocatoria.

El examen práctico se realizará el martes 31 de enero de 2012,  por la mañana.

El examen escrito se realizará el sábado 28 de enero de 2012,  por la mañana.

La hora y lugar de realización de ambos exámenes se anunciará en la página sobre evaluación, con antelación suficiente.

• Clase del 28 de noviembre.
• Clase del 29 de noviembre.

La Algoritmia persigue continuamente soluciones mejores para problemas conocidos. Uno de ellos es la multiplicación de matrices.

• El algoritmo estándar (basado en la aplicación directa de la definición del producto de matrices) requiere O(N³) operaciones aritméticas (sumas y multiplicaciones), para multiplicar matrices N x N.
• Es muy sencillo reducir ese coste a O(N^2,807), con un algoritmo de “divide y vencerás”, el algoritmo de Strassen (véase wikipedia o transparencias de “divide y vencerás” de la asignatura de Esquemas Algorítmicos).
• Durante veinte años, el algoritmo conocido con menor coste asintótico ha sido el de Coppersmith y Winograd, que requiere O(N^2,376).
• El año pasado, en su tesis doctoral, Andy Stothers propuso un algoritmo con coste asintótico O(N^2,374).
• Justamente ayer Virginia Vassilevska Williams dio a conocer la solución más rápida conocida hasta el momento, con un coste O(N^2,373).

Ya está disponible en la sección de prácticas el enunciado de la práctica 4 (ir a a la sección pinchando aquí). La fecha límite para presentar esta práctica, según las indicaciones dadas en el propio enunciado, será el 12/12/2011 (incluido).

Las hojas de ejercicios se pondrán en las páginas de material de los grupos de mañana y tarde.

• Soluciones de los ejercicios 1 y 3 de la clase del 8 de noviembre.
• Soluciones de los ejercicios 1 y 5 de la clase del 11 de noviembre.