Trade Lane Megacities. Recopilación de enlaces, julio 2015.

junio 30, 2015

Disclaimer. Por error he publicado ésta entrada antes de completar los 10 puntos. La dejo publicada y los iré completando. Igual aquí hay una nueva fórmula…

1. Las ciudades principales (o primates).

No se si me convence el concepto. Tenía claro el  motivo cuando leí el artículo y lo  tendré cuando lo relea.

2. St petersburgo vs. Moscu (como ciudades principales).

3. La importancia de las vías fluviales para la dispersión de la oleada neolítica.

Título. The role of waterways in the spread of the Neolithic.

Abstract. The causes and implications of the regional variations in the spread of the incipient agriculture in Europe remain poorly understood. We use population dynamics models to study the dispersal of the Neolithic in Europe from a localised area in the Near East, solving the two-dimensional reaction-diffusion equation on a spherical surface. We focus on the role of major river paths and coastlines in the advance of farming, to model the rapid advances of the Linear Pottery (LBK) and the Impressed Ware traditions along the DanubeeRhine corridor and the Mediterranean coastline, respectively. We argue that the random walk of individuals, which results in diffusion of the population, can be anisotropic in those areas and hence lead to an effective advection. The standard reaction-diffusion equation is thus supplemented with an advection term, confined to the proximity of major rivers and coastlines. The model allows for the spatial variation in both the human mobility (diffusivity) and the carrying capacity, reflecting the local altitude and latitude. This approach can easily be generalised to include other environmental factors, such as the bioproductivity of landscapes. Our model successfully accounts for the regional variations in the spread of the Neolithic, consistent with the radiocarbon data, and reproduces a time delay in the spread of farming to the Eastern Europe, Britain and Scandinavia. 2005 Elsevier Ltd. All rights reserved.

4. La retroplanificación en Los Angeles.

Que datos se tenían en cuenta en su planificación en los años 80.

5. Sobre el fin de la segunda globalización

Un análisis en profundidad.

6. ¿ Puerto Rico = Grecia ?.

Pienso en términos geográficos.

Si pensamos en la UE  y en EEUU como unidades aisladas,  ambas tienen una localización geográfica (de aislamiento, de isla) similar con respecto a la unidad más grande.

Si pensamos  en su situación con respecto a la Ruta Central, no está tan claro. Aparentemente Puerto Rico estaría  mejor posicionada (¿ no hay espacio en el Caribe para un Nodo Principal de tipo entrepot redistribuidor ?). Viendo el mapa, está claro que Puerto Rico no tiene el potencial de Nodo Principal y sin embargo recuerdo haber leído que tenían un puerto potente….

Como ya hemos comentado en otras ocasiones Jamaica, el este de Cuba o Haití son en éste sentido los mejor posicionados (salvo  que finalmente se haga  el proyectado en el pasado Canal de Cuba, sobre el que hablamos en otras entradas) si es que tiene sentido un Nodo Principal en éste punto. Y el Oeste de Cuba, para el Ramal del golfo de México.  Y la punta de la península de Yucatán.

caribe

Y aprendo hoy que están en una situación financiera similar.

Desarrollo. Recopilación de enlaces de julio 2015.

junio 30, 2015

Los 10 puntos habituales con enlaces recopilados en el último mes. El último punto varios enlaces de la temática del Lapo Azul: empieza a confirmarse la polémica hipótesis que lanzábamos en una entrada anterior. ¿?

1. Frase de la edición.

Pienso (en como ganarme la vida) luego existo.

Mr. Desarx de Macartes, PHD.

Traducción libre mía. Nunca el materialismo se resumió de manera más económica Pero en un futuro, tan lejano como los comunistas anti-patentes de hoy quieran, ya no se comprenderá el materialismo, como no comprendemos hoy ideologías lejanas en el tiempo.

2. Nuevo libro de la  colección ¿ Por qué Europa ?

Leer el resto de esta entrada »

Imperialismo Computacional. Recopilación de enlaces, julio de 2015.

junio 30, 2015

En ésta edición, los 10 puntos habituales y un bonus que acabo de encontrar posteriormente.

0. La frase de la edición.

“Pour l´honneur du logiciel de la machine”.

Professor Jacoger Zeilbelbi.

Éste profesor puede ser considerado como epígono de los románticos y precursor de los imperialistas (computacionales).

1. Privacidad. ¿ Que hacen con nuestros datos en Internet ?.

Algunos juzgarán que no pasa nada; para otros escalofriante.

2. La automatización en Facebook.

Escalofriante se mire por dónde se mire, pero tendencia irreversible a la que no queda más remedio que adaptarse.

3. Martin Wolf sobre el  Imperialismo Computacional.

Es un destacado economista, periodista y consultor. Lamentamos no tener más tiempo para comentar en profundidad el artículo. Aunque por otra parte,  nada realmente nuevo: sólo queda claro que la mentalidad comunista (sin justificación teórica) está calando a todos los niveles.

Y lo peor es que esa mentalidad que a lo mejor tendrá  sentido en el futuro (quizás Marx tenía razón, a la larga) se está trasladando al presente. La actual política de EEUU con respecto a las patentes de software lo demuestra. De esta manera se hace imposible ese comunismo, quizás deseable en un futuro cuando la  fuente del conocimiento quede agotada.

Señores, que está en juego la mismísima Sociedad del Ocio. ¿ No nos estamos precipitando ? Paradojas del presente.

Notas.

–En cuanto a la cantidad de conocimiento científico que se pueda generar, soy finitista radical, no sólo por marginalimo, sino en términos esencialistas; con la salvedad de las Ciencias formales que por otra parte sólo pueden tener un número finito de teorías con aplicaciones interesantes, si éstas de dan en una cantidad finita; pero problemas matemáticos del tipo de pour l´Honneur de l´esprit humain  (gran libro el del mismo título por cierto) o recreativo, más o menos interesantes, que piquen la curiosidad, los habrá siempre.

–Diría que la contemporánea mentalidad anti-patentes no  existía antes. Es un fenómeno cuya genealogía es digna de historiar. No parece tener raíces, o no sólo, con la izquierda. Y parece fruto de una mala regulación: en EEUU no han sabido gestionar el problema que han supuesto determinadas patentes, sin verdadero contenido novedoso. Desarrollaré ésto en otra entrada.

Fin de nota.

Extractos.

Making robots replicate all the complex abilities of human beings has proved extremely difficult. Yes, robots can do well-defined human jobs in well-defined environments. Indeed, it is quite possible that standard factory work will be entirely automated. But the automation of such work is already very far advanced. It is not a revolution in the making. Yes, it is possible to imagine driverless cars. But this would be a far smaller advance than were cars themselves.

Beyond this, people imagine something far more profound than robots able to do gardening and the like: the “technological singularity,” when intelligent machines take off in a rapid cycle of self-improvement, leaving mere human beings behind. In this view, we will someday create machines with the abilities once ascribed to gods. Is that imminent? I have no idea.

Third, we will have to reconsider leisure. For a long time, the wealthiest lived a life of leisure at the expense of the toiling masses. The rise of intelligent machines would make it possible for many more people to live such lives without exploiting others. Today’s triumphant puritanism finds such idleness abhorrent. Well then, let people enjoy themselves busily. What else is the true goal of the vast increases in prosperity we have created?

Fourth, we may need to redistribute income and wealth on a large scale. Such redistribution could take the form of a basic income for every adult, together with funding for education and training at any stage in a person’s life. In this way, the potential for a more enjoyable life might become a reality. The revenue could come from taxes on bads (pollution, for example) or on rents (including land and, above all, intellectual property). Property rights are a social creation. The idea that a small minority should overwhelmingly benefit from new technologies should be reconsidered. It would be possible, for example, for the state to obtain an automatic share of the income from the intellectual property it protects.

The rise of truly intelligent machines, if it comes, would indeed be a big moment in history. It would change many things, including the global economy. Their potential is clear: they would, in principle, make it possible for human beings to live far better lives. Whether they end up doing so depends on how the gains are produced and distributed.

Leer el resto de esta entrada »

HPC. El impacto de la patente US 8266089: lo que parecía imposible antes, ahora al alcance de la mano, sin esfuerzo.

junio 29, 2015

1. Introducción.

Debido al retraso en la (eterna) tramitación de la segunda solicitud de patente (también la primera fue eterna) que por motivos completamente injustificados (como venimos demostrando en las anteriores entradas) finalmente se ha denegado (aunque como tenemos la razón de nuestra parte, insistiremos), hacía tiempo que no  miraba las publicaciones más actuales sobre el problema al que nuestro método proporciona una solución teórica y práctica general: la determinación de la existencia y búsqueda constructiva de recorridos hamiltonianos en Dígrafos de Cayley bigenerados.

Y con (grata, creo) sorpresa he visto que varios autores (en la entrada publico dos ejemplos, los dos de autores canadienses creo), utilizando técnicas de la patente, están resolviendo problemas que antes de nuestra publicación parecían imposibles.

Todo ésto añade más leña al fuego a mi contencioso con la nueva e infame normativa en EEUU aplicable a patentes (situación post Alice v. CLS Corp; personalmente soy un firme defensor de la propiedad privada; mataría y moriría para defenderla; pero si el Estado de EEUU roba con tanta alegría los resultados de los demás, ¿ no están lanzando un mensaje en pro de la piratería informática ? ¿ si roban tan frivolamente los bienes en EEUU de un indefenso extranjero, al que han atraído con un señuelo legislativo que luego han cambiado con la aplicación retroactiva de una nueva normativa, no están incentivando que se haga los mismo con los bienes de los ciudadanos de EEUU en el extranjero ? ¿ No son éstas las señales que están enviando  ?), con la USPTO que no ha emitido instrucciones claras a los examinadores o no es capaz de imponer disciplina para que éstos las acaten (y diciendo ésto estoy pensando bien, pero mi denegación no dice nada bueno de la actual dirección de la USPTO; si se han enterado, y la han permitido malo; si no se han enterado peor), y sobre todo con el examinador que ha resuelto mi expediente (y sigo pensando bien). Lo que a mi me deniega éste, sin ninguna justificación, sin ningún argumento de peso, de manera completamente ilegítima, argumentando que son vaporosas ideas abstractas que se agotan en si mismas, sin ninguna consecuencia práctica, lo están utilizando destacados académicos e investigadores para obtener importantes resultados (por ejemplo de inexistencia) que ahorrarán tiempo y energía a futuros investigadores y a la industria.  

2. Los dos ejemplos:

Antes contestamos a una pregunta que seguramente se harán los lectores. ¿ Que demuestran estos  dos resultados ? Que pasos aislados de mi algoritmo son de utilidad para éste problema (que como vamos a ver tiene importantes aplicaciones industriales), por si solos, sin combinarlos con los demás y por lo tanto que tiene todo el sentido su inclusión en una solicitud de patente como reclamación independiente y que por ello, de acuerdo con la legislación vigente (incluso en un contexto post Alice Corp v. CLS Bank) ésta solicitud se debería de haber concedido. La no concesión ha sido completamente ilegitima.

Añadido 1, 30 de junio 2015. Está muy claro en que consisten algunos de estos pasos para los que estoy pidiendo protección en la segunda solicitud de patente y yo no veo abstracción por ninguna parte:

–son partes (digamos subdigrafos). Nótese que éstas partes están perfectamente definidas, son tan concretas que se le puede dar instrucciones a un computador para que las maneje). Nótese que hay muchos otras partes de éstos mismos dígrafos, para las cuales no pedimos protección, pues son irrelevantes para el problema que nos interesa. s

–de una clase muy concreta de dígrafos. Hay muchas otras clases de dígrafos, incluso algunas bastante relacionadas y en las cuales se pueden definir los mismas partes, para las que no pedimos protección. 

–dígrafos que se utilizan para modelar determinadas aplicaciones industriales que se pueden incluir en el término redes. Hablamos de redes técnicas, redes dónde haya una participación de máquinas, de aparatos. 

–estas partes muy concretas de una clase muy concreta de dígrafos con unas aplicaciones muy concretas en el campo de las redes, pueden ser un IAS regular (claim 1 de la segunda solicitud de patente), uno o varios IASes del entorno de la identidad con disposición lisa o smooth (claim 3 de la segunda solicitud de patente), que pueden ser dos IASes regulares entrelazados (claim 4 de la segunda solicitud de patente), pueden ser dos o varios IASes regulares con entrelazamiento de ciclos (claim 5). Nótese que las claims 2 y 6 son algo diferentes, pues son más procedimentales que estructurales, no se refieren a partes sino a cosas que se hacen con esas partes.   

–se usan como piezas de una máquina para resolver un problema muy concreto: el problema de recorridos hamiltonianos. Este uso se puede ser de varias formas: bien para tomar varias decisiones sobre como resolver un problema muy concreto como es el (en cuyo caso se hace un uso de ellos como tests), bien directamente como piezas para resolver éste mismo problema. En esta entrada hemos mostrado a dos investigadores que han utilizado a algunas de ellas.  Nótese que muy posiblemente estas partes se puedan utilizar para resolver otros problemas (por ejemplo, sin duda ninguna, y nosotros ya lo hemos utilizado para ello, para resolver el problema de isomorfismo, también para resolver el problema del camino más corto etc…) en esta misma clase de dígrafos, pero no estamos reclamando su protección para ello. Nos estamos refiriendo a un problema muy concreto.    

En definitiva, estamos definiendo muy concretamente la materia prima (las partes de los dígrafos), estamos definiendo muy concretamente sus usos (como tests, como componentes, para resolver un problema muy concreto) y estamos definiendo  muy concretamente su campo de aplicaciones industriales (redes). ¿ Se puede ser más concreto ?

Quiero recordar que este problema (recorridos hamiltonianos) en éstos dígrafos (de Cayley; hay otros nombres) se llevan estudiando décadas, por  destacados investigadores (del campo de la matemática aplicada, pero sobre todo del campo de la ingeniería de redes) y nadie había detectado que éstas partes se podían utilizar de ésta manera para resolver éste problema. Estaban allí y nadie las había visto: por lo tanto hay novedad, no hay obviedad y hay inventiva, hay invención genuina.

También hay que recordar que no hablamos de objetos puramente matemáticos, abstractos: si los estudian ingenieros de redes, es por que es un objeto con importantes aplicaciones industriales. Ni siquiera  hablamos de meras propuestas técnicas, de prototipos: hablamos de objetos que se utilizan en sistemas reales comerciales.   

Finalmente, como ponen de manifiesto estos dos artículos, creo que está claro que antes de la existencia de estas técnicas que hemos inventado nosotros estos problemas eran prácticamente imposibles de resolver. Ahora, usándolas, los investigadores pueden resolver el problema para casos antes inaccesibles. Por lo tanto el uso de estas técnicas supone una mejora clara sobre el estado del arte.     

Todo esto se le ha explicado muy claramente al examinador en varias ocasiones, en conversación teléfonica y por escrito.  

¿ Cual es el motivo de que se siga calificando a ésta concreta invención genuina que tiene importantes y reales (actuales) aplicaciones industriales, y para las cuales su nueva existencia supone un espectacular avance con respecto al anterior estado del arte,  de idea abstracta, actuando así en contra del muy claro Artículo I, Sección 8 de la Constitución de EEUU, que dice:

To promote the progress of science and useful arts, by securing for limited times to authors and inventors the exclusive right to their respective writings and discoveries 

?.

¿ Por qué éste modesto inventor (aunque no sea ciudadano norte américano) no tiene derecho a aquello que tan claramente establece la Constitución de éste país ?

¿ Por que no tiene derecho éste modesto inventor a beneficiarse de los frutos de su trabajo, que tanta inversión y sacrificio le han costado conseguir ?

Lo desconozco. En anteriores entradas ya hemos avanzado algunas posibles explicaciones:  

–el examinador, tras casi 8 (hablo de memoria) años no se ha leído en profundidad la invención y está mal juzgando algo que no conoce; por la contestación, toda ella centrada en la primera reclamación o claim, la correspondiente al IAS regular, y que incluye además argumentos genéricos, abstractos, dignos de un equilibrista que sabe que está actuando en la cuerda floja del dogmatismo, y que serían aplicables a cualquier otra solicitud, es decir no específicos para esta invención, me da la impresión de que estamos en éste escenario.  ¡¡ 8 años !!.  

–se lo ha leído y la conoce bien pero está actuando de mala fe haciendo un mal uso de las competencias de servicio público que se le han otorgado. Si estamos en éste escenario, desconozco los motivos (sólo se me ocurre uno que no voy a hacer público). Llevamos casi 8 años de relación, casi siempre a través de agentes y el poco trato directo que hemos tenido (dos o tres video conferencias con presencia de terceras partes, mi agente y su supervisor) ha sido completamente correcto y educado por ambas partes.   

–se lo  ha leído y la conoce bien, pero está siguiendo instrucciones de más arriba, está tele-dirigido, adaptándose a la nueva política del Estado de EEUU con respecto a determinadas invenciones del campo del software.    

Insisto en que todo ésto son hipótesis de trabajo.

Fin de añadido 1.

Añadido 2, 30 de junio de 2015. En el gráfico siguiente indicamos dónde se situarían los resultados de los que hablamos (por el nombre de los aurtores) de cuardo con nuestra teoría (ojo la asignación del resultado de Williams a la región indicada  es clara: a partir de un cierto n no muy grande sus casos son smooth; pero tengo pendiente de leer en detalle el artículo de Witte y por lo tanto la asignación de momento es hipotética). La estructura de la región twisted no está del todo clara todavía. Por ejemplo ¿ hay casos cycle-entangled con un número exponencial de IASes ?. Y hay otros interrogantes.

limite-supuesto-de-la-distribucin-1-7282

He modificado una figura que elaboré hace años, que ya hemos publicado en anteriores ocasiones y que tengo que revisar. Tampoco tengo claro que sea la más adecuada. Muestra, fijando Sn (una cantidad n!) la distribución de casos por grados (de las permutaciones). Si bien los casos de Williams sí generan Sn, no sucede lo  mismo con la familia infinita de Witte,  que muy posiblemente (no lo se todavía) serán de orden menor a n ! (tal y como veremos, incluye como subfamilia a metacíclicos, que son de orden bastante bajo).

Fin de añadido.

a) Primer resultado. 2013. David Witte. 

Título. On Cayley Digraphs That Do Not Have Hamiltonian Paths

Abstract.

We construct an infinite family of connected 2-generated Cayley digraphs that do not have hamiltonian paths, such that the orders of the generators and are unbounded. We also prove that if is any finite group with [[G,G]], then every connected Cayley digraph on has a hamiltonian path (but the conclusion does not always hold when or ). 

Extractos.

La primera familia (cuyo descubrimiento es seguramente anterior a mi resultado, pero se necesitó a todo un Milnor para obtenerlo…).

Proposition 2 (attributed to Milnor [2, p. 201]). Assume the finite group is generated by two elements a and b, such that a^2=b^3=e. If |G|>= 9|ab^2|, then the Cayley digraph does not have a hamiltonian path.

La segunda familia, posterior a mi resultado.

The examples in the above proposition are very constrained, because the order of one generator must be exactly 2 and the order of the other generator must be exactly 3. In this note, we provide an infinite family of examples in which the orders of the generators are not restricted in this way. In fact, and can both be of arbitrarily large order.

Theorem 3. For any n elemento de N, there is a connected Cayley digraph, such that 

(1) The corresponding Cayley Digraph does not have a hamiltonian path,

(2) a and b both have order greater than n. Furthermore, if p is any prime number such p > 3 that and p es congruente con 3 (mod4), then we may construct the example so that the commutator subgroup of G has order p. More precisely, G=Zm*Zp is a semidirect product of two cyclic groups, so is metacyclic.

Remark 4. Here are some related open questions and other comments.

(1)The above results show that connected Cayley digraphs on solvable groups do not always have hamiltonian paths. On the other hand, it is an open question whether connected Cayley digraphs onnilpotent groups always have hamiltonian paths. (See [3] for recent results on the nilpotent case.)

(2)The above results always produce a digraph with an even number of vertices. Do there exist infinitely many connected Cayley digraphs of odd order that do not have hamiltonian paths?

(3)We conjecture that the assumption “p es congruente con 3 (mod 4)” can be eliminated from the statement of Theorem 3. On the other hand, it is necessary to require that p>3 (see Corollary 16).

(4)If is abelian, then it is easy to show that every connected Cayley digraph on has a hamiltonian path. However, some abelian Cayley digraphs do not have a hamiltonian cycle. See Section 5 for more discussion of this.

(5)The proof of Theorem 3 appears in Section 3, after some preliminaries in Section 2.

No recuerdo si reseñamos ya éste artículo en su momento o fue otro del mismo autor, y éste no lo conocía. Como se ha visto, en él que dan dos ejemplos de familias infinitas de Dígrafos de Cayley bigenerados que no tienen caminos hamiltonianos.

El autor utiliza el IAS regular y el resultado de los vértices finales posibles, dos técnicas que nosotros hemos intentado incluir como reclamaciones en la segunda solicitud de patente, pero que el examinador considera que son meras ideas abstractas, que se agotan en si mismas, sin ninguna consecuencia práctica de cara a las aplicaciones. ¿ No es el examinador consciente  del ahorro de trabajo computacional que se obtiene al poder determinar de antemano que un caso no tiene recorridos hamiltonianos ? Lo debería de ser porque se lo hemos intentado explicar por teléfono y en escritos (formales) en varias ocasiones. ¿ Entonces por qué rechaza éstas reclamaciones ? O no se ha enterado o se está haciendo el sueco, y ha denegado con una larga cambiada.

Alguien pensará que el resultado de los vértices finales posibles ya se había publicado, con otro método diferente al mio (más general y mucho más aparatoso cuando se trata de aplicarlo a los casos con IAS regular, de los que  no habla el autor, en mi modesta opinión;  y ojo soy admirador de éste investigador), por otro autor a principios de los 80. Es cierto, y ésto hace aceptable  la publicación de éste autor sin citarme incluso aunque conociese mi resultado, pero resulta que hasta después de mi publicación no lo había utilizado nadie para demostrar éste tipo de resultados. ¿ Por qué ? Resulta que sin mi teoría, y sin las definitivas pruebas que se obtienen al aplicarla a los (brillantes) resultados experimentales obtenidos por otroa autores (Effler y Ruskey) sin los otros pasos de la patente, el resultado de vértices finales posibles no va mucho más allá.

En fin tengo que mirar en detalle éste artículo. A priori interesante aunque conociendo mi método éste tipo de resultados ya no tiene mayor dificultad.  Ya se sabe dónde mirar para encontrar éste tipo de casos.

b) Segundo resultado. 2013. Aaron Williams.

Título.  HAMILTONICITY OF THE CAYLEY DIGRAPH ON THE SYMMETRIC GROUP GENERATED BY σ = (1 2 ··· n) AND τ = (1 2)

Abstract. The symmetric group is generated by σ = (1 2 ··· n) and τ = (1 2). We answer an open problem of Nijenhuis and Wilf by constructing a Hamilton path in the directed Cayley graph for all n, and a Hamilton cycle for odd n.

Aunque todavía lo tengo que leer en detalle, para obtener éste resultado utiliza (conjuntamente con otras técnicas) cuando menos lo que nosotros hemos llamado el IAS regular (él lo llama de otra manera: alternating-cycle) y que hemos intentado proteger en una reclamación de la solicitud, rechazada ya que el examinador de la USPTO considera que éste método, a todas luces práctico y con consecuencias, es una idea abstracta sin mayor incidencia práctica en las aplicaciones. 

Si algún lector considera que las aplicaciones en matemáticas no dejan de ser ideas abstractas hay más. Además de las aplicaciones que éste artículo demuestra, éste tipo de dígrafos y dentro de ellos el enrutamiento mediante recorridos hamiltonianos, tiene importantes aplicaciones industriales. Entran dentro de lo que se llaman Rotator Graphs que se utilizan como  modelos de redes de interconexión, modelos que ha desarrollado un investigador de IBM. ¿ Por qué el examinador no ha querido valorar ésto si en la redacción de  las reclamaciones hacíamos referencia explícita a las redes de interconexión modeladas por Dígrafos de Cayley ? ¿ Se puede ser más concreto ?. Y eso que como estamos viendo en las últimas entradas nuestro método va más allá de los Dígrafos de Cayley. 

El citado no es el único investigador industrial  que ha investigado sobre Grafos de Cayley, ni mucho menos. Podría citar a cientos. Un caso reciente, Alexander Holroyd, de Microsoft research, coautor del autor sobre el que hablamos de un artículo titulado: Efficient generation of hamilton cycles in restricted and generalized Rotator Graphs, es decir una clase de Dígrafos de Cayley.  O podríamos citar a otro ¿ investigador ? de IBM, Ian Shields que ha publicado una destacad tesis sobre el problema (previa a la publicación de nuestro resultado. Y podriamos citar a otros cientos.

Extracto.

3.1. Basic Cycles. We first show that walks associated with σ n and (τσ−1 ) n−1 are (directed) cycles, which we refer to as σ-cycles and alternating-cycles, respectively.

Lemma 1. If p = p1···pn ∈ Pn , then walk(pσ n) and walk(p(τσ−1 ) n−1 ) are cycles.

Luego continua con la demostración. La tengo que leer pero en principio entiendo que está demostrando matemáticamente uno de los pasos de mi método. Seguramente habrá más de ésto en el futuro. Por ejemplo estoy a la  espera de ver al primero que publique, sin citarme, una demostración de la generalización del famoso teorema de Rankin que yo he publicado en mi patente, con demostración completa. Otras demostraciones no las he publicado por no estar relacionadas con métodos constructivos y por lo tanto no  tener sentido en una patente. También estoy a la espera de la publicación del importantísimo test de lisura o smoothness y sus consecuencias de cara a la propiedad de hamiltonicidad.

En nuestra descripción del método incluido en la solicitud ya decíamos que nuestro método se podía utilizar para resolver determinados problemas abiertos en relación a éste problema y entre otros nos referíamos a éste. Aplicando nuestra teoría es fácil ver que a partir de un cierto tamaño, por ser smooth, todos los Dígrafos de Cayley Bigenerados de tipo Sigma Tau tiene recorridos hamiltonianos en todos los vértices finales posibles.  Con nuestro método se pueden construir demanera eficiente todos los recorridos posibles en todos éstos vértices finales posibles (añadido 30 de junio. obviamente teniendo en cuenta el teorema de Rankin para ciclos y caminos cuando éste sea aplicable. fin de añadido).

Éste es el estado del arte hoy, tras la publicación de nuestro resultado, y éste era hace años. Se puede ver también éste otro artículo (en el que atacan  un problema de una clase similar):

Doubly adjacent gray codes for the symmetric group

ABSTRACT Let x 1 x 2…xi xi+1 …xn be a permutation of {1,2,…,n} written in one line notation. An “i-adjacent interchange” applied to this permutation produces the permutation x 1 x 2…xi+1 xi …xn obtained from the first permutation by interchanging the symbols in positions i and i+1. We denote such an interchange by (i,i+1), where i=1,…,n−1. The permutation x 1 x 2…xi+1 xi …xn results from x 1 x 2…xi xi+1 …xn by right multiplication by the transposition (i,i+1) in the symmetric group Sn . Two adjacent transpositions (i,i+1) and (j,j+1) are themselves adjacent if either i=j+1 or j=i+1. In this paper, we show that that for every n≥3, there is an n long sequence (f(1),f(1)+1),…,(f(n!),f(n!)+1) of adjacent transpositions, each except the first adjacent to its predecessor, the first adjacent to the last, and such that the set of products of transpositions {πt:πt=(f(1),f(1)+1)…(f(t),f(t)+1)t=1,…,n!} is Sn , with the final product πn equal to the identity. We call such a sequence of transpositions a doubly adjacent Gray code for the symmetric group Sn . We give a procedure for constructing such a Gray code. The existence of such a code (Theorem 6.2) seems to be a very nontrivial problem. As a consequence of the existence of this code we resolve an open problem in the theory of Cayley graphs of the symmetric group by showing that the Cayley graph of Sn with generators {(l,2),(l,…,n),(n,…,l)} has a Hamiltonian cyclen≥3 (Corollary 6.5). Our procedure shows how to braid n strands.

50  páginas de demostración para obtener lo que con nuestro método se puede obtener dándole a una tecla.

2. No se que pensar de todo ésto.

Aunque por determinados motivos que no vamos a detallar nos sorprendería que fuese así, no tenemos pruebas de que ninguno de éstos dos autores conozcan nuestro resultado y por ello dejamos el tema aquí.

Pero queremos pensar que la ética académica obliga a todo académico, sea del país que sea, a informarse primero de todo lo publicado en su campo y reseñarlo si tiene conocimiento, independientemente de quién y cómo se haya publicado.  ¿ Somos científicos o sólo un grupo de vanidosos y elitistas amiguetes ?. ¿ Somos civilizados o preferimos que el sector de conocimiento, la academia global que está emergiendo sea una jungla ?

No es complicado llegar al texto de  mi patente: aparece en cualquier búsqueda Google y está en inglés. Yo me la encuentro continuamente cuando busco sobre éstos temas. Por mi parte puedo admitir que haya partes no del todo claras y quedo a la disposición de cualquier autor para aclarar dudas.

De cualquier manera, sin acritud (tampoco es ésta mi guerra), les felicitamos por sus resultados. Nos alegra ver que hay avances en éste difícil campo.

Euro en crisis: ¿Argentina, noviembre 2001 = Grecia, noviembre de 2011 ?

junio 29, 2015

Presentación actual. Interrumpimos brevemente la serie de entradas técnicas relacionadas con la patente US 8266089 con ésta entrada de corte más de acutalidad política, que es una republicación de una entrada anterior de 2011. La republico tal cual, sin releerla, y no se si hoy estoy de acuerdo con todo lo que escribí  en ese momento. Ésta fue una primera de una serie de entradas sobre la temática de la crisis del Euro e incluso abrimos una categoría.  Los interesados pueden consultarlas pulsando sobre la categoría.

Creo recordar que ese año fue el más crítico para España en los mercados financieros de deuda y por eso la escribí (a petición de terceras partes). Afortunadamente hoy no estamos en las portadas todos los días por éste motivo. Pero lamentablemente el tema ha vuelto  a ser de actualidad. Esperemos que ahora también se resuelva la crisis de manera favorable. Por otra parte en breve nos toca decidir en España y la experiencia en otros países igual nos hace ser más responsables.

Como en ésta entrada se habla de Argentina, quiero comentar una cuestión sobre la que he tenido noticia recientemente, relacionado con la temática del blog y que me sorprendió: al día de hoy, 2015, todavía hay un control de cambios muy estricto en Argentina. Si quieres sacar tus ahorros de toda la vida, sudor y sangre

Fin de presentación.

Aunque este no es un blog de política o economía general, ni lo va a ser en un futuro, hoy he recibido una llamada de una persona muy cercana preocupada por sus ahorros y pidiendo consejo. La persona lo suficientemente cercana que no puedo sino intentar aconsejarla bien.

Su problema es el siguiente: es una persona no española, residente en España, nacional de uno de los supuestos países fuertes de la UE (por eso tiene varias cuentas), y  tiene entre 30000 y 100000 euros ahorrados, la mayoria depósitados en una cuenta en euros de un banco español y el resto depositados en una cuenta en euros de un banco extranjero en otro país zona euro.

Me pregunta: ¿ Que hago ? ¿ No hago nada o invierto la posición transfiriendo la mayoría de mis ahorros a la cuenta / banco extanjero y dejando sólo parte en la cuenta / banco nacional ? Me ha citado el caso de Argentina, dónde mucha gente perdió los ahorros de toda una vida (esto cómo veremos es un más un mito que una realidad)  o la posibilidad de que la salida de Grecia del euro provoque su posterior default y esto pueda causar un crash bancario por la exposición de todo el sistema bancario europeo a la deuda griega.

La persona podría haber sido española y tener otra cuenta bien en otro país zona UE, bien en otro bloque económico y hacerse la misma pregunta. Y hay otras personas  en otras situaciones parecidas. Por todo ello vamos a tratar el tema de la manera más abstracta posible, aunque la casuistica concreta de cada caso es importante.

Mucha gente no tiene ahorros y por lo tanto no tienen este problema. Muchos otros tienen ahorros pero no tienen la posibilidad a corto plazo de abrir una cuenta en el extranjero (no es tan fácil hacerlo a corto plazo; por ejemplo en UK; tengo previsto ampliar información sobre este tema: he consultado con un banco con presencia nacional y aunque no me han dado  información completa confirmo que la apertura de una cuenta en el exterior no es tan sencilla) y por lo tanto tampoco tienen este problema. Finalmente muchos otros se encuentran en la posición de esta persona. Pero pienso que el post puede tener interés para todos ellos.

Antes de contestar, aclarar un interrogante, que sin duda se ha planteado algún lector del post ¿ porque debería esta persona pedirme consejo a mi en estos temas ?  El principal motivo en mi opinión es que no se dispone de  fuentes de información fiables. Hay otros vinculados a mis actividades profesionales pero no creo que sean relevante detallarlos.

Una cosa está clara: estamos en una situación en la que, presuntamente,  por el bien de todos, nadie dice toda la verdad. Los bancos son fuente de información interesada y posiblemente no van a aconsejar correctamente. Las autoridades públicas están tan enrocadas en la defensa del euro que no están haciendo lo que deberian: informar de escenarios posibles (incluso de los  poco probables), de que plan de acción tienen preparado en cada caso (si es que tienen alguno: ya hemos visto que no había plan para el pinchazo de la burbuja del año 2007/2008 y este era más o menos previsible y a medida que estoy leyendo, me temo que tampoco hay planes para un colapso de la zona euro. Actualización 6 de noviembre 2011: totalmente confirmado, no hay planes) y de cuales son las mejores acciones que puede realizar cada particular en función de sus posibilidades. El mejor remedio contra el pánico (y por supuesto no estamos en eso) es la información. Fin actualización.

Cómo no he estado siguiendo los acontecimientos de cerca la he pedido un par de días para documentarme. De paso aprovecho y  me entero en detalle de la situación: hasta esta llamada realmente no me había ni preocupado ni ocupado mucho de las turbulencias financieras. Una vez documentado y listo para contestar (cosa que hago en este post, por supuesto con permiso de la persona que me consultó), antes de aconsejar creo que es honesto explicitar mi posición sobre la UE, el euro y su posible futuro, pues puede determinar el consejo.

A) Mi posición sobre el futuro de la UE y el euro (si no te interesa mi posición, tu te lo pierdes, puedes saltar al punto B, Argentina noviembre 2001):

Con una cierta perspectiva, al margen de las turbulencias actuales, mi posición con respecto a la UE y el Euro se resume en dos proposiciones y una conclusión:

–primera proposición, en el contexto mundial actual y de cualquier futuro previsible, la formación de uniones político-económicas de tamaño superior a los estados-nación europeos (incluido el más grande Alemania) no es una opción, es una necesidad. En ciencias sociales las necesidades son obligaciones, algo que debemos hacer sí o sí.

–segunda proposición, las uniones político-económicas multiculturales no funcionan, es decir uniones político económicas sin unificación de todos los sistemas de convenciones (lengua, moneda, reglas de tráfico de vehículos etc…) se acaban desitengrando. En la UE hemos tenido unión monetaria, pero no linguistica y ya se sabe: si en una unión económica todos los factores no se pueden mover fácilmente (aunque no sea por motivos legales) el mecanismo de mercado no puede funcionar correctamente.

–conclusión: UE sí, pero así no. Esto ya lo comenté en su momento un foro de Linkedin.

Es decir no creo en el futuro de la UE y del Euro tal y cómo están diseñados actualmente. Por supuesto  es una opinión personal, pero documentada y meditada, no una ocurrencia. Entonces la UE y sus países miembros, sigo opinando, tienen tres opciones:

1) seguir cómo estamos, dándo bandazos, capeando el temporal, gastando dinero público en parchear a la UE, sin cambios y perdiendo la UE posiciones económico-políticas a nível internacional poco a poco,

2) disolución total, programada o natural (y por lo tanto posiblemente catastrófica), con efecto dominó: primero Grecia, etc…y posterior situación de fraccionamiento. Si sucede ésto entiendo que refundar la UE de nuevo, de la misma o de otra manera, será complicado aunque no imposible.

3) refundación de la  UE desde la posición actual, con un programa de unificación total con el  objetivo de conseguir una especie de EEUU de Europa.

No soy optimista sobre esto. En los escenarios dos y tres, una refundación con el objetivo de crear una verdadera unión político económica no va a ser fácil, se mire por dónde se mire ya que implica necesariamente  grandes cambios políticos y esfuerzos por parte de todos: por ejemplo armonización de los sistemas políticos y por lo tanto eliminación de los regímenes monárquicos, primer y principal obstáculo a la unión política en Europa; unificación de sistemas de convenciones (sobre todo lenguas) segundo obstáculo a la unión política y primer y principal obstáculo a una unidad de mercado (unidad económica dónde el mecanismo de mercado funcione correctamente).

En esto no podemos esperar gran cosa de los partidos políticos, y no porque sean mejores o peores. Actualmente,  son maquinarias que piensan en modo nacional (lógico, están adaptadas a sistemas políticos nacionales) y cuando llegan al poder no pueden hacer nada que no hayan prometido antes: esto sería ilegítimo, estaría en contra del mandato que han recibido de sus electores. Tampoco podemos esperar nada de las autoridades comunitarias. Por mucho que se diga, la UE no es más que una organización intergubernamental y las instituciones comunitarias no son más que la administración o burocracia de esta organización intergubernamental. Su iniciativa política es mínima.

La barrera de la lengua única parece la más complicada. Esto se lo he planteado a mucha gente de mi  entorno. Todo el mundo responde lo mismo: preferirian una lengua única y no votarían necesariamente por su propia lengua en un eventual referendum paneuropeo sobre este tema. Pero por otra parte  la posibilidad de una lengua única en Europa, les parece algo cómo de Marte,  imposible.  Sorprendente.

Conclusión:

En conclusión parece que estamos en caso de equilibrio insatisfactorio acompañado de fuerzas, quizás no deseadas por nadie, pero  que están ahí e implican inmovilismo. Pero los mercados ya han detectado que el sistema actual de la UE está mal diseñado, tiene puntos débiles y no creo que cese el temporal hasta que la UE reaccione de manera adecuada, dándo señales de que hay voluntad política real de refundación.

La deuda de algunos países de la zona euro es sólo la superficie del problema y los compromisos políticos (de determinados países con el euro)  tienen un límite: a largo plazo se acabará implantando el escenario más eficiente desde el punto de vista económico.

Pero a  corto y medio plazo, aunque el refrán dice: “quien no conoce su historia está condenado a repetir sus errores”, en realidad sucede lo contrario: a la historia no le gusta repetirse y por lo tanto estamos condenados a equivocarnos. La prueba de esto es que debido a la decidida apuesta de los políticos europeos, en base a nuestro mandato, por el escenario 1, sin considerar el escenario 3, vamos a obtener el escenario 2.

Pero nos estamos desviando del tema.

B) Argentina, noviembre de 2001:

La mejor manera de comprender el caso argentino es siguiendo su cronología. Esto nos puede ayudar a ver los paralelismo con el caso europeo:

1991 Ley de Convertibilidad: se establece un régimen de convertibilidad tipo de cambio fijo peso / dólar; respaldo en reservas de la moneda en circulación. Esto es equivalente (simplificando mucho) a la creación del euro.

1998: Comienza la recesión. Equivalente al shock de 2007/ 2008 en todo el mundo especialmente en determinados paises de la UE.

Fin 1999-principios de 2001 crisis prolongada: tras una crisis económica que dura ya tres años, con una elevada deuda pública y cada vez mayor contracción económica, con cambios continuos en ministerio economia (Machinea, López Murphy, Cavallo), llega un momento en que la gente anticipa crash y devaluación, y empieza la fuga de capitales.

Ahora estamos en esta situación en la UE, al crecer la incertidumbre sobre el euro. Imagino que de momento, si hay fuga de capitales, es sólo de algunos grandes ahorristas, que pueden permitirse el lujo de  diversificar riesgos.

2001: corrida bancaria (retirada de dinero de los bancos) y fuga de capitales masiva: Argentina mantiene el régimen de convertibilidad. Entre julio y Noviembre 2001 los argentinos han retirado 15 billones de usd de los bancos y han aumentado de manera preocupante los cambios de pesos a dólares y la transferecnia de dólares a cuentas extranjeras,  usando medios más o menos picarescos. En total se movilizaron al exterior 16 billones de usd.

Sobre cifras de retirada del dinero de los bancos y picaresca en la fuga de capitales pinchar en este enlace.

Sobre la cifra del alcance de la fuga de capitales ver en este documento, la página 15.

2 de Diciembre de 2001. Gobierno De la Rua /Cavallo: corralito, cacerolazo y corralón: para evitar la  fuga de capitales el gobierno congela las cuentas bancarias (solo se autorizan pequeñas salidas semanales). No se autorizan sacar dinero de las cuentas en dólares. Resultado, malestar social y revueltas más o menos pacíficas (hubo saqueos de supermercados e incluso muertos).

23 de Diciembre 2002. Gobierno De Saa: default, de 132 billones de dolares.

6 de enero  2002. Gobierno Duhalde: fin convertibilidad o dolarización/pesificación: Duhalde, presidente interino, deroga la ley de convertibilidad, se mantiene el corralito, se pesifica la economía (hay un debate entre economistas sobre si hubiese sido mejor optar por la otra posibilidad, la dolarización) y establece un doble rasero sobre el tipo de cambio: tipo de cambio oficial que pasa de 1 a 1 a 1 usd 1,4 pesos para determinadas transacciones (por ejemplo pesificación de todos los depósitos en USD) y de libre flotación para otras transacciones (de acuerdo con esto el peso se devalua hasta un máximo de 1 usd = 4 pesos estabilizandose en 1 a 3; la  inflacción se dispara (35%), al igual que el desempleo (20% población activa). Lo que causó perdidas de ahorros fúe por un lado este doble rasero, y por otro lado la inflación (ampliamos esto  en un punto posterior). Cómo veremos el doble rasero enfureció a la mayoría de los ahorristas y se hizo un llamamiento por muchos ciudadanos para declarar su inconstitucionalidad. Finalmente el volumen de pesos no era suficiente para permitir que se realizasen todas las transacciones que la gente quería realizar y aparecen multiples mecanismos de pagos supletorios.

2004. Saneamiento. Tras la pesificación la economia Argentina quedó saneada. Esto no significa que esta sea necesariamente la buena solución para Grecia. La recuperación de Argentina y su mantenimiento posiblemente tiene mucho que ver  con el alza de los precios de las materias primas.

Perdida de ahorros en el caso argentino:

Una de las fuentes de perdida de ahorros fueron las medidas de pesificación obligada a un tipo de cambio fijo oficial (1 usd = 1,4 pesos) para las unidades monetarias depositadas en cuentas en dólares mientras que para el resto había un tipo flotante de 1 usd  = 4 pesos.

Es decir, cualquier argentino que consiguiese sacar y mantener en su casa, o transferir a una cuenta extranjera y luego traerlos por otro medio, por ejemplo 1000 dólares, antes de la secuencia corralito / pesificación en diciembre enero de 2001, acabaron con 4000 pesos, pero los que, debido al corralito, tuvieron que mantener el dinero en el banco y fueron sometidos al procedimiento de pesificación, acabaron con 1400 pesos. Es decir perdieron en torno al 65% de sus ahorros. Este 65% de perdida la tuvo necesariamente que ganar alguien: entiendo que fúe el gobierno argentino que obtuvo reservas de dolares a un precio ventajoso. ¿ Y que pasó con estos duros a cuatro pesetas (dólares a tipo de cambio tan ventajoso) que consiguió el gobierno argentino ? No lo sé, imagino que los utilizaron para pagar deuda externa.

En cualquier caso, tras tiempos duros, la historia tuvo un final feliz.

La segunda causa de perdida de ahorros fue la inflación. Tras la devaluación la inflación se disparó y  la economía se contrajo un 11% más. Si con 1000 pesos del año 2000, equivalentes a 1000 dolares americanos del  mismo año, se podía comprar una cantidad de bienes, de la noche a la mañana, con la misma cantidad de pesos se podía comprar muchos menos bienes. Esto al menos afectaba a todos por igual. Imagino que la pobreza cuando es el resultado de una injusticia duele más.

Obviamente todo lo anterior está demasiado simplificado. Para más detalles sobre quien ganó y quien perdió pincha aquí.

Crisis argentina: un balance.

Sobre el crisis argentina, sobre sus causas, sobre su gestión etc…se escribió mucho durante los años siguientes (2002, 2003, 2004) y no parece haber un consenso definitivo (es decir en este caso, a la economía cómo ciencia no le ha sido fácil ni siquiera hacer un  análisis ex-post): el sistema de convertibilidad no estaba bien diseñado y aunque resistió algunos shocks en la década de los 90, cuando se dió la conjunción persistente de una deuda externa galopante y unos tipos de cambio fijos (con respecto al dólar usa) y desfavorables para el sector exterior (peor caso para el sistema de convertibilidad establecido, caso que nadie esperaba ver realizado o de ser realizado, tan duradero), y unos precios relativos o productividades de los factores que no fueron capaces de ajustarse con rapidez, el sistema colapsó.

Algunas fuentes:

Una cronología mucho más detallada y completa.

Un buen resumen sobre esta crisis.

Sobre las imperfecciones del sistema de convertibilidad argentino por dos defensores de un sistema de convertibilidad más puro.

Uno de los mejores análisis que he visto sobre la crisis Argentina es este, escrito por dos profesores de Harvard, latinoamericanos (Venezuela  y Chile), que posteriormente han ocupado relevantes  cargos públicos en sus respectivos países.

Un punto  de vista europeo.

Un punto de vista del Banco Mundial.

Un punto de vista de un una institución de EEUU.

C) Europa noviembre de 2011,

Argentina y Europa:

En el punto anterior hemos resumido el caso argentino analizando los paralelismos con el caso europeo. ¿ Nos espera el mismo desenlace ? Ya hemos dicho que a la historia no le gusta repetirse.

Si nos ceñimos a los datos, la situación de deuda de algunos países es incluso peor que la de Argentina de entonces: su deuda suponía un 50% con respecto al PIB, mientras que algunos países de la UE están en torno al 150% (Grecia, 340000 millones de euros, entre el doble y el triple que la que tuvo argentina en su momento).

la magnitud de la deuda es un dato. La posibilidad de generar ingresos para poder pagarla es otro. En general la economía de los países europeos está más diversificada, más integrada con el exterior (sobre todo con otros  países de la zona euro) y por lo tanto se espera que su posición con respecto al pago de la deuda sea mejor que la de Argentina de entonces. Pero sólo se pueden pagar las deudas en un contexto de crecimiento y cómo hemos visto en el punto A opinamos que las perspectivas no son muy positivas, para toda europa.

Dónde parecen estar peor algunos países europeos, en comparación con la Argentina de entonces en en la ejecución de los ajustes de gasto público necesarios. Los países mediterráneos (especialmente Grecia e Italia) tienen economias muy dependientes del sector público (por ejemplo en Grecia el sector público supone un 7% del PIB, cuando la  media europea es del 3%)  y  un modelo de funcionariado elitista con salarios muy elevados (el coste anual medio por empleado público en grecia, teniendo en cuenta salario y otros costes es de 60.000 euros, costes que ahora estamos pagando con prestamos en parte el resto de miembros de la UE. En España está cercano a 40.000 euros. Italia en esto está entre España y Grecia). No va a ser fácil socialmente retocar esto, aunque sea necesario. Las turbulencias políticas en Grecia así lo indican.

Sobre la crisis griega hay opiniones de todos los gustos:

Ver por ejemplo este enlace o este otro,  o un buen artículo de wikipedia en Francés.

E incluso sesudos estudios cómo el informe ING titulado “EMU break-up: quantifying the unthinkable” de julio 2010 o el informe UBS titulado “Euro Break-up: the consequences” de septiembre de 2011.

Los informes ING y UBS:

En lo que sigue nos vamos a basar sobre todo en los estudios citados anteriormente  de ING y de UBS (¡¡cuidado!!: el informe proviene de dos  bancos, a los que no les interesa el default griego, y por lo tanto podría estar sesgado a favor del catastrofismo en caso de que  desaparezca el  euro) que tratan sobre las consecuencias económicas de un colapso de la zona euro (es decir en el caso de realización escenario 1 del punto A)).

Aunque el informe de ING es de Julio de 2010 es perfectamente extrapolable a noviembre 2011. Esto último ya es un dato muy relevante: llevamos un año y la situación sigue igual o peor. Contemplan dos casos extremos: el más benigno, salida de Grecia, y el peor caso desintegración total de la zona Euro.

Para cada caso analizan los efectos sobre la economía real, el sector financiero, los tipos de interés en mercados monetarios, de bonos del estado, los tipos de cambio, bonos de empresas, acciones y activos inmobiliarios.

El informe UBS es más reciente. Revisan secuencialmente los aspectos legales y consecuencias económicas de la salida de un país debil y fuerte. La senda previsible para un país débil sería muy parecida a la seguida por Argentina: país deja la zona euro, conversión de todas las deudas en  Euros en moneda nacional (esto es equivalente a un default para los prestamistas), devaluación brutal (60%), corrida bancaria, colapso sistema financiero y recapitalización, el país debe de dejar también la UE y por lo tanto establecimiento de aranceles brutales por la UE, equivalentes a la devaluación; quiebras masivas de empresas etc….La senda para un país fuerte es la inversa en algunos aspectos. Estudian, en base a precedentes de rupturas de uniones monetarias con papel moneda (USA en 1932-33, URSS, Checoeslovaquia) también las consecuencias políticas: en las zonas débiles, dictadura o guerra civil.

Estiman que la retirada de un país débil podría suponer una reducción del PIB de este país el 50% el primer año (11000 euros por persona). Para una economía fuerte 25% reducción en el PIB (unos 6000 / 8000 euros por persona). Cómo solución al nudo gordiano en que se encuentra la zona euro proponen a corto plazo una solución similar a la que finalmente se ha adoptado (default del 50% de deudas Griega, Irlandesa y Portuguesa, repartiendo sus costes por toda la UE)  y a largo plazo dar un paso hacía delante y crear una unión fiscal.

Para sustentar esta recomendación se basan en los casos de la unión monetaria de USA en los 30, UK y Alemania. No vale la comparación pues eran uniones unilinguisticas. Son suizos, país multicultural que vive bien gracias a su posición geográfica (está entre tres economias grandes a nivel europeo y fuertes) y a su status  de casi – paraíso fiscal: no pueden ser conscientes de la importancia del problema de las lenguas.  En general este informe de UBS me parece bastante flojo. Hace un análisis muy ligero de un tema serio.

Finalmente se plantean cómo sacar ventaja, cómo inversor, de una potencial ruptura, comprando activos en la zona euro. Su recomendación es, dado el caso,  no comprar ningún activo zona euro.

En cualquier caso la conclusión de ambos informes es clara: es más caro para todas las partes romper la baraja (escenario 2 del punto A de este post) que seguir cómo estamos (escenario 1). De acuerdo, ¿ pero esto es progresar? ¿ es ir a mejor ? ¿es mensaje que pueda motivar a cualquiera ?.

Enlaces a los estudios ING y UBS:

INGUBS, y un tercer informe de un académico USA sobre el mismo tema.

Una encuesta reciente a 22 economistas sobre esto (17 consideran que la zona euro seguirá con todos sus miembros pero que Grecia hará default):

Entonces, ¿ que debe de hacer esta persona con sus ahorros ?

Primero, señalar que el movimiento de dinero de una plaza a otra, bien dentro de la zona euro, bien desde la zona euro a otras zonas económicas es, de momento,  legal y   es legítimo (cualquiera que tenga ahorros ganados legalmente, puede hacer con ellos lo que le venga en gana, ¡ faltaría más !).

Segundo, tal y cómo está la situación económica en todo el mundo, no tendría mucho sentido una recomendación directa. En vez de eso vamos a proponer un esquema de análisis de la situación para que esta persona pueda recopilar la información relevante y unas recomendaciones más generales para que pueda tomar una decisión racional en cualquier momento.

Asumimos, cómo es el caso, que la persona es particular (no persona jurídica), no experta en temas financieros y quiere perder el menor tema posible en este tipo de decisiones y/o gestiones sobre ahorros. También, para simplificar, asumimos que la cuenta en un bloque diferente a la UE se abre en la divisa propia de ese bloque y que los ahorros se mantienen en la  cuenta corriente y no se invierte en renta fija o variable.

La casuística relevante depende básicamente tanto de las zonas o bloques económicos dónde se tengan las cuentas corrientes cómo de los bancos dónde se hayan abierto estas cuentas  (de su exposición a la deuda griega, italiana; de su exposición a activos tóxicos etc…). Es decir en la situación actual  existe tanto un riesgo país cómo un riesgo banco y la casuística relevante se puede resumir en el siguiente caso tipo (entre corchetes y en negritas las asignaciones posibles a las variables aréa económica / tipo de banco):

Caso: nacional de país de zona periférica en aréa euro (Grecia, Italia…) con ahorros en cuenta corriente banco nacional [expuesto/no expuesto] y cuenta en zona [fuerte (Alemania…)  del aréa euro / otro bloque económico] en banco  extranjero (expuesto / no expuesto).

Pregunta: ¿ que distribución de ahorros en las diferentes cuentas de que dispone, asegura al nacional del país en zona periférica la menor perdida de valor de sus ahorros en la situación actual  y siguientes periodos económicos (digamos en un horizonte de 3-5 años) ?

¿ Por qué un horizonte de tres a cinco años ? Si la zona euro se disolviese hoy mismo, posiblemente España no se recuperaría hasta el final de ese plazo, y por lo tanto podría ser conveniente mantener parte de la cuenta y ahorros en el exterior.

Fuentes de información y parámetros de evaluación:

La fuente más directa para analizar los riesgos de inversiones (y depositar unos ahorros en cualquier páis, incluido el propio, y en un banco se puede considerar una inversión son las tan denostadas agencias de rating  (ver también).

Las agencias de rating hacen exactamente lo mismo que vamos a hacer a continuación (asignar calificaciones de riesgos a agentes económicos emisores de instrumentos de deuda), pero de manera profesional y con métodos contrastados. Cualquiera que tenga cuentas corrientes con ahorros importantes debe de hacer un seguimiento periódico de las calificaciones de países y bancos dónde ha situado su dinero. Conviene ver las calificaciones de los agentes que nos interesan en varias agencias. Tienen un problema serio: sus modelos sólo detectan tendencias de corto plazo y su falta de transparencia. Para calificar utilizan modelos econométricos privados no publicados.

La alternativa a las agencias de rating es analizar uno mismo las diferentes alternativas, utilizando variables e indicadores de economía real, financiera o  de otro tipo, generales o más específicos. Ejemplos: PIB, estructura económica es decir distribución del PIB por sectores, dinamismo de los sectores, déficit y deuda pública, tipo de cambio, tipo de interés, tasa de inflación, tasa de desempleo, tasa de inversión en I+D, patentes activas etc…

En mi opinión los datos sobre economía real y dinamismo de sectores son más informativos (permiten predecir mejor) que los datos puramente financieros. Hay datos no económicos que dicen mucho. Por ejemplo variables cualitativas políticas (libertades políticas, democracia, Estado de derecho, derechos de propiedad, unidad de sistemas de convención cómo lenguas en uniones económicas) o sociales (los flujos migratorios) pueden ser muy informativos.

Algunos indicadores financieros útiles para el largo plazo son los tipos en mercados de futuros de bonos:  (en este artículo vemos que las noticias no son muy alentadoras incluso para Alemania).

En general, cuanto más grande (ya hemos visto que los países que han sufrido más en esta crisis son los más pequeños: Islandia, Irlanda, Grecia, Portugal), diversificada (actividades en muchos sectores diferentes no relacionados), avanzada (dominante desde el punto de vista tecnológico), equilibrada (en cuanto a situación financiera interna y exterior) y dinámica (sectores con perspectivas de crecimiento a largo plazo).

Para que se entienda esto: Alemania es grande (para los estándares europeos y mediana o pequeña a nivel global), diversificada, cada vez menos avanzada y dinámica (pero con mejor situación y perspectivas que el resto de países europeos) y está equilibrada y por lo tanto es el país europeo más sólido.  Rusia es grande (para los estándares europeos), está equilibrada pero no está ni diversificada ni es avanzada. EEUU es grande o mediana para estándares globales, está diversificada, avanzada, muy dinámica y algo desequilibrada últimamente (deuda publica 100% PIB).

En base a todos estos datos se puede determinar los riesgos de agentes emisores de títulos de deuda cómo países, bancos o de otro tipo. No se debe olvidar que  una cuenta corriente es un título de deuda.

Riego país: ¿ cuales serían los efectos del  colpaso de la zona euro en los diferentes países europeos ? Para determinar esto vamos a utilizar el estudio ING. Cómo hemos dicho, es posible esté sesgado (vamos a situarnos en el peor caso analizado en este estudio: el colapso de toda la zona euro), pero aunque debido a estos sesgos puedan variar las cifras estimadas, el esquema de análisis es válido: si colapsa una unión económica con asimetrias nacionales en cuanto a fortaleza de sus respectivas economias y por lo tanto monedas, la zonas débiles tendrán devaluación e inflación y las zonas fuertes reevaluación de la moneda y deflación.

Cómo asumimos el estudio del ING está sesgado podemos considerar que sus cifras son extremas y esto nos dá una cota inferior en los parámetros relevantes (variables económicas que pueden alterar el valor de los activos monetarios o dinero, a lo largo del tiempo, cómo el tipo de cambio, tipo de interés, la tasa de inflación, …). Cómo cota superior podemos tomar la situación actual: es decir podemos considerar que tras la disolución del euro no cambian nada o mucho  los parámetros relevantes.  Los parámetros relevantes de  cada país de europa, tras la virtual disolución del euro, se situarian por lo tanto dentro de esta banda en función de su relativa debilidad o fortaleza.

Parece que Grecia estaría en el extremo inferior y Alemania en el superior (aunque es la economía de mayor tamaño de Europa, a largo plazo personalmente  no me convence la economía alemana: basada en PYMES familiares, operando en  industrias maduras, muy dependientes de los hidrocarburos cómo química o  automóvil; pero en el horizonte de cinco años que nos hemos marcado acepto que estaría en la banda superior).

En cuanto a otras zonas económicas podemos considerar EEUU, paises europeos que  ahora no están en la zona euro (UK, Suiza y otros), países asiáticos con econnomías avanzadas  o países emergentes, por ejemplo los llamados BRIC. Todos ellos están calificados por las agencias de rating y tienen mercados de futuros de bonos.

BRIC: podrían tener varios posibles problemas (en un horizonte de cinco años),   riesgos políticos y económicos. Brasil e India parecen democracias consolidadas y su compromiso con el respeto a los  derechos de propiedad (incluidos de activos financieros) parecen irreversibles. No tengo tan clara la situación con respecto a Rusia y China. Por otra parte son economías todavia emergentes, menos resistentes a shocks de la magnitud de un colapso del Euro. En este sentido habría que analizar los terminos del comercio entre estos BRIC y la UE, para ver cuales seria menos afectados por un colapso del  euro. En mi opinión, sin profundizar más, una transferencia de ahorros significativa a zona BRIC podría ser peor cómo remedio, que la enfermedad.

Japón y otras economias más o  menos avanzadas de Asía:   sin riesgos políticos ni económicos previsibles, protegidos frente a shocks europeos, pero lejanos, dificilmente accesibles.

UK, Suiza y otros países europeos no pertenecientes a la zona euro: el mismo comentario con respecto al riesgo económico que se ha realizado con respecto a los BRICs se puede aplicar a estos países. Habría que analizar más en profundidad la magnitud de sus relaciones económicas con la zona euro, sin duda importante.

EEUU:  casi sería mi preferencia. Tiene una economía avanzada, bien posicionada en sectores de futuro (IT), más cerrada (y por lo tanto menos sensible a shocks), sólida, diversificada, sin riesgos políticos serios. El único problema que veo es que están lejos y dentro de poco se van a quedar pequeños. Pero este problema de tamaño lo empezarian a sufrir más allá del horizonte temporal que nos hemos marcado.

Varias cuentas en varias zonas:  esta es, en condiciones de ausencia de información sobre la evolución de cada una de las zonas,  posiblemente la mejor alternativa, pero también la  más cara y la que supone mayores costes de transacción (tiempo y dinero que se debe invertir en diseñar y montar la infraestructura de cuentas, su mantenimiento y gestión etc…). Los costes de transacción, a veces son difíciles de evaluar ya que pueden estar basados en intangibles cómo el tiempo libre, pero hay que tenerlos en cuenta.

A continuación un gráfico con los países más endeudados en relación a su PIB, datos de finales 2011, fuente FMI.

Riesgo bancario: para aquellos que estén pensando en movilizar sus ahorros, la otra decisión importante es sobre el banco en el que abrir la cuenta en el exterior.

¿ Existe de verdad riesgo bancario ?

Sí, existe, ahora y en cualquier otro contexto económico. Por ello las autoridades públicas y el propio sector han articulado instrumentos de cobertura de riesgos.

Adquisición: Vamos a suponer que el banco dónde esta persona ha depositado el dinero quiebra. Lo normal es que otro banco privado, en mejor situación lo acabe comprando, asumiendo sus activos y pasivos (entre los que están las cuentas corrientes). En este caso los efectos en los ahorros para el titular de la cuenta son imperceptibles.

Nacionalización: Si ningún otro banco privado se acaba interesando, cabe la posibilidad que las autoridades públicas lo nacionalicen, saneen y privaticen. De nuevo esto puede tener unos efectos imperceptibles para los ahorros del depositante.

Fondo de cobertura de depósitos: Pero si finalmente la quiebra no se sigue de una adquisición o nacionalización, existe una legislación concursal que determina las obligaciones de la empresa que quiebra. Para bancos hay instituciones específicas que entran en juego, cómo por ejemplo el fondo de garantía de depósitos: ver este y este enlace.

De esta última página web extraigo: “El importe dinerario garantizado tiene como límite 100.000 euros por depositante en cada entidad de crédito“. Es decir en España están garantizados 100.000 euros por titular y cuenta. Imagino que la legislación es similar en otros países europeos, pero se debe comprobar en cada caso.  En USA la entidad equivalente al FGD garantiza 250.000 usd. Para ahorradores con cantidades superiores a más menos 177.000 euros puede ser interesante posicionar sus ahorros en USA.

Es decir en caso de quiebra por exceso de exposición a determinados riesgos de cualquier banco europeo, es muy difícil que un pequeño ahorrador (ahorros inferiores a 100.000 euros) pierda sus ahorros. Esta proposoción tiene dos matices:

–los fondos de garantía son seguros y funcionan cuando la realización  de un riesgo no es masivo entre los asegurados. Si hay un colapso de la zona euro (muy improbable) acompañado de un colapso  del sistema financiero en la zona euro o incluso internacional (muy improbable), nadie garantiza que la realización del riesgo no sea masiva y por lo tanto no habrá fondos garantizados para todos. Entiendo que en este caso las autoridades públicas articularán algún mecanismo.

La no perdida de los ahorros por quiebra bancaria no implica la no perdida de poder adquisitivo de estos ahorros dependiendo dónde estén en el momento del colapso. Si tengo posicionados mis ahorros en un banco de país de economía débil (resp. en un banco de un país de economía fuerte) mis ahorros, aunque no los tenga se depreciarán (resp. apreciarán) con respecto a los que los tengan en una economía fuerte.

¿ Cómo  evaluar el riesgo de un sistema financiero y de un banco ?

Para evaluar el riesgo de un sistema financiero debemos estudiar su legislación bancaria, concretamente que pasa en caso de suspensión de pagos o quiebra. La mejor fuente es el Banco Central del país en cuestión.

Para evaluar un banco en concreto, en Europa existe una agencia (la EBA) que realiza test de estrés y otro tipo de evaluaciones a entidades financieras. Esto  es una primera fuente pero poco dinámica, su actualización es anual.

Una fuente más dinámica, son las agencias de rating:  ya lo hemos dicho, conviene hacer un seguimiento periódico de las calificaciones de nuestro banco en diversas agencias de rating. su actualización depende de la frecuencia de emisiones de deuda.

La fuente más dinámica con actualizaciones al segundo son las bolsas de valores. Conviene  seguir el comportamiento a diario de nuestro banco en las bolsas de valores en las que coticen. Las variaciones en la cotización en bolsa de los valores de una empresa incorporan toda la información disponible en el mercado sobre la empresa. Una bajada brusca puede indicar problemas de algún tipo. Cuando se detecte conviene inmediatamente intentar averiguar el motivo de la bajada. Para ello se puede acudir a blogs especializados, cómo por ejemplo este.

¿ Cuales son los países, sistemas bancarios y bancos más expuestos a la deuda griega ?

Sobre esto se puede ver un gráfico muy interesante (con datos a noviembre de 2011) y un artículo que lo acompaña. Y ver también este enlace.

Se ve claramente que, por este orden, en terminos absolutos Francia (de manera muy destacada: la exposición francesa, en su mayoria directa supone más del 2% de su PIB), EEUU y Alemania son los países más expuestos. Pulsando en la bandera de cada país de puede ver su exposición a la deuda de Grecia, Portugal e Irlanda. Francia tienen está bastante expuesto a Grecia e Irlanda y menos a Portugal. Alemania sobre todo a Irlanda. España está bastante expuesto a la deuda Portuguesa.

Es importante tener en cuenta que la exposición a la deuda de un determinado agente económico (país, banco) es una variable dinámica que puede variar de emisión en emisión de deuda.

Si fuese conveniente tener dos cuentas en dos zonas en vez de mantener todos los ahorros en una cuenta nacional ¿ Que es más conveniente, tener las dos cuentas en dos sucursales nacionales del mismo banco o en bancos diferentes ?

Aquí ya entran consideraciones no solo de riesgo sino también de coste y beneficio. Coste de apertura, comisiones de mantinimiento de cuentas, de transferencia etc…y con respecto a beneficios hablamos de remuneración de un depósito en cuenta corriente. Si nos ceñimos exclusivamente al riesgo, se debe estudiar la diversificación de riesgos de cada banco (presencia internacional en otras zonas no euro, test de estrés etc…) y en caso de similaridad mejor diversificar, por aquello de no meter todos los huevos en la misma cesta.

D) Conclusión:

Tras estudiar en profundidad el precedente de la crisis argentina y la situación actual  en Europa, y concretamente la de Grecia, no cabe sino concluir que son bastante similares. El acuerdo de 27 de octubre si finalmente lo acepta Grecia, es un default parcial encubierto (me refiero a la quita de parte de la deuda con la banca privada; ver un post recién salido del horno explicando el mecanismo e intenciones de la quita; además que ataquen con instrumentos de cobertura no son buenas noticias).

En el peor de los casos (muy improbable), la salida de Grecia del euro aunque de consecuencias trágicas para Grecia, tiene unas consecuencias asumibles para el resto.  Sería más preocupante el posible efecto dominó (¿cual sería el siguiente país en salir ?). Si Grecia o Italia llegasen a salir, no estaría de más  inmediatamente abrir cuenta en otro país,  en la zona dónde cada cual estime conveniente tras detallado estudio de riesgos y análisis coste- beneficio.

Pero dado que el riesgo de salida de un país del euro es bajo (mucho más bajo es el riesgo  de colapso total), me preocupa mucho más, a largo plazo, la causa profunda del estancamiento de la UE. Repitamosla una vez más para terminar: una unidad económica dónde no se pueden mover los factores (concretamente el factor trabajo) no puede funcionar. Y en la UE debido fundamentalmente pero no solo a diferencias linguisticas, el factor trabajo no se puede mover.

Actualización 6 de noviembre:

Me ha llamado la persona que ha motivado la redacción de este post y me ha comentado que le ha aclarado mucho el tema.

Actualización:

Un artículo en Cinco Días de temática similar.

Parece que los gestores de grandes patrimonios han llegado a conclusiones similares a las mías. El oro no me convence cómo valor refugio, ya que está sujeto a grandes oscilaciones impredecibles. Tampoco el mercado inmobiliario. Mejor divisas y entre estas el USD.

Actuallización 30 de noviembre 2011:

Un artículo de El País sobre la no solución ruptura del euro:

Actualización 8 de diciembre 2011:

JP Morgan Chase ha elaborado también su propio informe sobre el tema. Los autores son John Normand y Arindam Sandilya. Se puede ver un resumen aquí.  Parece que repiten punto por punto el esquema de informes anteriores que ya hemos citado en este post y llegan a similares conclusiones.

HPC. Generalización del método de la patente US 8266098 a (algunos) casos no vértice simétricos.

junio 27, 2015

1. Hace tiempo, años, que quiero escribir una entrada comentando éste tema, pero siempre se me acaba pasando, ya que de momento es sólo una idea que no he explorado ni superficialmente. Realmente no se ni siquiera si es una buena idea….Pero ahora que estoy plenamente concentrado en éstos temas me he acordado y no quería que se me pasase la oportunidad de  publicar la idea.

Claramente los resultados de nuestro método dependen sobre todo de la regularidad del IAS y de como están unidos los diferentes IAS. En este sentido, por ejemplo, mientras sean regulares, el grado de los dígrafos sea 4 (con dos entrantes y dos salientes) y el entorno de  la identidad sea liso entiendo (sólo  hipótesis de trabajo) que nuestro resultado  para estos casos se mantendría aunque los tamaños  de los IASes no fuesen todos  iguales. Si los tamaños de los  IASes ya no son todos iguales, entonces ya no estamos hablando de dígrafos vértice- simétricos.

¿ Siguen siendo válidos las técnicas de la patente para estos casos más generales ?. Entiendo que sí.

¿ Cuán generales son estos casos, con la restricción de vértice-simetría relajada ?. Estoy pensando en una posible relación (reducción) polinómica, por ejemplo, con los grafos de los que se habla en el resultado de Plesnik  u otros que son generales desde el punto de vista de la complejidad computacional.

Tema a estudiar.

2. Actualización día 28, 2:30 am.

Un ejemplo que acabo de construir nos demuestra (como era de esperar) que se pueden construir éste tipo de digrafos y que los métodos de la patente funcionan perfectamente. Desde los preliminares de marcar el vértice inicial hasta el final (marcar opciones, cinco en éste caso, y sacar consecuencias).

Los números indican el “orden” del IAS. El caso ha resultado ser fácil y siguiendo el método de la patentes he encontrado el recorrido hamiltoniano a la primera: es como un dihédrico, el producto de dos IASes de orden 4 (u 8), por otros tantos de orden 2.

Generalización

Esto le da mucha más flexibilidad al método de la patente, pues abarca una clase más amplia de dígrafos (no se si mucho más amplia pues aparentemente hay que cumplir con ciertas condiciones y además así de primeras no parece fácil construirlos, aunque al final igual se puede construir un modelo aleatorio: me ponga 4 de orden, 3 de orden 4, 5  de orden 6 y el resto, los que ajusten).

Pero me empieza a parecer una buena idea o al menos una idea digna de explorar y me pregunto si ya está circulando por ahí. Me pregunto también si  se corresponden con alguna estructura algebraica más flexible que los grupos (no creo)…

En fin hay que ver lo que dan de sí. En el segundo intento voy a intentar, valga la redundancia, que sea más irregular y entrelazado.

3. Actualización 28 de junio 2015,11:30 am.

Disclaimer. Esta parte 3 puede contener errores. Cuando los detecte los iré  corrigiendo.

Seguimos comentando sobre esta  clase de dígrafos.

a) Primero vamos a ponerles nombre: dígrafos IAS-regulares.

b) ¿ Son nuevos ?.

Un artículo sobre otras generalizaciones de los dígrafos o grafos de Cayley.

Cayley graphs and coset diagrams

1 Introduction Let G be a finite group, and X a subset of G. The Cayley graph of G with respect to X, written Cay(G,X) has two different definitions in the literature. The vertex set of this graph is the group G. In one definition, there is an arc from g to xg for all g ∈ G and x ∈ X; in the other definition, for the same pairs (g,x), there is an arc from g to gx. Cayley graphs are generalised by coset graphs. For these we take a subgroup H of G as part of the data. Now the vertices of the graph may be either the left cosets or the right cosets of H in G; and an arc may join the coset containing g to the coset containing xg, or to the coset containing gx. Thus, there are four possible types of coset graphs.

The two types of Cayley graph are in a certain sense equivalent, while the four types of coset graph fall into two distinct types:

–one type encompasses all vertex-transitive graphs,

while the other is seldom vertex-transitive but has more specialised uses in the theory of regular maps.

The purpose of this essay is to explain where the definitions come from and what purposes they serve.

En un principio no aparece el autor pero el estilo es claro y conciso, me sonaba. Y efectivamente, es de un autor conocido: Peter Cameron. Aunque claro y conciso todavía no  me he enterado muy bien sobre éstas generalizaciones, pero aparentemente no incluyen la nuestra.   

c) ¿ Son generales (desde el punto de vista de la complejidad computacional ?

Está claro que pertenecen a la clase de dígrafos 4-regulares, pero posiblemente sean una restricción de  ésta clase que ya por si misma es una restricción. ¿ Cuan general  es la  clase de grafos 4-regulares desde el punto de vista de la complejidad computacional ?. El artículo de Plesnik trata precisamente de ésto:

Extractos.

Garey , Johnson, and Stoclcmeyer [2] have proved that the problem remains NP-complete also in the case of undirected graphs with degrees at most 3. Then Garey, Johnson, and Tarjan [3] have shown. Then Garey, Johnson, and Tarjan [3] have shown the W-completeness under coustraints that the undirected graphs are planar, cubic, and 3-connected. This is obviously the best possible result as for degree bound. Replacing every line uu of undirected graphs with two arcs uv and vu, they have simultaneously settled the NP-completeness in the case of planar digraphs with indegrees and outdegrees at most 3. Here we show that the last result can be still improved as follows: The hamiltonian cycle problem is NPcomplete even in the case of planar digraphs with outdegrees at most 2. Clearly, t bound two on degrees is the best possible

Es decir los casos cuyos vértices tengan como mucho grado 2 de entrada y grado dos de salida (pueden tener menos, por ejemplo 1 de entrada y 2 de salida o viceversa) y son planares, siguen siendo NP-completos. Por lo tanto, entiendo que se puede afirmar que el problema para los dígrafos 4-regulares(2-in,2-out) es también NP-completo, dado que los casos de Plesnik son una restricción de éstos.

Todo ésto nos aclara que nuestros dígrafos son una restricción de una clase restringida que es bastante general, desde el punto de vista de la complejidad computacional, pero no que ellos mismos sean generales. Para demostrar que lo son se debería de construir una reducción de los casos de Plesnik a la generalización que estamos  estudiando.

Es posible que el  lector piense que estas clases son muy restringidas. Sin embargo la cantidad de dígrafos 4-regulares que se pueden construir ya es brutal para un tamaño de vértices no demasiado grande. Si tenemos en cuenta la isomorfia, la cantidad sigue siendo enorme. Por ejemplo para 13 vértices hay 7 371 560 dígrafos 2-regulares (es decir 2-in, 2-out; en otra fuente dan otro dato, similar pero no exacto: 13, 71971687). Que yo sepa no existe una fórmula exacta (o función que se pueda expresar mediante una fórmula más o menos sencilla y de un número exacto) tal que dados estos dos parámetros nos permita calcular el número de dígrafos no isomorfos. Sí existen fórmulas asíntoticas o que acotan superiormente ésta cantidad (para grafos). Ver también este otro enlace. Exista fórmula exacta o no, nos quedamos con que la cantidad ya es astronómica para pequeñas cantidades de vértices.

Posiblemente la mayoría de éstos, de éste tamaño, no tendrán la propiedad que tienen los que estamos investigando. Podemos preguntarnos cuando n (nº de vértices) tiende a infinito, ¿ cual es la probabilidad de que si seleccionamos un dígrafo k-regular sea uno de los nuestros ?. Teniendo en cuenta que la familia que estudiamos es bastante más amplia que los Dígrafos de Cayley, esto nos da una idea de los escasos que son éstos. Son verdaderas joyas, con propiedades muy ventajosas, y por eso se estudian tanto.

d) Método de construcción y cuantificación.

En éste punto presentamos  un método de construcción e intentamos dar  una cota superior de la cantidad de éste tipo de dígrafos dado el número de vértices. Primero ilustramos al lector con otro caso.

Ya he construido otro dígrafo IAS-regular y estoy viendo que no es complicado construir casos. Incluso no es complicado obtener un modelo aleatorio de construcción.

En la imagen el segundo caso que hemos construido. Es un dígrafo de 28 vértices, que tiene IASes de orden IV, III y II (4 de IV, 4 de 2 y 1 de 3):

generalización iases regulares

Dejamos al lector que determine si el dígrafo de la imagen tiene recorridos hamiltonianos o no.

Nota al margen.

En la imagen, a la derecha un dígrafo más pequeño que representa un IAS irregular, pero en  el que se sigue  pudiendo aplicar la técnica de arc-forcing (¿ piensa el lector generalizar el resultado de vértices finales a éstos casos de IAS-irregular ?). Si relajamos la restricción de regularidad en el IAS, y aceptamos este tipo de IASes que se muestran en este perqueño dígrafo, entonces obtenemos una generalización algo más potente que tratamos en el siguiente punto.

Fin de nota al margen.

Siguiendo con la primera generalización, los dígrafos IAS-regulares, hay un dato importante que es fácil ver: el tipo de dígrafos de IAS regular (es decir aquellos que se pueden descomponer IASes regulares de cualquier tamaño) tienen que tener un número par de vértices.

¿ Dado un número par de vértices, cualquiera, podemos construir un dígrafo IAS-regular ?

Sí, uno y varios, incluso bastantes, si el número de vértices que nos dan es elevado.

En lo que sigue vamos a intentar dar una fórmula (exacta o de acotación superior) que nos permita estimar o conocer dado un número de vértices, cuantos dígrafos de ésta clase diferentes podemos construir. Sólo nos interesan los dígrafos conexos y de momento excluimos la posibilidad de ciclos de orden 2, es decir de “involuciones”.

Primero mostramos un procedimiento de construcción y para obtener la fórmula que buscamos vemos de cuantas maneras diferentes se puede realizar ese procedimiento.

El procedimiento es muy sencillo: hacemos una partición en números pares del número de vértices, con p>4, siendo p el número mínimo de vértices de una parte (es decir el  IAS regular mínimo contiene 4 vértices), construimos los IASes correspondientes a cada parte y luego unimos cada uno de estos IASes con otros IASes regulares (al igual que cuando el número de vértices es elevado el número de particiones pares de un número será elevado, el número de maneras de unir con otros IASes estos IASes que se han conseguido para cada partición, será elevado también).

Por lo tanto dado un número (par) de vértices n, una fórmula para calcular el número de dígrafos IAS-regulares correspondiente tendría que tener dos componentes: primero las particiones pares, digamos P2(n); segundo, para cada partición el número de maneras diferentes de unir con IASes regulares a los obtenidos en la partición. Al final tendremos un sumatorio.

Para el primer componente ya existen fórmulas (que al menos nos permiten acotar superiormente la cantidad, de  momento nos es suficiente). Casi de todas ellas me quedo con la siguiente, que aunque sea de acotación, es la más sencilla de recordar: Hardy and Ramanujan (1918) used the circle method and modular functions to obtain the asymptotic solution

 P(n)∼1/(4nsqrt(3))e^(pisqrt(2n/3))
(23)

Como se ve vamos a tener un sumatorio con una cantidad subexponencial de términos.

De momento no tengo claro un modelo combinatorio sencillo para el segundo componente pero seguro que existe. Estoy en ello.

d1) Primer intento.

No estoy convencido de que sea la manera más directa, sencilla y económica de hacerlo, ni siquiera estoy seguro sobre la corrección (y el lector debe de tener ésto muy en cuenta) pero así vamos viendo.

Actualización: Parece que lo más sencillo hubiese sido asumir  que el grafo es bipartito y ahorrarse todo el tema de convertirlo en un bloque conexo. Fin de actualización.

Al final de la primera operación de partición y de construcciones de los IASes correspondientes nos quedan tantos componentes (dígrafos) sueltos como elementos de la partición. Ahora algunas definiciones. Digamos que |V| = número de vértices y |V| = p1+p2….pi es una partición cualquiera de éste número de vértices en números pares. Llamamos pp(|V|) a la partición en números pares del número  de vértices (que también es par). Tenemos i componentes o dígrafos disconexos. Si llamamos saturar un vértice hacer que tenga 2-in y 2-out arcos (condición necesaria para que el dígrafo pertenezca a la clase que estamos construyendo), de momento todos están no saturados. Algunos (la mitad) tendrán 2-in y otros (la otra mitad) tendrán 2-out.

Ahora tenemos  que ir añadiendo arcos. Decidimos primero añadir arcos de cualquier manera para obtener un dígrafo conexo

Las primeras elecciones de arcos son para unir los componentes sueltos y obtener un dígrafo conexo.

Maneras de dibujar el primer arco (por ejemplo de cualquier vértice del componente 1 a cualquiera del resto de vértices): (p1/2)*((|V|-p1)/2). Dividimos por 2 dado que obviamente no es cualquiera con cualquiera, sino 2-in con 2-out. Hemos unido p1, con por ejemplo p2 (pero da igual, podría haber sido con cualquier otro y obtendríamos la misma fórmula). Con esto ya tenemos (i-1) componentes diferentes. Tenemos que continuar con el procedimiento hasta obtener 1 sólo componente, el dígrafo que nos interesa.

Maneras de dibujar el segundo arco (por ejemplo, de nuevo cualquiera del componente que hemos  obtenido en el paso anterior, con cualquiera de los restantes; puede ser un arco que pertenezca al mismo IAS que el primer arco o a otro diferente, ésto da igual):

(((p1-1)+(p2-1))/2)*(((|V|-(p1+p2))/2) < |V|^2,

Maneras de dibujar el tercer arco (idem):.

(((p1-1)+(p2-1))-1)+(p3-1)/2)*((|V|-p1+p2+p3)/2) <|V|^2,

Maneras de dibujar el iésimo-1 arco.

Para obtener un sólo componente tenemos que utilizar ( i-1) arcos.

(((p1+p2+p3…+(pi-1)-2(i-1))/2)*(|V|-(p1+p2+p3+…+p(i-1))/2) <|V|^2

Como cada una de estas maneras de conseguir un dígrafo conexo se puede hacer de manera independiente de las otras  la manera de combinar cada una de estas maneras es la multiplicación.

Para cada partición, obtendríamos un productorio acotado por < |V|^2i. 

Por lo tanto una cota superior a la cantidad que estamos estimando es de momento pp(|V|)*|V|^2i. < O (subexp |V|).

Ya tenemos un sólo componente y de momento no hemos saturado ningún vértice. Tenemos (i-1) vértices con tres arcos y |V|-(i-1) vértices con dos arcos cada uno. Como de momento nos interesa sólo una cota superior vamos a simplificar: nos olvidamos de los arcos semi-saturados y consideramos que todos están en situación 2-in o 2-out. Tras esta simplificación ahora podemos pensar en un digrafo bipartito con dos partes, cada una con |V|/2 vértices. Y, de nuevo para simplificar, y para obtener una fórmula comparativa con la fórmula que hemos dado para dígrafos generales, nos da igual la conexión y la isomorfia. Calculamos el número de grafos bipartitos de grado o valencia 2 (como todos los arcos van en un mismos sentido, de un grupo de vértices, al otro, ¿ nos podemos olvidar de la dirección?).

e) ¿ Que ganamos y que perdemos con ésta generalización ?

stá claro también que hay parámetros (por ejemplo el orden del IAS / DAS, de la circunferencia etc…) y propiedades (por ejemplo la propiedad de lisura en el entorno de la  identidad) que, debido a la pérdida de simetría, o dejan de tener sentido (orden de IAS o de circunferencia, ya no habría una medida única para todo el dígrafo) o ya no se pueden testar de manera local y extrapolar a todo el dígrafo (la lisura en el entorno de la  identidad; ahora hay comprobar que se da en cualquier entorno). No está claro tampoco no lo sé) que esta nueva clase se pueda describir de manera sucinta. Por lo tanto al pasar a esta nueva clase,  se pierde potencia en los métodos.

4. Otra generalización: los dígrafos arc-forcing.

Estoy pensando que, en principio, nada nos obliga a que un IAS sea regular, en el sentido de que no se crucen los arcos que en él están contenidos.

En realidad, podemos suponer que la única propiedad que interesa que se conserve es que el dígrafo se pueda descomponer en grupos de arcos entre los que se pueda aplicar la técnica del arc-forcing, es decir que la inclusión de un arco en el recorrido hamiltoniano excluya a otro en contacto inmediato con él, y que ésta exclusión a su vez hace que un tercero inmediato quede incluido así hasta que se llega al primer arco que se había incluido. Llamemos a éste tipo de dígrafos, Dígrafos Arc-Forcing.

De  hecho, como  ya hemos comentado en la descripción de la patente, ni siquiera todos los Dígrafos de Cayley tienen el IAS regular: la mayoría de los abelianos o commutativos no tienen IASes regulares. Sin embargo si se conservan otras propiedades que los hacen vértice simétricos.

Digo en principio pues nos interesa que en las nuevas clases que estamos definiendo, que en las generalizaciones, sigan siendo aplicables lo máximo posible algunas de las técnicas de la patente, como el resultado de los vértices iniciales posibles, elegido un vértice inicial.

Con ésta relajación abarcamos a una clase que entiendo que es bastante más amplia. ¿ Cuan amplia ?. Por otra parte la técnica del arc-forcing es bien conocida desde hace décadas. ¿ Está ya definida esta clase que para nosotros es nueva ?.

He comprobado también sobre los Cayley Abelianos, que hacía años que no había vuelto a mirar y salvo que se cumplan determinadas condiciones arítmeticas los IASes son irregulares, multicruce. Sí creo recordar cuando los estudié, que en éste caso el resultado sobre vértices finales sí era generalizable así como todo el método: representar éstos dígrafos en forma de IAS era muy útil, aunque visualmente no eran muy atractivos.

A continuación algunos IASes irregulares o digrafos arc-forcing que he construido. Por deformación profesional utilizo en algunos arcos la línea continua y en otros la línea discontinua. A diferencia de los Dígrafos de Cayley no significan nada. En la primera linea los tres digrafos etiquetados A,B,C son mínimos:  si se les quita algún arco dejan de cumplir con la definición de arc-forcing. Podemos definir como unidad al par de arcos que salen de un vértice, uno de linea discontinua y el otro continua. Debajo, otros que no son mínimos (por cierto, el de abajo a la derecha es el que hemos  mostrado en una imagen anterior). Se les puede quitar arcos y seguimos  teniendo IASes. Todos los dígrafos no mínimos se pueden transformar en A, quitando una o varias unidades, pero no en B o C. Hay una relación en los dígrafos mínimos, de momento curiosa, pero que ya casi puedo demostrar que será robusta: nº unidades + nº de saturaciones + 1 = de vértices. Si finalmente la pudiese demostrar (como se ve si empezamos con una linea vertical con una, una y “media”, dos unidades etc…, en los extremos se puede construir un “triángulo” añadiendo una unidad y en medio serán cuadrados, añadiendo una unidad y media; seguramente todos los mínimos se podrán construir de ésta manera y teniendo ésto en cuenta es muy posible que se pueda deducir la relación señalada), podría utilizarse para identificar mínimos.

En realidad tanto los mínimos como el resto son válidos para construir los dígrafos de la clase que estamos definiendo. Pero igual se puede construir clases de equivalencia de mínimos y a lo mejor (mera ocurrencia de momento) esto es relevante para el problema de recorridos hamiltonianos en este tipo de dígrafos (igual se puede demostrar que dado un dígrafo, al transformarlo en el mínimo se mantenga la propiedad de hamiltonicidad; insisto, mera ocurrencia que puede evaporarse a la primera prueba).

Provisional: El  resultado de los vértices finales creo que sí se puede generalizar. Basta con hacer una analogía de cada caso (me refiero de momento a los mínimos, pero seguramente será ampliable a todos), con el caso homólogo regular (homólogo en el sentido de que tenga el mismo número de unidades. Etiquetamos primero los vértices del irregular con naturales (o con lo que sea). Luego construimos el homólogo regular y le vamos asignando a cada vértice correspondiente las etiquetas del irregular (los saturados aparecerán repetidos). Con aquellas etiquetas del irregular que aparecen en las posiciones del regular que serían vértices finales posibles, podemos reconstruir el mismo argumento en el irregular y obtener los vértices finales posibles de éste que serán los mismos. Sugiero que el lector lo pruebe con el mínimo más pequeño y luego es lo mismo. Fin de provisional.

Hablando de recorridos hamiltonianos, he construido un caso, el que figura debajo del todo, pero que no incluye sólo arc-forcing mínimos: le he cerrado con un IAS regular de orden 6, que es el del contorno. El lector podrá comprobar que contiene también un B y dos A.

generalis

He utilizado el método de la patente para éstos casos y funciona a la perfección (he encontrado un ciclo hamiltoniano). He marcado como vértice final e inicial dos vértices del IAS regular. Da la impresión de que todos los construidos con los mínimos van a ser fáciles. Sólo una impresión provisional. Nótese que es planar.

Por cierto, tanta estructura en los mínimos apesta, si el lector me permite la expresión: ¿ no habrá una estructura algebraica subyacente  ?.

5. Finalmente otra generalización.

La obvia: una combinación de las dos anteriores.

Con todo esto doy por satisfecha de momento mi curiosidad sobre estas generalizaciones. Si tengo tiempo en posteriores ocasiones y trabajo sobre ello, actualizaré.

Apéndice: enlaces relevantes encontrados para toda la entrada.

–una survey reciente (2010) sobre tests positivos de hamiltonicidad en dígrafos generales y algunas restricciones. Creo que toda la literatura se centra sobre todo en tests positivos. Hecho de menos literatura sobre tests negativos u obstáculos a la hamiltonicidad (y creo  que existen cosas publicadas). Sin embargo, uno de los grandes resultados de la teoría de grafos fue determinar todos los obstáculos posibles a la planaridad.

A SURVEY ON HAMILTON CYCLES IN DIRECTED GRAPHS DANIELA KUHN AND DERYK OSTHUS ¨ Abstract. We survey some recent results on long-standing conjectures regarding Hamilton cycles in directed graphs, oriented graphs and tournaments. We also combine some of these to prove the following approximate result towards Kelly’s conjecture on Hamilton decompositions of regular tournaments: the edges of every regular tournament can be covered by a set of Hamilton cycles which are ‘almost’ edge-disjoint. We also highlight the role that the notion of ‘robust expansion’ plays in several of the proofs. New and old open problems are discussed.

Por otra parte si decenas, cientos sino miles (quizás esta cantidad ya sea demasiada) de investigadores han publicado sobre tests positivos de hamiltonicidad, será porque son útiles, porque son informativos, porque ayudan al investigador de éste problema, porque le ahorran tiempo de búsqueda. Sin embargo el examinador de mi segunda solicitud de patente considera  que los tests que yo propongo, que son igualmente útiles en el mismo sentido señalado, para una clase muy concreta de dígrafos, son meras ideas abstractas, que se agotan en sí mismas, sin consecuencia práctica ninguna. Increíble pero cierto.

HPC. Sobre la propiedad de lisura o smoothness en Dígrafos de Cayley Bigenerados: ¿ una caso que la falsifica ?II.

junio 26, 2015

Nota. Salgo a una comida. Completaré la entrada más tarde, y seguramente la modificaré.

Seguimos la serie de entradas comentando sobre el método de la patente US 8266089 y sobre los tests incluidos en las 6 reclamaciones sustanciales (el resto son variaciones) de la solicitud de patente (de tipo continuation) 13/570898, de manera completamente injustificada por parte del examinador y que espero que finalmente se concedan en una próxima revisión. 

Ya hemos visto que no hay posibilidad de caso que falsee nuestro resultado, tal y cómo insinuábamos en el título. Nuestro resultado es robusto.

Pero sí creo que tras la sucesión de las últimas entradas la situación ha podido algo quedar confusa para el lector y quiero aclara las conclusiones principales del resultado:

1. Casi todos los Dígrafos de Cayley bigenerados son lisos o smooth y por lo tanto tienen recorridos hamiltonianos (en general varios, en general muchos) en todos los vértices finales posibles. Éste es el principal resultado de nuestra investigación y creo que es una buena noticia para los diseñadores de redes de interconexión. Esto que era completamente desconocido abre nuevas posibilidades al diseñador de redes, como diseñar redes en las que todo el enrutamiento se haga mediante recorridos hamiltonianos. Entiendo que habrá aplicaciones para las que este tipo de redes sea el más adecuado u óptimo. Teniendo esto en cuenta es altamente interesante disponer de un test que permita identificar los casos smooth. El test existe y lo hemos incluido como reclamación en la segunda solicitud de patente y por motivos que se me escapan (en la primera está claro, un formalismo legal; en la segunda, pese a la incidencia del caso Alice Corp. v CLS Bank, los motivos son completamente oscuros) se han rechazado.

2. El método que hemos presentado en la patente es secuencial pero es fácilmente paralelizable en la mayoría de sus etapas y sobre todo en la  que es computacionalmente más intensiva, tal y como hemos detallado en una anterior entrada.

3. Cuando por los motivos que sea al diseñador de redes de interconexión o de otro tipo, o a cualquier otro tipo de usuario le interesa (seguramente porque el caso tiene otras propiedades muy interesantes no relacionadas con la propiedad de hamiltonicidad) trabajar con un caso que no sea liso o smooth en el entorno de la identidad, y por lo tanto sea potencialmente complicado, no está todo perdido. El método de la patente incluye una serie de tests que permite identificar casos con propiedades estructurales diferentes a los que se puede aplicar técnicas diferentes.

Leer el resto de esta entrada »

HPC. Casos extraños de S6, 720 vértices.

junio 25, 2015

Nota. entrada incompleta que iré completando. 

1.1 Una investigación heroica.

Al hilo de la entrada anterior, he estado mirando, dentro de la base de datos con la que he trabajado, los resultados para todos los Dígrafos de Cayley bigenerados no isomorfos de S6, es decir del grupo simétrico de grado 6, con 720 vértices.

Aquí hablamos ya de palabras mayores: imposible la acción manual, hay que automatizar cualquier operación, e incluso automatizando puede no encontrarse la respuesta.  Es lo que les pasó a los investigadores que elaboraron la base de datos.

Por cierto de nuevo les estoy altamente agradecido a los dos investigadores que realizaron este gran trabajo. Una investigación heroica, en mi opinión. Tenga en cuenta el lector de que cualquier resultado nuevo con estos tamaños de input y la complejidad del problema, ya supone sangre sudor y lágrimas. Y trabajaban prácticamente a ciegas en lo teórico.

Para resolver un problema científico, un problema matemático, un problema ingenieril,  se necesita información. Incluso el matemático o ingeniero más competente necesita información para resolver un problema. Éstos no se pueden resolver en el vacío. Las soluciones a los problemas no brotan por generación espontánea. Y para algunos de los problemas que se estudian, como ha sido el caso del problema de encontrar recorridos hamiltonianos en Dígrafos de Cayley bigenerados antes de la investigación de éstos autores, simplemente no hay información suficiente para avanzar.

Y en el caso del problema sobre el que hablamos no la había precisamente, como lo sabe cualquiera que haya trabajado en ello, por la dificultad que hay había en encontrar las soluciones para cualquier caso. Las únicas alternativas disponibles eran o bien estudiar las propiedades ad-hoc del caso y si había suerte utilizarlas para encontrar algún recorrido hamiltoniano lo cual se ha podido hacer en contadas ocasiones o bien aplicar un algoritmo genérico que puede tardar una eternidad ya para casos no demasiado grandes. Ningún enfoque general eficaz y eficiente.

Nota. Creo que esta dificultad en encontrar soluciones que era patente antes de la publicación de mis resultados, y no lo digo yo, lo dice uno de los padres de las ciencias computacionales / informática al que cito  en la solicitud de patente,  no la ha comprendido bien todavía el examinador, pese a que lo explico en la solicitud y se lo he intentado explicar por teléfono en varias ocasiones. O no lo ha comprendido, o no lo quiere comprender.

Como ejemplo de lo que queremos decir, un extracto de una tesis de 2004: Hamilton Cycle Heuristics in Hard Graphs. SHIELDS, IAN BEAUMONT

Abstract. In this thesis, we use computer methods to investigate Hamilton cycles and paths in several families of graphs where general results are incomplete, including Kneser graphs, cubic Cayley graphs and the middle two levels graph. We describe a novel heuristic which has proven useful in finding Hamilton cycles in these families and compare its performance to that of other algorithms and heuristics. We describe methods for handling very large graphs on personal computers. We also explore issues in reducing the possible number of generating sets for cubic Cayley graphs generated by three involutions. 

Extractos.

Sjerve and Cherkassoff [102] also studied Cayley graphs where the group generating set consisted of three involutions. They completely determine those alternating groups An, symmetric groups Sn and projective groups PSL2(q) and PGL2(q) which can be generated by three involutions, two of which commute. They also show, by embedding the graph in a surface, that, for a finite group having this property, the Cayley graph corresponding to the generators has a Hamilton cycle. The question of whether a Cayley graph generated by three involutions no two of which commute is still open. 

We will now turn our attention to cubic Cayley graphs, that is, those where every vertex has degree three. We are particularly interested in the symmetric group, Sn, and its subgroups. Suppose X is a set of generators for a group G ⊆ Sn. If Cay(G : S) is cubic then either X is a set of three involutions or a set consisting of one involution and one element of G that is not an involution. The latter type can be studied as either a directed graph or an undirected graph but our research focuses on the undirected form.

We initially applied our algorithm to find Hamilton cycles in Cayley graphs generated by three involutions. As noted above, Cayley graphs generated by three involutions where two or more of the involutions commute were already known to be Hamiltonian [102]. Accordingly, we focused our attention on the case where no two of the involutions commuted. 

After our success with other types of vertex transitive graphs we were very surprised when we were not able to find results. Our heuristic, even when allowed to try a large number of times with a different random number seed each time, was unable to find Hamilton paths or cycles in Cay(S7, X7) which has only 5,040 vertices.

We decided to run a simple backtrack algorithm with no pruning or other enhancements as a comparison. This eventually ran for over a year on a 300MHz Intel processor without finding a Hamilton cycle. 

¡¡¡ Un año y no encontraron la solución y eso que son grafos y no dígrafos y tienen más generadores !!!. 

Nota. El problema de recorridos hamiltonianos en grafos es más sencillo que en dígrafos, y más si los primeros tienen más generadores. La prueba es que en la investigación sobre la que hablamos, para dígrafos bigenerados se pararon en S7 pero para grafos cúbicos llegaron hasta S7. Fin de nota.

Nosotros estamos proponiendo una serie de tests que para un tipo de dígrafos  y con menos generadores (bigenerados), y por lo tanto más complicados, que pueden ahorrar similar tiempo computacional, y el examinador considera que son meras ideas abstractas, que se agotan en si mismas, sin ningún impacto práctico.  

Siguiendo con la tesis, luego aplican otro algoritmo diferente, también con poco éxito: 

Although we had some success with smaller graphs generated by three involutions, this code was still problematic when graphs contained a couple of thousand vertices.

Finalmente comentan sobre la investigación sobre la que estamos hablando nosotros. 

At about this time Effler and Ruskey [36] started cataloging results for isomorphism and Hamiltonicity of Cayley graphs. They had confirmed that all but two of the cubic Cayley graphs on the alternating group, A7, with generators from S7 were Hamiltonian. They had spent thousands of hours of computer time on one of these using algorithms that had succeeded on similar graphs without finding a Hamilton cycle and were about to embark on an exhaustive search on a supercomputer.

We were invited to try our algorithm on these graphs. The graph A7 has 2520 vertices and the first set of generators was (0)(1)(2)(3, 4)(5, 6) and (0, 1, 2, 3)(4, 5)(6).

Vandegriend [107] had investigated the performance of several different Hamilton cycle algorithms on a variety of graphs with up to 1,000 vertices. One of the algorithms used was a backtrack algorithm which used extensive pruning techniques to reduce the size of the search tree. We modified this code to use dynamically allocated data structures so that we could handle larger graphs than those studied by Vandegriend without needing compiled maximum graph sizes. We also added code based on our existing code to handle generation of permutation groups using three involutions or an involution and another generator and its inverse (por lo tanto son grafos).

We used this modified code to show that several Cayley graphs generated by three involutions, no two of which commuted, were Hamiltonian. Although we had some success with smaller graphs generated by three involutions, this code was still problematic when graphs contained a couple of thousand vertices. Nevertheless, we were able to answer some previously unsolved questions as we shall see in Section 6.2.3

We made further modifications to the Vandegriend code to handle graphs generated by one involution and one non-involution. Using this version of the Vandegriend algorithm we found a Hamilton cycle within a minute or so of computation time.

Effler and Ruskey had also been unable to find a Hamilton cycle in the Cayley graph of A7 generated by (0)(1)(2)(3, 4)(5, 6) and (0, 3)(1, 4, 2, 5)(6). Again, the modified Vandegriend code found a Hamilton cycle within a minute or so of computation time.64

Nevertheless, the Vandegriend algorithm slowed down significantly on larger problems. For example, we did not find a cycle using this algorithm on the graph with 2520 vertices generated by the involution (03)(14)(25)(6) and the element (0)(1)(2)(3456) and its inverse which is result 7.294 in the table of Effler and Ruskey (Section 6.4).

Ciertamente un minuto es bastante notable para estos tamaños incluso tratándose de grafos y con más generadores que con los que trabajamos nosotros, lo cual por tener más grados de libertad hace mucho más sencilla su búsqueda.

Y seguramente son smooth, (lo comprobaré). De confirmarse ésto, repetimos que nosotros con nuestro test de smoothness, que se ha incluido en una de las reclamaciones de la solicitud de patente, podríamos haber confirmado la propiedad de hamiltonicidad, de manera no constructiva, de estos y tamaños mucho mayores mucho más rápidamente que en un minuto (milisegundos). Sin embargo el examinador considera que se trata de un test abstracto al que un diseñador no le va a sacar partido. Un ahorro de un año o  más no es práctico. Para un examinador, claro

Si queremos ser constructivos, los smooth son casos en los que que una adaptación de nuestro algoritmo a una heurística casi greedy puede funcionar correcta y rápidamente.

Y ya que hablamos de eficiencia, aprovechamos para recordar una vez más que la implementación de nuestro método no está optimizada. La programé yo. Era mi primer programa y búscaba más la sencillez de programación que la eficiencia. Por ejemplo utilizamos matrices para representar a los dígrafos, que para más inri son muy sparse. También nos interesaba encontrar los recorridos sí o sí sin posibilidad de errores, con lo cual la versión implementada del algoritmo es superfiable, una versión en la que por ejemplo en cada pasada se comprueban todos los IASes. Esto en realidad no es necesario, incluso manteniendo la condición de determinismo, es decir sin pasar a heurística, hasta que ya hay muchos IASes marcados. Con éstos breves comentarios cualquier experto ya se dará cuenta del recorrido que hay para optimizar nuestro método. Finalmente como señalan para casos de tamaño un poco mayor éste algoritmo de Vandegriend ya falla (ya no es tan eficiente, tarda un tiempo eterno; típico de los  métodos generales).

De cualquier manera ésta tesis de Shield que ya conocía es también muy interesante, así como la tesis de Vandegriend, que también conocía y creo recordar que aplica un algoritmo mucho más general que el nuestro. Su uso en éste contexto entra dentro de la estrategia de aplicar algoritmos genéricos que hemos citado antes.

Actualización. Ya tengo una copia de la tesis de Vandegriend. Confirmo que trata de algoritmos (o de heurísticas) de carácter general. Estoy preparando una entrada sobre algoritmos (heurísticas) genéricos para el problema de recorridos hamiltonianos. Fin actualización.

Finalmente comento que no conocía sin embargo el trabajo de Sjerve y Cherkassoff. Paso a intentar encontrarlo. Estaba precisamente leyendo esta mañana un artículo de Gross titulado Imbeddings of Metacyclic Cayley Graphs. Relacionado del mismo autor: A determination of the toroidal k-metacyclic groups. Realmente estos resultados tienen un interés relativo pues estudian el empotrado en superficies de grafos de Cayley, y les interesa la superficie mínima en la que se pueden empotrar todos los grafos de Cayley: The genus of a graph is the minimum of the genera of the orientable surfaces on which the graph can be embedded; the genus of a finite group the minimum of the genera of the Cayley graphs of the group. (To find the genus of a finite group, it suffices to consider only irredundant Cayley graphs.) The nonorientable genus of a graph or of a group is defined similarly. Por lo tanto son excesivas para nuestras necesidades.

Fin de nota.

Tras el  trabajo de matemática o ingeniería experimental de estos dos autores, que se tuvieron que detener en casos del tamaño de 720 vértices e incluso  en estos tamaños no resolvieron todos los problemas, ya había información suficiente para, utilizando conjuntamente otros resultados, hacer importantes avances en éste problema (como pone de manifiesto nuestra propia investigación; como no solo no lo dice nadie, sino que ni siquiera un examinador de la USPTO al que se supone experto en éstos temas es capaz de valorarlo, no me queda más remedio que decirlo yo; pido disculpas por ello) hasta el punto de que la investigación sobre el problema de recorridos hamiltonianos en Dígrafos de Caley Bigenerados, aunque todavía quedan casos abiertos (al menos para mi), ya está bien encauzada.

1.2. Misma información, resultados dispares.

Cabe preguntarse por qué estos dos autores no fueron más allá en lo teórico teniendo  información experimental suficiente. Espero que el lector no vea en éstas líneas un ejercicio de vanidad sino un intento de explicación del porqué investigadores diferentes que trabajan aproximadamente con la misma información y que son más o menos iguales en competencias (salvo casos extremos, ninguna mente humana es superior a otra), llegan a resultados dispares, en un caso que conozco de primera mano.

En mi modesta opinión ésto obedece al menos a cuatro motivos (al margen de que seguramente tampoco era ésto el objetivo de su investigación) y si los autores leen ésto (no creo, hablan otras lenguas), que me corrijan.

El primer motivo es que investigaron sólo el problema de los ciclos hamiltonianos. Si uno se fija sólo en éste problema y no incluye en su foco el problema de los caminos hamiltonianos, está ya en un enfoque teórico nebuloso, que no le va a permitir ver determinadas cosas. Por determinadas razones a mi me interesaban los recorridos en general,  y nunca he entendido la obsesión de la comunidad de investigadores por los ciclos.

Segundo, desconocían que en todos los casos no abelianos el IAS es siempre regular (regularidad según la definición de la  patente). El concepto de arc-forcing que lleva a la construcción del IAS ya existía para tanto abelianos como para no abelianos (no es evidente pero se llega a él fácilmente en cuanto que cualquiera intenta aplicar un mínimo de lógica al problema y muchos investigadores lo habían utilizado). Pero en el caso de los abelianos el IAS no permite  una descomposición del dígrafo en IASes que  sea visualmente informativa cuando los dígrafos se dibujan fijando el foco en los IASes y DASes y no en otros parámetros.

Tercero, relacionado con los dos anteriores, no conocían (de nuevo especulo, no  me consta, pero el caso es que creo recordar que no los citan) en primer lugar el resultado de los Vértices finales posibles (si les interesaban sólo los ciclos y no los  caminos, no podían conocerlo; lo descubrió y publicó primero un autor, seguramente luego otros y mucho más  tarde el que escribe éstas líneas; la demostración de la primera publicación es algebraica, del tipo de las que no comprende ni el tato, diferente a la mía, que he convertido en paso del método y he incluido en una reclamación de la segunda solicitud de patente) ni la generalización del  teorema de Rankin a caminos hamiltonianos. Esta generalización, que yo redescubrí bastante posteriormente (aunque de manera independiente) de otro autor, era y es, creo, bastante desconocida. Pero su combinación con la regularidad del IAS y lo que tratamos en el siguiente motivo son muy potentes de cara a descubrimientos.

Y cuarto, como el dibujo de los casos no era suficientemente informativo, se centraron casi exclusivamente (y aquí estoy especulando completamente) en métodos computacionales. La base de datos que elaboraron, repito que impresionante, pero conteniendo sólo ciclos, sin dibujos de casos significativos, no era informativa de cara a descubrimientos teóricos, no podía llevarles muy lejos.

Seguramente nunca tendrá la oportunidad, pero me gustaría cambiar impresiones al respecto con éstos dos investigadores. Yo, tras representar gráficamente de manera manual bastantes Dígrafos de Cayley sin tener en cuenta el tema del IAS regular, el resultado de los vértices finales posibles y el teorema de Rankin para caminos, salí de la completa oscuridad, vi la luz, pasé del caos al cosmos, sólo cuando encontré, no recuerdo muy bien como, primero el resultado de los vértices finales posibles en un caso no abeliano de IAS de orden 2, y luego en secuencia vi que se podía generalizar a cualquier tamaño y finalmente vi (es fácil demostrarlo) que todos los no abelianos tienen necesariamente un IAS regular. A partir de ese momento y solo a partir de ese momento es cuando, empecé a dibujar los dígrafos con el enfoque del IAS, a verlos de ésta manera  y a hacer avances.

Y por ser tan informativos para el investigador, he incluido en las reclamaciones la propiedad de regularidad del IAS y el resultado de los vértices finales posibles. El conocerlas es básico y supone un ahorro brutal pues ambas, me repito aportan al investigador informaciones clave. Pero el examinador entiende que son meras ideas abstractas que se agotan en si mismas sin ninguna practicidad. A lo mejor es necesario perder varias tardes representando gráficamente Dígrafos visualmente sin sentido o buscando recorridos hamiltonianos en vértices que no pertenecen al conjunto de vértices posibles en Dígrafos de 120 vértices para darse cuenta del valor informativo de estos dos resultados.   

También cabe preguntarse por los dos autores (me centro en ellos dos pues muchos otros que han estudiado éste problema se interesaban más por grafos que por dígrafos), que aparentemente sí se interesaron por todo tipo de recorridos hamiltonianos (ciclos y caminos) en Dígrafos de Cayley bigenerados, tenían un enfoque más teórico y tenían los avances necesarios (el resultado sobre vértices finales posibles y la generalización del teorema  de Rankin para caminos; no he visto que enunciasen, al menos explícitamente, el resultado de IAS regular para casos no abelianos y abelianos con unos parámetros muy específicos; y creo que los dos conocían a los dos resultados mencionados) para ir más allá. Uno de ellos aparentemente (y lamentablemente pues fue el  primero que encontró el resultado sobre vértices finales posibles conjuntamente con otros resultados, y seguramente hubiese  obtenido más resultados de haber continuado su carrera en este campo; el artículo enlazado es el único publicado por éste autor en éste campo y se centra en una cota superior para contar recorridos hamiltonianos en Dígrafos de Cayley bigenerados: la que divide el orden del grupo por el orden del IAS)  dejó la investigación. El otro investigador siguió, y ha seguido casi hasta hoy, publicando sobre el problema, siguiendo la linea que hemos comentado antes: estudiar las propiedades ad-hoc de determinados casos y si había suerte utilizarlas para encontrar algún recorrido hamiltoniano o algún resultado de existencia, obteniendo resultados notables (insisto que hay muchos otros investigadores que han trabajado éste problema, de diversas comunidades, mateméticos, ingenieros  etc…pero me centro en éstos dos por lo ya explicado). Realmente a falta de trabajos experimentales (y quizás también por el hecho de que a los matemáticos puros les interesa más los resultados de existencia y no utilizan tanto los resultados experimentales) como los que luego realizaron los dos autores cuyo trabajo hemos reseñado, prácticamente ésta era la única vía de ataque. Desconozco si estos dos autores conocían la investigación experimental sobre la que hablamos y si la utilizaron.

¿ Existe en las ciencias formales como la matemática o las ciencias computacionales la misma complementariedad entre experimento y teoría que existe en las ciencias naturales (muy acusada en física) o son dos corrientes que se dan la espalda ? Lo desconozco. Las opiniones de Zeibelger sobre las matemáticas experimentales son bien conocidas. Una entrevista realizada a éste investigador casualmente por un autor que ha trabajado también en el problema sobre el que hablamos.

Extracto.

Experimental mathematics is a rapidly growing field, both explicitly and implicitly.     Explicitly, there is a very good journal by that name, an Institute in Simon Fraser      University, and at the recent annual meeting at New Orleans there was a special      session dedicated to it. This is a good start, but still at its infancy.      However, implicitly, more and more mathematicians, even pure ones, use the      computer daily to formulate and test conjectures, in a mode that George      Andrews calls "pencil with power-steering". However, more often than not,      the computer's often crucial contribution is not mentioned, or grossly understated. Human beings are such ingrates.

Cerramos ésta introducción repitiendo una vez más lo mismo: sin la investigación experimental de esto dos autores, nosotros no hubiésemos avanzado prácticamente nada.

Nota al margen. un artículo reciente (2012) del que no tenía noticia y acabo de encontrar, sobre recorridos hamiltonianos en un tipo específico de Dígrafos de Cayley, los dihédricos. Lo he hojeado y parece que utilizan una técnica algorítmica basada en el IAS (¿ hay otra posibilidad ?). Título: ON HAMILTON CIRCUITS IN CAYLEY DIGRAPHS OVER GENERALIZED DIHEDRAL GROUPS ADRIAN PASTINE AND DANIEL JAUME ´ Abstract. In this paper we prove that given a generalized dihedral group DH and a generating subset S, if S ∩H 6= ∅ then the Cayley digraph → Cay(DH, S) is Hamiltonian. The proof we provide is via a recursive algorithm that produces a Hamilton circuit in the digraph.

Y una tesis reciente 2009, títulada Shift Gray Codes, en la que hablan del problema en el contexto de la generación combinatoria / códigos de Gray. El capítulo introductorio es interesante, así  como la bibliografía. Hablan de the utility of the reflected Gray code and de Bruijn cycles for n-tuples, as well as the Johnson-Trotter-Steinhaus order for permutations.

Fin de nota.

2. En fin, tras ésta larga introducción nos centramos en el tema principal de la entrada. La base de datos hay en total 227 casos de S6. Por grados:

–grado 6, 84.

–grado 8, 140.

–grado 9, sólo 3 (sólo incluían aquellos casos en los que un generador es una involución; aún así parecen pocos).

De todos estos me interesan:

–aquellos en los que han encontrado ciclos hamiltonianos (importante: ellos sólo buscaban ciclos, no caminos) y por lo tanto entiendo que son fáciles, pero son entangled (y por lo tanto potencialmente difíciles). A estos los llamo raros en el sentido de que los entangled son potencialmente difíciles. Hay 11 de éstos de grado 6, y he contado unos 22 de grado 8. Mañana los comprobaré.

Caso 1. G6, 123465 (orden 2), 234516 (orden 5). IAS, 6.

Caso 2. G6, 124563 (4), 236541 (4). IAS 6.

Caso 3. G6, 132564 (6), 214635 (5). IAS 6.

Caso 4. G6, 132564 (6), 412653 (5). IAS6.

Continuará….

–aquellos en los que no han encontrado positivamente ciclos hamiltonianos y no entran dentro del teorema de Rankin. Son, si no he contado mal, cinco  casos. 2 se pueden explicar por ser cycle entangled, otros dos según anoté son cycle-entangled (mañana lo volveré a comprobar) y en uno no comprobé ésta propiedad (lo comprobaré mañana). Los interesantes son aquellos que no sean ni rankin ni cycle entangled, si finalmente se confirma que hay alguno (podrían ser 3). Habría que analizar sus propiedades.

Continuará….

–aquellos en los que  no han podido decidir si existen o no existen ciclos hamiltonianos (ellos los califican como unknown). Si no recuerdo mal, la mayoría de éstos caen dentro de la categoría de cycle-entangled y gracias a nuestro resultado se puede determinar si los tienen o no los tienen. Me interesa sobre todo si existiese algún unknown  que no sea cycle entangled. Y confirmo que existe alguno.

Continuará….

HPC. Sobre la propiedad de lisura o smoothness en Dígrafos de Cayley Bigenerados: ¿ una caso que la falsifica ?.

junio 25, 2015

Actualizado 27 de junio de 2015, con un resultado de 2013 que utiliza los resultados de la patente para obtener una familia infinita de Dígrafos de Cayley bigenerados que no tienen caminos hamiltonianos. Aunque no lo he mirado en detalle y reservo mi opinión para cuando lo haga, como comento más adelante, aunque a priori éste resultado es interesante (sobre todo porque una de las familias sobre las que hablan en el artículo no está basada en involuciones), conociendo mi método (y sobre todo la teoría implícita en la que se basa), obtener éste tipo de resultados ye a no tiene gran dificultad. Se conoce cuales son los parámetros que hay que tocar. 

La alternativa a usar nuestra teoría y los tests que se derivan de ella serían inviables: al margen de que para tamaños grandes ya sería (posiblemente, ya digo que tengo que mirar el artículo; la familia propuesta podría ser de orden pequeño en relación al IAS y por lo tanto resultar ser computacionalmente fáciles para nuestro método; he visto que incluyen una familia metacíclica y como es sabido estos tienen orden <n(n-1) con n el grado de la permutación) imposible determinar computacionalmente que no existen recorridos hamiltonianos en éste tipo de dígrafos sería imposible, también lo sería poner a prueba un número infinito de dígrafos. Sin embargo el examinador considera que éstos resultados no son más que ideas abstractas, que se agotan en si mismas sin ninguna consecuencia práctica. 

Nota inicial. Como puede ver el lector, se me acumula el trabajo. Esto es lo que tiene el ser  un investigador independiente… :-(. No solo tienes que hacer tu todo el trabajo sino que  te  dan golpes por todas partes, los examinadores incluidos. Como en anteriores entradas distingo por  el color del texto la parte meramente técnica (color negro)  de la indignada (color rojo). La asignación de colores es puramente casual.  

Resuelto: el caso es twisted, no hay falseamiento, no podía haberlo.

En las anteriores entradas hemos hablado mucho de la propiedad de entrelazado o entangled ya que permite identificar casos potencialmente difíciles. Hay otra propiedad que nos permite afinar más: la de lisura o smoothmess, y sobre ella hablamos en éste punto.

I. La propiedad de lisura o smoothness.

Por definición los  casos en los  que uno de los generadores es de orden 2 son entrelazados. Pero hay muchos casos que siendo un generador de orden 2 y el otro de orden > 2, no son necesariamente difíciles y nos interesa  encontrar otra propiedad que nos permita identificar dentro de éste subconjunto de Dígrafos de Cayley bigenerados a los difíciles.

Para ésto hemos inventado o diseñado la propiedad de lisura o smoothnes. Esta propiedad viene a decir que hay casos  en los que el entorno de la identidad (con una definición muy concreta que se corresponde con un test muy concreto) es liso o smooth. Los que  no son lisos o smooth son retorcidos o twisted  y hacen honor a su nombre pues entre ellos están los casos más complicados.

En esta entrada, algunos ejemplos  gráficos, como el que sigue:

Parámetros: Grado 5, 120 vértices, identidad 12345, generadores 13254 de orden 2 y 24513 de orden 6, IAS de orden 12 (6 vértices finales posibles), Circunferencia de orden 2.

caso twisted

No es smooth ya que si construimos el IAS de la permutación 41324 o el DAS de la permutación 12543, teniendo en cuenta que ambas se encuentra dentro de las permutaciones que se encuentran al aplicar el generador de orden 6 a la identidad, este IAS y este DAS tienen permutaciones en común con los IASes o DASes de permutaciones que se encuentran dentro del IAS o DAS de la identidad. Por esto el entorno de la identidad no es liso.

Este caso es difícil ya que no tiene recorridos hamiltonianos en ninguno de los vértices posibles, excepto en uno. Ya obtuve éste resultado hace años y lo he repetido hoy. Para encontrar el RH en el único vértice que lo tiene ha tardado menos de 1 minuto. Para demostrar que no existe en los otros 5 vértices finales posibles ha tardado: 2 minutos para el primero, 7 minutos para el segundo, 5 minutos para el tercero, el cuarto es el que tiene RH, 2 minutos para el quinto y un minuto el sexto. Nótese que el método, aunque rápido es exhaustivo (y por lo tanto 100% fiable), es decir es el backtraking determinista más optimizado posible para éstos casos (Dígrafos de Cayley bigenerados) y que para casos de mayor tamaño (por ejemplo de 1000 o 10.000 vértices), seguramente ya sería poco práctico (en mis condiciones, ya comentadas en otras entradas digamos que tardaría no toda la vida del universo pero sí días o semanas; es suposición no lo he puesto a prueba; quizás en otras condiciones, la frontera de los casos difíciles en los que no merece la pena ni intentarlo sea más elevada, entre 10.000 y 100.000). ¿ Por otra parte tiene sentido  esta variación en el tiempo en función del vértice final ?. Si, tiene sentido, sobre todo aunque no solo, en los casos en los que un generador es una involución o de orden 2.

Pero precisamente por haber casos difíciles de este tipo es muy relevante desde el punto de vista práctico, para por ejemplo un diseñador de redes de interconexión, disponer de tests que nos permitan cribar los casos complicados de los tratables y dedicarnos a éstos últimos, siempre y cuando cumplan con otros parámetros que nos interesan. La diferencia está entre poder investigar o no poder investigar, por ser los tiempos prohibitivos.

Leer el resto de esta entrada »

HPC. La versión paralela del método de la patente US 8266089.

junio 25, 2015

La paralelización del método de la patente US 8266089 es evidente para cualquiera skilled in the art e igual no hacía falta publicar nada al respecto (como se verá es prácticamente idéntico al método secuencial, iniciando varios hilos en paralelo que implementan éste, intercalando en cada etapa la subrutina que ya existe de coherencia gloabal). Pero en caso de que el lector se quiera ahorrar el mínimo esfuerzo que pueda requerir el obtener una idea de la versión paralela, lo hacemos nosotros por él.

La versión paralela ya está en formato papel y se publicará en breve en el blog.

Se pueden paralelizar varios pasos del método. Adelantamos la idea principal de la fase de búsqueda una vez que ya está construido el dígrafo y el conjunto de IASes, una vez que el vértice final e inicial ya están marcados, que se ha activado el IAS inicial y se han extraído todas las consecuencias de ésta activación. Quede claro que todas éstas operaciones iniciales también se pueden paralelizar. En lo que sigue nos centramos en la aplicación a un caso smooth.

En la patente, una vez realizados los pasos preliminares, hemos planteado una búsqueda secuencial: elegir la primera opción (primer arco), sacar las consecuencias correspondientes de ésta primera opción (activar los IASes correspondientes a éste arco, comprobar que al marcar éste arco o los de  sus IASes correspondientes no se genera ni un ciclo no hamiltoniano ni un camino no hamiltoniano que comience por el vértice final y termine en el vértice inicial), elegir la segunda opción (marcar el segundo arco), sacar las consecuencias correspondientes a ésta segunda opción etc…

La alternativa paralela, tras la fase inicial, consiste en elegir varias opciones a la vez (marcar varios arcos iniciales, uno del vértice inicial, otro del vértice final y otros elegidos, por ejemplo al azar o de otro modo, con elecciones equilibradas entre los dos generadores en función de su orden, más de los de mayor orden; independientemente de la manera de elegirlos lo mejor es que estén distribuidos de manera espaciada en el dígrafo) en paralelo de manera independiente, a la vez, y extraer las consecuencias de cada una de las elecciones. En general, si el dígrafo es grande y smooth (como estamos suponiendo) y los arcos elegidos se han espaciado, las consecuencias serán locales y compatibles entre ellas hasta que se hayan marcado una mayoría de arcos.

En cualquier caso se debe de añadir  una subrutina (que de alguna manera ya se aplicaba en el en el algoritmo secuencial, y vale la misma (paralelizada), que se podrá incluir desde el principio tras las primeras elecciones paralelas o más adelante, en el  momento en el que se considere que ya hay una cantidad crítica de arcos marcados como para que emerjan contradicciones entre las elecciones), una subrutina decimos que haga una comprobación global de que estas activaciones de arcos o elecciones son compatibles entre ellas, que no generan contradicción y si generasen contradicción marcar otros arcos alternativos tal que se eviten  éstas contradicciones.

Hay que determinar cual es el número óptimo de opciones que se puede marcar a la vez en el primer ciclo o etapa. El equilibrio está en que al marcar un número determinado de opciones en paralelo no se pierda luego más tiempo en aplicar la subrutina  que las haga compatibles.

Cada arco marcado inicialmente en esta primera etapa genera un hilo paralelo,  y a cada uno de éstos hilos se empieza a aplicar el algoritmo secuencial de manera independiente, eligiendo opciones y extrayendo las consecuencias de éstas, alternando en cada etapa la subrutina de coherencia global (que de alguna manera ya se hacía en el algoritmo secuencial).

Al final el resultado es el mismo que el algoritmo secuencial o se obtiene un recorrido hamiltoniano o la prueba de que éste no existe. Por supuesto con ésta paralelización, se acelerará brutalmente el proceso de búsqueda de soluciones.

Entrada comenzada en la fecha de publicación y actualizada el día 26 de junio de 2015 a las 21:00.


Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.