Algoritmia para Problemas Difíciles

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

Está disponible la hoja de Problemas de algoritmos Probabilistas y Genéticos. La fecha de entrega es hasta el 20 de diciembre.

Aviso: por error aparecía en este texto una fecha diferente. La correcta es el 20 de diciembre tal y como refleja también la hoja de ejercicicios.

Hemos dejado en la página de material, unas transparencias para las clases restantes de la asignatura sobre el último punto del programa: análisis amortizado y estructuras de datos avanzadas.

OJO: nueva versión 29-11-2013, añadidas páginas 26 a 41.

Tal y como se ha venido anunciando la prueba escrita intermedia se celebrará el día 18 de noviembre en horario normal de clase. Según lo acordado:

• La prueba se basará en los temas 1 (Introducción. Los problemas NP-difíciles) y 2 (Algoritmos aproximados. Concepto. Diseño de algoritmos. Garantías y límites).
• Se pueden llevar los apuntes y documentos que se consideren necesarios.
• La duración de la prueba será la de la sesión completa que tenemos asignado en el horario de los lunes (aproximadamente entre las 12:10 y las 13:50).

Aquí podéis encontrar los ejercicios sobre algoritmos aproximados. La fecha de entrega es hasta el 2 de diciembre

Leed las transparencias finales sobre Algoritmos Aproximados (actualizadas en la sección de material de esta web), así como el texto sobre el problema TSP (caso general) extraído del libro [CLRS09], disponible también en la sección de material.

Las clases de la asignatura continuarán con normalidad el próximo 4 de noviembre, lunes. Los ejercicios pendientes se pueden entregar ese mismo día en clase.

Se suspende la clase de hoy lunes 28 de octubre.

Lamentamos las posibles inconveniencias.

Disculpad las molestias