El dogma central de la biología molecular, propuesto por Francis Crick en 1958, reza que todo gen (codificante) se transcribe en ARN mensajero que se traduce en una proteína. Hoy sabemos que las cosas nunca fueron tan sencillas. Un estudio del ADN de la levadura de la cerveza (S. cerevisiae) ha mostrado que, aunque contiene unos 6000 genes codificantes de proteínas, produce 1,88 millones de transcritos de ARN. Estas moléculas de ARN se llaman isoformas de transcripción (TIF por sus siglas en inglés) y tienen diferentes secuencias de inicio (5′) y final (3′). ¿Cuál es su función biológica? Lo más fácil es decir que su papel es regular la expresión de otros genes, pero esta función ha sido demostrado sólo en unos cientos de casos. La mayoría de los TIF podrían no tener ninguna función biológica, siendo un subproducto irrelevante de la maquinaria de transcripción. ¿Podrían tener algún papel en la evolución? Como es obvio, el contenido de TIF en un momento dado de una célula dentro de una población la diferencia de todas las demás y quizás podría proporcionarle la oportunidad de estar mejor adaptada a cambios en su entorno. Quizás esta gran diversidad de ARN transcritos sea una de las razones por la que es difícil matar a todas las células cancerosas de un tumor. Así finaliza su News & Views, cuyo titulo he copiado, B. Franklin Pugh, ”Molecular biology: The ends justify the means,” Nature 497: 48–49, 02 May 2013, quien se hace eco del artículo técnico de Vicent Pelechano, Wu Wei and Lars M. Steinmetz, “Extensive transcriptional heterogeneity revealed by isoform profiling,” Nature 497: 127–131, 02 May 2013.
Archivo de la categoría: Informática
El “arte” de la filogenética molecular
Cuando se habla de artes y ciencias (Arts & Sciences) la ingeniería se encuentra justo en la mitad, siendo en muchos casos arte y ciencia a partes iguales. Los algoritmos bioinformáticos utilizados en biología molecular para obtener un árbol filogenético son muy sencillos, pero la práctica del “arte de la filogenética molecular” sólo se aprende con la experiencia. Un buen arbol filogenético depende de qué genes (o secuencias dentro de ellos) se seleccionen y alineen, y de cómo se estime el efecto del entorno y de la evolución por selección natural en los organismos estudiados. Para el experto no hay ningún problema, por eso es un experto, pero la situación para el profesor que tiene que enseñar este arte no es fácil, pues incluso un gran “artista” puede que no sepa explicar de forma adecuada cómo decide cuando su obra es “perfecta” y está acabada. Un análisis filogénetico de 1070 ortólogos de 23 genomas de levadura ha permitido obtener 1070 árboles filogenéticos diferentes. ¿Cuál es el mejor entre todos ellos? ¿Existe el árbol filogenético óptimo? ¿Cómo debe lidiar el filogenetista molecular con este problema? Supongo que pensarás que me como mucho el coco, pero al menos no soy el único: Leonidas Salichos, Antonis Rokas, “Inferring ancient divergences requires genes with strong phylogenetic signals,” Nature 497, 327–331, 16 May 2013. Por cierto, los algoritmos bioinformáticos de filogenética molecular son parte del contenido que imparto a mis alumnos. ¡Cosas bolonias!
PS (17 mayo 2013): Por cierto, dos genes de dos especies de seres vivos son ortólogos si su origen evolutivo es un único gen de un ancestro común a ambos. La aplicación a los 1070 árboles filogenéticos diferentes obtenidos de las técnicas de bootstrap y de selección de árboles de consenso reduce las incongruencias, pero en ningún caso logra que en todos los nodos se supere un consenso del 50%. Más aún, cientos de estos árboles filogenéticos muestran “errores graves” agrupando especies “lejanas” como si hubieran divergido hace muy poco.
Simulación numérica multiescala de las burbujas de la espuma
La belleza de la espuma bajo luz diurna es indudable, pero el estudio mediante ordenador de la evolución (reología) de cada una de las membranas líquidas (películas de jabón) que la forman no es nada fácil pues involucra escalas en espacio y tiempo que varían en seis órdenes de magnitud. Se publica en Science un nuevo modelo matemático que permite una simulación multiescala de gran precisión basada en tres etapas: en la primera se calcula la solución de equilibrio estático, en la segunda se estudia el drenaje del líquido a través de las membranas y las fronteras entre ellas, y en la última se calcula la posible rotura en las zonas más delgadas de las películas de fluido. Este proceso se repite de forma iterativa. El resultado es una simulación sin precedentes de la evolución de la espuma lejos del equilibrio. Las espumas tienen una gran variedad de aplicaciones en la industria y en el diseño de materiales. Por ello, la simulación multiescala de su física promete importantes repercusiones prácticas. Nos lo cuenta Denis Weaire, “A Fresh Start for Foam Physics,” Science 340, 693-694, 10 May 2013, que se hace eco del artículo técnico de Robert I. Saye, James A. Sethian, “Multiscale Modeling of Membrane Rearrangement, Drainage, and Rupture in Evolving Foams,” Science 340: 720-724, 10 May 2013.
Nota dominical: El problema del viajante
El problema del viajante consiste en encontrar el camino más corto que permite visitar una serie de ciudades conectadas por carreteras volviendo al punto de partida y visitando cada ciudad una sola vez. No hay ningún algoritmo eficiente para resolver este problema (que es NP-duro [1]). En 1950 los ordenadores permitían resolver un problema con 50 ciudades, en 1980 con unas 2300 ciudades y en 2006 se alcanzó el récord actual, 85900 ciudades (en la figura aparecen 13509 ciudades de EEUU). Los informáticos han tratado de descubrir algoritmos eficientes que aproximen la solución del problema. En 1976, Nicos Christofides (Imperial College, Londres) desarrolló un algoritmo eficiente que produce caminos cuyo coste excede al óptimo en menos del 50% [2]. ¿Se puede mejorar? En 2011, se logró mejorar el algoritmo de Christofides con un nuevo algoritmo eficiente que excede del óptimo en menos del 49,99999999999999999999999999999999999999999999999996 por ciento [3]. ¿Por qué ha costado tanto obtener una ventaja tan pequeña? Nadie lo sabe, pero resulta muy sugerente. Nos lo cuenta Erica Klarreich, “Computer Scientists Take Road Less Traveled. After decades without progress, new shortcuts are discovered in the traveling salesman problem,” Simons Foundation, Jan 29, 2013.
Referencias
[1] Richard M. Karp (Univ. California at Berkeley), “Reducibility among combinatorial problems,” pp 219-241 in “50 Years of Integer Programming 1958-2008,” Springer, 2010 [free pdf].
[2] N. Christofides, “Worst case analysis of a new heuristic for the traveling salesman problem,” Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1976.
[3] Shayan Oveis Gharan, Amin Saberiy, Mohit Singh, “A Randomized Rounding Approach to the Traveling Salesman Problem,” IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), 2011, pp. 550-559 [free pdf].
¿Quién inventó el “doble click” con el ratón?
Julián Estévez (@Jeibros) preguntó “¿quién inventó el doble click?” y Ramón Ordiales (@ramoneeza) contestó “el Doble Click es de Microsoft” citando a NewScientist: Microsoft lo patentó el 27 de abril de 2004. Pero yo expliqué a mis alumnos c. 1998 el “Double clicking” del lenguaje Squeak, desarrollado por AT&T Bell Laboratories. De hecho, yo les dije a mis alumnos que el doble click lo inventó William M. Newman (quizás les engañé, pues ahora compruebo que el artículo original de Newman “A system for interactive graphical programming,” de 1968, solo menciona el click, pero no el doble click). Seguramente, el doble click fue inventado por Xerox a finales de los 1970, pero no he encontrado ningún artículo que lo atestigüe. En el artículo de NewScientist se menciona que “Hartmut Pilch apunta que la patente de Microsoft debería ser revocada porque seguro que la idea del “doble click” ya existía antes de 1997 cuando la patente fue solicitada.” Repito, lo más antiguo que un torpe como yo ha encontrado ha sido 1985, pero estoy seguro que a finales de los 1990 cuando yo dije que lo había inventado Newman debía ser porque lo había leído en algún sitio (torpe de mí que ahora soy incapaz de encontrarlo).
“Double clicking. As an example of a Squeak program using timeouts, consider the problem of detecting clicks (mouse button down and up again in a short time) and double clicks (two clicks separated by a longer but finite time) without losing any button transitions.” Pág. 201, SIGGRAPH ’85.
Por supuesto, alguien dirá en los comentarios que lo que Microsoft ha patentado es la semántica (qué hace Windows tras un doble click). Pero mi memoria me debe fallar, pero puedo asegurar que yo eso también lo leí en papel en un artículo de finales de los setenta. Seguramente, mi memoria me falla.
Resolviendo laberintos utilizando el programa Paint
Trata de resolver este laberinto (la entrada está en el lateral derecho, en la parte de arriba, y la salida en el lateral inferior, a la derecha). Imagina que copias esta figura en un programa de dibujo (como Paint de Windows). ¿Cómo podrías resolver este laberinto utilizando dicho programa? Piensa un poco, porque es muy fácil. Si al final no logras resolverlo, sigue este enlace para ver la solución. Por supuesto, este método gráfico es muy viejo, fue publicado por E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik 1: 269-271, 1959 [copias gratis en pdf]. Quien prefiera una explicación for dummies (de donde he sacado este ejemplo) y una implementación en Matlab preferirá leer a Cris Luengo, “Solving mazes using image analysis,” Cris’s Image Analysis Blog, April 17, 2010.
PS: Quien quiera probar que el método funciona, en lugar de usar el laberinto en JPG como aparece en la entrada, debería utilizar la versión en PNG (sigue este enlace) [solución en PNG].
La empresa D-Wave inventa la espectroscopia túnel para verificar que sus ordenadores son cuánticos
La compañía canadiense D-Wave afirma que ha fabricado un ordenador cuántico de 512 cubits, que se pondrá a la venta durante este año y que ejecuta ciertos algoritmos con cientos de bits unas diez mil veces más rápido que su análogo clásico. El ordenador utiliza la llamada computación cuántica adiabática. Muchas voces han criticado a D-Wave por no demostrar de forma rigurosa el funcionamiento cuántico de sus ordenadores. Los científicos de D-Wave han desarrollado una nueva técnica para verificarlo, llamada espectroscopía túnel, que han publicado en Physical Review B. En una conferencia en Londres el pasado 6 de marzo han afirmado que dicha técnica ha sido aplicada a grupos de hasta 8 cubits de su ordenador “cuántico” demostrando que se comportan de forma cuántica durante la ejecución de sus algoritmos. Los resultados aún no han sido publicados. Obviamente, no es lo mismo demostrar el comportamiento cuántico de 8 cubits en un ordenador de 512 cubits, que hacerlo con todos los 512 cubits, pero se trata de un paso importante cuyo objetivo es acallar a la mayoría de las voces críticas. D-Wave tiene financiación de grandes empresas, como Google, y su objetivo es la vía rápida de los inventores (construir un prototipo y demostrar que funciona), en lugar de la línea lenta de los científicos (estudiar el diseño apropiado antes de construir nada). Me enteré de la conferencia en Londres gracias a Jacob Aron, “Controversial quantum computer aces entanglement tests,” NewScientist, 08 March 2013. El artículo técnico que describe la técnica de espectroscopia túnel es A. J. Berkley et al., “Tunneling spectroscopy using a probe qubit,” Phys. Rev. B 87: 020502(R), 2013 [arXiv:1210.6310]. No me he hecho eco antes de este trabajo pues esperaba la publicación de los resultados de la aplicación de esta nueva técnica, pero por lo que parece se van a retrasar (aún no hay fecha, que yo sepa).
Más sobre D-Wave en este blog:
El ordenador “cuántico” canadiense de 128 cubits de D-Wave Systems (25 marzo 2012)
Por primera vez en la historia se vende un ordenador cuántico “D-Wave One” (6 junio 2011)
Inaudito, D-Wave Systems logra publicar un artículo en Nature (13 mayo 2011)
Tras Orion, Rainier, un ordenador cuántico adiabático de D-Wave Systems de 128 cubits (18 mayo 2009)
Los beneficios cognitivos de jugar a videojuegos violentos
Los videojuegos violentos (como Call of Duty o Unreal Tournament) se asocian a efectos negativos, como la obesidad, la agresividad, el comportamiento antisocial e incluso la adicción. Sin embargo, los neurólogos afirman que también tienen efectos beneficiosos en el cerebro, como aumentar la función de ciertas regiones del encéfalo y mejorar el bienestar general. Muchas habilidades cognitivas se refuerzan gracias a su entrenamiento continuo mientras se juega a este tipo de videojuegos, como la habilidad para ver pequeños detalles dentro de un conjunto desordenado de objetos, la capacidad para distinguir tonos de gris con mayor precisión, la de explorar entornos complicados o la de girar objetos tridimensionales complicados con la imaginación. Estas habilidades pueden ser útiles en muchas profesiones, como el diseño de compuestos químicos, la arquitectura o los servicios de rescate y emergencias. ¿Se pueden diseñar videojuegos para reforzar el aprendizaje controlado de ciertas habilidades cognitivas? Nos lo cuentan Daphne Bavelier, Richard J. Davidson, “Brain training: Games to do you good,” Nature 494: 425-426, 28 Feb 2013.
El centro de procesado de datos del CERN supera los 100 petabytes (75 PB en los últimos 3 años)
Los informáticos del CERN han anunciado hoy que su Centro de Datos (CERN Data Centre) ha superado los 100 petabytes (PB) de datos físicos almacenados en los últimos 20 años, de los que 75 PB corresponden a datos del LHC (Large Hadron Collider) obtenidos en los últimos 3 años. ¿Cuánto son 100 PB de datos? Cien millones de gigabytes (GB), más o menos unos 700 años de vídeo a calidad full HD, o unos 21 millones de DVD (cada uno de 4,7 GB); como un DVD tiene un grosor de 1,2 mm, apilados uno encima de otro (sin caja) formarían una torre de 25,5 km de altura. En el CERN, unos 88 PB están almacenados en cinta (sistema CASTOR, por CERN Advanced Storage system), aproximadamente 52 mil cintas de capacidades unitarias entre 1 y 5,5 terabytes (TB); el resto (unos 13 PB) están almacenados en disco duro (EOS Disk Pool System), para su acceso rápido por usuarios concurrentes (hay unos 17 mil discos conectados a 800 servidores de disco). Todo el sistema de almacenamiento está robotizado y distribuido entre dos edificios (se cuenta con 52 mil cintas con una capacidad cada una entre 1 y 5,5 terabytes). Más información en Cian O’Luanaigh, “CERN Data Centre passes 100 petabytes,” CERN News, 14 Feb 2013, y en Ashley WennersHerron, Kelly Izlar, “Achievement unlocked: 100 petabytes of data. Experiments at the Large Hadron Collider reached a milestone in data collection just before the accelerator’s last collisions of the next two years,” Symmetry Breaking, Feb. 13, 2013.
Un vídeo del BSC sobre el corazón latiendo gana un concurso de la revista Science y la NSF
Este vídeo de Guillermo Marín, Fernando Cucchietti, Mariano Vázquez y Carlos Tripiana, afiliados al Barcelona Supercomputing Center, ha ganado el 2012 International Science Visualisation Challenge, concurso de la revista Science y la NSF (National Science Foundation) de EEUU. El vídeo titulado “Alya Red: A Computational Heart” presenta una simulación por ordenador tridimensional de un corazón latiendo. Aunque está en inglés, como debe ser, puedes elegir subtítulos en español, ¡qué lo disfrutes!
Más info en Special Feature on 2012 International Science & Engineering Visualization Challenge, Science, Feb 1, 2013, y Video winners, Science 1 February 2013.
JAABA, un etólogo automático que anota comportamientos animales en vídeos de laboratorio
Los naturalistas, como Félix Rodríguez de la Fuente, y los etólogos, como Konrad Lorenz, estudian el comportamiento animal buscando conductas y pautas innatas o aprendidas de diferentes especies. Una vez han determinado las más comunes (de agresividad, apareamiento, desarrollo, vida social, impronta, etc.) para una especie concreta, se pasan horas y horas observándolas una y otra vez, repetidas hasta la saciedad, buscando comportamiento atípicos o excepcionales de gran valor documental. En la Naturaleza parece difícil sustituir a una persona, pero en un laboratorio se puede utilizar un software de análisis de vídeo que busque los dichos comportamientos, como JAABA (Janelia Automatic Animal Behavior Annotator), que es open source. El investigador anota cada comportamiento en una serie de vídeos que sirven para entrenar un sistema de aprendizaje que más tarde se encargará de buscar dichos comportamientos en nuevos vídeos de forma automática. El sistema puede detectar comportamientos no anotados, quitando la paja y guiando al investigador directamente hacia los más interesantes o novedosos. El siguiente vídeo de youtube describe cómo funciona el sistema, que se ha publicado en Mayank Kabra, “JAABA: interactive machine learning for automatic annotation of animal behavior,” Nature Methods 10: 64-67, Jan. 2013.
Nota dominical: Richard Feynman, los ordenadores y los métodos numéricos
El interés de Richard P. Feynman en los ordenadores y en los métodos numéricos nació durante la Segunda Guerra Mundial, cuando estaba en Los Alamos en el Proyecto Manhattan. Hans A. Bethe le encargó coordinar un grupo que realizaría los cálculos para modelar la implosión de una bomba de plutonio. Feynman desarrolló un sistema de “computación paralela” que usaba personas, cada una con una calculadora mecánica, como elementos de proceso. Su interés en los ordenadores se renovó en sus últimos diez años de vida, cuando su hijo Carl se matriculó en informática en el MIT (Instituto Técnico deMassachusetts), llegando a impartir un curso de aplicación de los ordenadores a la física en su propia universidad, el CalTech (Instituto Técnico de California), junto a John J. Hopfield y Carver A. Mead. El doctor Feynman publicó tres artículos sobre ordenadores [1,2].
El superordenador español MareNostrum del BSC retorna al Top50 de los superordenadores

Uno se siente un poco viejo cuando lee el listado Top500 de los superordenadores más poderosos del mundo (Top500 November 2012). Hace 20 años (Top500 June 1993) los superordenadores más poderosos alcanzaban decenas de Gflops (gigaflops, mil millones de operaciones en coma flotante por segundo), ahora superan la decena de Pflops (petaflops, mil billones de flops). MareNostrum (BSC-CNS, Barcelona Supercomputing Center, Centro Nacional de Supercomputación) sigue siendo el gran superordenador español, pero solo ocupa un honroso trigésimo sexto (36) puesto con 0,64 Pflops (su pico es 0,70 Pflops). MareNostrum 3 (la tercera actualización) está en construcción y solo el 70% está en funcionamiento; finalizará a principios de 2013 y logrará superar 1 Pflops, lo que nos hará ganar unos pocos puestos en junio de 2013. “El objetivo de MareNostrum no es ocupar un lugar destacado en el Top500, sino ser una herramienta útil al servicio de la comunidad científica española y europea,” en palabras de Mateo Valero, director del BSC-CNS. La crisis nos pasa factura a todos y MareNostrum 3 supone una inversión de 22,7 millones de euros (financiados por el Estado y Fondos FEDER).
Qué lejos queda noviembre de 2004, cuando MareNostrum era el superordenador más poderoso de toda Europa y ocupaba el cuarto puesto en el Top500; en junio de 2005 bajamos al quinto puesto, en noviembre de 2005 al octavo y en junio de 2006 abandonamos el Top10. Pero había que recuperar posiciones y en noviembre de 2006 retornamos con MareNostrum 2 y nuevos bríos al quinto puesto, para bajar al noveno en junio de 2007. La crisis económica nos ha hecho caer en picado hasta el puesto centésimo septuagésimo séptimo (177) en junio de 2012. Ahora mismo, el 70% de MareNostrum 3 ocupa el puesto duodécimo (12) de toda Europa. Hay 15 superordenadores europeos entre los primeros 50 puestos.
MareNostrum 3, fabricado por IBM, incorporará 6.000 chips Intel SandyBridge de 2,6 GHz, cada uno de ellos con 8 procesadores y una memoria total de casi 100 TB en 120 metros cuadrados. Su consumo será un 28% superior al MareNostrum 2, mientras que la potencia de cálculo se multiplicará por 10,6. El primer MareNostrum contaba con una capacidad de cálculo de 42,35 Tflops (teraflops) y fue actualizado en 2006 hasta los 94,21 Tflops. MareNostrum 3 tendrá una capacidad superior a 1 Pflops. Más información en “La nueva versión de MareNostrum multiplicará por 10 su capacidad de cálculo,” BSC, 9 Nov 2012.
El primer ordenador capaz de superar un Pflops fue Roadrunner (LANL, Los Alamos National Laboratory), en 2008, que ahora está relegado al puesto vigésimo segundo. En Los Alamos no tenían bastante y adquirieron un segundo ordenador en la escala de los petaflops, Cielo (bonito nombre en español), pero también está relegado al décimo octavo puesto. El primer puesto en el Top500 (noviembre 2012) lo ocupa Titan (ORNL, Oak Ridge National Laboratory), con 17,6 Pflops (su pico es 27,1 Pflops), seguido por Sequoia (LLNL, Lawrence Livermore National Laboratory), con 16,3 Pflops (su pico es 20,1 Pflops). IBM domina el Top10 con 6 superordenadores; hace 20 años dominaba Thinking Machines Corporation, que cayó en bancarrota en 1994 y fue adquirida por Sun Microsystems.
Nota dominical: ¿Puede un ordenador cuántico resolver el problema del viajante de forma eficiente?

El problema del viajante (TSP por Traveling Salesperson Problem) consiste en “dado cierto número de ciudades en un mapa conectadas por cierto número de carreteras, encontrar el camino más corto que un viajante de comercio debe tomar para visitar todas las ciudades exactamente una sola vez y retornar a la ciudad de origen.” Clara Grima @ClaraGrima definiría el TSP con mayor rigor como: “Dado un grafo G de vértices V conectados mediante arcos E de coste no nulo, encontrar el ciclo hamiltoniano de menor coste.” Mucha gente afirma que este problema TSP es un ejemplo de problema NP-completo, lo que es completamente falso. Un problema se puede resolver de forma eficiente si está en P. Incluso si fuera verdad que P=NP, no sabríamos si existe algún algoritmo eficiente para resolver el problema TSP. Los algoritmos cuánticos eficientes está en la clase BQP. ¿Existe algún algoritmo en BQP para el problema TSP? Nadie lo sabe, pero la opinión de los expertos es que no existe. Más aún, la opinión de los expertos es que las clases de complejidad BQP y NP-completo son disjuntas. Quizás conviene que recordemos algunas definiciones. Por cierto, todo esto viene a cuento por la entrada de Rod Hilton, “Traveling Salesperson: The Most Misunderstood Problem,” Absolutely No Machete Juggling, September 14, 2012, y por el comentario en este blog de josejuan.
En la teoría de la complejidad computacional se dice que un problema pertenece a la clase P si existe un algoritmo determinista para resolverlo que requiere en el peor caso un tiempo de ejecución descrito por un polinomio en el tamaño de la entrada, es decir, es O(nk), donde k≥1; un algoritmo con un coste en tiempo más que polinómico, como O(2n) no pertenece a la clase P. Se dice que un algortimo es eficiente si pertenece a la clase P, aunque de hecho, cuando k>3 un algoritmo es poco práctico.

Un problema pertenece a la clase NP si existe un algoritmo no determinista para resolverlo que requiere en el peor caso un coste en tiempo de ejecución polinómico; la “N” de “NP” significa “no determinista” aunque mucha gente se confunde con “no polinómico.” Un problema NP cumple la propiedad de se puede verificar (decidir) la corrección de una solución en tiempo polinómico. Si para verificar una solución se requiere un tiempo no polinómico, entonces el problema no pertenece a la clase NP. Por ello, el problema TSP no es un problema NP, pues decidir si una solución concreta es la óptima requiere un tiempo no polinómico.
Un problema pertenece a la clase NP-completo si es un problema NP equivalente a algún otro problema NP-completo. Esta definición recursiva exige especificar un problema concreto. Por ejemplo, el problema de la suma de subconjuntos: dado un conjunto de enteros, ¿existe algún subconjunto cuya suma sea exactamente cero? Por ejemplo, dado el conjunto { −7, −3, −2, 5, 8}, la respuesta es sí, porque el subconjunto { −3, −2, 5} suma cero. Cualquier problema NP que se pueda resolver en tiempo polinomial si existiera una solución en tiempo polinomial para el problema de la suma de subconjuntos es también un problema NP-completo (en este sentido esta clase de problemas NP es completa).

El problema TSP de “encontrar el camino óptimo” (o más corto) no es un problema NP-completo. Entres otras razones porque la clase NP-completo solo se aplica a problemas de decisión. Hay otra formulación del problema TSP, como problema de decisión que pertenece a la clase NP-completo. Clara Grima @ClaraGrima definiría el problema de decisión TSP como: “Dado un grafo G y un coste máximo k, decidir si existe un ciclo hamiltoniano cuyo coste sea menor o igual que k.” Este problema está en NP y además es NP-completo, porque el problema TSP de optimización es NP-difícil (en inglés NP-hard); aquí hay que recordar que la clase NP-completo es la intersección entre las clases NP y NP-difícil.
Un punto importante que hay que destacar es que si se pudiera resolver en tiempo polinómico el problema TSP, también sería resoluble el problema de decisión TSP (como es obvio) y con él todos los problemas de la clase NP-completo. Pero no a la inversa.
La clase BQP corresponde a los problemas de decisión que se pueden resolver en un ordenador cuántico en tiempo polinomial con una probabilidad de error acotada por 1/3, por convenio. Se trata del análogo cuántico a la clase BPP, los problemas de decisión que se pueden resolver de forma no determinista probabilística con una probabilidad de error menor de 1/3 (es decir, utilizando una máquina de Turing probabilística). Se conocen unos pocos (muy pocos) algoritmos cuánticos en BQP que se sospecha que no están en P (aunque no hay demostración de esto último), siendo el más famoso el algoritmo de factorización de enteros de Peter Shor.
¿El problema de la decisión TSP es un problema BQP? Nadie lo sabe, pero lo expertos opinan que no lo es (salvo que P=NP).
Nota dominical: Los matemáticos polacos, Alan Turing y el secreto de la máquina Enigma
Muchos creen que Alan Turing, que recibió la Orden del Imperio Britanico por ello, fue el responsable de las técnicas matemáticas de criptoanálisis que revelaron el secreto de la máquina Enigma, utilizada por los nazis para cifrar sus conversaciones militares. Sin embargo, entre 1932 y 1938, el servicio secreto polaco (Biuro Szyfrów), gracias al criptoanálisis de la máquina Enigma de tres ruedas realizado por Marian Rejewsky, fue capaz de descifrar el 75% de los mensajes cifrados que lograron interceptar. Nos lo cuenta estupendamente B. Jack Copeland, “Enigma,” pp. 217-264 in “The Essential Turing. Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma,” Edited by B. Jack Copeland, Clarendon Press, 2004. Todos los que quieran saber más sobre la vida y obra de Turing deberían leerse este libro de Copeland.
En septiembre de 1938 los nazis cambiaron el sistema para asignar claves diarias. Pocas semanas más tarde, Rejewsky y sus colegas desarrollaron dos nuevos métodos de criptoanálisis, uno basado en hojas de papel perforadas con agujeros que permitían determinar la nueva clave diaria y el otro basado en una máquina electromecánica (diseñada por Rejewski y el ingeniero Antoni Palluth) a la que llamaron “bomba” (en plural “bomby”). El nombre “bomba” fue elegido de forma jocosa; no sabían que nombre elegir y mientras le daban vueltas al asunto, uno de ellos disfrutaba de un postre helado de origen francés que en polaco recibía el nombre de “bomba” (versión polaca del francés “bombe”). En noviembre de 1938 ya disponían de seis “bomby” en operación, capaces de descifrar en dos horas lo que de otra forma requería unas 200 horas de trabajo de una persona. Sin embargo, en diciembre de 1938, los nazis añadieron dos ruedas más a la máquina. Los recursos disponibles por el Biuro Szyfrów polaco no eran suficientes para fabricar todas las réplicas necesarias para cubrir todas las combinaciones posibles de las ruedas de la máquina (donde antes bastaban 6 diferentes ahora eran necesarias 60 y por cada una había que fabricar 36 réplicas). Los polacos necesitaban ayuda.
Las redes sociales y las elecciones en EEUU

Cada año electoral en EEUU es un hervidero de artículos sobre el papel de la web y las redes sociales (Facebook, Twitter y YouTube) a la hora de predecir el resultado. Como solo hay un 50% de posibilidades de acertar (o errar) siempre hay artículos cuyos autores pueden presumir de haber acertado, incluso en más de una ocasión. Sin embargo, los medios de comunicación social y los resultados de los algoritmos de análisis pueden ser fácilmente manipulados. Por ejemplo, alterando el número de seguidores de los candidatos en Twitter (uno de los candidatos presidenciales de este año aumentó su número de seguidores en 110.000 en un solo día, pero un análisis demostró que la mayoría de estos seguidores no eran personas reales). Los organizadores de la campaña utilizan de forma regular “Google bombs” (que engañan al algoritmo PageRank de Google y logran posicionar ciertos sitios web en los primeros lugares en los resultados de búsqueda para ciertos términos) y ”Twitter bombs” (que logran trending topics gracias a retuitear de forma automática los tuits que incluyen cierta etiqueta o hashtag). Predecir los resultados electorales de forma fiable gracias a la web y las redes sociales requiere técnicas avanzadas de detección de “bombas” y de spam, técnicas contra las que compiten los desarrolladores de “bombas.” Por ello, algunos algoritmos tienen éxito en sus predicciones y otros no, o solo en algunas ocasiones y no en otras. La verdad es que muchos no usamos Twitter para hablar de política y los estudios indican que solo el 1% de los usuarios es responsable del 30% del volumen de tráfico sobre política. Nos lo cuentan Panagiotis T. Metaxas, Eni Mustafaraj, “Social Media and the Elections,” Science 338: 472-473, 26 October 2012.
La física de los arcoíris múltiples con gotas de agua no esféricas

Esta imagen de un arcoíris doble y bífido no es real, ha sido obtenida mediante el mejor software de simulación de arcoíris del mundo, resultado de una colaboración internacional en la que participa el grupo de investigación de Francisco Serón en la Universidad de Zaragoza. Para ello se ha mejorado el modelo físico de Lorenz-Mie, que asume gotas esféricas, para considerar gotas con forma no esférica realista (porque las de mayor tamaño lo son). En concreto, en esta imagen se observa un arcoíris ”bífido” porque se ha utilizado una mezcla de gotas pequeñas (esféricas) y gotas grandes no esféricas. El resultado es realmente espectacular y si no te dicen que está hecho por ordenador, lo mismo hasta te crees que es una fotografía de verdad. El artículo técnico para los interesados en los detalles técnicos es Iman Sadeghi, Adolfo Muñóz, Philip Laven, Wojciech Jarosz, Francisco Serón, Diego Gutiérrez, Henrik Wann Jensen, “Physically-Based Simulation of Rainbows,” ACM Transactions on Graphics 31: 3, January 2012 [tuit de Rafael Bachiller (@RafaelBachiller); la verdad es que ya no leo revistas de investigación en gráficos por ordenador (cuando hace un lustro las leía todas).
¿Realmente existen los arcoíris bífidos? Por supuesto, la imagen de la izquierda es una fotografía real obtenida por Benjamin Kuehne y la parte derecha la simulación correspondiente utilizando el nuevo software; se han utilizado gotas de agua de dos tamaños, con radio 0,4 mm y 0,45 mm. El acuerdo entre teoría y realidad es espectacular. Haz click en la imagen para verla en tamaño más grande (si te apetece disfrutar de sus sutiles detalles).

En estas cuatro imágenes de arcoíris incluyendo los arcos supernumerarios, la banda oscura de Alejandro y diferentes efectos. En concreto, arriba-izquierda, el arcoíris ideal según la teoría de Lorenz-Mie (gotas esféricas), arriba-derecha, cómo cambia éste cuando se introduce la efecto de que el Sol no es puntual, abajo-izquierda, una arco doble mostrando cómo cambian los colores de orden en el secundario, y abajo-derecha, un arcoíris doble con múltiples arcos supernumerarios resultado de una distribución uniforme de muchas gotas pequeñas.

La clave de la nueva teoría del arcoíris es considerar gotas de agua que no son esféricas. Beard y Chuang construyeron un modelo teórico de las gotas en 1987, que ratificaron con medidas experimentales. Os voy a confesar que yo le propuse a uno de mis estudiantes de doctorado hacer casi exactamente lo mismo que han hecho Paco Serón y sus colegas, estudiar cómo cambia la teoría de Lorenz-Mie cuando se usa el modelo de Beard-Chuang para la forma de las gotas. Pero al final mi estudiante, sin beca de investigación, no pudo completar su trabajo. Quizás por ello me ha encantado este nuevo trabajo. Los interesados en este modelo de gotas disfrutarán con Kenneth V. Beard and Catherine Chuang, “A New Model for the Equilibrium Shape of Raindrops,” Journal of the Atmospheric Sciences 44: 1509-1524, 1987, y Kenneth V. Beard, Rodney J.Kubesh, Harry T. III Ochs, “Laboratory Measurements of Small Raindrop Distortion. Part I: Axis Ratios and Fall Behavior,” Journal of Atmospheric Sciences 48: 698-710, 1991.

No este blog el lugar adecuado para discutir la teoría de la formación de los arcoíris. Quienes no la recuerden o nunca la hayan estudiado pueden recurrir a la web. En cualquier caso, resumiendo mucho, un arcoíris se forma por la refracción y reflexión de la luz del Sol en el interior de gotas de agua, incluyendo efectos de óptica geométrica (u óptica de rayos) y ondulatoria. El arcoíris primario (ver figura arriba-izquierda) se forma gracias a la luz que se refleja en el interior de la superficie interior de la gota, que ha llegado allí tras una refracción y que llega a nuestros ojos tras otra. El arcoíris secundario (ver figura arriba-derecha) requiere dos reflexiones en el interior de la gota (más las dos refracciones). Los arcos supernumerarios que se ven debajo del arcoíris primario se deben a la combinación de dos fenómenos ondulatorios, por un lado la interferencia (ver figura abajo-izquierdo), que les da los detalles finos, y por otro la difracción (ver figura abajo-derecha), que emborrona estos detalles finos.

El responsable de los maravillosos colores del arcoíris es la dispersión de la luz, el hecho que la refracción dependa de la longitud de onda de la luz incidente. La intensidad y el color de la luz dependen del ángulo con el que penetra la luz en el gota de agua y de su radio, como muestran estas dos figuras obtenidas utilizando la teoría de Lorenz-Mie para gotas esféricas. Para el caso de gotas no esféricas, el nuevo artículo técnico ha desarrollado un método numérico capaz de obtener el equivalente a estas figuras para diferentes radios de la gota de agua modelada según la teoría de Beard-Chuang.

Fotografía de un arcoíris en la que se ha insertado un trozo simulado por ordenador (solo se ha ajustado el color de fondo del arcoíris insertado). Click para ampliar.
¿Cómo compara el nuevo algoritmo con fotos reales de arcoíris? En estas fotografías reales de arcoíris se han insertado un pequeño trozo del arcoíris simulado por el nuevo modelo (los colores simulados no han sido retocados, solo se ha retocado el color de fondo para lograr un mejor ajuste con la fotografía). Tienes que ser click en la imagen para ampliar esta imagen y disfrutar del increíble acuerdo entre teoría y experimento. Los valores de los parámetros del arcoíris utilizados en estas fotografías aparecen en la siguiente tabla.


Haz click en la imagen para verla mejor. Arriba, se comparan la teoría de Lorenz-Mie y la nueva teoría; abajo izquierda, se ilustra el efecto del radio de la gota; y abajo derecha, se ilustra el efecto de la posición del Sol para gotas de 0,5 mm de radio.
En resumen, ya habrás notado que soy un apasionado de la óptica física de los arcoíris (y de otros fenómenos ópticos atmosféricos). Realmente si te apasionan como a mí este tema, te recomiendo leer el artículo de Paco Serón y sus colegas, así como muchas de las otras fuentes que hay disponibles por la web. Conocer la teoría detrás de los arcoíris te permitirá disfrutar mucho más del espectáculo que puedes contemplar cuando ves regar con aspersores el césped en cualquier parque de tu ciudad, o cuando disfrutas de los primeros rayos de Sol al acabar de llover.
Vídeo de la Mesa sobre Inteligencia Artificial en Naukas Bilbao 2012

MESA SOBRE INTELIGENCIA ARTIFICIAL con Francis Villatoro, Miguel Santander y Arturo Quirantes, moderada por Aberron y J. Cuesta. Click para acceder al vídeo en EITB a la carta.
Turing fue el padre de la inteligencia artificial (a la que él llamó inteligencia computacional en 1947). En 1948 introdujo el test de Turing para verificar si un ordenador es inteligente. Ciertos chatbots son capaces de superar el test de Turing (ELIZA fue el primero en 1966). Hoy en día se prefiere el test de la sala china. Más información en la propia charla, que espero no os parezca un monólogo por mi parte. Quedaron muchas cosas en el tintero, pero creo que es amena. Por cierto, mi pájaro no es un canario, es un agapornis o inseparable (Agapornis roseicollis).
Vídeo de “Los números que no se pueden calcular (Homenaje a Turing)” en Naukas Bilbao 2012

“Los números que no se pueden calcular (Homenaje a Turing)”
Francis Villatoro (Emulenews). Click en la imagen para ir a EITB.
Alan (Mathison) Turing nació el 23 de junio de 1912 en Londres (hace 100 años) y murió el 7 de junio de 1954, como Blancanieves, tras comer una manzana envenenada. No se suicidó, le asesinó la madrastra, la sociedad puritana británica que le persiguió por ser homosexual, un delito penal en 1954. El 10 de septiembre de 2009 el primer ministro del Reino Unido, Gordon Brown, emitió un comunicado declarando sus disculpas en nombre del gobierno por el trato que recibió Alan Turing durante sus últimos años de vida.
Celebramos este año el centenario del nacimiento de Alan Turing y en esta charla hablaré de su trabajo matemático más famoso, el que le convirtió en uno de los padres de la informática. La demostración de que hay números que no se pueden calcular. Trabajo en el que introdujo las famosas máquinas de Turing como modelo matemático del concepto de algoritmo.
Turing estudió en el King’s College, Cambridge, 1931-1934, y obtuvo una beca de investigación en 1935. Asistió a un curso de doctorado impartido por el Prof. Max Newman, sobre los teoremas de Gödel y el Entscheidungsproblem de Hilbert-Ackermann (1928), el problema de la decisión. En el verano de 1934, Turing tuvo una idea en los prados de Grantchester, Cambridge, utilizar una máquina para modelar el trabajo de un matemático demostrando teoremas o calculando números. Nació la máquina de Turing. Le llevó dos años escribir el programa de la máquina universal de Turing, necesaria para resolver el problema de la decisión.
En 1936, cuatro matemáticos, trabajando de forma independiente, resolvieron el problema de la decisión. El primero, Alonzo Church, que utilizó el cálculo lambda, el segundo, Alan Turing, que usó las máquinas de Turing, el tercero, Stephen Kleene, gracias a las funciones mu-recursivas, y el cuarto, Emil Post, que usó la máquina de Post. Hoy en día se suele hablar de la solución de Church-Turing. El trabajo de Turing introdujo un algoritmo para calcular números y estudió los números reales que se pueden calcular.
La máquina de Turing que calcula un número es un algoritmo que se puede escribir mediante símbolos. Todas las máquinas de Turing posibles corresponden a todas las secuencias finitas de símbolos y por tanto son enumerables. Su cardinal es el mismo que el de los números naturales, el mismo que el de los enteros, el mismo que el de los racionales (cocientes de enteros), el mismo que el de los números algebraicos reales (soluciones de polinomios con coeficientes enteros). Los números reales computables, entre ellos muchos números transcendentes, como pi o e, tienen como cardinal el mismo que el de los números naturales. Por tanto, hay números reales que no son calculables. Más aún, con probabilidad uno, todo número real es no calculable. Sin embargo, todo lo que sabemos sobre la realidad se basa en operar con los números reales que son calculables.
La demostración más elemental de que hay más números reales que enteros se basa en el argumento de diagonalización de Cantor (1891).
Si no has visto aún mi charla, te animo a disfrutarla en la web de EITB a la carta. La noche anterior dormí un par de horas, pero espero que no se me note mucho.
Puertas lógicas basadas en gotas de agua sobre un sustrato superhidrófugo
La idea de utilizar las colisiones de gotas de agua para construir puertas lógicas capaces de simular un ordenador es muy antigua. Lo más difícil es lograr que dos gotas reboten en una colisión. Henrikki Mertaniemi, de la Universidad de Aalto (antes llamada Universidad Técnica de Helsinki), Finlandia, y sus colegas lo han logrado utilizando un sustrato superhidrófugo adecuado. Gracias al rebote de las gotas han logrado implementar un conjunto universal de puertas lógicas combinacionales (puertas AND/OR y NOT/FANOUT), así como elementos de memoria tipo biestable (Flip/Flop). Obviamente, si el sistema fuera escalable en la práctica, sería posible construir un ordenador utilizando (millones de) estos elementos. Pero, claro, no lo es. Por ello sus aplicaciones prácticas son muy limitadas, lo que no quita que sea un artículo muy curioso. La clave de todo es el diagrama de estado para las colisiones en función del parámetro de impacto y el número de Weber, que muestra bajo qué condiciones se logra la coalescencia y el rebote en las colisiones de las gotas. El artículo técnico es Henrikki Mertaniemi, Robert Forchheimer, Olli Ikkala, Robin H. A. Ras, “Rebounding Droplet-Droplet Collisions on Superhydrophobic Surfaces: from the Phenomenon to Droplet Logic,” Advanced Materials, Article first published online: 4 SEP 2012.

Os recuerdo, a los que no seáis ni informáticos ni ingenieros electrónicos, lo que son las puertas lógicas combinacionales básicas. La puerta NOT es un inversor con una entrada y una salida que convierte un 1 en un 0 y un 0 en un 1 (se toma el 1 como presencia de gota en cierto momento y el 0 como ausencia de gota en dicho momento). La puerta FANOUT es un distribuidor con una entrada y dos salidas que copia la entrada en ambas salidas. La puerta AND (producto lógico) y la OR (suma lógica) tienen dos entradas y una salida; la primera solo da 1 cuando entran dos 1, y la segunda siempre da 1 salvo cuando entran dos 0. Las figuras de abajo, que complentan el vídeo que abre esta entrada, explican el funcionamiento de las puertas lógicas desarrolladas.















