Tag: lógica

21 febrero 2007

La Computación Cuántica Asoma la Cabeza

izquierda_sinmarco La computación cuántica es un paradigma de computación distinto al de la computación clásica. Se basa en el uso de qubits en lugar de bits, y da lugar a nuevas puertas lógicas que hacen posibles nuevos algoritmos. Una misma tarea puede tener diferente complejidad en computación clásica y en computación cuántica, lo que ha dado lugar a una gran expectación, ya que algunos problemas intratables pasan a ser tratables. Mientras un computador clásico equivale a una máquina de turing, un computador cuántico equivale a una máquina de turing indeterminista.

La empresa canadiense D-Wave System presentó el 13 de febrero de 2007 en Silicon Valley, una primera computadora cuántica comercial de 16-qubits de propósito general; luego la misma compañía admitió que tal máquina llamada Orion no es realmente una Computadora Cuántica, sino una clase de máquina de propósito general que usa algo de mecánica cuántica para resolver problemas.

Continuar leyendo...

Más noticias sobre: Física, Computabilidad
Tags: chip, física cuántica, lógica, nanotecnología
Comentarios (2) | Trackback

15 octubre 2006

El segundo número

Alfonso Jiménez

Matemáticas Vamos a plantear un sencillo juego. El número de participantes será mayor de dos sin establecer un máximo de jugadores. Cada jugador seleccionará un número entero mayor de 0 y lo guardará en secreto. Al final todos los participantes mostrarán el número que escogieron. Ganará el jugador que haya seleccionado el segundo menor número no repetido. Por ejemplo, si los números elegidos fuesen 2-2-3-4-4-4-5-6-6-7-10 gana el que seleccionó el número 5, ya que el primer número no repetido es el 3 y el segundo es el 5. En el caso de que no se den las condiciones suficientes para haber ningún ganador, es decir, no haya dos números que no se repitan, se volverá a empezar el juego.

Continuar leyendo...

Más noticias sobre: Matemáticas
Tags: lógica
Comentarios (7) | Trackback

10 octubre 2006

Problema de satisfacibilidad (SAT)

Alfonso Jiménez

Bombilla Los problemas NP-completo son los más complicados de la clase NP, en el sentido que si Q’ es un problema de decisión en NP y Q es un problema NP-completo, entonces todas las instancias de Q’ son polinomialmente reducibles a una instancia de Q. El problema de satisfacibilidad (SAT) fue el primer problema identificado como perteneciente a la clase de complejidad NP-completo por Stephen Cook en el año 1971.

Comenzamos con una lista de variables booleanas x₁, …, x_n. Un literal es una de las variables x_i (o la negación de una de las variables ¬x_i). Hay 2n literales posibles. Una cláusula es un conjunto de literales.

Las reglas del juego son las siguientes: Asignamos valores booleanos Verdadero (V) o Falso (F) a cada una de las variables. De este modo a cada uno de los literales se le asigna un valor booleano. Finalmente una cláusula tiene valor V si y sólo si al menos uno de los literales de la cláusula tiene un valor V, en otro caso tendrá un valor F.

Un conjunto de cláusulas es satisfactible si existe una asignación de valores booleanos a las variables que hagan que todas las cláusulas sean ciertas. Consideramos or entre cada unos de los literales en una cláusula y and entre las cláusulas.

Continuar leyendo...

Más noticias sobre: Computabilidad
Tags: complejidad, computablidad, lógica, np-completo
Comentarios (2) | Trackback