¿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

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)

Los beneficios cognitivos de jugar a videojuegos violentos

Dibujo20130227 Brain Game - When searching for a particular object in a sea of shapes people who played video games regularly showed less activation of the brain regions

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.

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