HPC. Novedades investigacion.

agosto 20, 2017

Disclaimer. Escribimos la entrada desde el smartphone. Nos es complicado poner acentos. Pedimos disculpas al lector por ello.

Pocas entradas ultimamente eh ? Muchos motivos lo explican. Entre otros el smartphone, un autentico killer. Pero no solo esto.

Lamentablemente, pese a lo planificado tambien poca investigacion. Por los mismos motivos. Pero si he pensado mentalmente en algunos temas que queremos resumir muy brevemente en esta entrada y que desarrollaremos en otro momento. Lealos el lector como unas reflexiones no muy maduradas en voz alta que pueden ser incorrectas, sobre todo la parte que se refiere a los casos twisted.

–Primero, cuando un caso al aplicar el metodo de la escalera queda fuera del rango factible esta claro que no puede tener RHs. Pero que pasa cuando queda dentro ? Hemos dado por supuesto que entonces tiene RHs, y asi es, pero hay que demostrarlo.

–Segundo, una vez demostrado esto, es facil demostrar que cuando un caso es smooth, entonces necesariamente tiene RHs en todos los vertices finales posibles. Basta con demostrar que en estos casos aplicando el metodo de la escalera siempre caeremos en la region factible, y edto es facil ver que tiene que ser asi.

–Tercero, hay que demostrar que el caso medio (aquel que obtenemos al seleccionar al azar un par de permutaciones de Sn) es smooth. Ya hemos hablado en otras entradas sobre el valor de los parametros que tendra este caso medio: n^log n creo recordar (escribo de memoria basandome en un resultado de terceras partes). Este valor para todos los parametros: orden de los generadores, orden del ias, orden de la circunferencia.

Nota al margen.

Siempre volvemos a este tema. La ultima vez fue en marzo de 2016:https://ireneses.wordpress.com/2016/03/13/algoritmica-y-complejidad-computacional-algunos-resultados-sobre-permutaciones/. No fue la primera. El resultado es de Erdos-Turan. Luego ha sido revisitado. El concepto de orden medio de una permutacion existe tambien pero nos interesa menos.

Cuando decimos permutacion media queremos decir tipica y su orden tiende o esta acotado por n^raiz cuadrada de log n. Faltaba la raiz cuadrada en la formula que hemos dado de memoria.

Fin de nota..

–Cuarto, aunque hay avances sigo sin tener del todo claro algunos temas relacionados con los casos twisted. Al contrario, casi todo lo relacionado con los casos entangled esta claro.

Con respecto a los twisted, aunque no tengo claro si habra 3-twisted, 4-twisted etc…si parece claro que, si estos casos existiesen, los efectos de esta propiedad se tienen que diluir a medida que n crece. Cuando digo diluir quiero decir que se atenuan, o mas tecnicamente que el multiplicador disminuye. Lo veo claro, pero hay que demostrarlo. Primero que existen casos 3-twisted, 4-twisted etc…y segundo que los efectos se diluyen.

Tambien establecer un criterio claro que distinga estos casos n-twisted de los smooth. Ya hemos comentado sobre este tema en entradas anteriores.

En un caso smooth el entorno de la identidad, segun lo hemos definido, quedaria saturado. Esto nos lleva a una situacion paradojica: si esta saturado entonces es smooth; si no lo esta entonces sera 1-twisted o 2-twisted. Son posibles entonces, repetimos los casos 3-twisted, 4-twisted etc…Es lo que no conseguimos, desde hace tiempo, visualizar bien. Por ello quiero hacer comprobaciones adicionales al respecto y aterrizar este tema definitivamente.

Al hilo de todo lo comentado hasta ahora, es oportuno matizar un comentario anterior. No esta claro que el caso medio o mas bien tipicio sea, el que tiene los parametros indicados , sea smooth. Si es seguro que el caso medio tiene que ser o smooth o twisted (? 1-twisted, 2-twisted?) ?. Los casos entangled y cycle-entangled son muy restringidos. La pregunta clave es si este tipico o medio se satura asintoticamente o no se satura. Para contestarla hay que hacer calculos avanzados.

Una reflexion al respecto: si fijamos los parametros un caso smooth solo se puede dar de una manera, pero uno twisted se puede dar de varias. Tambien uno entangled. Simplificando mucho, si el valor de los parametros es X, en teoria puede haber 1 caso smooth, X casos entangled, y X^2 1 -twisted. Los casos cycle-entangled son necesariamente entangled y por lo tanto estos ultimos son cota superior. Todo esto es un calculo puramente teorico y estamos dando cotas superiores. Teniendo en cuenta que hablamos de objetos altamente estructurados, la realidad puede ser muy otra a lo permitido por la teoria que no tiene en cuenta esta estructura. Pero si la realidad no se aleja de la teoria,  de la cota superior, los casos twisted tienen que ser los mas abundantes y los smooth extremos.

Pero por otra parte el hecho de ser twisted (sobre todo si es 1-twisted o 2-twisted) limita el tamano  o el crecimiento del caso. Teniendo en cuenta el valor de los parametros del caso medio y que si lo relacionamos con n! el limite tiende a cero, no parece posible que el caso medio pueda ser twisted. En fin, ya se ve que este tema esta bastante confuso.

Quinto, la gran incognita sigue siendo como encajar los casos cycle-entangled en el metodo de la escalera.

Finalmente, tenemos pendiente encajar el tema del metodo de la escalera con el tema de la distribucion de la complejidad de casos por grados. Este ultimo es un tema sobre el que hicimos varias entradas hace anos.

P.s. Hemos seguido con interes los acontecimientos de este verano relacionados con el problema clasico de comlejidad computacional, que para algunos es el fundamental y para otros es uno mas…

 

 

Ip. La prueba documental.

agosto 6, 2017

Por el titulo nos referimos a las pruebas documentales de la concesion de la segunda patente.

La recepcion por correo.

Y en las siguientes imagenes la primera pagina de la segunda, las portadas de las dos y las primeras paginas de las dos.

 

 

 

IP. Las fechas de concesion de las patentes.

julio 14, 2017

He visto en Internet que la segunda patente ya tiene fecha de concesion: 4 de julio de 2017. Es una fecha muy significativa para la historia de EEUU. He vivido en persona el jubilo con el que se celebra.

Curiosamente la fecha de concesion de la primera patente tambien es importante en la historia de este pais. En este caso con connotaciones negativas.

Casualidades de la vida…

P.s. Quiero destacar que la primera concesion fue durante la presidencia de Obama.

Sin embargo en esta misma presidencia fue imposible obtener la segunda concesion. Tuvimos que sufrir rechazo tras rechazo, completamente injustificados todos ellos. La concesion solo ha sido posible, tuvo que esperar a la presidencia de Trump.

No estamos insinuando que ninguno de estos dos presidentes tuviese conocimiento de todo esto. Pedro asi ha sido.

Si es posible que hayan impulsado politicas mas o menos favorables hacia la propiedad privada y esto se acabe notando en todos los aspectos.

 

Metablogging. Cuantos contactos tiene el usuario medio de Linkedin ?

julio 10, 2017

Hacia tiempo que no hablabamos de estadisticas.

Lee el resto de esta entrada »

Arte. Versiones: Cumbia sobre el Mar.

julio 9, 2017

DISCLAIMER. En esta entrada aparecen multiples videos musicales. No me hago responsable sobre lo que pueda aparecer en las imagenes de estos videos. En esta entrada nos centramos en la musica. Fin de disclaimer.

Ya hemos hablado en varias ocasiones en el blog  de la cumbia como estilo musical, el estilo mas universal en Latam.

Y creo que tambien hemos hablado de la cumbia en concreto, sobre la que hoy hacemos la entrada.

En el primer video la version original. En el segundo una mas actual, mas cool, pero sin perder el estilo. Y en el tercero una version actual pero en un tempo mucho mas rapido. La tercera es de los mismos que la segunda pero en modo remix.

Musica refrescante, que vuelve el calor…y bastante pegadiza, sobre todo la tercera version.

Lee el resto de esta entrada »

Algoritmica y complejidad computacional. La complejidad de resolver el Cubo de Rubik de manera optima.

julio 9, 2017

Se ha publicado recientemente un articulo sobre el tema que indicamos en el titulo.

Nota. No se muy bien como cortar y pegar un enlace en el espacio habilitado para ello en wordpress, en el smartphone.

En general hay bastantes cosas que se pueden hacer en un portatil y no se como hacer en el smartphone, o no se como hacerlo de manera rapida.

Ya he aprendido. Pero el comentario general aplica…

Otro ejemplo es marcar un bloque completo de texto, para cortar y pegar o darle el formato adecuado. Siempre se marca solo una palabra.

Ya se como hacerlo en general pero no al editar un post en wordpress. Ya se como hacer esto tambien. No era evidente.

En fin, poco a poco…

. Fin de nota.

Solving the Rubik’s Cube Optimally is NP-complete.

Erik D. Demaine∗ Sarah Eisenstat∗ Mikhail Rudoy†

Abstract.

In this paper, we prove that optimally solving an n×n×n Rubik’s Cube is NP-complete by reducing from the Hamiltonian Cycle problem in square grid graphs. This improves the previous result that optimally solving an n×n×n Rubik’s Cube with missing stickers is NP-complete. We prove this result first for the simpler case of the Rubik’s Square—an n × n × 1 generalization oft he Rubik’s Cube—and then proceed with a similar but more complicated proof for the Rubik’s.

Nuestro interes en el articulo va mas alla de lo anecdotico (el hecho de que hable de un puzzle muy conocido), y lo estamos leyendo con atencion.

En particular nos interesan en el dos puntos:

–primero, en la cadena de reducciones aparecen los hipercubos, que como es bien conocido, son grafos de Cayley.

–segundo, la reduccion lo es del problema RH a un ? problema de camino mas corto ?. Signos de interrogacion pues esto ultimo no lo tengo claro.

Por otra parte me ha sorprendido conocer que la version cuadrada es mas “compleja” que la cubica. Pensaba que era lo contrario.

Comentar que el problema se queda en NP pues el diametro del tipo de grafos que representan el problema es polinomico.

P.s. En el blog hemos publicado mucho sobre la posible complejidad computacional del problema de nuestro interes. Ya tenemos intuitivamente claro el tema. Pero solo intuitivamente. Hablo de la version normal, no de la sucinta. De ahi nuestro interes en este articulo.

Actualizaciones.

Lee el resto de esta entrada »

Madrid. Julio 2017.

julio 9, 2017

Disclaimer. No se muy bien, o no me resulta comodo poner los acentos en el teclado del smartphone. Normalmente corrijo las entradas publicadas a traves de este medio posteriormente en el portatil. Pero desde que tengo el smartphone, ya casi no enciendo el portatil…Pido disculpas al lector por estas faltas de ortografia. Fin de disclaimer.

Seguimos publicando algunas de las fotografias que vamos realizando en las mas variadas circunstancias.

Este tipo de camaras (las de los smartphones) dejan mucho que desear, especialmente para las fotografias de distancia. Pero es lo que hay.

En este caso presentamos fotografias de una zona bien conocida por madrilenos y turistas. El extremo sur del parque del oeste, bastante fotogenico.

Las fotografias donde se ve el Palacio Real, la Almudena y al fondo San Francisco el Grande no parecen de Madrid. La parte inferior parece de alguna ciudad del norte de los Pirineos. La parte superior con las cupulas parece oriental. Por no hablar del Templo de Debod.

Bueno, sin mas preliminares las imagenes. Anadimos algunos comentarios en cada imagen.

De la siguiente me gusta el contraste entre la luz artificial de la farola y la atenuada luz natural de la puesta de sol.

La luz de la farola parece el sol en un dia seminublado o en un dia de eclipse, pero en una posicion inverosimil. Dudo que el sol ocupe esta posicion en ningun momento del ciclo anual. Tambien puede ser un sol de amanecer pero en una posicion de atardecer. Y si es eclipse, es un eclipse con un sol pleno !!

En fin, todo esto le da a la fotografia, realizada y publicada tal cual sin ningun tipo de proceso artificial una sensacion de absoluta irrealidad. Es una fotografia que con elementos completamente anodinos crea una sensacion de completa irrealidad.

Por todo ello creo que esta bastante conseguida.


Con respecto a la siguiente fotografia, el aspecto de ciudad nortena que ya hemos comentado es debido a los techos de pizarra, no muy frecuentes en Madrid, que tiende mas a la teja.

Siempre que paso por aqui, y es frecuente pues vivo cerca, pienso lo mismo: deberian de podar algun arbol que otro, para permitir una vista completa del conjunto monumental.

El dia de la fotografia la vista era especialmente espectacular pues el tono dorado de los edificios contrastaba con el tono muy oscuro del cielo. La fotografia, de una calidad muy deficiente, no refleja la realidad.

En la siguiente imagen lo que nos gusta es el contraste entre el azul oscuro del cielo y el negro del estanque.

Ecommerce. Marketplace vs. DTC: el caso Nike.

julio 1, 2017

Pese al poco tiempo de que disponemos, tampoco queremos dejar de reseñar una noticia que salió hace poco relacionada con el comercio electrónico. Se refiere al inicio de las ventas explícitas de Nike en Amazon.

Ya se vendía esta marca, Nike, en esta plataforma, Amazon (imagino que tanto en su linea de trader como en la de broker o marketplace), pero en contra de la estrategia comercial del fabricante, que quería reforzar el canal DTC. Amazon es la bestia negra delos fabricantes con estrategia de branding.

Pero el canal existe, tiene peso y es absurdo que un fabricante, aunque aplique una estrategia de branding, se niegue a utilizarlo, ceda este instrumento a terceras partes en vez de beneficiarse de él.

Lee el resto de esta entrada »

HPC&IP. Segunda patente concedida.

julio 1, 2017

Este blog nació para hablar sobre temas relacionados con nuestro proyecto de investigación que esperamos se convierta en empresarial.

Aunque ahora no tenemos tiempo para ni para el blog ni para el proyecto de investigación / empresarial, si quiero reseñar un hito importante del proyecto:  nos han concedido finalmente la segunda patente.

Nota. Estoy agradecido especialmente a AN, el tecnico de mis agentes en EEUU, con ellas que gracias a un gran trabajo de equipo esta segunda patente ha llegado a buen puerto. Y una vez mas señalo que ninguno de los rechazos tenia ningun sentido. Pero no mezclemos celebracion con polemica. Fin de nota.

Todavía no tengo el documento físico que suelen enviar, pero he aquí la prueba: una fotografía de la página correspondiente a la patente en USPTO PAIR.

Nadie que no lo haya vivido se puede imaginar lo que ha costado en todos los sentidos. Y ahora falta la parte mas complicada del proyecto, la parte empresarial, que ademas no podemos acometer por falta de tiempo. No es una queja pues el proyecto actual en el que estamos implicados es también muy interesante. Un gran reto…

Lo que aparece en la fotografía anterior son todo buenas noticias: notice of allowance y issue. Cuando hay issue, pagar las tasas correspondientes duele menos :-).

Las imágenes del expediente completo a continuación. Hemos marcado las rejections, finales o no.

Lee el resto de esta entrada »

Arte. Genero, excelencia e imitacion.

junio 19, 2017

Dicen que Cervantes inventó la novela. Entonces todos los escritores que se han expresado dentro de este genero posteriormente eran sus imitadores ?. Absurdo.

Lee el resto de esta entrada »