Monday, May 24, 2010

Proyecto 5 - Transitive Closure


Clausura Transitiva
La clausura transitiva de un grafo G se define como el grafo G* = (V, E*), donde E*={(i, j): hay un camino desde el vértice i al vértice j en G}.
Definición Formal:
Optimización: ¿Cuáles son los caminos existentes entre pares de nodos?
Recordemos transitividad:
El concepto de transitividad es el mismo que se utiliza en teoría matemática el cual postula que si a<b<c Þ a<c, en el caso de clausura transitiva, el concepto se refiere a que existe un camino que une el vértice i con el vértice j, no importando que para llegar desde i a j tengamos que visitar otros vértices del grafo. Por esta razón es que el algoritmo fue diseñado para grafos dirigidos, donde si es importante hacia donde están apuntando los vértices, ya que en digrafos muy grandes, el problema de encontrar caminos entre pares de vértices es demasiado complicado, sólo siguiendo el trazado del dibujo del mismo, de ahí la importancia de este algoritmo y el interés que generó su estudio.   

Trabaja sobre grafos orientados, i G es no orientado, se sustituye cada arco, si G es orientado, se dice que el vértice B es alcanzable desde A si existe en G un camino desde A hasta B.






Objetivo: Determinar si cada par de vértices es alcanzable entre sí en un grafo orientado G







A
B
C
D
A
1
0
0
1
B
0
1
1
1
C
0
0
1
0
D
1
0
1
1

Proposición: Hay un camino de largo k desde A hasta B en un grafo G=(V, E) si y sólo si (A,B) Є EK, donde EK es la composición k-ésima de la relación E k veces, siendo E0 la relación identidad.

El algoritmo recibe una matriz de adyacencia que sería el grafo inicial, y regresa una matriz de alcance la cual se agregan aristas indicando si es posible llegar del nodo A al nodo B.
La matriz de alcance indica la existencia de caminos entre pares de nodos.


El algoritmo utilizado para encontrar la clausura transitiva de un grafo dirigido es muy parecido al algoritmo de Floyd_Warshall, con la diferencia que este utiliza las operaciones lógicas Ú y Ù, sustituyendo las aritméticas min y + usadas por Floyd_Warshall, además que rellena la matriz de adyacencia sólo con 0 y 1, a diferencia del otro que les asocia un peso a cada arista que está en el grafo, y si no hay conexión entre los vértices, entonces le asigna ¥.

Generalizando los pasos:
  1. A los 0 de la matriz de adyacencia los ponemos como infinitos.
  2. Floyd intenta sacar un camino
  3. Al final sustituimos costos por 1s e infinitos por 0s.

Algoritmo Propuesto:

transclosure( int adjmat[max][max], int path[max][max])
{
 for(i = 0; i < max; i++)
  for(j = 0; j < max; j++)
      path[i][j] = adjmat[i][j];

 for(i = 0;i <max; i++)
  for(j = 0;j < max; j++)
   if(path[i][j] == 1)
    for(k = 0; k < max; k++)
      if(path[j][k] == 1)
        path[i][k] = 1;
}

El costo asociado a este algoritmo es de 0(n3), ya que el costo de encontrar la matriz de alcance está íntimamente ligado con los ciclos que se necesitan para recorrer la matriz, además por ser un algoritmo de programación dinámica el costo tiene que ser polinomial.  
Una vez aplicado el algoritmo la matriz de alcance del ejemplo sería:











A
B
C
D
A
1
0
1
1
B
1
1
1
1
C
0
0
1
0
D
1
0
1
1


    A continuación adjunto un archivo con el contenido del reporte con su respectiva codificación en c++.

http://groups.google.com/group/algcomp/web/Proyecto%205%20-%20Transitive%20Closure.zip

Bibliografía:







Proyecto 4 - Hash Table

Tablas de Dispersión

Las tablas de dispersion: Es una estructura de datos compuesta por listas en un arreglo y que cuenta con una función de disepersión la cual decide en que casilla del arreglo estara el parametro entrante.

¿Qué hice yo?

Me encarge de delegar tareas en el equipo de tal manera que cada quien se desenvolviera en el proyecto de acuerdo a las fortalezas de cada integrante.

¿Como me salio?
Muy bien, logre implementar una tabla de dispersión con su respectiva función de disepersión.


¿En que aspectos estoy bien y en qué me hace falta mejorar?
Los puntos fuertes es la dedicación, sin embargo un punto en contra muy fuerte es la administración de tiempo.


¿Ayudo a los demas o me apoyo en ellos?
Ambas partes son escenciales para un buen trabajo en equipo, asi que trato de hacer ambas siempre.


¿Qué papel tomo yo?
Tome la parte técnica del proyecto, la implementación y parte en coordinación.

¿Quién se encarga de coordinar a los demas?
Todo el equipo se encargo de esta tarea.

Presentación:


Estos son los blogs de mis compañeros de trabajo:

http://htinajero.blogspot.com/
http://salomon-karr.blogspot.com

    A continuación adjunto un archivo con el contenido del reporte con su respectiva codificación en c++.

http://groups.google.com/group/algcomp/web/Proyecto%204%20-%20Hash%20Table.zip
 

Monday, March 22, 2010

Proyecto 3 - Distance of Levenshtein

Contenido de reporte 

Recursión
Es una forma de solucionar algunos problemas un tanto drásticos ya que la mayoría de las veces aumenta las posibilidades de una forma espantosa, consta de un procedimiento que realiza una serie de pasos llamándose a sí mismo y volver a realizar la acción 1 o más veces.

Fortaleza del equipo
La investigación y el trabajo en equipo fue nuestra fortaleza más importante ya que cada integrante aporto algo al proyecto ya sea en la investigación de términos o de algoritmos para el problema presentado.

¿Qué fue tu contribución al trabajo?


La investigación de los 2 diferentes algoritmos y tratar de aportar en aprendizaje a mis compañeros.

¿Cómo compara lo que hiciste tú con el trabajo de los demás?

Mis compañeros realizaron un trabajo de investigación de términos y material, mientras yo me encargue de los algoritmos y orden asintótico del mismo.

¿Qué podrías mejorar en el futuro?

Los horarios de trabajo y la sincronización de nuestro equipo. 

Ligas a los blogs de los demás de tu grupo
http://w0oh0o.blogspot.com/
http://blankardz22.blogspot.com/
http://www.adrianaa17.blogspot.com/
http://lauraegh.blogspot.com/

    A continuación adjunto un archivo con el contenido del reporte con su respectiva codificación en c++.

http://groups.google.com/group/algcomp/web/Proyecto%203%20-%20Distance%20of%20Levenstein.zip

Sunday, March 21, 2010

Proyecto 2 - Subset sum problem


Subset Sum Problem

El problema de la suma de sub conjuntos es una buena introducción para los problemas NP Completos, este es un problema de decisión y no de optimización, y tiene una definición forma muy simple.
Dada el problema puede ser resuelto con una función generadora. Considerando el numero de formas C(m,s) a seleccionar m de M números enteros {a1,….am} tales que su suma es igual a s y se define la función generada como:





Al ampliar “y” esto se convierte

pero como resultado de la ley de exponentes x^m x^n = x^(m+n), Gm(x) es precisamente la función que desee generar:







Por ejemplo:
Dado C un conjunto (15, 22, 14, 26, 32, 9, 16, 8) y s =53. Entonces una solución a G(C,53) está dado por el vector X = (1,1,0,0,0,0,1,0), porque CX = a1 + a2 + a7 = 15 + 22 +16 = 53.El correspondiente del subconjunto es C = (15,22,16).
En general ahí puede existir varias soluciones a (C,s) como por ejemplo otra solución es X = (0,1,1,0,0,1,0,1) con el subconjunto C’ = (15,22,16).

El problema de decisión sería:
¿Existe un subconjunto m de M que contenga una suma s?     

Algorithm 1: Exact-Subset-Sum(S, t)
n  <− |S|
L0  <− h0i
Para i = 1 a n hacer:
Li  <− MergeLists (Li1,Li1 + xi)
Elimina para Li cada elemento más grande que t
Regresa el elemento más grande para Ln

Algoritmo de tiempo exponencial en general, ya que la duración de Li puede ser tan alta como 2^i.

El problema es NP Completo.


Bibliografía
http://en.wikipedia.org/wiki/Subset_sum_problem
http://www2-fs.informatik.uni-tuebingen.de/~reinhard/krypto/English/4.5.1.e.html
http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/nanda-scribe-3.pdf
http://mathworld.wolfram.com/SubsetSumProblem.html



    A continuación adjunto un archivo con el contenido del reporte con su respectiva codificación en c++.

http://groups.google.com/group/algcomp/web/Proyecto%202%20-%20Subset%20sum%20problem.zip

Friday, February 26, 2010

Proyecto 1 - Knapsack

Problema de la Mochila - Reporte de solución al algoritmos para generar el máximo de valores de un conjunto de productos de una mochila con capacidad limitada.

Desarrollo y lógica del problema

    Una solución al algoritmo sobre generar el máximo de valores de un conjunto de productos en una mochila con capacidad limitada puede resultar un tanto confuso, una forma para resolver el problema es mediante un árbol de decisiones, donde por ejemplo para un listado de 4 productos donde la capacidad de la mochila es de 936 tenemos la siguiente tabla.


Productos: 4
 Capacidad: 936
Producto    Valor       Volumen
1                  700             440
2                  258             117
3                  952             811
4                  993             491
    Necesitamos introducir un conjunto de productos que no sobrepasen la capacidad de la mochila y necesitamos saber cual es la mayor cantidad de valor que podemos recolectar. Una solución para esto es mediante el uso de un árbol de decisión por ejemplo a continuación:



    Entendemos que para cada nivel es un producto y que todos los nodos naranjados son los nodos que se permitieron entrar a la mochila, aquí el ganador es el camino que junte mas valor, por ejemplo: para la entrada anterior el resultado sería 1693 que nos indica la raya roja ganadora.

    El volumen del producto 1 y producto 4 no superan los 936 y la suma de sus valores superan cualquier otro.


    Otro ejemplo con un número de productos mas grande sería:

Productos: 8
Capacidad: 931
Producto       Valor       Volumen
1                   431           823
2                   590           359
3                   153           899
4                   370           292
5                   698           404
6                   876           699
7                   705           442
8                   527           757

    Aquí el resultado sería 1403 sumando los Productos 5 y 7.


Código y Pseudocódigo

cantidadProducto
cupoLimite
vectorValores[1000]
vectorEspacio[1000]

ganador = 0
producto = 0


procedimiento genera(espacio,valor,producto)
    //En este bloque paramos la búsqueda en el árbol
    si producto es igual a cantidadProducto entonces
        si ganador < valor entonces ganador <- valor
        regresa
    fin si

   
    //Si aun nos cabe el proximo producto creamos una rama con el valor positivo
    si espacio+vectorEspacio[producto] <= a cupoLimite entonces
        llama genera(espacio+vectorEspacio[producto],valor+vectorValor[producto],producto+1)
    fin si

   
    //Tambien creamos una rama en el arbol para que el producto no entre
    llama genera(espacio,valor,producto+1)
fin procedimiento



procedimiento main()

    lee cantidadProducto
    lee cupoLimite



    //Leemos los productos (su valor y espacio que ocupan)
    para i=0 hazta i<n haz i+1
        lee vectorValores[i]
        lee vectorEspacio[i]
    fin para

   
    //Generamos el arbol
     llama genera(0,0,0)

     imprime ganador

fin procedimiento


    A continuación adjunto un archivo con el contenido del reporte con su respectiva codificación en c++.

http://groups.google.com/group/algcomp/web/Proyecto%201%20-%20Knapsack.zip

Tuesday, February 9, 2010

3.1 - Maquina de turing que resta 1 en binario


Maquina de turing que resta 1
ΡЄΚ
σЄ
(Ρ,σ)
s
s,►,->
s
0
s,0,->
s
1
q,1,->
s
|_|
r,|_|,<-
q
0
q,0,->
q
1
q,1,->
q
|_|
t,|_|,<-
t
0
t,-1,-
r
0
r,1,<-
r
1
r,0,-

Tuesday, February 2, 2010

2.4 - Resta Binaria

Aquí otro ejemplo con la misma mecanica que la suma binaria pero aplicada a la resta.

------------------------------------------------------------------------------------------------

#include <iostream>
#include <string>
#include <algorithm>

int mayor[25];
int menor[25];

//Nota: El std:: significa que usamos algun elemento de la biblioteca estandar

void convierte(unsigned long n1, unsigned long n2){
    std::string binario;                                //Definimos string del resultado
    int c=0;
    for(unsigned long i=n1,j=n2;i!=0 || j!=0;i/=2,j/=2){
        if(n1 >= n2){                                    //Acomodamos el mayor - menor para que no quede resta negativa
            if(i % 2 != 0){
                mayor[c] = 1;
            }else{
                mayor[c] = 0;
            }
           
            if(j % 2 != 0){
                menor[c] = 1;
            }else{
                menor[c] = 0;
            }
        }else{
            if(i % 2 != 0){
                menor[c] = 1;
            }else{
                menor[c] = 0;
            }
           
            if(j % 2 != 0){
                mayor[c] = 1;
            }else{
                mayor[c] = 0;
            }
        }
        c++;
    }
   
    for(int i=0;i<25;i++){
        if((mayor[i]-menor[i]) < 0){                    //Acomodamos el algoritmo como cualquier resta
            mayor[i+1] -= 1;
            mayor[i] += 2;                                //Como el sistema es binario aumentamos 2
            std::cout << 'h';
        }

        binario.push_back('0' + (mayor[i]-menor[i]));    //Asignamos en la cadena el resultado
        mayor[i] = 0;                                    //Reiniciamos los valores
        menor[i] = 0;
    }
  
    std::reverse(binario.begin(),binario.end());        //Como push_back lo inserta adelante de la cadena, lo invertimos
   
    if(binario.empty()){
            binario.push_back('0');                        //Si nos dieron 0 les davolemos 0
    }
      
       std::cout <<"Resta: " << binario <<"\n\n\n";
}

int main(){
    unsigned long n1,n2;
    while(std::cin>>n1>>n2){                            //Ciclo los valores decimales
        convierte(n1,n2);
    }
  
    return 0;
}

2.3 - Suma Binaria

Aquí una forma para simular la suma binaria, me salio algo largo el código, después tratare de mejorarlo un poco, uso un algoritmo simple de suma sobre la base del sistema en este caso binario.

----------------------------------------------------------------------------------------------------

#include <iostream>
#include <string>
#include <algorithm>

bool decimal1[25];
bool decimal2[25];

//Nota: El std:: significa que usamos algun elemento de la biblioteca estandar

void convierte(unsigned long n1, unsigned long n2){
    std::string binario;
    int c=0,acomulado=0;
    for(unsigned long i=n1,j=n2;i!=0 || j!=0;i/=2,j/=2){    //Calculamos los numeros binarios
        if(i % 2 != 0){
            decimal1[c] = 1;
        }else{
            decimal1[c] = 0;
        }
       
        if(j % 2 != 0){
            decimal2[c] = 1;
        }else{
            decimal2[c] = 0;
        }
        c++;
    }

    for(int i=0;i<25;i++){
        binario.push_back('0' + ((decimal1[i]+decimal2[i]+acomulado) % 2)); //Calculamos el resultado del digito
        acomulado = (decimal1[i]+decimal2[i]+acomulado)/2;    //Acomulamos si sobrepaso la base
        decimal1[i]=0;                                        //Reiniciamos los valores
        decimal2[i]=0;
    }
  
    std::reverse(binario.begin(),binario.end());            //Como push_back lo inserta adelante de la cadena, lo invertimos
   
    if(binario.empty()){
        binario.push_back('0');                                //Si nos dieron 0 les davolemos 0
    }
      
       std::cout <<"Suma: " << binario <<"\n\n\n";                //Resultado
}

int main(){
    unsigned long n1,n2;
    while(std::cin>>n1>>n2){                                //Ciclo pidiendo los valores decimales
        convierte(n1,n2);
    }
  
    return 0;
}

Thursday, January 28, 2010

2.2 - Decimal a Binario Forma 2

Aqui otra forma un poco mas sencilla de resolver el problema de convertir decimal a binario, radica en tener el decimal y dividirlo entre 2, si resulta non el bit es activo, se vuelve a dividir entre 2 (sin fracción) y si resulta par el bit es inactivo, asi hasta obtener 0.

Como lo vamos almacenando de izquierda a derecha, solo invertimos el orden.

Nota: Si lo realizan en alguna libreta, pongan los bits de derecha a izquierda.

---------------------------------------------------------------------------------------------------------------------------------

#include <iostream>
#include <string>
#include <algorithm>

//Nota: El std:: significa que usamos algun elemento de la biblioteca estandar

std::string convierte(unsigned long n){
    std::string binario;                    //Declaramos una cadena
   
    for(unsigned long i=n;i!=0;i/=2){        //Repetimos la operacion n bits (la calculamos dividiendo hasta que de 0)
        binario.push_back('0' + (i % 2));     //Dividimos entre 2 si es non el bit es activo
    }
   
    std::reverse(binario.begin(),binario.end()); //Como push_back lo inserta adelante de la cadena, lo invertimos
   
    if(binario.empty()){
        binario.push_back('0');                //Si nos dieron 0 les davolemos 0
    }
   
    return binario;
}

int main(){
    unsigned long n;
    while(std::cin>>n){                        //Ciclo pidiendo el valor decimal
        std::cout<<convierte(n)<<"\n\n";    //Imprimimos
    }
   
    return 0;
}

2.1 - Decimal a Binario Forma 1

El siguiente problema es un ejemplo de como resolver el problema de conversión de decimal a binario de la forma que la maestra nos explico en clase. Incluye algunos comentarios.

-------------------------------------------------------------------------------------------------------------

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

unsigned long temp = 0;

void convierte(unsigned long decimal,int cont){
    bool bit;   
   
    if(cont == -1){                        //Calcula la potencia
        if(decimal == 0){ std::cout << 0; return; }
        while(temp<=decimal){
            temp = pow(2,cont);
            cont++;
        }
         cont -= 2;
    }
   
    temp = pow(2,cont);                    //Temporal a restar
   
    if(temp<=decimal){                    //Decide si es bit activo o no
         bit = 1;
        decimal -= temp;                //Resta del decimal
    }else{
        bit = 0;
    }
   
     std::cout << bit;                    //Imprimimos el bit
   
    if(cont > 0){                         //Recursion para seguir calculando
        cont--;
        convierte(decimal,cont);
    }
   
}

int main(){
    unsigned long dec;
   
    for(;;){                            //Ciclo infinito
        std::cout << "\nNumero a convertir: ";
        std::cin >> dec;                //Leemos el decimal
        convierte(dec,-1);
    }
   
    std::cout<<"\n";
   
    return 0;
}