lunes, 4 de julio de 2011

Fundamentos de la complejidad Computacional: Problema de Bin Packing

Problema
El problema de Bin Packing es un problema NP Complejo (Polinomial No Determinista), El problema consiste en intentar acomodar en un recipiente la mayor cantidad posible de objetos de diferente valor y volumen, ocupando el mayor espacio posible.

En este problema lo que se busca es tratar de aprovechar la mayor cantidad de espacio posible que este disponible en el contenedor o recipiente y acomodar todo de una mejor manera para que pueda caber mas y se pueda optimizar el espacio como se muestra en la imagen siguiente.

Como podemos observar en la imagen no hay ningun espacio en blanco. Todo ese espacio fue bien aprovechado debido a que los objetos dentro del contenedor se colocaron adecuadamente.
Este problema se puede plantear de diferentes maneras, dependiendo del algoritmo que tengamos para resolverlo. Podria plantearse como un problema de definicion en el siguiente caso:
Imaginemos que tenemos varios objetos de diferentes volumenes y valores:

Para poder obtener el valor total maximo de los objetos que podrian caber en el recipiente necesitamos preguntar si existe N valor de objetos adentro (De preferencia tenemos que utilizar uno grande).

Por ejemplo, podemos preguntar si dentro del recipiente se podria obtener un valor total de 500. Si la respuesta a esta decision es si, entonces vamos disminuyendo el numero hasta que nos diga que el valor proporcionado no es el mayor. Despues de que nos diga que no debemos aumentar los valores hasta llegar al valor maximo correcto.
En cuanto al algoritmo de optimizacion, se iran desechando solos los objetos que no sean indispensables o que no tengan mucho valor y se ira acomodando todo de una manera automatica asi como podemos ver en el siguiente video


Justificacion
Este problema me llamo mucho la atención porque tiene una inmensa variedad de aplicaciones y usos. Se puede aplicar por ejemplo en los contenedores de basura, en los trailes que tienen que mantener cierto peso estable, para conservar la ecologia y hacer menos desperdicio de recursos y espacio de los que normalmente se utilizan.
Es indispensable saber administrar bien el espacio y hacerlo rendir. Es por esto que considero este problema muy común en el mundo actual y se puede aplicar en muchos aspectos.


Complejidad
Como dije anteriormente, este problema es Combinatorio NP(Polinomial No Determinista) Complejo. 


Algoritmos
Aqui les muestro el video de un algoritmo que encontre en internet sobre este problema. Me gusto porque viene informacion detallada del algoritmo.




Este es un codigo que encontre en internet solucionando el mismo problema



float[] used = new float[n + 1];
   //used[j] is the amount of space in bin j already used up.
   int i, j;
   Initialize all used entries to 0.0
   Sort S into descending(nonincreasing)order, giving the sequence S1 >= S2 >= ... >= Sn.
   for(i = 1; i <= n; i++)
     //Look for a bin in which s[i] fits.
     for(j = 1; j <= n; j++)
      if (used[j]+si<+1.0)
        bin[i] = j;
        used[j] += si;
        break;  //exit for(j)
     //continue for(i).




Referencias



jueves, 30 de junio de 2011

Algoritmo de Cifrado Xor

Criptografía Xor
Criptografía es la forma en la que un mensaje es descrifrado por medio de diferentes tecnicas para intercambiar informacion entre un emisor y un receptor.  
La criptografia tiene muchos usos, muchas veces al usarla no nos damos cuenta, ya que la computadora realiza este proceso por si misma. Un ejemplo de aplicacion de esto es al momento de entrar a ver correos electronicos o a cualquier lugar al que entremos con una cuenta.  
Este algoritmo de sirve para encriptar textos o claves por medio de la utilizacion del operador Xor y de una clave secreta. Dicha clave es proporcionada previamente por el emisor con la finalidad de codificar. El receptor del mensaje la puede utilizar para poder decodificar el mensaje y ver el original.
Elegí hablar sobre este algoritmo porque me llama mucho la atención la forma en la que un mensaje cambia, se oculta y se recupera por el receptor del mensaje. Es una forma muy útil y practica de mantener información segura.
Recordemos un poco sobre la tabla de verdad utilizando el operador xor. Esta tabla nos facilitara la encriptacion.





Supongamos que el emisor envia un mensaje 10010110. 
Para mayor seguridad este mensaje es decodificado con la clave 11100100. 
 El resultado ya codificado se veria de la siguiente manera:

Mensaje original (a): 10010110
Clave privada    (b): 11100100
(a) ⊕ (b)                  : 01110010

El emisor envia el mensaje 10010110. Este mensaje se encripta y llega de la forma 01110010. Sin embargo, para poder mostrar el mensaje original al receptor es necesario volver a utilizar el operador binario xor.
Se utiliza la misma clave privada tanto para la codificacion como para la decodificacion

Mensaje recibido (a): 01110010

Clave privada     (b): 11100100
(a) ⊕ (b)                   : 10010110

Con esto podemos observar que el mensaje obtenido como resultado es el mensaje enviado originalmente, por lo que se puede decir que la encriptacion y la decodificacion fue realizada exitosamente.


Para poder ver la aplicacion de este algoritmo en la programacion pondre este codigo que encontre en internet



#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;

int main(){
 
 char archivo[20], fcifrado[20], cadena[100];
 int key, xor;
 
 cout << "Nombre del fichero a cifrar: ";
 gets(archivo);
 cout << "Nombre del nuevo archivo ya cifrado: ";
 gets(fcifrado);
 cout << "Introduzca la llave para encriptar (1..255): ";
 cin >> key;

 //Creamos los archivos para leer y escribir...
 ifstream fichero(archivo,ifstream::in);
 ofstream cifrado(fcifrado,ofstream::out);
 
 //Mientras no lleguemos al final del archivo...
 while(!fichero.eof()){
  fichero.getline(cadena,100); //Leemos una linea con getline, el primer parámetro es el arreglo de char
  fflush(stdin);     //y el segundo es la cantidad máxima de caracteres que puede leer. 
  for(int i=0; i<strlen(cadena); i++){ //Recorremos cada caracter de la linea que leimos
        xor = (int)(cadena[i])^(key); //Aplicamos XOR a cada caracter con la "key" que introdujimos convirtiendolo a su valor en ascii (int)
   cifrado << (char)xor;  //Escribimos en el archivo el resultado del xor pero convirtiendolo en char. 
  }
  cifrado << endl; //Escribimos un salto de linea
 }
 system("pause");
}



A continuacion les mostrare un video de un ejemplo de la encriptacion xor para que pueda quedar mas claro


Fuentes de investigacion:
Imagen: