juaninf - notas de psudoprogramador

Sunday, March 24, 2013

Torres de Hanoi Implementación [code C++]

El juego, en su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Los discos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas: 
  1. Sólo se puede mover un disco cada vez. 
  2. Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo. 
  3. Sólo puedes desplazar el disco que se encuentre arriba en cada varilla. 

[fuente Wikipedia]

A continuación presento una implementación de este juego en C++, usando la estructura pila. 

#include <iostream>
#include <stack>
using namespace std;
void hanoi(int, stack<int>&, stack<int>&, stack<int>& );
int main(){
  int n;
  stack<int> origen;
  stack<int> destino;
  stack<int> auxiliar;
  printf("Ingresa el número de discos:\n");
  scanf("%d", &n);
  //llenando la pila de origen con los discos
  for (int i=0; i<n; i++){
      cout<<endl<<n-i<<endl;
      origen.push(n-i);
  }

  hanoi(n, origen, destino, auxiliar);
}


void hanoi(int n, stack<int> &origen, stack<int> &destino, stack<int>& auxiliar){
  if (n == 1){
      int top = origen.top();
      destino.push(top);
      origen.pop();
      return;
  }
  else{
      //{mover n-1 discos de la torre origen a la torre auxiliar}
      hanoi(n-1, origen, auxiliar, destino); //{llamada recursiva}
      //Mover un disco de la torre origen a la torre destino
      int top = origen.top();
      destino.push(top);
      origen.pop();
      //{mover n-1 discos de la torre auxiliar a la torre destino}
      hanoi(n-1, auxiliar, destino, origen); //{llamada recursiva}
  }
  return;
}

Wednesday, March 13, 2013

Representación de qbits en la esfera de Bloch

Un qubit o cubit (del inglés quantum bit, bit cuántico) es un sistema cuántico con dos estados propios y que puede ser manipulado arbitrariamente. A seguir desarrollaré un ejercicio que trata acerca de la representación de qbits en la esfera Bloch. Para este propósito usaré una herramienta para hacer los gráficos respectivos.

Encontrar la posición del siguiente vector: 
$$|+\rangle = \dfrac{|0\rangle + |1\rangle}{\sqrt[]{2}},$$
en la esfera de Bloch.

Usando la reducción $$\alpha|0\rangle + \beta|1\rangle = e^{i\alpha}(\cos \dfrac{\theta}{2}|0\rangle+e^{i\phi}\sin \dfrac{\theta}{2}|1\rangle).$$ Llevando en consideración que $$e^{i\alpha}$$ es una fase global y haciendo $$j = \sqrt[]{-1}$$ tenemos:$$|+\rangle = \dfrac{|0\rangle + |1\rangle}{\sqrt[]{2}}= \dfrac{|0\rangle}{\sqrt[]{2}}+ \dfrac{|1\rangle}{\sqrt[]{2}}= \alpha|0\rangle + \beta|1\rangle = e^{i\alpha}(\cos \dfrac{\theta}{2}|0\rangle+e^{i\phi}\sin \dfrac{\theta}{2}|1\rangle)$$ $$\alpha = \dfrac{1}{\sqrt[]{2}}= \cos \dfrac{\theta}{2}$$ y

$$\beta = \dfrac{1}{\sqrt[]{2}}= e^{i\phi}\sin \dfrac{\theta}{2},$$ luego $$\theta = \pi/2\,\,\,,\phi = 0$$ A seguir mostramos el respectivo gráfico para esos valores de θ y φ




Wednesday, March 06, 2013

Livraria LibMC

Introdução


Dentro dos sistemas criptográficos de chave pública existem alguns que, atualmente, têm se destacado devido ao fato de, aparentemente, resistirem aos ataques que são provenientes do uso dos computadores quânticos, formando, assim, uma família denominada de post-quantum cryptosystems. Estes sistemas criptográficos, em sua grande maioria, têm suporte matemático nos códigos códigos de Goppa binário, como apresentado por McEliece e Niederreiter. Neste post, apresento uma livraria para implementar os algoritmos de decodificação algébrica para códigos de Goppa binário com parâmetros $[n,k,d]$ suficientemente grandes. Para conseguir isto, desenvolvemos uma implementação híbrida, usando o CAS(computer algebra system) SAGE para os algoritmos de decodificação e algumas funções modificadas do software HyMES (feito em C) para a geração do polinômio síndrome (de forma randômica), que é uma das entradas para os algoritmos de decodificação. Caso a livraria não fosse usado para gerar o polinômio síndrome, randomicamente, a implementação apenas no SAGE ficaria, obviamente, muito limitada em tempo de decodificação, devido ao carácter simbólico do mesmo. 

Como usar

A livraria esta feita para ser usada em SAGE versão para 32 bits. Para instalar a livraria segue os passos:
  1. Descarregar de aqui.
  2. Descomprimir o arquivo zipeado.
  3. Copiar o arquivo na pasta: local/lib/python/site-packages.
  4. Reiniciar o SAGE.
Exemplo de uso

Veja que as entradas do gerador são: $m$ é o grau do polinômio $p(X)$ tal que $F = K/p(X)$, com $K = \mathbb{F}$$_2$, $n$ é o comprimento de cada palavra chave e delta é o grau do polinômio de Goppa. As saídas são: o Polinômio de Goppa, a matriz de teste de paridade do código gerado e o vetor codificado, ou seja $mG+e$.

Este trabalho foi desenvolvido no LNCC, sendo meus orientadores Renato Portugal e Nolmar Melo.


Related Posts Plugin for WordPress, Blogger...