jueves, abril 24, 2008

Opinión humilde computación cuántica

Yo no sé casi nada de computación cuántica.

Lo que comentaré aquí es una opinión personal y poco relevante por ni nivel de desconocimiento

No me hago responsable de las consecuencias que pueda tener que alguien me haga caso


Dicho esto...


El bogosort del comentario anterior, para mi es un buen ejemplo de lo que es computación cuántica.

Esto es un tema muy de moda.
Hay mucha gente investigando y ganando premios (y mucho dinero)

Probablemente porque de ser posible la computación cuántica... la gente tiene miedo de quedarse rezagados en algo tan rompedor


BASES DE LA COMPUTACIÓN CUÁNTICA...

* Tenemos unos cuantos qbits

* Están "relacionados" entre sí de forma que sólo pueden coexistir con valores concretos cuando se cumple la solución del problema a resolver (ejemplo habitual, la factoriazación)



Un qbit es un bit cuántico, que puede tener (y habitualmente tiene) los dos valores posibles al mismo tiempo

Por tanto, un grupo de 32 qbits, representan en todo momento todos los números posibles con 32 bits

Eso es fantástico y mucho mejor que el sistema "antiguo", donde con 32 bits, sólo puedes representar un caso concreto


Pero hasta el momento esto es poco práctico.

Si sumamos un número de 32qbits a otro de 32qbits y el resultado lo tenemos en 33qbits...

Pues no se moleste oiga, coje 33qbits y ya tienes todas las posibles sumas de números de 32bits

Y después de esta chorrada metafísica que no sirve para nada...

¿Como narices se puede hacer que los qbits sean prácticos?


Pongamos un ejemplo complicado


Tenemos 3 grupos de 32qbits

El grupo 1 y el 2 están "relacionados" con el 3 de forma que sólo admite valores en los que g1 y g2 son factores de 3

Ahora le damos un valor a g3 y voalá...

g1 y g2 tiene inmediatamente dos factores del número representado en g3



Fantástico, pero hay un par de problemas...


PROBLEMA 1
==============

¿Cómo los "relacionamos" para este fin?

Complicado, pero se sabe que en determinados casos pueden haber propiedas cuánticas "relacionadas"

Supongamos que se puede hacer



PROBLEMA 2
==============


¿Me tengo que creer que asignado unos valores en unos qbits otros dejan de tener valores simultáneos?

Ahí está el gatito de Schrodinger y la famosa interpretación de Acapulco (me gusta pensar que estaban en la playa mientras definían estas cosas complicadas)



Más o menos dicen.


El gato está vivo y muerto a la vez mientras nadie lo observe.
Una vez que lo miramos, el gato estará vivo o muerto

Pero eso no es ciencia.
No se puede verificar, no sirve para realizar predicciones más generales que se puedan verificar (en realidad no sirve para nada)

Chorradas parecidas nos podemos inventar muchas.
Ejemplo, nada existe, todo es producto de mi imaginación
Pues vale, no es demostrable ni rebatible. Tampoco es ciencia ni sirve para nada


Si pudiéramos hacer que el gato al abrir la caja estuviera vivo (por ejemplo) significaría que hemos forzado a que el átomo que lanzaría la radiacción, no la lance. Ahí tenemos dos efectos cuánticos conectados.

Lo malo es que nadie sabe como hacer que el gato esté vivo

Repetimos, esto no es ciencia, esto no sirve para nada


Pero a eso se parece la computación cuántica tan de moda


En caso de que se pudiera...
¿Cuál sería el esfuerzo necesario para interconectar cuánticamente 3 grupos de 32qbits en factores y resultado
¿Y 64qbits?
¿Merecería la pena?


Roger Penrose escribió un libro difícil que no entendí muy bien.
En este libro defendía la hipóteis de que el cerebro funcione con algoritmos cuánticos

Como no lo entendí, no me lo creo

Así se podría explicar porque los ordenadores son tan terriblemente torpes en cosas que son triviales para nosotros (incluso para un perro)


Hace meses, salió la fabulosa noticia del primer ordenador cuántico comercial del mundo con más de una decena de qbits

Desgraciadamente luego explicaron que cuántico, cuántico... que utilización de algoritmos cuánticos... no, pero era muy chulo


Pues nada, que sigan buscando el primer ordenador con algoritmos cuánticos y que me avisen cuando lo encuentren

miércoles, abril 23, 2008

El algoritmo de ordenación MÁS EFICIENTE posible

Hacía tiempo que se conocía el peor algoritmo de ordenación posible y su coste, pero no se sabía cual podría ser ni el coste, ni mucho menos cómo podría ser el mejor algoritmo para ordenar (no mezclar, sin más consumo de memoria que la propia lista)


Un concienzudo estúdio teórico ha desvelado la respuesta a este problema nada trivial y ahora...
Ya se conoce el coste del mejor algoritmo de ordenación posible, y no sólo eso YA SE CONOCE EL MEJOR ALGORITMO DE ORDENACIÓN POSIBLE

Esto puede parecer trivial, pero es realmente un problema teórico enorme
No es el qsort ni variantes semejantes, es muchísimo mejor y revolucionario


El coste es O(n) pero todavía es teórico, no se ha conseguido llevar a la práctica

Hay varias universidades tratando de hacerlo efectivo

Consta de dos pasos muy sencillos de entender, pero el segundo paso, no ha sido resuelto

Es curioso porque está inspirado en el peor algoritmo de ordenación posible (que sí se conocía desde hace mucho tiempo)


Disfruta de esta revelación todavía poco popular, sé privilegiado...



bogo-sort: /boh`goh·sort´/, n.

(var.: stupid-sort) The archetypical perversely awful algorithm (as opposed to bubble sort, which is merely the generic bad algorithm). Bogo-sort is equivalent to repeatedly throwing a deck of cards in the air, picking them up at random, and then testing whether they are in order. It serves as a sort of canonical example of awfulness. Looking at a program and seeing a dumb algorithm, one might say “Oh, I see, this program uses bogo-sort.” Esp. appropriate for algorithms with factorial or super-exponential running time in the average case and probabilistically infinite worst-case running time. Compare bogus, brute force.

A spectacular variant of bogo-sort has been proposed which has the interesting property that, if the Many Worlds interpretation of quantum mechanics is true, it can sort an arbitrarily large array in linear time. (In the Many-Worlds model, the result of any quantum action is to split the universe-before into a sheaf of universes-after, one for each possible way the state vector can collapse; in any one of the universes-after the result appears random.) The steps are: 1. Permute the array randomly using a quantum process, 2. If the array is not sorted, destroy the universe (checking that the list is sorted requires O(n) time). Implementation of step 2 is left as an exercise for the reader.



http://www.catb.org/~esr/jargon/html/B/bogo-sort.html

jueves, abril 17, 2008

Seguridad informática

O deberíamos decir INseguridad


http://historiasdequeso.blogspot.com/2008/04/usuarios-entregan-sus-contraseas-cambio.html


Usuarios entregan sus contraseñas a cambio de ¿chocolate?

¿Quiere que un gusano llegue en forma de correo electrónico a la bandeja de entrada de alguien? Nada más sencillo, prométale una tableta de chocolate y todas sus contraseñas serán suyas.

Así lo aseguran los analistas de seguridad informática Infosecurity Europa, que encuestó a 576 trabajadores de oficinas de los alrededores de Liverpool Street, en Londres, como parte de su semana de concienciación sobre la seguridad de la información que comienza el 21 de Abril de este mismo año.

Según la encuesta, el 45% por ciento de las mujeres daban sus contraseñas a extraños con total tranquilidad a cambio de una tableta de chocolate, frente a sólo un 10% de los hombres. De haberles ofrecido cervezas gratis los resultados de la encuesta hubieran sido todavía más divertidos, si cabe. Para conseguirlo los de Infosecurity se hicieron pasar por analistas de mercado.

A los incautos se les pidió rellenar una encuesta que en realidad no era más que una tapadera para realizar la investigación sobre "ingeniería social" con tal de demostrar lo crédulos que podrían llegar a ser los usuarios, dando todo tipo de información privada a cambio de chocolate.

A pesar del gran numero de personas que picaron, Infosecurity estima que, en conjunto, la gente lo hizo mucho mejor que el año pasado cuando se realizó el mismo experimento. En el 2007 un tremendo 64 por ciento de personas estaban dispuestas a regalar sus contraseñas a cambio de una barra de chocolate con respecto al 21 por ciento que ha sucumbido a la tentación. Tal vez este año estén todos a dieta... xD. Pero aún así, las cifras son alarmantes.

El 61 por ciento no tuvieron ningún pudor a la hora de revelar su fecha de nacimiento, ni dudaron a la hora de dar la información personal de sus colegas, incluidos nombres, números de teléfono, solo para poder participar en un sorteo donde supuestamente podrían ganar un viaje a París. Paquetes de chocolate y París... no es de extrañar que el 60 por ciento de los hombres y el 62 por ciento de las mujeres dijeran "Si, quiero"

Infosecurity también descubrió que más de la mitad de las personas "encuestadas" utilizan una contraseña para todo, y que el 43 por ciento no la ha cambiado nunca. Un 58 por ciento entregó sus contraseñas cuando llamaron haciéndose pasar por el departamento de TI de su empresa, y la mitad afirmó conocer las contraseñas de sus colegas de oficina.

Claire Sellick, director de eventos de Infosecurity Europa dice que la promesa de un viaje podría costar muy cara a la gente, porque "una vez que un ciberdelincuente obtiene tu fecha de nacimiento, nombre y número de teléfono ya tiene toda la información necesaria para llevar a cabo ataques de "ingeniería social" más sofisticados hacía usted y posiblemente pretenda hacerse pasar por su banco o compañía de teléfonos para obtener más información valiosa que pueda ser utilizada para ejecutar algún fraude usando su identidad"

Cuando finalmente se les comunicó que la encuesta que acababan de rellenar era en realidad parte de una prueba para la semana de la concienciación sobre seguridad informática la mayoría se sorprendieron y algunos afirmaban que los investigadores parecían honestos y dignos de toda confianza.

Caos y Lorenz

Visto en Barrapunto

No sé si la historia es real, no he podido contrastarla, pero es un ejemplo interesante de caos.

Lorenz estaba haciendo simulaciones de tiempo atmosferico con ecuaciones diferenciales (totalmente deterministas) e iba viendo como variaban con el tiempo parametros como temperatura, presion atm, etc. Pero como en aquella epoca (70's) el tiempo de CPU estaba muy requerido, no tenía tiempo para hacer simulaciones largas completas. Entonces, cuando se acababa su tiempo, imprimia en un papel los valores de las variables y, cuando volvía a tener tiempo, introducía estos valores iniciales y continuaba la simulacion desde ahí. Entonces empezó a darse cuenta de que cuando repetía simulaciones que deberían ser exactas, los resultados variaban muchísimo. Al indagar en la causa, se dio cuenta de que se debía a que él imprimia los valores con unas pocas cifras decimales, mientras que el ordenador internamente consideraba más. Y esas diferencias en la 5a cifra decimal (consideradas totalmente despreciables) producían cambios drasticos (dependencia absoluta de los detalles de las condiciones iniciales, una caracteristica de los sistemas caóticos). Es decir, si el ordenador continuaba una simulación a partir de un valor de temperatura T=25.034256893823, y Lorenz continuaba otra a partir del valor que había impreso con menos decimales (T=25.03456899), las 2 simulaciones iban por derroteros totalmente diferentes. Cuando cualquiera hubiese esperado que fuesen igual o, al menos, trementamente parecidas (predicibilidad), ya que esa diferencia de temperatura (0.000000005) se pensaba era despreciable a todos los efectos.





Visto en Wikipedia...
La forma de mariposa del atractor de Lorenz puede haber inspirado el nombre del efecto mariposa en la Teoría del Caos.

martes, abril 15, 2008

El famoso formato IEEE754

Este es el archiconocido formato para representar números en coma flotante.

No niego que sea un buen formato, pero es propenso a muchos errores. Tanto de técnicos como no técnicos.


Este formato no es un formato de números exactos, pero todos los lenguajes y sistemas que trabajan con él permiten hacer comparaciones de igualdad

Nunca lo he entendido.

Prueba en tu sistema favorito...

1*(0.5-0.4-0.1)
pensarás que es cero, ¿pero lo es en tu sistema?

(43.1-43.2)+1
pensarás que es 0.9 ¿pero que resultado da en tu sistema?


Lo que me ha sorprendido mucho es que OpenOffice hace las dos comparaciones correctamente, pero no el Excel


El problema, es viejo y conocido.

Un número representado exactamente en decimal, puede ser periódico en binario y viceversa


Entonces

¿PORQUÉ CARAJO LOS SISTEMAS PERMITEN COMPARAR COSAS QUE NO SON EXACTAS?


Y si lo hacen, al menos deberían tomarse las molestias de corregir esos defectos potenciales en la gran mayoría de casos como hace OpenOffice (y no hace Mocosoft Office)



Y además, los pobrecillos usarios de estos números pueden pensar que la suma es asociativa consigo misma y lo mismo para la multiplicación y división, pero no es así


No es necesariamente lo mismo...


(a+b)+c ~ a+(b+c)

(a*b)*c ~ a*(b*c)



Y mucho más evidente...


(a*b)/c /= a*(b/c)



Que los informáticos se tropiecen con esto... Pues que aprendan porque para eso son informáticos y deberían saberlo.

Pero es que esto también le toca las narices a los usuarios de hojas de cálculo como Excel.



En este caso gana por goleada OpenOffice, que se procupa por ser coherente con el usuario