Archive for the ‘TECNOLOGÍA Y APLICACIONES’ Category

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.

 

 

 

IBM Q. ¿ Cuánta sombra hace ?

marzo 6, 2017

Hace años publicamos  una entrada sobre las promesas de  la computación cuántica. Leyendo la prensa parecería que estas promesas se están cumpliendo ya.

Pero leyendo artículos sólo un poco más técnicos, de prensa técnica, parece que no es así. No veo nada realmente nuevo sino futuribles, como siempre que se habla de esta tecnología. No es la única: la energía de fusión nuclear le gana en esto.

Realmente no hay mucha información al respecto pero parece más bien una operación de marketing más, orquestada ahora por motivos que desconozco. Posiblemente lo que realmente IBM quiera publicitar es el simulador de 5 qubits accesible en modo cloud y útil para aprender a programar algoritmos cuánticos. Lo han incrementado a 20 qubits, lo cual es interesante. Pero esto no es más que  una hipótesis.

Quedamos a la espera de que el influencer más famoso que opina sobre estos temas se manifieste, si es que lo hace. Esperamos que no nos deje mal…:-).

Aquellos interesados en profundizar (no es mi caso ahora mismo) pueden buscar publicaciones de los responsables de las criaturas cuánticas.

IBM’s work is based on research done at Yale through professor Robert Schoelkopf (the IBM team is mostly his Ph.D. and post-grad students).

The other prominent US school working on this is the University of California at Santa Barbara under professor John Martinis in an effort that was backed and absorbed by Google in 2014.

P.s.1. Explicamos el título. No tiene nada que ver con la sombra que pueda proyectar una eventual nube (cloud). Simplemente hace años también publicamos una entrada sobre estos temas cuyo título contenía la frase Cuánto sol hace (de  cuyo contenido no me acuerdo), título que recogía el chascarrillo que circuló en España sobre el título de la (floja) película Quantum Solace.

P.s 2. No se por qué no aparece en el cuadro de herramientas de tratamiento de texto de WordPress la herramienta para cuadrar el texto de la entrada.

Actualización 20 de marzo de 2017. Ya se han manifestado dos blogueros a los que se les puede conceder la máxima confianza cuando opinan sobre estos temas.  El lector los puede leer aquí y aquí.   Se centran más en un nuevo resultado de D-Wave que en el proyecto de IBM (o el similar Google).  Pero creo que mi calificación de futurible se sostiene. En el primer enlace se recomienda leer también los comentarios: suelen ser informativos. Cuando terminemos con la entrada sobre la historia alto medieval de Borgoña/Provenza, tema mucho más complejo  que este de computación cuántica, seguramente haremos una entrada sobre los grafos implicados en la máquina de D-Wave.

Actualización 3 de marzo 2017.

Una entrada de otro bloguero, que como los dos anteriores ofrece la máxima confianza. En este caso conviene aclarar que se trata de investigador escéptico sobre las posibilidad de construir un computador cuántico.

Ya adelanto que es una entrada con una elevada densidad de enlaces. Este bloguero además de como investigador en matemáticas, campo en el que ya no tiene nada que demostrar (entiéndase esto sólo en uno de los dos sentidos de la frase; esperamos que su trabajo siga dando grandes frutos) tendría un buen futuro como periodista de investigación :-).

Extracto.

List of companies involved in quantum computers. A few webpages:  1Qbit ; D-wave ;Quantum circuits (Yale group) ; Rigetti ; Monroe’s blog; Station Q (Microsoft); GoogleIBM-Q;

Sobre Microsoft  y la computación cuántica.

Un extracto de otro blog de un investigador y empresario en computación cuántica:

 Alibaba, Google, IBM, Intel, and Microsoft (alphabetical order) , not to mention the govs. of Australia, Canada, China, EU, Holland, UK and USA are each spending tens of millions of dollars per year to achieve the same goal as Rigetti, to build an elusive gate model quantum computer.

Decenas de millones no parece demasiado teniendo en cuenta los nombres que aparecen.

Una muy breve historia de la organización industrial del sector de computación cuántica. Nos centramos en proyectos empresariales y dejamos de lado a la academia o instituciones públicas. La fuente es el mismo blog de la última cita, Quantum Bayesian Networks. y la revista MIT Technology Review.

1999. Se funda D-Wave. Since it was founded in 1999, D-Wave has obtained more than $100 million in funding from sources such as: the venture capital firm Harris & Harris, the Canadian government, and Goldmann Sachs.

Mayo 2011. La única empresa dedicada públicamente a estas actividades sigue siendo D-Wave. Este año firma un contrato con Lockheed Martin. En 2017 D-Wave sigue desarrollando actividades.

¿ 200? Microsoft e IBMGoogle will be competing not only with whatever improvements D-Wave can make, but also with Microsoft and IBM, which have substantial quantum computing projects of their own (see“Microsoft’s Quantum Mechanics” andIBM Shows Off a Quantum Computing Chip).

Junio 2014. Google contrata a Martinis. He was hired by Google in June 2014 after persuading the company that his team’s technology could mature rapidly with the right support. With his new Google lab up and running, Martinis guesses that he can demonstrate a small but useful quantum computer in two or three years. “We often say to each other that we’re in the process of giving birth to the quantum computer industry,” he says.

Terminamos la breve historia aquí. Hasta 2011 las incumbents seguían viendo la corrida desde la barrera y en 2014 Google ¿ da el primer paso o hubo otro anterior de alguna otra multinacional ?. No Microsoft e IBM ya se habían implicado antes. Más adelante en esta  entrada nos planteamos una serie de preguntas más detalladas sobre todo esto.

Se me ha ocurrido un par de reflexiones adicionales sobre la teología cuántica (1) computación cuántica:

Primera reflexión, que se me ha ocurrido pq desde hace poco tiempo dispongo de una información de la que no disponía: ¿ pq de repente empresas (no hablo de ahora sino de hace pocos años) con una trayectoria seria y dilatada en sus estrategias de I+D e incluso de Marketing (que yo conozca hay al menos dos en la lista anterior que cumplan con estos rasgos; y se puede excluir al menos a otra, Google, que ni es seria ni tiene trayectoria acreditada: tuvo suerte en una ocasión pero no la han vuelto a repetir) están apostando fuerte por ésta, aparentemente incierta, tendencia ?. ¿ Hay alguna novedad científica o tecnológica que no conocemos el resto de los mortales, que lo explique ?. Tengo una posible explicación, pero me la reservo. Creo que es un tema digno de investigar.

Lo primero que habría que ver es si el fenómeno es real: de verdad están apostando fuerte. ¿ Constituyen estos esfuerzos una proporción importante de sus inversiones en I+D ?. Y lo segundo, si se confirmase que la apuesta es fuerte, ¿ desde cuando exactamente ha aparecido ?, ¿ a partir de que momento ha tenido lugar este cambio de actitud, de mirar la corrida académica y científica desde la barrera, como hacían desde hace décadas o al menos quinquenios, a bajar a la plaza y coger el toro por los cuernos ?. Y tercero el pq. ¿ Que gran descubrimiento ha habido en este campo, campo que como decimos ya lleva unas décadas sobre la mesa,  como para que estas empresas apuesten fuerte ahora ? ¿ O ha sido una acumulación gradual de pequeñas causas ?. Ahora invertir tiempo en esto es imposible para nosotros. Esperamos que lo hagan otros. Sí señalamos que aunque un computador cuántico es una máquina, las tres multinacionales implicadas son de software. Uno esperaría ver implicados a otros actores en este drama.

Nota. Se puede poner como momento de comienzo de este sector principios de los 80 con Benioff, Manin, Feynman o Deutsch y otros o principios de los 90, con Deutsch–Jozsa, Simon, Shor, Grover y otros. 

The field of quantum computing was initiated by the work of Paul Benioff[2] and Yuri Manin in 1980,[3] Richard Feynman in 1982,[4] and David Deutsch in 1985.[5] A quantum computer with spins as quantum bits was also formulated for use as a quantum space–time in 1968. Fin de nota.

Segunda reflexión: todos  los expertos saben que la mecánica cuántica es correcta. Pero también que es incompleta como teoría física.

El pilar de todos estos esfuerzos de I+D es un teoría incompleta. Supongamos que tras una inmensa inversión se consigue la computación cuántica práctica, pero lo que se obtiene es una especie rueda de cuadrada, en relación a lo que podría conseguirse si la tecnología estuviese basada en una teoría completa, un rueda redonda, que son las que ruedan bien de verdad. ¿ No sería mejor invertir todo este dinero en desarrollar la teoría completa antes ?. Lo que queremos decir es que quizás con la teoría completa se podría conseguir lo mismo pero con mucho menos esfuerzo.

Ok, anticipo el contra-argumento correcto pero quizás incompleto y sin duda fácil: la mecánica de Newton también es incompleta, pero se sigue utilizando por igual en muchas aplicaciones, pese a disponer de otras más completas. Por lo tanto quizás para el campo de aplicaciones de la computación cuántica, la mecánica cuántica sea suficiente. Quizás.

En cuanto a lo de invertir para obtener la teoría correcta y completa, quizás algún lector pensará ¿ todavía más ?.  Y algún otro, en que,  ¿ en teoría de cuerdas ?.

(1) Que no se lea esto como como una ironía que intenta minimizar o ridiculizar estos proyectos. Sólo me hizo gracia descubrir el otro día que la disciplina de la teología cuántica…¡¡ existe !!.

 

Algorítmica y complejidad computacional. El problema P vs. NP, un survey.

enero 8, 2017

El autor del survey es el merecidamente popular bloguero (y por supuesto académico experto en computación cuántica) Aaronson.

Lo he leído muy muy en diagonal este finde aprovechando que tenía un potente resfriado, lo cual en general y paradójicamente me inspira. Me ha gustado sobre todo (y mucho) el punto 6, en el que he concentrado mi tiempo. Los otros puntos, que finalmente me he saltado, diría que no aportan demasiado a cualquiera que ya conozca el tema (aunque yo lo tengo completamente oxidado y me vendría bien un recordatorio, así que lo leeremos más detalladamente en otra ocasión).

El punto 6 repasa las barreras o limitaciones teóricas que se han encontrado (y se pueden encontrar) en los intentos de demostraciones de esta conjetura (tema muy bien explicado que finalmente creo que he comprendido, pero que nadie me pida que se lo explique ahora :-); nos demuestran que hay niveles de abstracción inadecuados o más bien insuficientes para atacar este problema, sea por exceso o sea por defecto, lo cual da que pensar; realmente los nombres elegidos para las denominarlas no dicen mucho de lo que luego son) así como algunos enfoques prometedores, que permiten saltarse estas barreras (aunque a lo mejor se encontrarán con otras) como el utilizar cotas superiores algorítmicas para demostrar cotas  inferiores teóricas y así separar clases de complejidad (método que ya ha dado sus frutos hace unos años, separando dos clases de complejidad, eso sí muy extremas; también tiene un nombre raro) o el enfoque llamado Geometric Complexity Theory que aplica técnicas de geometría algebraica (el estudio de los conjuntos de soluciones de los sistemas de ecuaciones algebraicases decir a ecuaciones polinómicas multivariables, cuando las variables recorren determinados tipos de estructuras algebraicas) a estos temas. Gracias a este survey también he comprendido este último enfoque, obviamente en líneas muy muy generales (idem, que  nadie me pida que se lo explique…).  El autor no entra en demasiados detalles técnicos al respecto, lo cual algunos agradecerán, pero nos da una visión de (un) pájaro con muy buena vista. Por lo visto a algunos expertos este enfoque les parece una complicación innecesaria; a otros un camino viable.

Espero lector, que disfrutes del  survey.

Por cierto, al leerlo me he acordado de un tema que tenemos pendiente de comprobar con respecto a nuestro método de demostración de no hamiltonicidad en casos, que bien por ser entangled o twisted, no tienen recorridos hamiltonianos, método que hemos detallado largamente en varias entradas el pasado verano: ¿ como escala este método con el tamaño del input ?.

Ya en el peor caso, sólo determinar o decidir si un caso es entangled puede ser subexponencial (cota de Landau). Si es entangled el caso es potencialmente complicado y ya podemos decidir abandonarlo sin más e identificar otro que sea potencialmente sencillo.

Pero si por los motivos que sean nos gustan sus propiedades conocidas y además queremos que tenga recorridos hamiltonianos luego hay una serie de pasos más que nos permiten demostrar que no los tiene y aplicar el  razonamiento contrapositivo, según hemos detallado en las entradas del año pasado. Así de memoria pensamos no incrementarán la cota teórica señalada en el peor caso (según pienso hablaríamos de una suma de operaciones de complejidad subexponencial, lo cual sólo añadiría constantes). Pero queremos comprobarlo.

De  cualquier manera ya la cota subexponencial peor caso sólo para decidir si el caso es entangled nos deja completamente insatisfechos…Por otra parte también hemos comentado en varias entradas anteriores que hay buenos argumentos para pensar que el caso medio no será subexponencial, sino más bien cuasipolinómico (ver también aquí), lo cual nos consuela. Por otra parte de momento no hemos investigado si hay un test más eficiente para identificar si un caso tiene las propiedades de entrelazado (entanglement) o de retorcimiento (twistedness). No me parece fácil mejorar el  estado del arte en esto, pero tampoco imposible.

Algunos extractos (barriendo para casa :-)):

 –2.2.1 Search, Decision, and Optimization . . . . . . . . . . . . . . . . . . . . . . . . 16

Es un extracto del índice. En el punto indicado nos explica la diferencia entre estos problemas (también la no diferencia desde el punto de vista de complejidad computacional). ¿ Por qué es tan complicado entender esta diferencia ?

–Just as Hilbert’s question turned out to have a negative answer, so too in this case, most computer scientists conjecture that P!= NP: that there exist rapidly checkable problems that aren’t rapidly solvable, and for which brute-force search is close to the best we can do. This is not a unanimous opinion. At least one famous computer scientist, Donald Knuth [151], has professed a belief that P = NP, while another, Richard Lipton [171], professes agnosticism.   

Desconocía esta posición de Knuth tan extrema (bastante reciente; la referencia es: D. E. Knuth and E. G. Daylight. Algorithmic Barriers Falling: P=NP? Lonely Scholar, 2014; se trata de una entrevista). Si conocía la del otro investigador pues leemos su blog. Son, dicho sea con todos los respetos, dos veteranos que ya no tienen nada que demostrar a nadie ni nada que temer y, a calzón quitao, muestran un escepticismo a contracorriente muy sano y recomendable, que equilibra la balanza. Hace poco hicimos una entrada sobre otro investigador, más joven, que también expresaba sus dudas abiertamente.

–More broadly, there are many cases in mathematics where we can prove that some object O of interest to us has a property P, even though we have no hope of finding a general polynomial time algorithm to decide whether any given object has property P, or even to certify a large fraction of objects as having property P. In such cases, often we prove that O has property P by exploiting special symmetries in O—symmetries that have little to do with why O has property P, but everything to do with why we can prove it has the property. As an example, a random graph is an expander graph (that is, a graph on which a random walk mixes rapidly) with overwhelming probability. But since the general problem of deciding whether a graph is an expander is NP-hard, if we want a specific graph G that’s provably an expander, typically we need to construct G with a large amount of symmetry: for example, by taking it to be the Cayley graph of a finite group. Similarly, even though we expect that there’s no general efficient algorithm to decide if a Boolean function f is hard,51 given as input f’s truth table, we might be able to prove that certain specific f’s (for example, NP- or #P-complete ones) are hard by exploiting their symmetries. Geometric Complexity Theory (see Section 6.6) is the best-known development of that particular hope for escaping the natural proofs barrier.

Esta es la única mención honorífica a los Grafos de Cayley en todo el survey, en un contexto perfectamente conocido desde hace años. Pero lo hemos extractado sobre todo porque es una prueba más del hecho de que demostrar que un grafo tiene determinadas propiedades, y sólo esto, añade valor. Cosa que de nuevo parece que a algunos les cuesta comprender.

–ETH is an ambitious strengthening of P!= NP. Even assuming P!= NP, there’s by no means a consensus in the field that ETH is true—let alone still further strengthenings, like the Strong Exponential Time Hypothesis or SETH, which asserts that any algorithm for kSat requires Ω ((2 − ε) n ) time, for some ε that goes to zero as k → ∞. SETH, of course, goes even further out on a limb than ETH does, and some algorithms researchers have been actively working to disprove SETH (see [275] for example).

En el blog nos hemos interesado bastante por la conjetura ETH hace años.

–But now we come to the main insight of GCT, which is that the permanent and determinant are both special, highly symmetric functions, and it’s plausible that we can leverage that fact to learn more about their orbit closures than we could if they were arbitrary functions. For starters, Per (X) is symmetric under permuting X’s rows or columns, transposing X, and multiplying the rows or columns by scalars that multiply to 1. That is, we have

Per (X) = Per ( XT ) = Per (P XQ) = Per (AXB) (2)

for all permutation matrices P and Q, and all diagonal matrices A and B such that Per (A) Per (B) = 1.

The determinant has an even larger symmetry group: we have

Det (X) = Det ( XT ) = Det (AXB) 

Nos gusta la simetría. Muy interesante. En esto se basa todo el enfoque GCT, al parecer.

Imperialismo Computacional. Recopilación de enlaces enero 2017.

enero 2, 2017

Estrenamos el año con una recopilación de la serie Imperialismo Computacional. Son enlaces recopilados a partir de ¿ septiembre ? de 2016 hasta diciembre de 2016. Estos temas, sobre los que comenzamos a publicar siendo pioneros allá por 2011, aparecen ya como noticias diarias en las portadas de todos los periódicos y otros medios. Por ello seguramente ésta será la última recopilación que publiquemos sobre este tema. Seguiremos publicando sobre ello, pero lo incluiremos en la recopilaciones Trade Lane Megacities.

Las dos primeras entradas que publicamos sobre esta tendencia, cuando el blog transicionó de publicar sólo sobre temas relacionados con nuestras patentes a temas más generales son las dos siguientes:

a) Emperador Jobs (13 de octubre de 2011). La entrada era un homenaje a este innovador y emprendedor en el  momento de su fallecimiento. Aunque entre el personal  más técnico Jobs no tiene buena prensa (¿ que avance tecnológico ha inventado en realidad ?), lo cierto es que le dio la vuelta a varios sectores precisamente aplicando la estrategia del imperialismo computacional, no sabemos si de manera consciente o no. Luego otros sí que la han aplicado de manera totalmente consciente. De cualquier manera el apellido de este personaje es completamente irónico con respecto a esta tendencia. :-).

b) Imperialismo computacional y mercado de trabajo. En esta entrada también de octubre de 2011 comentábamos sobre el fuerte impacto sociológico que  iban a tener las nuevas tecnologías.

Extracto, fotografía incluida (perdón por la autocita).

Cada vez más gente no puede correr al ritmo que impone la  cinta de la realidad. Siendo esto lamentable a corto plazo, reacciones luditas no tienen sentido hoy, cómo no lo tuvieron en el pasado: esta realidad no es hostil si la miramos con una nueva mentalidad. Quizás la sociedad del ocio no esté tan lejos. Gracias al imperialismo computacional, quizás algún día nuestros descendientes, comenten con curiosidad: “nuestros antepasados trabajaban…”.

Y también publicamos  una entrada, bastante extensa, sobre la historia del concepto:

c) Imperialismo computacional, una historia del concepto. Creemos que es una entrada muy recomendable.

Extracto de la introducción de la entrada (perdón por la autocita).

Por supuesto la historia del impacto de la tecnología en la sociedad es larga. Pero nos  interesa sólo como han ido cambiando las concepciones sobre el impacto de las tecnologías computacionales  en la sociedad.

Diría que la concepción de una sociedad  en la que la máquina haya sustituido completamente al hombre en las actividades laborales, no como una posibilidad remota, casi de ciencia ficción, sino como una posibilidad muy real y muy próxima, tan próxima que es presente, que la estamos experimentando (algunos dirían que sufriendo) ya desde hace años y que podremos ver el fin del proceso en esta generación o en la próxima es bastante reciente. Seguramente posterior a 2007, posterior a la crisis.

Esta concepción, sus ideas y giros asociados (la computadora y el robot como amenazas, primero económicas y más recientemente en relación a la  seguridad) son las que queremos rastrear. Nos interesa también la diferente visión que sobre esta cuestión han tenido los científicos sociales (sobre todo los economistas, que tienen una visión completamente abstracta de la tecnología) y los ingenieros computacionales (autores de otras disciplinas, como la filosofía,  también tienen algo que aportar). Otro tema relacionado, sobre el que posiblemente no hablemos, es la  valoración que de esta eventual situación se hace: en general negativa, cuando en realidad puede ser una fuente de emancipación. Así lo vemos nosotros,  que hemos vinculado este fenómenos con el advenimiento de la Sociedad del Ocio.

1. Tecnoescépticos.

Albert Cortina, profesor de la Universidad Autónoma de Barcelona (UAB), abogado y urbanista y autor de la trilogía de libros ¿Humanos o posthumanos?, Humanidad infinita y Singulares pone en cuestión el transhumanismo, una ideología emergente del siglo XXI basada en el mejoramiento del ser humano mediante la tecnología.

Fuente.

En esto somos completamente tradicionales.

2. IA. Estados Unidos quiere saber a quién culpar si un coche sin conductor se estrella

¿ Por que no resuelven primero este problema con los buscadores que literalmente atropellan a los usuarios que quedan completamente indefensos ?

3. La primera tienda física de Amazon.

Creo que no era el proyecto sobre el que se habló hace meses…

4. Los problemas de innovación de Canada.

5. La agonía del largo plazo.

¿ Quien piensa hoy a un plazo de más de 3 o 4 años ?. Ni los particulares, ni las empresas, ni siquiera ya los gobiernos. Un ejemplo de negocio centenario afectado por este cambio en la concepción del tiempo: como el futuro ya está aquí, completamente presentista…

The world’s oldest bell foundry, which made Big Ben and Liberty Bell, is closing after 500 years despite its attempts to keep the business afloat with the Downton Abbey effect.

However, quality craftsmanship takes time. The average time from enquiry to order is 11 years, and the longest commission in the foundry’s history took 100 years to produce.

Order to installation takes another year, and a major project could cost as much as £250,000 to produce.

Mr Hughes, who learnt the craft from his father, previously told the Telegraph: “We’ve survived because we produced stuff that people want. That means constantly adapting. You do not remain in business if you keep saying no. Twenty years ago we didn’t provide any doorbells.

“We are a tiny market. And at the end of the day, there aren’t many churches being built now, but people still love the sound of bells and that’s what has kept us going.”

The firm has been at its premises on Whitechapel Road since 1670, previously a coaching inn called the Artichoke that was damaged in the Great Fire of London.

6. Ecommerce. La nueva estrategia de Nike.

7. Traducción automática. ¿ un traductor universal ?

Aunque sea un artículo de la infame empresa, interesante. ¿ Universal ?. Yo este año he tenido que traducir de lenguas no indoeuropeas a indoeuropeas y el traductor, de discurso escrito a discurso escrito, de esta empresa deja mucho mucho que desear. Y entiendo que mucho más  complicada es la traducción automática de discurso verbal a discurso verbal.

Relacionado.

8. Imperialismo computacional. En McDonald´s.

9. La barrera de 1000 usd por genoma completo superada: veritas genetics.

Es  una noticia que tiene ya meses pero me he enterado hace muy poco.

10. Telerobótica y telepresencia, el trabajo del futuro.

11. El lapo azul: la propiedad de la  información genética. El caso de dos  gemelas.

12.La sociedad del ocio, ¿ a la vuelta de la esquina ?…

Título y resumen del artículo periodístico.

Cómo será nuestro trabajo cuando tengamos que trabajar la mitad

Las nuevas tecnologías impulsan un mundo de autónomos, jornadas reducidas, mayor tiempo de ocio y la promesa de que trabajar será una elección personal

13. La cuarta revolución industrial: Schwab vs. Gordon.

Schwab.

Gordon. The Rise and Fall of American Growth: The U.S. Standard of Living Since the Civil War.

14. Música electrónica 2. Otra producción (creo) del sello argentino ZZK. 

Disclaimer. Es  novedad en WordPress que ahora los enlaces a los vídeos en las entradas tienen una aparición visual. Lo celebramos con algunos videos.

No supera a la otra a la que enlazamos en su momento pero está muy bien en general.

Relacionado. Música electrónica colombiana.

15. Google y las noticias falsas: ¡¡ Dios, cuanto fariseo !!.    

Relacionado.

16. Los coches autónomos ya son realidad en Singapur. 

17. Fintech. La inevitable cooperación de la banca tradicional (incumbentes) y start ups (disruptores).  

Relacionado.

18. Sondeos en tiempos de Big Data: elecciones USA:  ¿ que falló ?.

Disclaimer. Trabajé como consultor en temas relacionados con sondeos científicos y desde entonces mantengo un interés sobre este tema.

Dejo los enlaces que he encontrado, tal cual, sin editar. Algunos muy interesantes. 

http://andrewgelman.com/

https://www.washingtonpost.com/news/the-fix/wp/2016/11/09/why-polling-faces-a-moment-of-reckoning-after-the-2016-election/?hpid=hp_hp-bignews6_fix-polls-212pm%3Ahomepage%2Fstory

http://www.lemonde.fr/les-decodeurs/article/2016/11/10/l-election-de-trump-et-les-trois-echecs-du-big-data-electoral_5028978_4355770.html

https://www.washingtonpost.com/news/the-fix/wp/2016/11/11/prediction-professor-who-called-trumps-big-win-also-made-another-forecast-trump-will-be-impeached/?tid=pm_politics_pop_b

Big Data no es un término que sea puro marketing. Tiene sustancia. Es la aplicación de técnicas estadísticas no clásicas a datos de fuentes heterogéneas para obtener conocimiento sobre una determinada realidad. Su aplicación al  marketing político ejecutivo (campaña de Clinton) y predictivo  (sondeos) se tiene que pulir.

19. El impacto de la tecnología sobre la cultura.

20. Cursos de ecommerce.

21. Fintech: Blockchain

22. Venter

Algorítmica y Complejidad Computacional. Recopilación de enlaces, noviembre 2016: Redes de Interconexión, Grafos de Cayley, Recorridos Hamiltonianos, Permutaciones y otros. 

noviembre 30, 2016

Una recopilación de artículos sobre los temas que aparecen en el título, realizada en fechas varias, la última esta misma mañana (por el lunes), en la cual he encontrado cosas muy interesantes con respecto a potenciales aplicaciones. Aunque ya se sabe que entre la ingeniería apegada a la tierra y las elevadas matemáticas se encuentra el limbo de potenciales aplicaciones que nunca terminarán de concretarse en sistemas reales.

Antes de empezar con los enlaces un extracto de una muy reciente entrada en un blog de un experto en complejidad computacional. Creo que es reseñable ya que la declaración es sorprendente, contundente y va contracorriente:

The bottom line of this post is that we can’t prove lower bounds because they are false, and it is a puzzle to me why some people appear confident that P is different from NP.

Añadido a última hora.

On the Complexity of the Word Problem of Automaton Semigroups and Automaton Groups

I. Enfoque de ingeniería de redes: redes de interconexión (supercomputadores, NoC´s, Data Center Networks).

Data center interconnection networks are not hyperbolic

David Coudert1,2 and Guillaume Ducoffe2,1 1 Inria, France 2Univ. Nice Sophia Antipolis, CNRS, I3S, UMR 7271, 06900 Sophia Antipolis, France

Abstract Topologies for data center networks have been proposed in the literature through various graph classes and operations. A common trait to most existing designs is that they enhance the symmetric properties of the underlying graphs. Indeed, symmetry is a desirable property for interconnection networks because it minimizes congestion problems and it allows each entity to run the same routing protocol. However, despite sharing similarities these topologies all come with their own routing protocol. Recently, generic routing schemes have been introduced which can be implemented for any interconnection networks. The performances of such universal routing schemes are intimately related to the hyperbolicity of the topology. Roughly, graph hyperbolicity is a metric parameter which measures how close is the shortest-path metric of a graph from a tree metric (the smaller gap the better). Motivated by the good performances in practice of these new routing schemes, we propose the first general study of the hyperbolicity of data center interconnection networks. Our findings are disappointingly negative: we prove that the hyperbolicity of most data center topologies scales linearly with their diameter, that it the worst-case possible for hyperbolicity. To obtain these results, we introduce original connection between hyperbolicity and the properties of the endomorphism monoid of a graph. In particular, our results extend to all vertex and edge-transitive graphs. Additional results are obtained for de Bruijn and Kautz graphs, grid-like graphs and networks from the so-called Cayley model.

–Muy interesante. Y muy reciente, de 2016.

The Influence of Datacenter Usage on Symmetry in Datacenter Network Design

Alejandro Ericksona , Iain A. Stewarta,∗ aSchool of Engineering and Computing Sciences, Durham University, South Road, Durham DH1 3LE, U.K.

Abstract We undertake the first formal analysis of the role of symmetry, interpreted broadly, in the design of server-centric datacenter networks. Although symmetry has been mentioned by other researchers, we explicitly relate it to various specific, structural, graph-theoretic properties of datacenter networks. Our analysis of symmetry is motivated by the need to ascertain the usefulness of a datacenter network as regards the support of network virtualization and prevalent communication patterns in multi-tenanted clouds. We argue that a number of structural concepts relating to symmetry from general interconnection networks, such as recursive-definability, the existence and dynamic construction of spanning-trees, pancyclicity, and variations of Hamiltonicity, are appropriate topological metrics to use in this regard. In relation to symmetry, we highlight the relevance of algebraic properties and algebraic constructions within datacenter network design. Built upon our analysis of symmetry, we outline the first technique to embed guest datacenter networks in a host datacenter network that is specifically oriented towards server-centric datacenter networks. In short, we provide the graphtheoretic foundations for the design of server-centric datacenter networks so as to support network virtualization and communication patterns in cloud computing.

Extractos.

Whilst the design of DCNs is more recent, it has much in common with general interconnection network design yet there are profound differences too, prompted by, for example, usage, scale, and packaging. Hitherto, the most common metrics used for DCN evaluation are the availability of routing algorithms, hardware cost (e.g., number of servers and switches), hardware complexity (e.g., number of server-ports), diameter, bisection width, connectivity, and shortest-path lengths. It is probably fair to say that the development of appropriate topological metrics for DCNs is not as advanced as it is for distributed-memory multiprocessors and networks-onchips, and that the validity of these topological metrics within a datacenter environment is not as well established. Our paper seeks to strengthen the role of topological metrics in DCN design.

Our work sits between the engineering process of building datacenters and the theoretical consideration of abstractions of DCNs as discrete structures; that is, it is graph theory targetted towards a practical application area.

(more…)

Imperialismo computacional. Recopilación de enlaces octubre 2016.

octubre 17, 2016

Recopilación de enlaces sobre los temas habituales de la serie Imperialismo Computacional. 18 puntos, en general sin comentarios adicionales excepto al final.  Algunos recién salidos del horno. 

0. Ahora que por fin me había decidido a perder la virginidad… :-).

1.Capital riesgo para nuevos emprendimientos en España.

2.Ecommerce: su crecimiento.

(more…)

Diferencia entre un caso twisted y otro smooth (2).

septiembre 12, 2016

1.No tengo demasiado tiempo ahora para desarrollar las entradas anteriores sobre este mismo tema plenamente. Vamos a describir rápidamente la diferencia más importante, a efectos prácticos de un caso smooth (S5, sigma-tau) y otro twisted (S5, 2-twisted). Soy consciente de que el sigma  tau es C2C5 pero como se verá esto no es relevante (los escépticos al respecto tendrán que esperar a que se analice un caso C2C5 o C2C6 twisted…).

Cuando  hemos marcado el IAS de la identidad (VF ciclo) y su opuesto por el generador de orden 4, y alguno intermedio que maximice el número de IASes marcados (hay diferencias y esto se puede hacer para los dos casos) se trata de aplicar el siguiente método:

Paso 1. Hacer una lista de los ciclos que tengan al menos 2 arcos marcados.

Paso 2. Dentro de esta lista identificar que IASes tienen presentes arcos en varios de los ciclos. Si marcamos estos en un digrafo de C2C4, ya tendremos que marcar el otro arco de todos estos ciclos por el generador de orden 2 para evitar obtener ciclos de C4. Así maximizamos el nº de IASes marcados cuando tengamos que extraer las consecuencias. Puede haber varios IASes que cumplan con esta condición.  Supongamos (hipotéticamente) por ejemplo el IAS nº 2 y el IAS nº 5 y el IAS nº 7.

Paso 3. identificar algún IAS tal que al ser marcado por C2 obligue a estos tres IASes a ser marcados por el generador de orden 4. De esta manera maximizamos todavía más el número de IASes que serán marcados en cada opción, al extraer sus consecuencias. Supongamos que el IAS 9 cumple esta condición.

Entonces, elegimos la opción de marcar el IAS 9 por el generador de orden 2, esto tiene como consecuencias que los IASes 2,5 y 7 tienen que ser marcados por el generador de orden 4 y a su vez los arcos que completan estos tres ciclos tendrán que ser marcados por el generados de orden 2.

Lo importante es que al  marcar uno solo IAS obtenemos, como consecuencia muchos otros IASes marcados (llamemos a esto efecto multiplicador, por ponerle algún nombre), algunos por el generador de orden 2 y otros por el de orden 4, pero en una determinada proporción desequilibrada. Esto  se puede repetir de manera iterativa de tal manera que al final le media de la que hemos hablado en las anteriores entradas sale elevada.

La diferencia entre un caso smooth y uno  twisted es que los casos smooth, en el paso 2 no vamos a encontrar un IAS que tenga varios arcos en diferentes ciclos de los que ya tienen marcados . Por lo tanto no se puede obtener este efecto multiplicador y la media saldrá baja. Y en los casos 1-twisted y 2-twisted si se encontrarán y por lo tanto se dará el efecto multiplicador

Veamos esto con detalle (hemos realizado exactamente las mismas operaciones en los dos casos antes de realizar la lista de ciclos).

Lista de ciclos del caso 2-twisted (los datos no son hipotéticos, son reales; los números indican el número de IAS (los IASes se han numerado de manera arbitraria, un número es equivalente a un color); los signos más o menos indican si el IAS correspondiente está marcado o no; la lista incluye solo a aquellos ciclos que tienen 2 o más arcos marcados).

Una imagen del caso con los IASes marcados tal y como se han indicado. Es en esta imagen en la que  nos hemos basado para realizar las tablas siguientes. Por lo  tanto la numeración se corresponde con al del texto. El nº del IAS aparece al lado de los arcos. El IAS amarillo, el nº 18 que rodea el digrafo es el que se marca como tercera opción, por el generador de orden 2, tras marcar el IAS de la identidad y su opuesto dentro de la circunferencia  por el generador de orden 4:

s5-c2c4-twisted-22

Tabla 1.

1+,6-,7+,8-

1+,8-,10+,11-

1+,11-,12+,2-

1+,2-,3+,4-

1+,4-,5+,6-

23+,7+,6-,13-

3+,23+,9-,4-

Para simplificar hagamos ahora una lista de los IASes que no están marcados en cada ciclo.

Tabla 2 derivada de la tabla 1 simplificando.

6,8

8,11

11,2

2,4

4,6

6,13

9,4

Vemos que el IAS 6 tiene arcos en 3 ciclos, al igual que el 4. El 8,11 y 2 tienen arcos en dos ciclos. Por lo tanto 6,4,8,11 y 2 son los IASes de nuestro interés.

El siguiente paso, el Paso 3, sería identificar IASes que estén unidos al 6 y al 4 y posiblemente a alguno de los otros 3. Si existe, se selecciona el que maximice el numero de IASes. En el caso en concreto hay varias posibilidades: el IAS nº 24 por ejemplo conecta con el 6 y con el 11 y con otros cuatro, ninguno de ellos marcado; el IAS 13 conecta con el 2, con el 17 y con otros 4 uno de ellos ya marcado etc…. Habrá que seleccionar la opción que conecte con más de ellos y si es posible que tengan presentes más arcos en diferentes IASes.

El lector podrá comprobar como el que suceda este fenómeno depende de la propiedad de ser retorcido o twisted.

Lista de ciclos para el caso Sigma-Tau (caso real, nos ceñimos a la tabla 2; se han obtenido tras marcar el IAS de la identidad y su opuesto por el generador de orden 4, y marcando como tercera opción un IAS seleccionándolo para que maximizase el nº de IASes marcados).

Por cierto, tras consultar en mi base de datos, confirmo que este caso Sigma-Tau tiene recorridos hamiltonianos en todos los vértices finales posibles.

La imagen (idem anterior):

s5-sigma-tau-22

Tabla 2 (ninguno de los IASes que aparecen está marcado).

5,6,24

10,11,2

8,28,16

12,27,20

No hay ninguno repetido. Es importante señalar que en realidad si hay varios ciclos tal que un mismo IAS pasa por ellos pero en todos ellos hay un arco de orden 4 marcado como que no se debe de marcar (es decir su correspondiente IAS está ya marcado por el generador de orden 2) y por lo tanto este ciclo no se puede compltar, que es lo que nos preocupa. Estos ciclos con una arco marcado como que no se debe de marcar no cuentan.

Como había otro IAS candidato a la tercera opción hemos repetido el proceso para varios IASes diferentes, para todos los candidatos y estas son las tablas de tipo 2 que se obtienen:

2,4,5

10,24,9

20, 19, 8

12,16, 25

De nuevo, ninguno repetido, como puede comprobar el lector. En el caso Sigma-Tau, como en todos los smooth, no hay efecto multiplicador y por lo tanto no existe el mismo obstáculo que en los twisted a la hora de que pueda haber recorridos hamiltonianos.

De la misma manera, seguramente en los smooth, seguramente no será posible encontrar un IAS en el paso 3 que sea más ventajoso que el resto. Cada opción en los casos smooth es mucho más independiente que en los casos twisted.

2. Lo anterior obviamente no es una demostración de que el caso 2-twisted no puede tener recorridos hamiltonianos. Los parámetros del caso analizado 2-twisted son S5, C2C4, IAS5 y circunferencia 6. como el IAS es de orden 5, tiene 24 IASes y por lo tanto la distribución recorre desde 0 IASes activados por el generador de orden 2 y 24 activados por el de orden 4, es decir (0,24) al otro extremo (24,0). Interesa determinar un método rápido que nos permita identificar las fronteras, es decir entre que intervalos de pares [(0,24); (x,y)] y [(w,z); (24,0)] sabemos que no pueden existir RHs. Ahora mismo, para este caso en concreto no me parece evidente determinar esto salvo los extremos extremos, pero igual es que es última hora del día…

Los parámetros del caso Sigma-Tau son S5, C2C5, IAS4 y circunferencia 6. Tiene por lo tanto 30 IASes y el rango de la distribución recorre (30,0) a (0,30).  Idem anterior.

Actualización día siguiente.

El método más directo para determinar acotar la frontera es el siguiente (vale para cualquier caso). Nos conformamos con acotar la frontera.  Pienso que será suficiente para lo que nos interesa.

Frontera para el generador de orden 2.

El  método (que hoy me parece obvio) es el siguiente:

–Obtenemos primero el nº de ciclos de orden 4 que tiene el caso. Para el 2-twisted hay 120/4 = 30.

–Si queremos que no aparezca un ciclo de estos con todos los arcos marcados, tiene que haber en cada uno de ellos al menos un arco desactivado por el generador de orden 4. Y por lo tanto el IAS de ese arco tendrá que ser activado por el generador de orden 2. Por lo tanto tiene que haber al menos 30 arcos marcados por el generador 2.

–Como el IAS es de orden 5, cada IAS tiene 5 arcos del generador 2. Para obtener la cota dividimos el número obtenido anteriormente, 30, que indica el número de arcos que deberán de ser activados por el generador 2, por el número de arcos del generador 2 que contanga un IAS, que es equivalente al orden del IAS, en este caso 5. Es decir 30/5 = 6. La cifra obtenida, 6 en este caso nos da el número de IASes mínimo que tendremos que marcar para que no haya un ciclo de orden 4.

¿ Podemos concluir que tiene que haber al menos 6 IASes marcados por el generador 2 para que pueda haber recorridos hamiltonianos  y que por lo tanto (6,18) es la frontera para el generador de orden 2 ?. Es decir que menos de 6 IASes marcados por el generador 2, no puede haber recorridos hamiltonianos, y más de 6 IASes sí puede haberlos.

No lo tengo claro: ¿ no puede haber algún ciclo que contenga arcos de dos de los 6 IASes diferentes y por lo tanto aunque marquemos 6 IAses todavía habría ciclos de orden 4 sin ningún arco marcado como que no puede ser activado ? . Hagamos la pregunta traducida a un lenguaje experimental: en el caso 2-twisted ¿ podemos seleccionar entre los 24 IASes 6 de ellos tal que al activarlos por el generador de orden 2 todos los ciclos de orden 4 tengan un arco de orden 4 desactivado ?.

¿ Y en el caso Sigma-Tau ?. Apliquemos este método al caso Sigma-Tau para ver cuantos IASes tendríamos que marcar. 120/5= 24 ciclos de orden 5. Hay que marcar 24 arcos por el generador de orden 2. El IAS es de orden 4 y por lo tanto cada IAS tiene 4 arcos de orden 2. 24/4=6. También en este caso hay que marcar 6 IASes entre 30. Aquí tenemos más espacio, lo cual ya es un dato….

Tras estudiar este tema para el caso Sigma Tau (de manera no sistemática, no he agotado todas las posibilidades, pero no hay duda) se puede concluir que para este caso no existen 6 IASes independientes entre los 30.

La segunda conclusión es que cuando no existe este número mínmo de IASes independientes, al haber repeticiones, hay que marcar más IASes que los que indica este límite teórico para que todos los ciclos de orden 4 tengan al menos un arco desactivado.

Por lo tanto este método, que se puede aplicar de manera muy rápida cuando conocemos los parámetros, nos sirve para encontrar una cota inferior de la frontera.   En algunos casos, conocer esta cota inferior será suficiente para poder demostrar que el caso en cuestión no puede contener recorridos hamiltonianos.

La fórmula para encontrar esta cota inferior es:

Cota frontera = (Orden del digrafo / orden del ciclo) / orden del IAS. 

Calculemos las dos cotas para el caso Sigma-Tau y para el 2-twisted.

Sigma-Tau: [C2(6,24);C4(15,15)]. Es decir menos o 6 IAses marcados por C2, no podría haber recorridos hamiltonianos; menos o 15 IASes marcados por C4 tampoco podría haber recorridos hamiltonianos. La situación con respecto a los pares contenidos entre estas fronteras es indeterminada.

2-Twisted: [C2(6,18); C4(12,12)]. Idem anterior. Aquí vamos a concretar: podría haber recorridos hamiltonianos con 7 IASes marcados por el generador de orden 2 y 17 IASes marcados por el generador de orden 4. Con (8,16), con (9,15), con (10,14) y con (11,13). El rango entre las cotas de las fronteras es menor que en el caso Sigma-Tau.

Los conceptos y métodos que hemos expuesto en las entradas anteriores lo que permitirían (el tema está en investigación) es demostrar que en los casos twisted, por el fenómenos de multiplicador o amplificación que la propiedad twisted provoca o permite, no son posibles activaciones “coherentes” que nos lleven al rango que está entre las cotas de las fronteras teóricas. Cualquier activación posible dentro de este rango que intente evitar ciclos no hamiltonianos, hará que acabemos en activaciones por debajo de las cotas teóricas de la frontera.

Comentar que en todas las últimas entradas no estamos teniendo en cuenta consideraciones de complejidad computacional. Pero cuando hayamos aclarado todas estas dudas estas consideraciones serán clave: encontrar test rápidos  y que utilicen poca memoria de retorcimiento.

Fin de actualización.

Imperialismo computacional. Recopilación de enlaces septiembre de 2016.

septiembre 3, 2016

Publicamos una entrada de recopilación de enlaces que llevamos arrastrando desde hace ya varios meses. ¡ Hoy o nunca !. Aprovechamos que llevamos prácticamente todo agosto sin entrar en Internet y realmente teníamos mono.

La mayoría de los enlaces son del primer trimestre del año, y algunos aunque han perdido actualidad, conservan el interés para todos aquellos interesados en los temas sobre los que hablamos desde hace años en la serie Imperialismo Computacional. Otros, los menos, son más recientes.

No todo son enlaces. Como suele ser habitual, en un par de puntos nos hacemos unas muy breves reflexiones sobre que supone, para el ser humano, el ciberespacio como nuevo entorno artificial, con el foco en la omnicanalidad (punto 18; lo hemos titulado pomposamente: Filosofía del ciberespacio, mucho título para tan poco contenido; como explico en el punto citado, la omnicanalidad me ha tenido abducido durante unos meses y es un concepto que hemos usado ampliamente en el desarrollo del proyecto) y, en el punto 24, sobre el ambiente ideológico a principios del s XXI, es decir del corriente, en las vanguardias intelectuales: postmodernos vs. tecnoptimistas (el título es también bastante artificioso y se puede aplicar el mismo juicio que en el caso anterior).

En fin agrupamos por primera vez agrupamos los diferentes enlaces / puntos (29 en total) en varios temas: robótica, internet, el estado de la cultura global e IA.

I.Robótica.

1.La extensión de la robótica.

La tabla siguiente es realmente interesante. Seguramente el dato español se explica en gran parte por la importancia en nuestro país de la industria de automoción.

Los crecimientos internuales en el stock total son de en torno a un 10%.

industrial-robots-by-country

(more…)

HPC. Top 500. El sistema Sunway TaihuLight es nº 1.

septiembre 2, 2016

Sunway TaihuLight is the new No. 1 system with 93 petaflop/s (quadrillions of calculations per second) on the LINPACK benchmark.

Fuente, la página web del TOP500.

Como siempre en las últimas ediciones del actualizado bianualmente ranking TOP500, informamos con retraso, en esta ocasión de un par de meses o más, sobre las novedades en su última edición de junio de 2016.

Desarrollamos el tema en tres puntos: el primero con enlaces a detalles técnicos del sistema; el segundo con información sobre los 6 centros de supercomputación en China y su localización y el tercero con algunos enlaces que contienen consideraciones geopolíticas sobre estos avances en la tecnología de la R.P. China.

1.La mayor novedad del ranking es que ahora el sistema nº1, que da nombre a la entrada, es un nuevo sistema chino, que adelanta así a al también sistema chino Tianhe-2 que ha reinado en las primeras posiciones en los 2 o 3 últimos años.

(more…)

Caso de S5, C2C4 Twisted (3).

agosto 24, 2016

Actualización 12 de mayo 2017. Hemos añadido el (3) en el título. Fin de actualización. 

Disclaimer. Entrada en construcción. Cuando esté terminada, eliminaremos este mensaje.

En entradas anteriores hemos analizado casos entrelazados (entangled) y hemos visto como esta propiedad era clave para que emergiesen obstrucciones a la hamiltonicidad. En otras hemos realizado lo mismo para casos Twisted, pero de manera poco satisfactoria en nuestra opinión. En esta entrada lo intentamos de nuevo para casos Twisted, creo que de manera algo más clara ilustrativa. Pienso que el tema va tomando ya forma, aunque todavía hay algunos interrogantes.

En linea con la última actualización presentamos el análisis, según vamos realizando de un caso 1-twisted de S5. Ya lo hemos presentado en una anterior entrada pero con otro análisis. Con éste se aprecia claramente el efecto de la propiedad twisted.

1.Opción 1. 

Nota al margen 1.

Pido disculpas al lector por lo confuso de los dibujos. No tengo tiempo para hacerlos con más claridad y para lo que me interesa, es suficiente.

Fin de nota al margen 1. 

S5 c2 c4 twisted

Hemos marcado el IAS de la identidad por el generador de orden 2. Y su opuesto, el IAS de color violeta que contiene el arco 31245–>32154 entre otros, también por el generador de orden 2. Extraemos la consecuencias de estas dos opciones y el efecto es una contradicción que se aprecia en el ciclo 23145–>34215–>41325–>12435.

Los factores determinantes que generan obstáculos a la hamiltonicidad en los casos twisted.

¿ A que se debe que el efecto de realizar estas opciones sea una contradicción ?:

–primero, que el IAS amarillo que contiene, entre otros, el arco 34152–>31425, está conectado con el IAS de la identidad y al marcar este último en un sentido, obliga a ser marcado en el otro.

–segundo, que este IAS amarillo se tuerce (esto es precisamente la propiedad de twisted) y se conecta con otro IAS que está conectado con el de la identidad y que también “sufre”  sus consecuencias.

–Tercero, idem anterior con respecto al IAS opuesto a la identidad y los dos IASes conectados con él directamente por un generador de orden 2, y que intervienen en el fenómeno, es decir el de color verde que contiene, entre otros el arco 21354–>15234 y el de color negro o azul oscuro, que contiene el arco 14325–>13452 y que aunque no se aprecia se retuerce también.

–cuarto, el hecho de que el ciclo es de orden 4, es decir corto, también ayuda. A  medida que los ciclos sean más largos será más complicado que se genere la obstrucción. Es un hecho que si bien todos los del tipo C2C4 de S5 no tienen RHs en ninguno de los VFs posibles, los del tipo C2C5 o C2C6 son más bien del tipo que tienen RHs en algunos de los VFs. Ya lo hemos visto en otras entradas. Para más detalle el lector puede leer concretamente esta entrada.

Nota al margen 2.

De momento ya damos por resueltos los casos C2C3 (digamos que hay una “teoría general” para todos ellos, basada en el resultado de Milnor).

Ahora nos estamos concentrando en algo similar para los casos c2C4 (conseguir una teoría general es un tema más complicado, pero de momento diría que no imposible).

Aunque los hemos recopilado conjuntamente con sus propiedades de hamiltonicidad, no hemos analizado en detalle de momento estos casos C2C5 y C2C6. Lo dejamos para más adelante.

Fin de nota al margen 2.

Nótese que los varios factores señalados, explican completamente el fenómeno. Veamos que pasaría si fallase alguno de ellos. Antes recordamos que el IAS de la identidad no es un IAS cualquiera. Es aquel en el que están localizados los vértices finales posibles y dependiendo del vértice final posible que marquemos, se puede activar de diferentes maneras. Esto lo diferencia de todos los demás IASes. Por otra parte, en el caso de que lo que busquemos sean ciclos, este IAS es equivalente a cualquier otro y por simetría podemos elegirlo. Elegir cualquier otro no cambiaría nada.

–supongamos que la longitud de la circunferencia (en este caso contiene 6 IASes) es mayor y que el amarillo twisted conectase con un IAS. Si la circunferencia fuese más larga y el IAS amarillo conectase con un IAS que no estuviese en contacto directo con el de la identidad. Entonces no se generaría la contradicción, al menos tan directamente, ya que faltaría uno de los arcos para completar el ciclo de orden 4. Por lo tanto en este caso, para que se genere la contradicción de manera tan directa, dos de los IASes tienen que estar conectados con el de la identidad  y los otros dos con su opuesto.

–supongamos que ninguno de los IASes que conectan con el IAS de la identidad son twisted. A continuación el caso Sigma Tau de orden 5 cuyas propiedades de hamiltonicidad conocemos.

Nota al  margen 3.

Sobre el caso Sigma Tau, una famosa familia infinita de dígrafos de Cayley Bigenerados, ver este artículo reciente, dónde utilizando en parte técnicas de nuestra patente, lo resuelven. Como ya hemos señalado en otras entradas, pensamos, cierto que sin evidencias,  que no es casualidad que este problema se haya resuelto tras la publicación de nuestra patente. De hecho hacíamos referencia a él de manera velada en ella. Me pregunto si lo que afirman es que todos los Sigma Tau tienen recorridos hamiltonianos en todos los vértices finales posibles. Para  mi esto sería la solución más completa.

Fin de nota al margen 3.

ignacio reneses sigma tau orden 5

Como se puede ver con claridad, ninguno de los IASes que salen del IAS de la identidad es twisted, como no lo es ninguno de los que salen del IAS opuesto, uno de color rojo que contiene, entre otros el arco 21543–>12543. Al activar los dos IASes, el de la identidad y el opuesto, el efecto es que sólo se activan dos arcos del ciclo de orden 5 de los IASes que están en conexión con ellos.

Se puede concluir que en este caso la propiedad de retorcimiento o twistedness es clave para que se genere la contradicción en este caso y que un caso similar aunque no idéntico que “no la tiene” (ya explicaremos por qué el entrecomillado) no es problemático. Ojo, todavía no hemos demostrado que la propiedad sea clave para que no existan RHs en ninguno de los VFs posibles: quedan 3 opciones de activación del IAS de la identidad y de su opuesto, cuyos efectos iremos viendo en succesivas actualizaciones.  Los casos 1-twisted como este, en los que los IASes que conectan con la identidad están interconectados entre ellos son los más sencillos para ver como opera la propiedad de twistedness. Y son los más sencillos para que el algoritmo determine que no puede haber RHs en ninguno de los vértices finales posibles.

Pero como veremos los casos 2-twisted, de los que mostramos  una imagen a continuación (que ya hemos mostrado en entradas anteriores) no son twisted en los IASes que conectan con el de la identidad. Sin embargo tampoco son como el caso Sigma Tau. Más adelante explicaremos la diferencia.

Ignacio RenesesS5 2-twisted

Sigma Tau y otros casos: diferencias.

¿ Cual es entonces la diferencia entre el caso Sigma Tau, que no es problemático y el caso de la última imagen, que si lo es ?.

Observe el lector primero, que en ambos casos hay IASes del DAS de la identidad que si son retorcidos. Por ejemplo en el Sigma Tau, el amarillo, que contiene el arco 23451–>32451, el gris que se encuentra a su lado o el rosa que se encuentra al lado de este último. Y lo mismo sucede con el caso de la última imagen.

La diferencia es que en el caso Sigma Tau, falta uno de los factores señalados: ninguno de los que son Twisted conectan con un IAS que conecte con el IAS de la identidad por  un generador de orden 2. Bien conectan con IASes que están fuera del entorno de la identidad (definición fija), por ejemplo el IAS amarillo ya señalado, bien conectan con el IAS de la identidad a través de un ciclo de orden 5.

Sin embargo en el caso de la última imagen, los que son Twisted del DAS, como por ejemplo el de color azul que también pertenece a la circunferencia y contiene el arco 45132–>51342 si conectan con un IAS que está en contacto directo con la identidad por un generador de orden 2 y por lo tanto puede sufrir los efectos que se obtienen al marcar este IAS de la identidad de manera mucho más inmediata. En este sentido es un caso más restringido que el anterior, que el Sigma Tau, aunque menos que el 1-twisted.

Otra diferencia (me interesa poder expresar la diferencia de manera más cuantitativa) se puede explicar como  sigue: supongamos  que somos un punto (por ejemplo  una hormiga) que nos movemos en un plano, la hoja dónde se encuentra el dibujo y que estamos dentro del IAS de la identidad. Sólo podemos salir por los arcos de orden 2, que digamos serían las puertas (los de orden 4 o más serían las paredes). Nos interesa contar por cuantos generadores de orden 2 pasamos si salimos de la identidad y llegamos de la  manera más directa posible a IAS que es retorcido y luego regresamos al IAS de la identidad siguiendo el retorcimiento. En el caso de la última imagen, tenemos que pasar cuatro arcos: 12354–>12345; 45123–>45132; 13245–>13254  (para llegar aquí hemos tenido que seguir las “paredes” retorcidas) y 54123–>54132. Es decir, pasando cuatro puertas (y esto es lo mínimo) volvemos al IAS de la identidad. Si realizamos lo mismo con el primer caso 1-twisted, lo podemos hacer pasando tres puertas. Y si lo hacemos con el caso Sigma Tau, no lo podemos hacer con cuatro. No se si es posible hacerlo pasando 5. De momento esta diferencia es más escolástica, pero es posible (y ya veo horizonte) que se pueda hacer pragmática: de alguna manera lo que estamos diciendo es que hay grados de retorcimiento. Cuando menor sea el grado (cuantos menos generadores de orden 2 haya por medio, más restringido, más complicado será el caso en el sentido de contener RHs).

Una tercera diferencia es la manera que tiene el IAS opuesto al de la identidad de conectar con los IASes que conectan con él de manera digamos simétrica, cosa que no sucede en los otros casos. De momento no tengo claro como definir de manera operativa esta diferencia.

2.Opción 2. 

En la opción 2 marcamos el IAS de la identidad por el generador de orden 2 y el opuesto por el generador de orden 4. Esta opción vale por dos, ya que si hacemos la inversa el resultado sería el mismo. En la imagen siguiente la situación al  final de realizar esto y extraer consecuencias. Aquí la contradicción va a surgir de manera menos directa y seguramente hay varias maneras alternativas de generarla algunas más rápidas o cortas que otras.

ignacio reneses 1-twisted opción 2

Nosotros probamos la siguiente estrategia: se trata de demostrar que partiendo de esta situación al marcar un IAS por las dos opciones posibles, las dos llevan a contradicción. Marcamos el IAS azul claro que contiene el arco 43512–>45321 dado que está bastante interconectado con los IASes ya marcados (este es un criterio de selección que se podría automatizar fácilmente).

Si marcamos el IAS azul  claro indicado por el generador 2, entonces se genera una contradicción en el ciclo de orden 4 nº 21 ya que el arco 54321–>42531 del IAs amarillo y el arco 42531–>23451 del IAs rosa se deben de marcar por el generador 4 generandose un ciclo de orden 4 al estar los otros dos arcos de este ciclo ya marcados. De nuevo se aprecia en esta contradicción que el hecho de que el IAS violeta que contiene el arco 35241–>54321 sea retorcido juega un papel clave en la emergencia de esta contradicción. El resultado se muestra en la imagen siguiente:

ignacio reneses 1-twisted opción 2

En conclusión si marcamos el IAS de su identidad por el generador de orden 2 y su opuesto por el generador de orden 4, entonces necesariamente el arco azul tiene que ser marcado por el generador de orden 4.  Pasamos a explorar las consecuencias de realizar esto.

Si marcamos el IAS azul claro indicado por el generador de orden 4, entonces se fuerza al IAS de verde claro que contiene el arco 32415–>34251 a ser marcado por el generador de orden 2. Si no aparecería un ciclo de orden 4. Si marcamos este IAS verde claro por el generador 2, fuerza al IAS rojo que contiene el arco 35214–>32541 a activarse por el generador de orden 4.

Al activarse este IAS de color rojo de esta manera, se genera un ciclo de orden 4, el que contiene los arcos 34512–>41352–>15432–>53142, la contradicción esperada.

Como se ve todo en todo el proceso no ha habido opción, son consecuencias necesarias. Queda demostrado que al marcar el IAS de la identidad por el generador 2 y su opuesto por el 4 (o viceversa) no se puede obtener un RH.

En la imagen siguiente se presenta gráficamente todo lo comentado:

ignacio reneses s5 opcion 2

En este último caso también (aunque se ve menos claramente en el dibujo, se podría modificar el dibujo para que se apreciase esto) el hecho de tener algunos IASes la propiedad de ser retorcidos o twisted es condición necesaria para que se genera la contradicción.

Pasamos a estudiar la última opción que entendemos tiene que tener una demostración más complicada.

Nota al margen. ¿ Están siendo más cortas estas demostraciones que las que se obtienen al activar el ciclo de la identidad de todas las maneras posibles ?. Posiblemente no, o no mucho más. Pero creo que si son más ilustrativas del papel que juega la propiedad de retorcimiento para que surjan las contradicciones. Fin de nota al margen.

3. Opción 3.

En este caso  marcamos inicialmente el IAS de la identidad y su puesto en la circunferencia por el generador 4. La situación aparece en la imagen siguiente.

(Continuará próximamente…)

Actualización 29 de agosto de 2016.

Ya tengo perfilado el método (en realidad nada nuevo, es el lógico, pero con una vuelta de tuerca) tal que si el caso es twisted y no tiene RHs en alguno o en ninguno de los vértices finales posibles, entonces puede generar la demostración de que no los tiene de manera sucinta (utilizando ordenador: de momento las pruebas no son del todo rápidas, pero si evitan una búsqueda exponencial, lo cual ya es bastante notable). Funciona tanto para los casos 1-twisted como para los 2-twisted, de momento aplicado a casos de S5. Y discrimina los casos smooth como el Sigma Tau del que hemos hablado en esta misma entrada. Quiero aplicarlo a casos de S6, lo cual llevará un cierto tiempo.

Dónde me encuentro ahora no tengo acceso fácil a Internet. Tampoco tengo las herramientas habituales que necesitaría para publicar imágenes. Además hay que hacer más comprobaciones y aunque lo que tenía en la cabeza ya está aterrizando quedan todavía algunos interrogantes sobre la propiedad twisted / smooth. Cuando tenga todo esto más claro igual se le puede dar una vuelta de tuerca más. Daremos detalles en unos días.

 Fin de actualización.

Actualización 31 de agosto de 2016.

Antes publicar todos los detalles, cosa que haremos en un par de días, queríamos adelantar un resumen de la idea general (que es aplicable tanto a los casos twisted como a los entangled). Para ello introducimos dos conceptos: el primero es una distribución que se puede asociar a cada caso, que podemos llamar distirbución de RHs y el segundo es una media, que también se puede asociar a cada caso, de IASes de un generador que se activan por cada IAS del otro generador que hayamos activado. Nos abstraemos de momento del hecho de que al se puedan marcar diferentes vértices finales posibles. Luego comentaremos sobre como afecta esto.

Distribución: cuando hemos activado todos los IASes de un caso, por u generador o por otro, podemos contar el número de generadores activados de cada tipo y obtenemos 2 cifras. La distribución asocia a cada una de estas dos cifras bien un sí (si con esta activación se obtienen recorridos hamiltonianos) bien un no (si no se obtienen), bien un número, que indica el número de RHs diferentes que se pueden obtener con esta activación. Un ejemplo de distribución para un caso hipotético de 10 IASes de C2C4:

(0 IASes activados de C4, 10 de c2)——-0 RHs,

(1, 9)————————————-0 RHs,

(2,8)————————————-0 RHs

(3,7)————————————-1 RH

(4,6)————————————2 RHs

(5,5)————————————4 RHs,

(6,4)————————————2 RHS

(7,3)————————————0 RHs

(8, 2)———————————–0 RHs

(9,1)————————————0 RHs

(10,0)———————————-0 RHs.

Repetimos que el ejemplo es puramente hipotético.

Media. Cuando analizamos un caso de C2C4, si el IAS es por ejemplo de orden 5, si buscamos un ciclo y marcamos el IAS de la identidad inicial por el generador de orden 2 se activaran, como consecuencias, 5 IASes por el generador de orden 4. A medida que vamos activando IASes, esta cantidad de IASes que se activan por un generador al marcar un IAS de otro generador puede ir variando. Y tomando nota de todo esto, al final podríamos hacer una media del numero de IASes que se activan de un generador al marcar uno del otro tipo.

Aplicación de los dos conceptos indicados.

Hay casos en los que por sus propiedades estructurales, la media que se obtiene es baja y permiten recorrer todos los pares de cifras de la distribución. Pero hay otros casos, tales que sus propiedades estructurales (como por ejemplo el ser 1-twisted o 2-twisted, o el ser entangled) hacen que la media sea tan elevada que los saltos en la distribución hacen que, independientemente de como se activen los IASes, se salte de un extremo de la distribución al siguiente, extremos en los que no pueden existir RHs.

Creo que dentro de este esquema se pueden encajar varios de los resultados previos a nuestra patente (el de Rankin casi seguro; el de Milnor tengo mis dudas), así como varios de los que hemos aportado nosotros (no tengo muy claro si los casos cycle-entangled se pueden encajar dentro de este esquema). Cuando demos detalles se verá claramente porqué en los casos twisted la media es elevada. Todo es más complejo que lo aquí descrito (pues también entra en juego el número de IASes: a igualdad de media elevada, si el número de IASes del caso es también elevado es posible que incluso saltos elevados a lo largo de la distribución no impidan que haya RHs. Realemente los casos de S5 que hemos analizado no son los más representativos. Y también hay que tener en cuenta que al activar vértices finales posibles diferentes, se activan inicialmente un número diferente de IASes por los dos generadores. El esquema presentado explica concretamente que haya casos sin ciclos hamiltonianos pero que sí tengan caminos. Y posiblemente haya otras complicaciones que iremos viendo.

¿ Podemos derivar de este esquema una teoría general que nos permita dado un caso determinar rápidamente (con unas comprobaciones mínimas) si el caso tendrá RHs en los diferentes VFs ? No lo descarto. El método sobre el que hablamos en la actualización anterior, que es puramente algorítmico,  lo que hace es tener en cuenta que en los casos 1-twisted y 2-twisted la media es elevada, y teniendo en cuenta esto permite acelerar la prueba algorítmica de que no tiene RHs, seleccionando de manera “inteligente” pero automatizable, para su activación desde los primeros paso, los IASes que suben la media para llegar lo antes posible a la solución, es decir la determinación si el caso, para el VF dado, tiene RHs o no. De la misma manera se podría retrasar. Y el algoritmo tal y como lo tenemos programado ahora mismo, hace una selección no inteligente y por lo tanto hace computaciones que se podrían evitar. Este nuevo método algorítmico (el que comentamos en la última actualización), que como decíamos no aporta nada realmente nuevo, es ya un avance significativo con respecto a lo que teníamos pues ahorra bastante tiempo y uso de memoria.

Con respecto al tema de la segunda solicitud de patente, tras todo lo comentado en la presente actualización, se justifica con mayor razón su concesión, que está pendiente, pues en todo lo descrito anteriormente  lo que hemos hecho es utilizar dos de las propiedades estructurales que se pueden dar en los casos (la propiedad de retorcimiento y la propiedad de entrelazado) para resolver de manera más eficiente que la que existe en el estado del arte actual el problema de recorridos hamiltonianos en digrafos de Cayley bigenerados. Esto es precisamente lo que intentamos proteger en dos de las reclamaciones (las correspondientes a la propiedad de entrelazado y a la propiedad de retorcimiento). Las otras reclamaciones hacen los mismo con respecto a otras propiedades estructurales. Tras cuatro años de tramitación, no me explico todavía cuales on las dudas de la USPTO al respecto…

Fin de actualización.

Actualización 2 de septiembre de 2016.

Ya estamos instalados en nuestro entorno habitual de publicación. Esperamos poder terminar esta entrada hoy mismo.

Antes, en esta actualización queremos comentar que la redacción de la actualización anterior es algo confusa y aclarar algunos puntos.

Distribución. Obviamente, aunque tal distribución exista, es desconocida salvo algunos puntos que si se pueden calcular de manera rápida sobre todo en los extremos. Por ejemplo se sab que si activamos todos los IASes por el generador de orden 2, no podrá haber recorridos hamiltonianos. Y lo mismo si los activamos por el generador de orden 4. Un paso importante es determinar dentro del rango de pares, la frontera entre aquellos pares que se sabe que no pueden tener recorridos hamiltonianos y aquellos pares o puntos de la distribución en los que el tema queda como posibilidad indeterminada. Y obviamente habrá casos, aquellos que no tienen recorridos hamiltonianos, en los que ningún par o punto de la distribución tendrá este tipo de recorridos. Es claro que dado un par puede haber diferentes activaciones de IASes que se correspondan con este par y cada activación se corresponderá con un recorrido hamiltoniano diferente. Por lo tanto a cada para le puede corresponder una cantidad de recorridos hamiltonianos. Una pregunta interesante, creo, es hasta que punto podemos considerar que la distribución es continua entre extremo y extremo.

Media. Este concepto se puede comprender mejor como un proceso que empieza con el caso en cuestión sin haber marcado ningún IAS. A lo largo del proceso se van marcando IASes, siempre controlando que no se generen ciclos o caminos que contengan menos vértices que todos los del dígrafo (es decir controlando que no sean ciclos caminos no hamiltonianos). Al final del proceso, en el que se han activado todos los IASes, se ha llegado a un punto de la distribución. Si vamos anotando a lo largo del proceso el número de IASes que se marcan de un generador por cada otro generador, podemos calcular esta media.  Entiendo que esta media es invariante al camino que siga el proceso (tema pendiente de averiguar / demostrar). Pero igual el concepto de media es prescindible… De momento para entendernos vamos a seguir hablando de media pero tenga el lector en cuenta que el concepto se puede modificar o caer.

Lo que queríamos dejar claro en la actualización anterior, la clave de todo es que en algunos casos twisted (como los que estamos analizando)  y entangled se puede demostrar o ver claramente, que debido a que en cada marcado de IAS por un generador se marcan muchos del otro, al final del proceso tenemos que llegar necesariamente a uno de los pares o puntos extremos de la distribución, de aquellos sobre los que es fácil conocer de antemano que no pueden tener recorridos hamiltonianos.

Otros puntos importantes que está pendiente de investigación son:

–primero, si para un grado de retorcimiento (por ejemplo 1-twisted), la media obtenida es siempre constante dado un tamaño de IAS, independientemente del número de vértices del dígrafo. Pensamos que así es  y por ello al aumentar el número de vértices, siendo el mismo el grado de retorcimiento, pueden variar los resultados en cuanto a propiedades de hamiltonicidad.

–segundo, si las medias varian para los diferentes grados de retorcimiento. Por ejemplo si los casos 2-twisted tienen una media inferior a los casos 1-twisted. También pensamos que así es. Si se confirmase hay como una especie de efecto gravitatorio: a mayor distancia, a mayor grado de retorcimiento, menores efectos con respecto a la propiedad de hamiltonicidad, hasta el punto de que a partir de un cierto grado (2-twisted) y un cierto tamaño de dígrafo, el efecto es nulo.

Fin de actualización.

Actualización 3 de septiembre de 2016.

Por  lo comentado en los anteriores puntos le habrá quedado claro al lector que la existencia de recorridos hamiltonianos en un caso twisted depende de al menos los siguientes parámetros:

–nº de IASes del caso.

–Tamaño del IAS.

–Vértice final posible elegido.

–Grado de retorcimiento (esto está por ver).

También de que en los casos C2C4 se da un fenómeno inverso a los casos C2C3.

Si bien en estos últimos casos, cuanto mayor sea el número de IASes, cuantos menos IASes contenga el entorno de la identidad en relación con este número total de IASes, menos podemos esperar que tenga recorridos hamiltonianos el caso.

Al contrario, en los casos C2C4, cuanto mayor es el número de IASes en relación al entorno de la identidad, mayores son las expectativas de que el caso contenga recorridos hamiltonianos.

Fin de actualización.