ESTRUCTURAS DE DATOS

UNION-FIND

O también llamado Disjoint-Set(Conjuntos Disjuntos), esta estructura de datos nos ayuda a particionar de alguna forma que nos convenga una serie de conjuntos que un principio todos están disjuntos(separados) vamos a verlo gráficamente.

Podemos ver que los 4 nodos están separados esa sería la definición de conjuntos disjuntos en teoría de grafos.

Pero, ¿para que nos puede ayudar esta estructura de datos?

Hace un tiempo en el club de algoritmia se nos dio a la tarea de resolver un problema con esta estructura y consistía en lo siguiente...

Existía una red social en la cual podías hacer amistad con alguna persona y esa persona podía hacer amistad con otra y al mismo tiempo tu podías hacer amistad con otra, básicamente todos podían ser amigos de todos. Entonces nos daban un número n que era el número de amistades que podían surgir, y para cada n teníamos que dar el nombre de las dos personas que se volvían amigos por ejemplo:

Definiremos a
q0 = Beto
q1 = Elisa
q2 = Esteban

q3 = Pedro
q4 = Estefany

q5 = Ivan

en un inicio todos en el conjunto todos son padre de sí mismos.

Con n = 3

Beto Elisa
Esteban Pedro
Ivan Estefany

después de formar las redes sociales:

Y lo que teníamos que decir era de que tamaño hasta ese momento con esas personas, que se volvieron amigos, era la red social. Para el caso anterior las respuestas serían:

Personas          Respuesta

Beto Elisa              2
Esteban Pedro        2
Ivan Estefany         2

¿Pero porque dos? Bien pues en un principio la unión de dos personas forma una red de tamaño 2 y ninguna de las uniones de personas en cada consulta se volvió amigo de otra red social, para entenderlo mejor pondré otro ejemplo:

Personas          Respuesta

Beto Elisa              2
Esteban Pedro        2
Elisa Estefany         3

En este caso Beto y Elisa formaron una red de 2 personas pero después Elisa se volvió amiga de Estefany entonces la red que era de dos personas agregó a su conjunto otra persona entonces se volvió una red total de 3 personas.

Y así sucesivamente se iban agregando conjuntos a otros conjuntos para más información sobre el problema pueden ver acá
Pero como resolverlo, es aquí donde entra la magia de esta estructura de datos Disjoint Set y el algoritmo de Union Find.

Un algoritmo Unión-Buscar es un algoritmo que realiza dos importantes operaciones en esta estructura de datos:

• Buscar: Determina a cual subconjunto pertenece un elemento. Esta operación puede usarse para verificar si dos elementos están en el mismo conjunto
• Unión: Une dos subconjuntos en uno solo.

Para ello entonces tendremos dos funciones importantes la de calcular raíz del conjunto que analicemos y la de unión y en c estarán implementadas de la siguiente manera:

Primero tendremos un arreglo llamado padre donde el índice i es el conjunto y el contenido en el indice i es su raíz o su padre.

padre[]    1   2   3   4   5   //Nótese que al inicio el padre de cada conjunto es si mismo

raiz         1   2   3   4   5   // porque cada uno forma un conjunto por si solo

Para la raíz

int raiz(int a){//Devolvera un entero para saber cual es la raiz y recibe el numero del que se quiere calcular su raiz

   if(padre[a] != a)//Si el padre de ese numero a su contenido quiere decir que esa no es su raiz

      return padre[a] = raiz(padre[a]); //Y en esa posicion se guarda el contenido del padre y se calcula recursivamente hasta que el padre de 'a' sea igual a 'a'

   return a;//y se regresa a 'a'

}

Para la unión:

void une(int a, int b){//Se reciben los dos números a unir

   raizA = raiz(a);//Se calcula la raiz de a y se guarda en raizA

   raizB = raiz(b);//Se calcula la raiz de b y se guarda en raizB

   padre[raizA] = raizB;//La raiz de b o raizB se convierte en el nuevo padre de a o raizA }

Esta función es muy interesante porque recibe los dos números que se quieren unir y se calculan sus raices y se guardan en dos variables raizA y raizB una para cada número y en el arreglo de padres en la posición de la raiz de a se guarda la raiz de b entonces el padre de b pasa a ser el padre de a y así se une dicho conjunto. Su complejidad es O(nlogn).

Por esta sesión es todo y sugiero si quieres entender mejor como funciona esta sensacional estructura de datos en este algoritmo agarres lápiz y papel y hagas tus pruebas de escritorio que en verdad sirven y notes como funciona. ¡Hasta la próxima!
 

Ya saben si tienen dudas escríbanme a adrian.ipod25@gmail.com. Visitenme en Twitter @ferprogramming. Saludos.

MEMOIZACIÓN

En uno de mis anteriores post había mencionado el término "memoización" específicamente en el del cálculo del factorial de un número implementado de manera recursiva. Bien ahora veamos en que consiste...
 Esta técnica de optimización suele emplearse sobre todo en algoritmos implementados de manera recursiva, básicamente lo que hace es reducir considerablemente el número de llamadas dentro de una función recursiva, esto evita cálculos innecesarios los cuales ya se habían hecho antes dentro de la función.
Para hacer más gráfica mi explicación tomaré el cálculo de los números de la sucesión Fibonacci.

Cuando tenemos una sucesión de Fibonacci decimos que nuestros casos base son cuando dada una función  fibo(1) es igual a 1, y fibo(0) = 0, visto de mejor forma:

si fibo(0) = 0

ó
si fibo(1) = 1

lo demás es sencillo pues solo calculamos las respuestas para un número (n-1) + (n-2), según la sucesión.
Ya para conocer mejor aquí implementada la sucesión Fibonacci en C de manera recursiva:

int fibo(int n){

   if(n<=0)

      return 0;

   if(n==1)
      return 1;

return fibo(n-1) + fibo(n-2);
}
Aquí tenemos el código de una sucesión Fibonacci pero, si nos ponemos a analizar un poco el problema podemos observar que se harán cálculos de números que posiblemente en otra llamada ya se hayan hecho, por ejemplo para el fibonacci de n = 5, el la primera llamada sería...

1) fibo(4) + fibo(3); //Calculando el fibonacci de 3 y 4

2) Para la llamada con n=4 fibo(3) + fibo(2)  y para n=3 fibo(2) + fibo(1); //Note que se repite el cálculo para la del 3 con la anterior llamada y en esta misma llamada la del 2 se calcula dos veces, así en la próxima recursión tendremos otras ocho llamadas en total.

Esto no suele ser óptimo ya que si lo hacemos para un n con valores muy grandes tendría que hacer el cálculo de cada llamada calculando para su n-1 y n-2 y sobre esas mismas aplicar el mismo procedimiento. 

Para optimizar esto la técnica consiste en memorizar cada respuesta que ya se haya calculado en un arreglo y verificar que no se haya calculado antes. Veamos...

1° Llenamos un arreglo un número "infinito" que jamás llegaremos a obtener en la sucesión de fibonacci.

2° Preguntamos ya en nuestra función recursiva si el número que calculamos es diferente a nuestro número "infinto"(antes puesto en el arreglo), esto nos quiere decir que sí es diferente a ese infinito quiere decir que ya ocupa otro número antes calculado su lugar entonces basta con regresar ese número porque ya ha sido calculado

3° Por último regresamos el calculo de los casos base dentro de nuestro arreglo.

NOTA: dentro de nuestra función el índice del arreglo será nuestra misma n.
El código mejorado queda así...
En el main...
fill(memo,memo+n,INF) // Paso 1. INF es nuestro "inifnito" y la función fill() esta en la librería algorithm de C++ y llena un arreglo de número, para más info, consulte el C++ Reference en internet. ^_^

int fibo(int n){

   if(memo[n] != INF)
      return memo[n];  // Paso 2

   if(n<=0)

      return memo[n] = 0;//Paso 3

   if(n==1)
      return memo[n] = 1; // Paso 3

return memo[n] = fibo(n-1) + fibo(n-2); //Paso 3
}
Así un ejemplo de prueba de escritorio...
1) Nuestro arreglo esta de la siguiente manera:
pos    0       1      2     3      4      5

val   INF   INF   INF   INF   INF   INF

2) Aquí posiblemente ya tenga el calculo para el níumero 1 y 0
pos  0   1     2      3     4      5

val   0   1    INF   INF   INF   INF

Y así se irá llenando nuestro arreglo hasta que llegue a un caso base y de la respuesta pero sin volver a recalcular un número puesto que el paso 2 pregunta que si nuestro número n es diferente a nuestro "infinito" lo cual si es cierto solo devuelve el mismo.
La memoización es una técnica que nos ayuda mucho sobre todo en la Programación Dinámica(dp), porque si hacemos Top-Bottom o sea recursiva una solución podemos memorizar y evitar el recálculo de números...
Eso fue todo por esta sesión y si hay dudas por favor escríbeme a adrian.ipod25@gmail.com, hasta pronto!

Estructuras de Datos (1):

LISTAS ENLAZADAS...

Empezaré por dar una breve introducción de lo que son las estructuras de datos, como bien sabemos podemos ordenar, guardar y/o manipular datos (números, caracteres, etc...) en arreglos unidimensionales, bidimensionales, o tantas dimensiones queramos darles, pero en muchas ocasiones la forma en que necesitamos usarlos no es la óptima para algún tipo de problema que se nos presenta.

Para eso existen la Estructuras de Datos, nos dan más formas de poder manipular los datos conforme a lo que necesitemos. Hoy vamos a tocar un poco el tema de las Listas (enlazadas), las cuales tienen la estructura LIFO por sus siglas en inglés "Last In, First Out" que quiere decir que el ÚLTIMO elemento en ENTRAR es el PRIMERO en SALIR. Expliquemos un poco esto con una imagen que me encontré por ahí...

Por defecto una lista que es vacía es también una lista, solo para aclarar.

Bien, expliquemos la imagen. Claramente se ve que tenemos una lista con 4 nodos. ¿Qué es un nodo? En las Listas es aquella parte de la estructura de datos, que se conforma de dos elementos:

1° Aquella que guarda el dato o elemento el cuál estamos manipulando y 2° El direccionador hacia el siguiente nodo en la Lista, también podemos llamarle APUNTADOR pero eso es más en cuestiones de programación y no de el concepto. Ahora metiéndonos más a la cuestión de programación analizaremos y les mostraré como se arma una Lista en C o C++.

typedef char* Elem;

typedef struct Nodo{ 

    Elem dato;

    struct Nodo *sig;

           }*Lista;

El siguiente código es la construcción de la Lista como tal, me refiero a su forma inicial siendo vacía y un apuntador apuntando a nulo (NULL) válgase la redundancia. Primero vemos nuestro "Elem" previamente yo lo definí como un typedef de tipo caracter que tengo en otra librería, pero aquí solo lo creo como un apuntador a caracter para poder manipularlo en mi Lista. Después creo un tipo de dato Nodo (typedef struct Nodo) que en realidad va a ser un apuntador a Lista (*Lista). Dentro de todo mi tipo de dato Nodo tengo dos elementos:

1° Elem dato: este será un apuntador a caracter, la parte de la Lista donde se almacenará mi DATO.

2° struct Nodo *sig: parecería que es complicado hasta entenderlo, pero es simple , tenemos un apuntador llamado sig (*sig) que de forma recurrente apuntará a mi tipo de dato Nodo (struct Nodo) y así de forma sucesiva en cada nodo que se cree.

O sea que cada nodo tendrá un dato guardado y un apuntador al siguiente nodo como lo vemos aquí:

struct Nodo{

   Elem dato;

   *sig;----------------------->struct Nodo{

                                               Elem dato;

                                                *sig;------------->struct Nodo{

   }                                                                            Elem dato;

                                                                                *sig;------>NULL;

                                                                                  }

Apuntará a NULL hasta que dejemos de meterle elementos a nuestra Lista.

Cabe decir que las Listas se crean de forma Dinámica es decir se crean tantos espacios para datos como los necesitemos.

La Estructura de Datos, Lista es desde mi punto de vista la más fácil de implementar, aunque también de las más difíciles en entender pues fue la primera con que me tope yo, pero después en las demás estructura ya tienes mas dominado el concepto.

Ahora, en C++ ya esta definido el tipo de dato Lista para usarlo así como sus funciones, la podemos usar declarando la librería:

#include<list>

y la creamos así...

list<tipo_de_dato> nom_Lista;

Para más información se puede checar el reference en: http://www.cplusplus.com/reference/list/list/

ahí se encuentran todas las funciones, además si tienen dudas de como implementarlas pueden escribirme a mi correo: adrian.ipod25@gmail.com.

Con esto concluimos el tema de Listas Enlazadas y pueden escribirme sus dudas y en cuanto tenga tipo les responderé, el siguiente tema veremos la ED Pila...

Aquí la librería de la Lista con mis funciones:

https://drive.google.com/file/d/0B0PEfOTzyLQAdWhRQnFGM093clk/edit?usp=sharing

También incluí las funciones para usarse con archivos :).

Recursividad

La recursión es un proceso muy natural en la programación ya que con la práctica es muy fácil implementarla, profundicemos un poco...

Caso contrario de la iteración, la recursión va de un caso general a un caso particular en donde se va desglosando en subproblemas hasta llegar a un caso en donde el problema es obvio y evidente.

Pongamos el famoso ejemplo del factorial de un número aplicado en programación con la Recursión.

Se tiene un número n! con n = 5, la solución a el factorial de este número no la conocemos, pero si profundizamos y buscamos la solución de raíz llegaremos al resultado.

Donde:

5! = 5 * (4!)

5! = 5 * 4 * (3!) 

5! = 5 * 4 * 3 * ... (1!)

así hasta llegar al caso en el cuál sea obvio, como el factorial de 1! = 1.  

En pseudocódigo la función recursiva como solución a este problema sería de la siguiente manera:

Fact(n){

 si n == 1

   ret 1;  

ret n * Fact(n-1); 

}

//(n==1) Nuestro caso obvio donde conocemos el resultado y también es nuestro punto donde la recursión pare y nos devuelva el resultado.

//(n*Fact(n-1)) Aquí n multiplicará al valor de n restandole 1 y así sucesivamente hasta llegar al caso cuando n valga 1 y nos arroje la multiplicación de n hasta 1.

Cabe decir que en C o C++ bien codificado el algoritmo funciona de maravilla, aunque, no para números muy grandes, por el stack de la pila recursiva de C. Pero existen maneras de hacerlo más óptimo con la memorización tema que veremos después en este blog.