sábado, 13 de agosto de 2016

Matriz de adyacencia para un grafo



"La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias."; aunque para nuestro caso será una de las formas de representar un grafo.

¿Por que matriz cuadrada? (si fuera profesor lo preguntaría para pescar a más de un distraído), la razón es que tanto las filas como las columnas representan cada uno de los nodos del grafo, si el grafo es de n nodos, la matriz correspondiente sería de n * n, es decir matriz cuadrada, fácil.

Continuemos analizando el paso de grafo a una matriz.


Como ya sabemos al tener 6 nodos nuestro grafo, nuestra matriz tendrá unas dimensiones de 6 * 6, es decir 6 filas y seis columnas.

Si nos fijamos en lo que consideraremos nuestro primer nodo, el nodo uno solo esta conectado con el nodo 2 y 5; en la fila 1 que representa el nodo 1 se ha marcado con ceros los nodos con que no se tiene relación y se ha fijado un 1 en los que si, el nodo 2 y 5.

Si nos fijamos en lo que consideraremos nuestro segundo nodo, el nodo dos esta conectado con el nodo 1, 3 y 5; en la fila 2 que representa el nodo 2 se ha marcado con ceros los nodos con que no se tiene relación y se ha fijado un 1 en los que si, el nodo 1, 3 y 5.

Análogamente hacemos de igual forma con los demás nodos hasta terminar el grafo.

Les dejo algunos ejemplo y un ejecutable en Java de mi autoría para que se diviertan.
Clic aquí para descargar ejecutable.



viernes, 19 de febrero de 2016

Métodos de ordenamiento usando java

Cuando tenemos una estructura de datos una de las operaciones más relevantes es ordenar el contenido de la misma, ya sea para hacerla más amistosa de leer o mejor aún para aplicar más operaciones sobre dichos datos como por ejemplo hacer búsquedas en ellas, (véase búsqueda binaria y búsqueda secuencial).

El ordenamiento en una estructura de datos la podemos definir como los posibles cambios aplicados a la posición de los datos que la llevaría a estar una relación de orden, ésta relación de orden puede ser alfabética, numérica, entre otras.




Aunque la formulación del problema es fácil y hasta cotidiana, tanto como dar una secuencia de números aleatorios a alguien y pedirle de los ordene de mayor a menor; existen muchos métodos para la resolución de éste problema, y aún en la actualidad se sigue trabajando en ello para lograr cada vez más rapidez y eficacia.

En éste blog abordaré varios de los métodos más usados para la ordenación de datos y que a su vez nos servirán como introducción a éste tema usando Java como lenguaje de programación.

Clic para ver el método de selección.
Clic para ver el método de inserción. (próximamente)
Clic para ver el método de burbuja. (próximamente)
Clic para ver el método de shell. (próximamente)



Método de ordenamiento por selección usando Java

Es un método poco eficiente pero fácil de entender, en caso de ordenar números éste consistirá en determinar cual es el menor de todos y ubicarlo en la primera posición, luego determinar cual es el segundo menor y ubicarlo en la segunda posición hasta terminar con todo los numero.

La cantidad de comparaciones para éste método de ordenamiento está dada por la fórmula: c(n) = (n² – n)/2; es decir para un arreglo de 10 elementos el numero de comparaciones es de (10² – 10)/2 = 45; en el siguiente código fuente al descomentariar la linea 7 y compilar notarán el número de comparaciones.

Analizando podemos darnos cuenta que aunque nuestro arreglo a mitad del proceso este ordenado, el método seguirá haciendo comparaciones innecesarios haciéndolo poco eficiente sobre todo para grandes cantidades de elementos.

Sin más preámbulos, el código:




class seleccion{
 public static void ordenar(int[] arreglo){
  int contador = 1;//solo util para contar las comparaciones
  for (int i = 0; i < arreglo.length - 1; i++){
   int min = i;
   for (int j = i + 1; j < arreglo.length; j++){
   //System.out.println("Comparacion #" + contador);
    contador++;
    if (arreglo[j] < arreglo[min]){
     min = j;
    }
   }
   if (i != min){
    int aux= arreglo[i];
    arreglo[i] = arreglo[min];
    arreglo[min] = aux;
   }
  }
 }
 public static void imprimirLista(int[] arreglo){
  for(int i = 0; i < arreglo.length;i++){
   System.out.print(arreglo[i]+",");
  }
  System.out.println();
 }
 public static void main(String[] args){
  int lista[] = {9,1,4,2,8,3,5,6,7,0};
  System.out.print("Lista desordenada: ");
  imprimirLista(lista);
  
  ordenar(lista);

  System.out.print("Lista ordenada: ");
  imprimirLista(lista);
 }
}

Deseaba en ésta entrada hacer una prueba de escritorio al método, pero haré algo mejor, agregaré comentarios de salida al codigo para detallar cada comparación de la lista que ustedes introduzcan, abajo está el link de descarga, espero les guste y hagan sus comentarios.

Descarga aqui codigo con prueba de escritorio



jueves, 10 de diciembre de 2015

Recursividad usando java





Saludos lectores, aunque éste tema está muy bien documentado en Internet, a continuación lo expongo de manera fácil y como de costumbre con código.

Definición: Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva o recurrente (Por Wikipedia).

En pocas palabras, usamos recursividad cuando un método se llama a sí mismo para resolver un problema.

Expongo un método no muy común para darlo como ejemplo, pero fácil de entender:

public class recursividad{
 private static int suma(int a,int b){
  return a + b;
 }
 private static int suma(int a,int b,int c){
  return suma(suma(a,b),c);
 }
 private static int suma(int a,int b,int c,int d){
  return suma(suma(a,b),suma(c,d));
 }
 private static int suma(int a,int b,int c,int d, int e){
  return suma(suma(a,b,c,d),e);
 }
 public static void main(String []args){
  int a = 1;
  int b = 3;
  int c = 4;
  int d = 5;
  int e = 6;
  System.out.println(suma(a,b));
  System.out.println(suma(a,b,c));
  System.out.println(suma(a,b,c,d));
  System.out.println(suma(a,b,c,d,e));
 }
}

El anterior código desde el punto de vista de algoritmo no es exactamente recursividad ya que éste codigo funciona gracias a una propiedad presente en Java llamada poliformismo; pero es un buen ejemplo de inicio para entender.

Si observamos el primer método suma que recibe por parámetros dos número enteros es el que hace la operación arismetica de la suma, los demás métodos suma se benefician de manera recursiva del primero.

Muchos problemas mátematicos se pueden resolver de manera recursiva, pero por lo general es el problema y nuestra forma de abordarlos lo que define si se puede o no resolver de manera recursiva.
Hosting

Pasemos a un ejemplo más practico y usado para enseñar recursividad, hallar el factorial de un numero usando la recursividad en Java.

El factorial de un numero se define de la siguiente forma:

n! = 1 X 2 X 3 X 4 X ... X (n -1) X n

O de ésta otra forma más facil para nosotros: n! = 1 * 2 * 3 * 4 * ... * (n -1) * n

Para entender mejor miremos ejemplos y lo facil que es calculemos 5! que se lee factorial de 5.

5! = 1 * 2 * 3 * 4 * 5 =  120

Calculemos otros factoriales.

3! = 1 * 2 * 3 = 6

2! = 1 * 2 = 2

Surge una pregunta, cual es el factorial 0?, por definición el factorial de cero es uno, es decir ( 0! = 1 ), ¿Por que?, soy sincero, ésta respuesta la saben los matematicos y ellos la pueden explicar mejor que yo, con todo y demostración.

Antes de seguir hay algo muy importante al momento de hacer métodos recursivos, hay que tener un caso base; el caso base es el punto en el código donde acaba la recursividad, sin este caso base se generaría una recursividad infinita, más adelante mostraremos con ejemplo el caso base.




Sigamos calculando factoriales:

Ya sabemos que factorial de 5 es  1 * 2 * 3 * 4 * 5; pero podemos decir que es igual a (1 * 2 * 3 * 4) * 5; hasta aqui lo unico que hicimos fue agrupar (1 * 2 * 3 * 4) y multiplicarlo por 5; asi:

5! = 1 * 2 * 3 * 4 * 5 = (1 * 2 * 3 * 4) * 5 = 120

pero a que es igual  (1 * 2 * 3 * 4) ?

(1 * 2 * 3 * 4) = 4!

Es decir que:

5! = 4! * 5

Si se fijan aqui ya hay recursividad, para hallar el factorial de 5 necesitamos hallar el factorial de 4.

Este orden de idea resolveremos el factorial de 5 paso a paso, y usando algo asi como una prueba de escritorio.

Factorial de 5?
5! = ?

Factorial de 5 es factorial de 4 por 5
5! = 4! * 5

Pero no se cual es el factorial de 4, facil, factorial de 4 es factorial de 3 por 4
4! = 3! * 4

Pero no se cual es el factorial de 3, facil, factorial de 3 es factorial de 2 por 3
3! = 2! * 3

Pero no se cual es el factorial de 2, facil, factorial de 2 es factorial de 1 por 2
2! = 1! * 2

Pero no se cual es el factorial de 1, facil, factorial de 1 es factorial de 0 por1
1! = 0! * 1

Pero yo si se cual es el factorial de 0, por definición 0! = 1; éste es nuestro caso base.

Ahora toca devolverse para ir resolviendo lo calculos que dejamos pendientes atras asi:
si: 0! = 1
y si: 1! = 0! * 1
entonces:
1! = 1 * 1 = 1

si: 1! = 1
y si: 2! = 1! * 2
entonces:
2¡ = 1 * 2 = 2

si: 2! = 2
y si: 3! = 2! * 3
entonces:
3¡ = 2 * 3 = 6

si: 3! = 6
y si: 4! = 3! * 4
entonces:
4¡ = 6 * 4 = 24

si: 4! = 24
y si: 5! = 4! * 5
entonces:
5¡ = 24 * 5 = 120

Cuando nos regresamos a resolver las operaciones que dejamos pendientes, nuestros computadores también lo hacen cuando resuelven algoritmos recursivos, dichas operaciones pendientes por resolver las almacenan en las llamadas pilas de procesos, es por esta razón que nuestros algoritmos recursivos exigen más de nuestros computadores que los algoritmos no recursivos.




Una cosa curiosa que ustedes han notado, es que hacer nuestras pruebas de escritorio de algoritmos recursivos resultan largos pero ironicamente las linea de código que usamos es menor vs no recursivos.

Como ya habiamos visto la forma de representar el factorial de un numero es:

n! = 1 * 2 * 3 * 4 * ... * (n -1) * n; ésta es la forma iterativa y se resumen en una sucesión de multiplicaciones que parten de uno y terminan hasta el numero que deseamos calcular.


Ahora miremos como representar el calculo de un número factorial usando recursividad:

n¡ = (n - 1)! * n

pero para tener encuenta el caso base para que no se nos valla la recursividad al infinito la definiremos mejor así:


Sin más preambulo, les comparto el sencillo código para calcular factorial de un número de manera recursiva.
public class factorial{
 private static double factorial(int n){
   if (n==0){//caso base
   return 1;
  }else{
   return (factorial(n-1))*n;
  }
 }
 public static void main(String []args){
  System.out.print(factorial(5));
 }
}

Otro problema que se puede resolver recursivamente es la sucesión de Fibonacci, el codigo ya lo hice en una entrada anterior, aquí te dejo el link

Chao y exitos a todos



martes, 1 de diciembre de 2015

DJ Java Decompiler







Saludos a todos, me gustaría compartir con ustedes esta útil herramienta DJ Java Decompiler, que nos permite descompilar archivos de java class-file y guardarlos posteriormente en archivos de textos de manera simple y fácil.

Es compatible para las plataformas Windows 7, Windows 8, Windows NT/2000, Windows NT/2000/2003/SBS2003, Windows Vista, Windows XP.

Funciona descompilando y/o reconstruyendo el código fuente original de los archivos CLASS binarios compilados.

Ademas esta aplicación no necesita tener instalado Java para funcionar y como punto adicionar sirve como editor y todas las funciones típicas.

DJ Java Decompiler es adecuado para el estudio de bytescode de Java. El programa permite a los usuarios guardar, imprimir, editar y compilar el código Java generado. Incluido Applet Tag Editor permite a los usuarios crear applets rápidamente.

Aquí les dejo el link para que descarguen una versión trial y exploren esta herramienta


Si les gustó pueden tener la versión completa en este otro link, descarga completa

EXITOS



lunes, 28 de julio de 2014

Web scraping para consultar contenido en paginas web ajenas, llenar formularios y capturar respuesta usando Java.





Saludos a todos.

La siguiente entrada resolverá las siguientes incógnitas:
  • ¿Cómo capturar el contenido de una pagina web usando Java?
  • ¿Cómo llenar con datos un formulario de una web ajena y enviar los datos usando Java?
  • ¿Cómo llenar con datos un formulario de una web ajena, enviar los datos y capturar la respuesta usando Java?
La solución a las anteriores dudas nos será de mucha utilidad si por ejemplo tienes muchos datos que deseas consultar en un formulario web y deseas automatizar dicha tarea.

Empecé a practicar web scraping sin saber que lo hacia, a mi esposa le encomendaron la tarea de consultar un poco mas de 1000 cédulas (dni en otros países) para determinar, mesa de votación, lugar y dirección donde debía realizar el sufragio para elección de senado y cámara en mi país Colombia, todo esto lo debía hacer desde una desde la pagina que el gobierno habilita http://wsr.registraduria.gov.co/servicios/elec-presidente2014.htm.

Mi esposa me solicitó ayuda para realizar la descomunal tarea, para mi dicha tarea es tediosa y representa perder mi tiempo en algo que no quería hacer, pesé que debía haber una forma de automatizar dicha tarea; así que con ayuda de mi amigo Google nos pusimos en la tarea de averiguar como hacer tal cosas.

Las sugerencia que encontramos nos dirigirían a que debía integrar un web browser a una aplicación Java, después de intentar con muchas librerías de las cuales la mayoría hacían el problema más grande, me quede con htmlunit.

¿Porque integrar un web browser? Mi idea era emular un navegador web y consultar dato por dato, pero aclaro que esto no lo haría yo, lo haría mi PC el cual no se aburre y hace esta tarea mucho más rápido que yo.

Hosting

Les dejo un vistazo de la aplicación funcionando.



Es hora de ver código,  le ofrezco uno muy básico y fácil de comprender que les ayudara a hacer cosas mas complicadas después; en el código emulé una consulta al buscador de Google.

package scraping;

import com.gargoylesoftware.htmlunit.FailingHttpStatusCodeException;
import com.gargoylesoftware.htmlunit.WebClient;
import com.gargoylesoftware.htmlunit.html.HtmlForm;
import com.gargoylesoftware.htmlunit.html.HtmlPage;
import com.gargoylesoftware.htmlunit.html.HtmlSubmitInput;
import com.gargoylesoftware.htmlunit.html.HtmlTextInput;
import java.io.IOException;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 *
 * @author rey salcedo
 */
public class Scraping {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        //emulamos un navegador web
        final WebClient webClient = new WebClient();

        try {
            //Pagina donde se hara la consulta
            HtmlPage page1 = webClient.getPage("https://www.google.com.co/search");
            
            //nombre del formulario
            final HtmlForm form = page1.getFormByName("f");
            //el valor "f" no es arbitrario es el nombre del formulario web de google
            
            //nombre de la caja de texto
            final HtmlTextInput textField = form.getInputByName("q");
            //el valor "q" no es arbitrario es el nombre de la caja de texto del formulario web de google

            //nombre del boton del formulario
            final HtmlSubmitInput button = form.getInputByName("btnG");
            //el valor "btnG" no es arbitrario es el nombre del boton del formulario web de google
                        
            //llenamos la caja de texto
            textField.setValueAttribute("usandojava");

            //Creamos la pagina que nos devolverá el resultado
            final HtmlPage pageResultado;
            
            //hacemos clic en el boton del formulario y asignamos el resultado a la pagina pageResultado
            pageResultado = button.click();
            
            //imprimimos el resultado
            System.out.println(pageResultado.asText());
            
            //cerramos el navegador emulado, para liberar todo esto de la memoria
            webClient.closeAllWindows();
        } catch (IOException ex) {
            Logger.getLogger(Scraping.class.getName()).log(Level.SEVERE, null, ex);
        } catch (FailingHttpStatusCodeException ex) {
            Logger.getLogger(Scraping.class.getName()).log(Level.SEVERE, null, ex);
        }
    }
}




Advierto que para el caso del formulario de google no es estrictamente necesario llenar un formulario como lo he hecho, ya que solo bastas con un simple link https://www.google.com.co/search?q=usandojava


Para la consulta de los nombre de los componentes les sugiero que descarguen la pagina web donde está el formulario y como nota importante les sugiero de no usen chrome, mejor usen FireFox ya que chrome no me daba los nombres apropiados de los componentes del formulario, para la descarga de las librerías necesarias les dejo el link de la pagina oficial http://sourceforge.net/projects/htmlunit/files/htmlunit/



Como siempre esperando serles de ayuda.

No olviden comentar.





martes, 29 de abril de 2014

Aprendiendo a programar en java usando el valor de π(pi)





Saludos a todos.

Hace muchísimo tiempo cuando curioseaba el lenguaje Pascal y antes de dormir me puse a pesar en la geometría del circulo y recordé las clases de colegio donde me decían que el valor de pi no era mas que la longitud de la circunferencia dividida entre su diámetro.





Tenia presente que midiendo la circunferencia y el diámetro de un plato redondo por ejemplo solo hallaría un valor aproximado de pi, y que dicho valor más exacto sólo lo podían hacer los matemáticos y sus demostraciones, cosa que difícilmente lograría yo.

Siempre he sido regular en matemáticas, para algunos muy bueno, la verdad no lo creo; pero sí me consideraba mejor en la geometría y dibujo técnico.

De tanto pensar en círculos, matemática y geometría llego a mi una forma de hallar el valor de pi sin hacer demostraciones, gracias a que recordé que había leído en alguna parte la teoría que mas o menos dice "Un circulo es una figura geométrica con muchos lados que equidistan de un centro o eje"

Se me prendió el bombillo, me dije, tomare un cuadrado del cual conozco su diámetro y le agregare más lados calculado de los ya existentes sin cambiar el diámetro del mismo, es decir que el diámetro sera una constante; la suma de sus lados me darían el perímetro el cual dividiría por el diámetro y me daría el valor aproximado de pi, si hago esto muchas veces me acercaré cada vez más a pi; en otras palabras le agregare más lados al cuadrado tratando de convertirlo en un circulo.

Tome lápiz, cuaderno y comencé ha calcular, para el caso de un cuadrado de diámetro 1 los lados medirían 0,707106781, ya que según Pitágoras:

h^2 = co^2 + ca^2

Como para un cuadrado sus lados son igual, es decir sus catetos, nos quedaría:

h^2 = co^2 + co^2

h^2 = 2 * co^2

Sacamos raíces a ambos términos de cada igualdad

h = √2 * co

finalmente

co = h/√2

siendo la hipotenusa nuestro diámetro y remplazando...

co = 1/√2 = 0,707106781;

Listo ya tengo los datos de mi cuadrado, como los cuadrados tienen 4 lados el perímetro sería (0,707106781 * 4) = 2,828427125

Nuestro primer valor aproximado para pi seria:

2,828427125/1 = 2,828427125

2,828427125 es un valor muy distante al verdadero valor de pi; lo que sigue ahora es usando geometría agregarle más lados a figura y calcularlos sin cambiar el diámetro (1) y recalcular el valor de pi; en la practica debía recalcular miles de veces para llegar a un valor decente de pi.

Hosting

Tome nuevamente mi cuaderno y lápiz, y escribir un programa en Pasca (en esa época no tenia computador, así que me tocaba a papel y compilar en mi cabeza) para luego esperar el sábado que tenia nuevamente contacto con un computador; para sorpresa mía el día que pase mi programa a computador funciono sin problemas dándome el valor de pi tal cual una calculadora, estaba muy excitado al llegar muy cerca al valor de pi sin ser matemático.

Como mencione al inicio, eso paso hace mucho tiempo; y hoy que empece a recordar me ha sido duro reconstruir el programa, sospecho que es por mi pereza de hacer algo dos veces, así que investigue algo que me ayudara a recordar y me tope conque ya eso lo habían hecho Arquimedes y lo llamó Método exhaustivo, aunque mi método es ligeramente distinto, así que más pereza me da reconstruirlo, pero en un futuro lo haré para ustedes.

Pero como es costumbre escribir código en cada una de mis entradas, me tope con la Fórmula de Leibniz que no es más que una sumatoria que tiende al infinito y que es fácil programar.


//Autor Rey Salcedo
class FormulaLeibniz{
 public static double formula(int repeticiones){
  double pi = 0;
  for(int n = 0;n < repeticiones;n++){
   pi += ((Math.pow(-1,n))/(2*n + 1));
  }
  return pi*4;
 }
 public static void main(String[] args){
  System.out.println(formula(100000000));
 }
} 

Espero le sirva y les sea de agrado