Resolviendo laberintos utilizando el programa Paint

Dibujo20130318 maze to be solved

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

Dibujo20130316 D-Wave computer qubits

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)

Las limitaciones de la biología sintética mediante BioBricks

Dibujo20130314 Composition of irregular transcription and translation genetic elements

El mayor problema de la biología sintética es que un gen insertado en el ADN de un organismo no se comporta siempre de la misma forma. Una solución es insertar junto al gen un promotor adecuado (una secuencia de ADN que induzca inicio de la transcripción de dicho gen). Hay muchos promotores, pero todos no se portan igual de bien para un gen concreto, como muestra un nuevo artículo que ha estudiado la acción de 77 promotores en dos genes en la bacteria procariota E. coli. Las diferencias en la expresión de dichos genes son enormes (recuerda que el ADN del gen es transcrito a ARN mensajero y luego traducido a proteínas en los ribosomas; el promotor controla la cantidad de proteína traducida de forma indirecta a través del control de lo que se transcribe). Muchos lectores dirán que el resultado era esperable, pero la doctrina de muchos biólogos sintéticos era que el promotor importa, pero poco (muy pocas veces se prueban de forma sistemática decenas de promotores). Junto a varios colegas estudié la posibilidad de diseñar un calibrador de promotores (capaz de comparar la acción de un promotor cualquiera con respecto a un promotor de referencia); no lo logramos (todo se quedó en un modelo teórico que sólo funcionaba in silico). El nuevo estudio muestra que aún no se entiende bien el funcionamiento de los promotores y cómo su acción afecta a lo que interesa, la expresión final de la proteína. El camino hacia el diseño de redes genéticas sintéticas parece más arduo y tortuoso de lo esperado. Nos lo cuenta Ewen Callaway, “DNA tool kit goes live online. Standard control sequences aim to make genetic engineering more predictable,” Nature 495: 150–151, 14 Mar 2013, que se hace eco de los artículos Vivek K Mutalik et al., “Quantitative estimation of activity and quality for collections of functional genetic elements,” Nature Methods, AOP 10 Mar 2013, y Vivek K Mutalik et al., “Precise and reliable gene expression via standard transcription and translation initiation elements,” Nature Methods, AOP 10 Mar 2013.

Sigue leyendo

Cálculo eficiente del permanente de una matriz mediante computación cuántica

Dibujo20130215 classical vs quantum random walk with photons

El permanente de una matriz cuadrada N×N se define como el determinante, pero sin alternar los signos de los factores. No hay ningún algoritmo clásico eficiente para calcular el permanente de una matriz general (aunque hay algoritmos de coste polinómico para ciertos tipos de matrices). Se publica en Science un algoritmo cuántico eficiente para calcular el permanente de una matriz que utiliza un ordenador cuántico analógico basado en caminos aleatorios. La matriz se define mediante el acoplo de N guías ópticas coplanares, fabricadas en la superficie de un chip, que son recorridas por fotones acoplados entre sí por las fuerzas de intercambio (las que resultan de la simetría de la función de onda asociada a que son partículas indistinguibles). Midiendo la probabilidad de encontrar un fotón a la salida de las guías se puede calcular el valor del permanente de la matriz. Más aún, la computación cuántica con caminos aleatorios es universal, permite simular cualquier ordenador cuántico basado en puertas lógicas, aunque se requiere un polinomio de grado doce en el número de cubits, como también se publica hoy en Science, lo que lo hace eficiente, pero no práctico. Nos lo cuenta James D. Franson, “Beating Classical Computing Without a Quantum Computer,” Science 339: 767-768, 15 Feb 2013, que se hace eco de los artículos de Matthew A. Broome et al., “Photonic Boson Sampling in a Tunable Circuit,” Science 339: 794-798, 15 Feb 2013, Andrew M. Childs et al., “Universal Computation by Multiparticle Quantum Walk,” Science 339: 791-794, 15 Feb 2013, y Justin B. Spring et al., “Boson Sampling on a Photonic Chip,” Science 339: 798-801, 15 Feb 2013.

Sigue leyendo

El centro de procesado de datos del CERN supera los 100 petabytes (75 PB en los últimos 3 años)

Dibujo20130214 CERN Data Centre passes 100 petabytes

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

Dibujo20130117 JAABA - interactive machine learning for automatic annotation of animal behavior

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.

Sigue leyendo

Nota dominical: Richard Feynman, los ordenadores y los métodos numéricos

Dibujo20121216 Richard Feynman - 1985 - from Shelley Gazin

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].

Sigue leyendo

El superordenador español MareNostrum del BSC retorna al Top50 de los superordenadores

Dibujo20121203 marenostrum barcelona supercomputing center - bsc - 2005

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, “Trav­el­ing Sales­per­son: The Most Mis­un­der­stood Problem,” Absolutely No Machete Juggling, Sep­tem­ber 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).