Algoritmia para Problemas Difíciles

cuando los problemas se resisten …

Archivo de la categoría ‘curiosidad’

Sobre el problema de las N-reinas

Sin comentarios

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)

 

Publicado por Elvira

September 12th, 2017 at 10:23 am

Publicado en Anuncios,curiosidad

Tagged with

Mañana viernes concurso de algoritmos

Sin comentarios

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

Publicado por Elvira

January 12th, 2017 at 11:06 am

Sobre Rabin (test de primalidad)

Sin comentarios

Interesante charla sobre Rabin (enviada por Javier Campos)

Publicado por Elvira

November 11th, 2015 at 9:19 am

Publicado en curiosidad

It probably works …

Sin comentarios

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

Publicado por Elvira

October 26th, 2015 at 9:55 am

Publicado en curiosidad

El algoritmo de google maps

Sin comentarios

Publicado por Elvira

September 21st, 2015 at 8:48 am

Publicado en curiosidad

Grafos skip

Sin comentarios

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:

 

Publicado por Javier Campos

December 17th, 2013 at 1:02 pm

Publicado en curiosidad