Algoritmia para Problemas Difíciles

Jelani Nelson explica lo que le gusta de la algoritmia y da buenos consejos para empezar en ello

He is behind the Lempel-Ziv compression algorithms

(puede que el link no funcione para no miembros de IEEE)

Podéis ver aquí el vídeo de la charla sobre intratabilidad que dí el martes (charla introductoria sobre lo que estamos viendo más en profundidad en clase)

Pavel Pevzner is the recipient of the ACM Paris Kanellakis Theory and Practice Award for pioneering contributions to the theory, design and implementation of algorithms for string reconstruction and to their applications in the assembly of genomes.

Hay una diferencia entre el problema de las N-reinas (poner N reinas en un tablero NxN sin que se maten) y el problema de Completar N-reinas (algunas reinas están colocadas y hay que poner el resto, si es posible).

Recientemente se ha demostrado que Completar N-reinas es NP-completo (ver artículo), eso quiere decir que resolverlo en tiempo polinómico supondría el premio del millón de dólares del instituto Clay

No hay que confundir los dos problemas, por lo visto es lo que ha ocurrido … (ver nota)

Se han presentado 4 algoritmos al concurso. Cuento con la asistencia de todos y con vuestra valoración.

Os recuerdo las reglas:

• Hay que presentar durante la clase del 13 de enero (de 10 a 12h) y durante un máximo de 10 minutos (más 5 minutos para preguntas) el algoritmo junto con una clara explicación de su funcionamiento, características y propiedades.

• Se valorará:

• que el algoritmo no haya sido tratado en esta u otras asignaturas de la carrera
• la novedad, dificultad, belleza e interés del algoritmo
• la claridad de la explicación y el dominio de la asignatura demostrado en la presentación

Interesante charla sobre Rabin (enviada por Javier Campos)

Javier Campos nos manda un interesante artículo sobre algoritmos probabilistas de Communications de la ACM …

The Simple, Elegant Algorithm That Makes Google Maps Possible …

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