martes, octubre 26, 2010

Guía de estilo de JAVA

A continuación se transcribe, desde la página del curso Curso práctica en ingeniería de software publicado por el Instituto Tecnológico de Massachussets (MIT) en su iniciativa de cursos libres OpenCourseWare  traducidos a su vez al español por el portal Universia, una guía de estilo para programar en java:




Boletín S1: Guía de estilo de Java™

Visión global

El estilo del código constituye una parte crucial en el ejercicio de la buena ingeniería del software. El objetivo se centra en escribir código que sea claro y fácil de entender, y que al mismo tiempo reduzca el esfuerzo que se emplea en hacer ampliaciones o modificaciones futuras.
Hay varios aspectos del código que lo pueden hacer más legible. Algunos de los más importantesson el empleo de nombres descriptivos, así como el uso de una indentación coherente y decomentarios informativos.
En el curso 6.170 no le indicamos que siga un estilo de código detallado. No obstante, esperamos que su código sea claro y fácil de entender. Este boletín le facilita una serie de directrices generales dentro de las cuales usted debería desarrollar un estilo de código propio y logrado.

Nombres descriptivos

Debería usar nombres nemónicos para los paquetes, los tipos, las variables y las etiquetas de ramificación, mediante los cuales se pudiese vislumbrar su uso y/o significado. Esto no significa que
los nombres tengan que ser muy largos. Por ejemplo, nombres como i y j servirían para nombrar los índices de bucles cortos, ya que los programadores conocen por convención los significados y usos de estas variables.

Le aconsejamos que siga una convención común que consiste en poner en mayúsculas los nombres
de las clases y en empezar los nombres de las variables y de los paquetes con letra minúscula. Existen otras convenciones comunes tales como escribir el nombre completo de las constantes en mayúsculas; no le pediremos que siga ninguna convención en concreto, pero debería elegir aquellas que le resultaran útiles y seguirlas de manera coherente.

Indentación coherente

Una indentación coherente del código ayuda al lector a comprender la estructura lógica de mismo,
al facilitarle la tarea de ver dónde acaban las sentencias if y los bucles while, etc. 
Debería hacer uso de estrategias coherentes; por ejemplo, sea coherente en cuanto a si pone el corchete en la misma línea que el if o en la línea siguiente, o en cuanto a la apariencia de sus bloques try-catch-finally.Examine el código del libro de texto para observar una muestra de estilo; puede desarrollar su propio código con total libertad si le resulta más cómodo.
Emacs proporciona un modo autoindent, que activa la indentación automática. Debería utilizarlo para dar formato a su código al mismo tiempo que lo escribe y volver a darle formato después de
realizar alguna modificación. También puede usar grind para dar a su código un formato decente para la impresión, incluso si el fichero fuente no está bien indentado.

Comentarios informativos

No cometa el error de escribir comentarios por todas partes --un comentario malo o inútil es peor que no poner nada. Si la información está clara en el código, el añadir un comentario simplemente supondrá trabajo de más para el lector.
    i++;    // se incrementa i     ESTE COMENTARIO ES INÚTIL
Los buenos comentarios añaden información al código de manera clara y concisa. Por ejemplo, los comentarios son informativos si:
  • Permiten que el lector evite leer el alguna parte del código: el siguiente comentario ahorra al lector el esfuerzo de tener que averiguar el efecto de algunas fórmulas complicadas, y pone de manifiesto la intención del programador, de manera que las fórmulas se puedan revisar más tarde.
    // calcula la desviación estándar de los elementos de la lista que son 
    // menores que el valor límite
    
    for (int i=0; i<n; i++) {
    
        //...
    
    }
    Una aplicación importante de este tipo de comentario consiste en documentar los argumentos y los valores que devuelven las funciones, de modo que los clientes no tengan que leer la implementación para comprender cómo usar la función.
     
  • Explican un algoritmo o paso oscuro: esto es particularmente importante cuando los resultados
    de algún paso no quedan claros en ese trozo de código. Debería explicar algoritmos que puedan resultar engañosos, operaciones con efectos secundarios, números mágicos del código, etc.
    // Señal de que una nueva petición de transferencia se ha completado y está lista
    // para ser procesada. El hilo principal comenzará la transferencia del disco
    // la próxima vez que despierte y se dé cuenta de que esta variable ha cambiado.
    
    buffer_manager.active_requests ++;
  • Indican supuestos: ¿bajo qué supuestos funciona adecuadamente una parte del código?
    // La memoria intermedia (buffer) contiene al menos un caracter.
    // Si la memoria intermedia está vacía, el gestor de interrupciones vuelve sin
    
    // llamar a esta función.
    
    c = buffer.get_next_character();
  • Señalan deficiencias del código y partes de código incompleto: es habitual que la primera versión del código no esté completa; es importante señalar el código que se sabe que es incorrecto. Si se le agota el tiempo de entrega de un ejercicio y presenta un programa que no funciona correctamente en todas las entradas, esperamos que su código muestre que usted es consciente de esas deficiencias.
    if (n > 0) {
    
        average = sum / n;
    
    } else {
    
        // XXX necesita utilizar el promedio de decaimiento de la  iteración anterior.
        // Por ahora, use simplemente un valor arbitrario. 
        average = 15;
    
    }
Consejos:
  • No escriba primero el código para luego comentarlo; coméntelo sobre la marcha. Es poco probable que pueda volver y hacerlo más tarde.
  • No le exigiremos que escriba comentarios en cada objeto del programa como se hace en algunos cursos de ingeniería del software. Sin embargo, su nota dependerá considerablemente de la claridad del código y puede que alguna parte del programa que esté clara para usted, no resulte tan clara para el lector. Por lo tanto, le conviene añadir comentarios aclaratorios a todas las clases, campos y métodos.

lunes, octubre 25, 2010

Descargar documentos desde la red

Para descargar un archivo desde la red se utiliza la clase URL para tener acceso al archivo o documento de red y se abren un flujo de entrada y otro de salida para recorrer y copiar dicho documento.

import java.io.*;
import java.net.*;

public class TestDescarga {
    public static void main(String[] args) {
        // Por simplicidad se supondrá que el archivo a descargar y la ruta donde
        // se va a guardar son conocidas.
        String origen = "http://mit.ocw.universia.net/1.00/s02/class-sessions/lecture-31/lecture-31.pdf";
        String destino = "c:/downloads/salida.pdf";
        descargar(origen, destino);
    }

    public static void descargar(String origen, String destino) {
        try {
            // Paso 1: crear el objeto URL para enlazar la dirección del documento
            URL url = new URL(origen);

            // Paso 2: crear un flujo de entrada para leer el contenido del documento
            byte[] data = new byte[1024];
            DataInputStream in = new DataInputStream(url.openStream());

            // Paso 3: crear el archivo de salida
            FileOutputStream out = new FileOutputStream(destino);

            // Paso 4: recorrer el archivo de entrada
            int leidos;
            while(true) {
                leidos = in.read(data);
                if(leidos >= 0) out.write(data, 0, leidos);
                else break;
            } 
            out.flush();
            out.close();
        }
        catch(MalformedURLException x) {
            System.err.println("Error, dirección mal formada, intente más tarde");
        }
        catch(IOException x) {
            System.err.println("Error de IO: " + x.getMessage());
        }
    }
}

jueves, octubre 21, 2010

Números Primos

Verificación

Teniendo en cuenta que, por definición, un número primo es aquel que es divisible exclusivamente por sí mismo y por la unidad, se puede escribir una función que verifique si un número entero es primo dividiéndolo por todos los números entre 1 y él, y finalmente contar cuántos divisores tuvo. Si la cantidad de divisores es 2, entonces el número es primo, de lo contrario no lo es. Este algoritmo se puede representar como:

// Version inicial.  Cuenta el numero de divisores y si es menor o igual
// que dos entonces es primo.
    public static boolean esPrimoV1(long n) {
        long contador=0;
        for(long i=1; i<=n; i++) {
            if(n%i == 0) contador  ;
        }
        if(contador>=2) return false;
        else return true;
    }

Este algoritmo, si bien identifica si el número es primo, es bastante ineficiente, entre otras por razones tales como la espera para hacer todas las divisiones para decidir que un número no es primo aunque, si se omite la división por uno y por el mismo número, basta con encontrar un solo divisor más para determinar que el número no es primo. De la misma manera, el algoritmo divide el número por todos los pares anteriores a él cuando no es necesario, ya que diviéndolo por dos es suficiente para saber si es múltiplo de un número par.

Una versión optimizada del algoritmo es la siguiente:

// Version seis.  Hace los cálculos de funciones solo cuando es necesario
    public static boolean esPrimoV6(long n) {
        double raiz = Math.sqrt(n);
        if(n==2) return true;
        if(n%2==0) return false;
        for(long i=3; i<=raiz; i+=2) {
            if(n%i == 0) return false;
        }
        return true;
    }

Se sugiere calcular con las dos versiones el tiempo que se tarda en determinar si el número entero más grande que puede manejar java (Long.MAX_VALUE) es primo o no.

Generación

Si se quiere generar un conjunto de números primos, una posible alternativa es utilizar el método de Eratóstenes, en el cual se ubican en un vector todos los posibles números en un rango, e iniciando en el número 2 se marcan como no primos todos los múltiplos de dicho número; el proceso continua para todos los números no marcados.

El siguiente método genera un vector con todos los números enteros entre 1 y 2 a la 31:

// Generación de primos por el método de Eratóstenes
    public static int[] generarPrimos() {
        boolean[] tmp = new boolean[Integer.MAX_VALUE/2];
        for(int i=0; i<tmp.length; i++) tmp[i]=true;
        int contador  = tmp.length;
        int raiz      = (int) Math.sqrt(tmp.length);
        for(int i=2; i<=raiz; i++) {
            if(tmp[i]!=true) continue;
            for(int j=i*i; j<tmp.length;j+=i){
                if(tmp[j]==true) {
                    contador--;
                    tmp[j]=false;
                }
            }
        }
        int   j         = 0;
        int[] respuesta = new int[contador];
        for(int i=0; i<tmp.length; i++) if(tmp[i]==true) respuesta[j++]=i;
        return respuesta;
    }

Nótese que el arreglo tmp podría usarse para determinar de forma inmediata si un número dado es primo o no, pues bastaría con mirar si la posición respectiva de ese número en el arreglo hay un valor de falso o verdadero.

Ruta más corta - Solución por el algoritmo de Dijkstra

Para solucionar el problema de la ruta más corta entre dos nodos de un grafo se puede utilizar el Algoritmo de Dijkstra, el cual sigue el siguiente procedimiento para calcular la ruta más corta desde el nodo origen hasta cada uno de los nodos del grafo:


  • Crea una listas de nodos para almacenar los nodos con distancia mínima ya calculada
  • Crear una cola de prioridad para los nodos pendientes de evaluar
  • Inserta el nodo origen a la cola de prioridad
  • Mientras que haya nodos en la cola de prioridad
    • Extrae el primer nodo de la cola de prioridad (tmp)
    • Agrega el nodo tmp a la lista de nodos ya calculados
    • Genera una lista de los nodos conectados al nodo tmp que no estén en la lista de ya calculados
    • Para cada nodo de la lista (nod)
      • Calcula la distancia al origen con la distancia entre tmp y nod más la distancia calculada entre el origen y tmp.
      • Si el nodo nod no está en la cola de prioridad lo agrega
      • Si el nodo nod ya está en la cola de prioridad y la distancia con la que está guardado en la cola es menor, lo deja como está y sino, lo actualiza con la distancia calculada
    • Fin
  • Fin
Al finalizar este procedimiento se tiene una lista con la menor distancia desde el origen a cada nodo.

La clase Grafo descrita en un post anterior se puede modificar para incluir un nuevo método que calcula la menor ruta usando el algoritmo de Dijkstra con dos nuevos métodos: uno para calcular la distancia entre el origen y todos lo nodos, guardando estos resultados en una lista, y el segundo para mostrar la ruta entre el origen y el nodo destino tomando la información de la lista de distancias calculadas.  Se implementa también un método adicional para verificar si un nodo ya está en la lista de terminados:

import java.util.*;

public class Grafo {
    char[]  nodos;  // Letras de identificación de nodo
    int[][] grafo;  // Matriz de distancias entre nodos
    String  rutaMasCorta;                           // distancia más corta
    int     longitudMasCorta = Integer.MAX_VALUE;   // ruta más corta
    List<Nodo>  listos=null;                        // nodos revisados Dijkstra

    // construye el grafo con la serie de identificadores de nodo en una cadena
    Grafo(String serieNodos) {
        nodos = serieNodos.toCharArray();
        grafo = new int[nodos.length][nodos.length];
    }

    // asigna el tamaño de la arista entre dos nodos
    public void agregarRuta(char origen, char destino, int distancia) {
        int n1 = posicionNodo(origen);
        int n2 = posicionNodo(destino);
        grafo[n1][n2]=distancia;
        grafo[n2][n1]=distancia;
    }

    // retorna la posición en el arreglo de un nodo específico
    private int posicionNodo(char nodo) {
        for(int i=0; i<nodos.length; i++) {
            if(nodos[i]==nodo) return i;
        }
        return -1;
    }
    
    // encuentra la ruta más corta desde un nodo origen a un nodo destino
    public String encontrarRutaMinimaDijkstra(char inicio, char fin) {
        // calcula la ruta más corta del inicio a los demás
        encontrarRutaMinimaDijkstra(inicio);
        // recupera el nodo final de la lista de terminados
        Nodo tmp = new Nodo(fin);
        if(!listos.contains(tmp)) {
            System.out.println("Error, nodo no alcanzable");
            return "Bye";
        }
        tmp = listos.get(listos.indexOf(tmp));
        int distancia = tmp.distancia;  
        // crea una pila para almacenar la ruta desde el nodo final al origen
        Stack<Nodo> pila = new Stack<Nodo>();
        while(tmp != null) {
            pila.add(tmp);
            tmp = tmp.procedencia;
        }
        String ruta = "";
        // recorre la pila para armar la ruta en el orden correcto
        while(!pila.isEmpty()) ruta+=(pila.pop().id + " ");
        return distancia + ": " + ruta;
    }

    // encuentra la ruta más corta desde el nodo inicial a todos los demás
    public void encontrarRutaMinimaDijkstra(char inicio) {
        Queue<Nodo>   cola = new PriorityQueue<Nodo>(); // cola de prioridad
        Nodo            ni = new Nodo(inicio);          // nodo inicial
        
        listos = new LinkedList<Nodo>();// lista de nodos ya revisados
        cola.add(ni);                   // Agregar nodo inicial a la cola de prioridad
        while(!cola.isEmpty()) {        // mientras que la cola no esta vacia
            Nodo tmp = cola.poll();     // saca el primer elemento
            listos.add(tmp);            // lo manda a la lista de terminados
            int p = posicionNodo(tmp.id);   
            for(int j=0; j<grafo[p].length; j++) {  // revisa los nodos hijos del nodo tmp
                if(grafo[p][j]==0) continue;        // si no hay conexión no lo evalua
                if(estaTerminado(j)) continue;      // si ya fue agregado a la lista de terminados
                Nodo nod = new Nodo(nodos[j],tmp.distancia+grafo[p][j],tmp);
                // si no está en la cola de prioridad, lo agrega
                if(!cola.contains(nod)) {
                    cola.add(nod);
                    continue;
                }
                // si ya está en la cola de prioridad actualiza la distancia menor
                for(Nodo x: cola) {
                    // si la distancia en la cola es mayor que la distancia calculada
                    if(x.id==nod.id && x.distancia > nod.distancia) {
                        cola.remove(x); // remueve el nodo de la cola
                        cola.add(nod);  // agrega el nodo con la nueva distancia
                        break;          // no sigue revisando
                    }
                }
            }
        }
    }

    // verifica si un nodo ya está en lista de terminados
    public boolean estaTerminado(int j) {
        Nodo tmp = new Nodo(nodos[j]);
        return listos.contains(tmp);
    }

    // encontrar la ruta mínima por fuerza bruta
    public void encontrarRutaMinimaFuerzaBruta(char inicio, char fin) {
        int p1 = posicionNodo(inicio);
        int p2 = posicionNodo(fin);
        // cola para almacenar cada ruta que está siendo evaluada
        Stack<Integer> resultado = new Stack<Integer>();
        resultado.push(p1);
        recorrerRutas(p1, p2, resultado);
    }

    // recorre recursivamente las rutas entre un nodo inicial y un nodo final
    // almacenando en una cola cada nodo visitado
    private void recorrerRutas(int nodoI, int nodoF, Stack<Integer> resultado) {
        // si el nodo inicial es igual al final se evalúa la ruta en revisión
        if(nodoI==nodoF) {
            int respuesta = evaluar(resultado);
            if(respuesta < longitudMasCorta) {
                longitudMasCorta = respuesta;
                rutaMasCorta     = "";
                for(int x: resultado) rutaMasCorta+=(nodos[x]+" ");
            }
            return;
        }
        // Si el nodoInicial no es igual al final se crea una lista con todos los nodos
        // adyacentes al nodo inicial que no estén en la ruta en evaluación
        List<Integer> lista = new Vector<Integer>();
        for(int i=0; i<grafo.length;i++) {
            if(grafo[nodoI][i]!=0 && !resultado.contains(i))lista.add(i);
        }
        // se recorren todas las rutas formadas con los nodos adyacentes al inicial
        for(int nodo: lista) {
            resultado.push(nodo);
            recorrerRutas(nodo, nodoF, resultado);
            resultado.pop();
        }
    }

    // evaluar la longitud de una ruta
    public int evaluar(Stack<Integer> resultado) {
        int  resp = 0;
        int[]   r = new int[resultado.size()];
        int     i = 0;
        for(int x: resultado) r[i++]=x;
        for(i=1; i<r.length; i++) resp+=grafo[r[i]][r[i-1]];
        return resp;
    }

    public static void main(String[] args) {
        Grafo g = new Grafo("abcdef");
        g.agregarRuta('a','b', 3);
        g.agregarRuta('a','e', 6);
        g.agregarRuta('a','f',10);
        g.agregarRuta('b','c', 5);
        g.agregarRuta('b','e', 2);
        g.agregarRuta('c','d', 8);
        g.agregarRuta('c','e', 9);
        g.agregarRuta('c','f', 7);
        g.agregarRuta('d','f', 4);
        g.agregarRuta('e','f', 4);
        char inicio = 'a';
        char fin    = 'd';
        String respuesta = g.encontrarRutaMinimaDijkstra(inicio, fin);
        System.out.println(respuesta);
    }
}


Esta clase requiere del uso adicionalmente de la clase Nodo, que va a servir para la cola de prioridad y para llevar registro de la distancia mínima desde el origen a un nodo, así como la referencia al nodo inmediatamente anterior:


public class Nodo implements Comparable<Nodo> {
    char id;
    int  distancia   = Integer.MAX_VALUE;
    Nodo procedencia = null;
    Nodo(char x, int d, Nodo p) { id=x; distancia=d; procedencia=p; }
    Nodo(char x) { this(x, 0, null); }
    public int compareTo(Nodo tmp) { return this.distancia-tmp.distancia; }
    public boolean equals(Object o) {
        Nodo tmp = (Nodo) o;
        if(tmp.id==this.id) return true;
        return false;
    }
}

martes, octubre 19, 2010

Programación Cliente/Servidor básica

Una aplicación cliente servidor requiere básicamente tres elementos: un programa servidor que atiende las peticiones de los clientes; un programa cliente que se conecta al servidor y; un protocolo de comunicaciones que indica la secuencia de mensajes que se pasan un cliente y un servidor.

En el siguiente ejemplo, el servidor será multiusuario, es decir, atenderá simultáneamente varios clientes, y para ello se utilizarán hilos -uno por cada cliente que se conecte- que atenderán en forma exclusiva el proceso de cada cliente. El cliente, por su parte, se conectará al servidor e iniciarán un diálogo (protocolo) en el cual el cliente enviará un número y el servidor devolverá el valor del área del círculo de radio igual al valor envíado por el cliente. El proceso para cada cliente terminará cuando se le envíe al servidor un valor negativo.

Servidor

El proceso del servidor inicia creando un ServerSocket para escuchar peticiones por el puerto 65432 (debe ser un valor entre 1225 y 65535 que no esté siendo utilizado en el equipo donde va a correr). Cada vez que un cliente ingrese se crea un nuevo objeto de la clase Socket y se instancia un nuevo hilo de la clase HiloServidor que se encargará de manejar la interacción con el cliente.


import java.io.*;
import java.net.*;
public class ServidorAreaCirculo {
    final int puerto = 65432;   // puerto sobre el que se esperarán conexiones
    ServerSocket  ss;
    public void proceso() {
        try {
            ss = new ServerSocket(puerto);
            while(true) {                       // ciclo infinito para esperar conexiones
                Socket socket = ss.accept();    // espera hasta que un cliente se conecta
                Thread   hilo = new Thread(new HiloServidor(socket));   // crea hilo hijo
                hilo.start();                   // inicia el hilo hijo que atiende al cliente
            }
        }
        catch(IOException x) {
            System.err.println("Error de conexión: " + x.getMessage());
        }
    }

    class HiloServidor implements Runnable {
        Socket socket;
        HiloServidor(Socket s) { socket = s; }
        public void run() {
            try {
                // crea flujos de entrada y salida
                BufferedReader in = new BufferedReader(
                                    new InputStreamReader(socket.getInputStream()));
                PrintWriter   out = new PrintWriter(socket.getOutputStream());
                // paso 1: envio mensaje de bienvenida
                out.println("Bienvenid@, este servidor calcula áreas de círculos");
                while(true) {
                    // paso 2: solicita envio del radio del círculo
                    out.println("Digite radio del circulo (ó número negativo para terminar): ");
                    out.flush();
                    // paso 3: recibe el radio y genera la salida a enviar
                    String cadena = in.readLine();
                    try {
                        double  radio = Double.parseDouble(cadena);
                        if(radio<0) break;
                        double area = Math.PI*Math.pow(radio,2);
                        cadena = "El área de un círculo de radio " + radio + " es " +
                                String.format("%,.4f", area);
                    }
                    catch(NumberFormatException x) {
                        cadena = "Error, la cadena recibida no es un número válido";
                    }
                    // paso 4: devuelve el mensaje al usuario
                    out.println(cadena);
                    out.flush();
                }
                out.println("Gracias por venir, vuelve pronto");
                out.flush();
                socket.close();
            }
            catch(IOException x) {
                System.err.println(x.getMessage());
            }
        }
    }

    public static void main(String[] args) {
        ServidorAreaCirculo s = new ServidorAreaCirculo();
        s.proceso();
    }
}


Cliente

En este caso, el cliente inicia abriendo un socket con el equipo y puerto donde debe estar esperando el programa servidor. Para la prueba se supone que el servidor debe estar ejecutándose en la misma máquina del cliente (localhost) en el puerto 65432.


import java.io.*;
import java.io.*;
import java.net.*;
import javax.swing.*;
import static javax.swing.JOptionPane.*;

public class ClienteAreaCirculo {
    public void proceso() {
        try {
            // Se crea socket conectado al servidor y puerto conocidos
            Socket     socket = new Socket("localhost",65432);
            // Se crean los flujos de entrada y salida
            PrintWriter   out = new PrintWriter(socket.getOutputStream());
            BufferedReader in = new BufferedReader(
                                new InputStreamReader(socket.getInputStream()));
            // Paso 1: se recibe mensaje de bienvenida del servidor
            String cadena = in.readLine();
            System.out.println(cadena);
            while(true) {
                // Paso 2: se recibe mensaje de solicitud de número
                cadena = in.readLine();
                System.out.println(cadena);
                // Paso 3: se pregunta al usuario el número a enviar
                cadena = showInputDialog(cadena);
                // Paso 4: se envia el número al servidor
                out.println(cadena);
                out.flush();
                // Paso 5: se recibe la respuesta del servidor
                cadena = in.readLine();
                System.out.println(cadena);
                if(cadena.startsWith("Gracias por venir")) break;
            }
        }
        catch(IOException x) {
           System.err.println("Error de conexión: "+x.getMessage());
        }

    }

    public static void main(String[] args) {
        ClienteAreaCirculo c = new ClienteAreaCirculo();
        c.proceso();
    }
}

lunes, octubre 18, 2010

Complejidad del algoritmo del camino más corto por fuerza bruta

Para probar la eficiencia del algoritmo de búsqueda de la ruta más corta entre dos puntos por fuerza bruta se requieren en primer lugar dos modificaciones a la clase Grafo: la creación de dos atributos (public String rutaMasCorta e int longituRutaMasCorta) donde se almacenarán respectivamente, la ruta más corta de recorrido del grafo en forma de cadena de caracteres y la longitud de dicha ruta; y en segundo lugar, se modifica el método recorrerRutas para que haga la comparación de cada ruta recorrida y guarde la ruta más corta y la distancia de dicha ruta en las variables mencionadas anteriormente, y adicionalmente para que no muestre cada ruta evaluada. El método queda así:

// recorre recursivamente las rutas entre un nodo inicial y un nodo final
    // almacenando en una cola cada nodo visitado
    private void recorrerRutas(int nodoI, int nodoF, Stack<Integer> resultado) {
        // si el nodo inicial es igual al final se evalúa la ruta en revisión
        if(nodoI==nodoF) {
            int respuesta = evaluar(resultado);
            if(respuesta < longitudMasCorta) {
                longitudMasCorta = respuesta;
                rutaMasCorta     = "";
                for(int x: resultado) rutaMasCorta+=(nodos[x]+" ");
            }
            return;
        }
        // Si el nodoInicial no es igual al final se crea una lista con todos los nodos
        // adyacentes al nodo inicial que no estén en la ruta en evaluación
        List<Integer> lista = new Vector<Integer>();
        for(int i=0; i<grafo.length;i++) {
            if(grafo[nodoI][i]!=0 && !resultado.contains(i))lista.add(i);
        }
        // se recorren todas las rutas formadas con los nodos adyacentes al inicial
        for(int nodo: lista) {
            resultado.push(nodo);
            recorrerRutas(nodo, nodoF, resultado);
            resultado.pop();
        }
    }

Una vez realizadas estas modificaciones, se crea una nueva clase de pruebas, TestGrafo, en la cual se van a crear grafos de tamaño 1 en adelante, aprovechando las letras del alfabeto romano, desde el nodo 'a' hasta el nodo 'z' en forma secuencial, se crearán las rutas para estos grafos y se realizará la búsqueda de la ruta más corta entre dos nodos aleatorios. A continuación se presenta el código completo en java de la clase TestGrafo:

import java.util.*;

public class TestGrafo {
    public static void main(String[] args) {
        // variables para cálculo del tiempo
        long      tiempo1;
        long      tiempo2;
        double    tiempo;
        String    cadena="";            // cadena con los posibles nodos
        Random    rnd = new Random();   // generador de números aleatorios
        final int MAX_DIST = 50;        // máxima distancia entre 2 nodos

        for(char letra='a'; letra<='z'; letra++) {
            cadena+=letra;
            // Crea un nuevo grafo con tantos nodos como letras en la cadena
            Grafo g = new Grafo(cadena);
            // Crea rutas de tamaño aleatorio entre todos los nodos
            for(char i='a';i<=letra;i++) {
                for(char j=(char)(i+1);j<=letra; j++) {
                    g.agregarRuta(i, j, rnd.nextInt(MAX_DIST));
                }
            }
            // Selecciona dos nodos aleatorios para buscar la ruta mas corta
            char origen  = cadena.charAt(rnd.nextInt(cadena.length()));
            char destino = cadena.charAt(rnd.nextInt(cadena.length()));
            // Tiempo del sistema antes del proceso
            tiempo1      = System.currentTimeMillis();
            // Busqueda de la ruta más corta entre los dos nodos aleatorios
            g.encontrarRutaMinimaFuerzaBruta(origen, destino);
            // Tiempo del sistema al finalizar el proceso
            tiempo2 = System.currentTimeMillis();
            // Tiempo del proceso
            tiempo  = (tiempo2-tiempo1)/1000.0;
            // Mostrar cantidad de nodos del grafo y tiempo transcurrido
            System.out.printf("%3d %,10.2f %n", cadena.length(), tiempo);
        }
    }
}

La ejecución del anterior programa trae los siguientes resultados para cantidad de nodos desde 1 hasta 13, con tiempos en segundos:

 1       0,01 
 2       0,00 
 3       0,00 
 4       0,00 
 5       0,00 
 6       0,00 
 7       0,02 
 8       0,00 
 9       0,13 
10       1,18 
11       9,92 
12      44,91 
13     564,72 

Siguiendo esta secuencia, se podría pensar que el tiempo de respuesta para 14 nodos podría estar en el orden de varias horas; puede notarse entonces que a partir de un número relativamente pequeño de nodos el tiempo para encontrar la solución se torna inmanejable. La razón de esto estriba en que la cantidad de rutas posibles que conectan los puntos de un grafo es proporcional al factorial del número de nodos en el grafo, por lo que el tiempo de ejecución de cualquier algoritmo que deba recorrer todos los nodos de un grafo será entonces del orden de O(N!).

domingo, octubre 17, 2010

Evaluador de Funciones con Constantes

En este versión del evaluador de funciones en Java se ha agregado la funcionalidad de usar las constantes definidas en la clase java.lang.Math (PI y E).

En el método main de ejemplo se crea una función que calcula el área de un círculo utilizando el valor de PI:


import java.util.*;
import java.util.regex.*;
import java.lang.reflect.*;

public class Expresion {
    enum TipoToken  {   NUMERO, VARIABLE, FUNCION, ADD, SUB, MUL, DIV,
                        EXP, P_IZQ, P_DER, ERROR };
    class Token {
        TipoToken tipo;
        String    texto;
        Token(TipoToken ti, String te) { tipo=ti; texto=te;}
        Token(TipoToken ti) { tipo = ti; }
    }
    Queue<Token>    colaTokens;
    String          cadenaFuncion;
    double          variableX;

    Expresion(String c) throws Exception {
        cadenaFuncion = c;
    }

    private void generarTokens() throws Exception {
        colaTokens = new LinkedList<Token>();
        StringBuffer entrada   = new StringBuffer(cadenaFuncion);
        Pattern pNumero = Pattern.compile("\\-?\\d+(\\.\\d+)?");
        Pattern pID     = Pattern.compile("\\p{Alpha}\\w+");
        Pattern pFuncion= Pattern.compile("\\p{Alpha}\\w+\\s+\\(");
        while(entrada.length()>0) {
            Matcher      m  = pNumero.matcher(entrada);
            if(m.lookingAt()) {
                colaTokens.add(new Token(TipoToken.NUMERO,m.group()));
                entrada.delete(0, m.end());
                continue;
            }
            if(entrada.charAt(0) == 'x' || entrada.charAt(0) == 'X') {
                colaTokens.add(new Token(TipoToken.VARIABLE,"x"));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '+') {
                colaTokens.add(new Token(TipoToken.ADD));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '-') {
                colaTokens.add(new Token(TipoToken.SUB));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '*') {
                colaTokens.add(new Token(TipoToken.MUL));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '/') {
                colaTokens.add(new Token(TipoToken.DIV));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '(') {
                colaTokens.add(new Token(TipoToken.P_IZQ));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == ')') {
                colaTokens.add(new Token(TipoToken.P_DER));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '^') {
                colaTokens.add(new Token(TipoToken.EXP));
                entrada.deleteCharAt(0);
                continue;
            }
            m = pFuncion.matcher(entrada);
            if(m.lookingAt()) {
                String cadena = m.group();
                cadena = cadena.split("\\s+\\(")[0].trim();
                colaTokens.add(new Token(TipoToken.FUNCION, cadena));
                continue;
            }
            m = pID.matcher(entrada);
            if(m.lookingAt()) {
                colaTokens.add(new Token(TipoToken.VARIABLE, m.group()));
                entrada.delete(0, m.end());
                continue;
            }
            throw new Exception("Elemento no reconocido en la entrada: "
                                + entrada.charAt(0));
        }
    }

    private double evaluar(double x) throws Exception {
        generarTokens();
        variableX = x;
        return expresion();
    }

    private double expresion() {
        double respuesta=termino();
        while(!colaTokens.isEmpty() ) {
            switch(colaTokens.element().tipo) {
                case ADD:   colaTokens.remove();
                            respuesta+=termino();
                            continue;
                case SUB:   colaTokens.remove();
                            respuesta-=termino();
                            continue;
            }
            break;
        }
        return respuesta;
    }

    private double termino() {
        double respuesta=factor();
        while(!colaTokens.isEmpty() ) {
            switch(colaTokens.element().tipo) {
                case MUL:   colaTokens.remove();
                            respuesta*=factor();
                            continue;
                case DIV:   colaTokens.remove();
                            respuesta/=factor();
                            continue;
                default:
            }
            break;
        }
        return respuesta;
    }

    private double factor() {
        double respuesta=valor();
        while(!colaTokens.isEmpty() ) {
            switch(colaTokens.element().tipo) {
                case EXP:   colaTokens.remove();
                            respuesta=Math.pow(respuesta,valor());
                            continue;
            }
            break;
        }
        return respuesta;
    }

    private double valor() {
        Token token;
        try {
            double respuesta = 0;
            token     = colaTokens.poll();
            switch(token.tipo) {
                case P_IZQ:     respuesta = expresion();
                                leaToken(TipoToken.P_DER);
                                return respuesta;
                case NUMERO:    return Double.parseDouble(token.texto);
                case VARIABLE:  if(token.texto.toLowerCase().equals("x")) {
                                    return variableX;
                                }
                                Field f = java.lang.Math.class.
                                        getField(token.texto);
                                return f.getDouble(null);
                case FUNCION:   double argumento=expresion();
                                leaToken(TipoToken.P_DER);
                                Method m = java.lang.Math.class.
                                           getMethod(token.texto, Double.TYPE);
                                return (Double) m.invoke(null, argumento);
            }
            return respuesta;
        }
        catch(Exception ex) {
            System.err.println("Error: " + ex.getMessage());
            System.exit(0);
        }
        return 0;
    }

    private boolean leaToken(TipoToken t) {
        Token token = colaTokens.poll();
        if(token.tipo.equals(t)) {
            return true;
        }
        else {
            System.err.println("Error: elemento no permitido " + token.texto );
            return false;
        }
    }

    public static void main(String[] args) throws Exception {
        String funcion = "PI*x^2" ;
        Expresion  exp = new Expresion(funcion);
        for(int x=0; x<=10; x++) {
            System.out.println(x + " -> " + exp.evaluar(x));
        }
    }
}

viernes, octubre 15, 2010

Ruta más corta - Solución por fuerza bruta

El problema de encontrar la ruta más corta entre dos puntos se puede abordar por diferentes enfoques de programación. La solución más obvia es la de evaluar todas las posibles rutas para luego compararlas y encontrar la más corta. Si bien esta solución puede encontrar la ruta más corta (o más larga) en forma absoluta, su implementación cuando la cantidad de nodos a evaluar es relativamente alta es demasiado costosa computacionalmente hablando porque la cantidad de rutas tiende a crecer exponencialmente.

Una posible implementación de esta evaluación de todas las rutas por fuerza bruta se presenta a continuación. El programa tiene dos partes, en la primera de ellas está la definición de una clase Grafo, con los métodos para la creación de los nodos y la asignación de rutas entre dos puntos y la distancia entre cada punto. Cada nodo puede ser identificado con una letra o caracter y, para efectos de simplificar el proceso estas denominaciones se envían al constructor del grafo en una cadena de caracteres. El grafo se representa por una matriz cuadrada donde cada elemento de la matriz representa la distancia entre el nodo fila y el nodo columna respectivo. Se han obviado las comprobaciones para dar mayor claridad al código:

import java.util.*;

public class Grafo {
    int[][] grafo;
    char[]  nodos;

    Grafo(String serieNodos) {
        nodos = serieNodos.toCharArray();
        grafo = new int[nodos.length][nodos.length];
    }

    // asigna el tamaño de la arista entre dos nodos
    public void agregarRuta(char origen, char destino, int distancia) {
        int n1 = posicionNodo(origen);
        int n2 = posicionNodo(destino);
        grafo[n1][n2]=distancia;
        grafo[n2][n1]=distancia;
    }

    // retorna la posición en el arreglo de un nodo específico
    private int posicionNodo(char nodo) {
        for(int i=0; i<nodos.length; i++) {
            if(nodos[i]==nodo) return i;
        }
        return -1;
    }

    // encuentra la ruta mínima entre dos nodos del grafo
    public void encontrarRutaMinimaFuerzaBruta(char inicio, char fin) {
        int p1 = posicionNodo(inicio);
        int p2 = posicionNodo(fin);
        // cola para almacenar cada ruta que está siendo evaluada
        Stack<Integer> resultado = new Stack<Integer>();
        resultado.push(p1);
        recorrerRutas(p1, p2, resultado);
    }

    // recorre recursivamente las rutas entre un nodo inicial y un nodo final
    // almacenando en una cola cada nodo visitado
    private void recorrerRutas(int nodoI, int nodoF, Stack<Integer> resultado) {
        // si el nodo inicial es igual al final se muestra y evalúa la ruta en revisión
        if(nodoI==nodoF) {
            for(int x: resultado) System.out.print(nodos[x]+ " ");
            System.out.print(": " + evaluar(resultado));
            System.out.println();
            return;
        }
        // Si el nodoInicial no es igual al final se crea una lista con todos los nodos
        // adyacentes al nodo inicial que no estén en la ruta en evaluación
        List<Integer> lista = new Vector<Integer>();
        for(int i=0; i<grafo.length;i++) {
            if(grafo[nodoI][i]!=0 && !resultado.contains(i))lista.add(i);
        }
        // se recorren todas las rutas formadas con los nodos adyacentes al inicial
        for(int nodo: lista) {
            resultado.push(nodo);
            recorrerRutas(nodo, nodoF, resultado);
            resultado.pop();
        }
    }

    // evaluar la longitud de una ruta
    public int evaluar(Stack<Integer> resultado) {
        int  resp = 0;
        int[]   r = new int[resultado.size()];
        int     i = 0;
        for(int x: resultado) r[i++]=x;
        for(i=1; i<r.length; i++) resp+=grafo[r[i]][r[i-1]];
        return resp;
    }

    public static void main(String[] args) {
        Grafo g = new Grafo("abcdef");
        g.agregarRuta('a','b', 5);
        g.agregarRuta('a','e', 3);
        g.agregarRuta('b','e', 6);
        g.agregarRuta('b','f', 9);
        g.agregarRuta('b','c', 10);
        g.agregarRuta('c','d', 15);
        g.agregarRuta('c','f', 9);
        g.agregarRuta('d','e', 1);
        g.agregarRuta('d','f', 2);
        g.agregarRuta('e','f', 12);
        char inicio = 'a';
        char fin    = 'd';
        g.encontrarRutaMinimaFuerzaBruta(inicio, fin);
    }
}

jueves, octubre 14, 2010

Generar combinaciones de caracteres

Generación con sustitución

Si se quieren generar todas las posibles cadenas que se forman con un determinado número de caracteres, una primera estrategia es hacer un programa con ciclos anidados, uno para cada posición de la cadena que se debe generar. Un ejemplo de esta estrategia es el siguiente:


// Generar secuencias de 4 caracteres
public static void generar4Caracteres(char[] elementos) {
        String r;
        for (int i = 0; i < elementos.length; i++) {
            for (int j = 0; j < elementos.length; j++) {
                for (int k = 0; k < elementos.length; k++) {
                    for (int l = 0; l < elementos.length; l++) {
                        r=""+elementos[i]+elementos[j]+elementos[k]+elementos[l];
                        // Acá se debe hacer algo con la cadena generada
                        System.out.println(r);
                    }
                }
            }
        }
    }


La principal limitación del anterior método es que solo se generan cadenas de 4 caracteres, y en caso de requerir cadenas generadas de otro tamaño, se requiere un nuevo método, pues la cantidad de caracteres de la cadena generada es la que determina el número de ciclos for del proceso. Una mejor estrategia para generar una cadena de N caracteres es, comenzando con la cadena vacía, agregar un caracter y llamar recursivamente el mismo método para generar las cadenas de tamaño N-1. Cuando la cadena a generar sea de tamaño 0, es porque ya se completó la generación de una ocurrencia y se puede proceder a procesar la cadena generada. En este caso el método queda así:


// Permutaciones con sustitución
    public static void generarPermutacionSust(char[] elementos, String actual, int cantidad) {
        if(cantidad==0) {
            // Hacer con la secuencia generada
            System.out.println(actual);
        }
        else {
            for(int i=0; i<elementos.length; i++) {
                generarPermutacionSust(elementos, actual elementos[i],cantidad-1);
            }
        }
    }


Para probar este método para generar todas las posibles subcadenas de dos caracteres con sustitución formadas con los dígitos 1, 2 y 3, se puede utilizar este segmento de instrucciones:


String alfabeto = "123";
char[] elementos = alfabeto.toCharArray();
generarPermutacionSust(elementos, "", 2);


Con este código se generarían como salida las siguientes cadenas: 11, 12, 13, 21, 22, 23, 31, 32 y 33


Generación sin sustitución

Cuando se requieren generar todas las posibles cadenas de determinado tamaño formadas a partir de un conjunto de caracteres pero sin que se repita ningún caracter entonces se debe llevar un pequeño control de que caracteres ya han salido para evitar su inclusión.

En este programa basado en la entrada anterior anterior del blog se agrega un arreglo de valores booleanos de 100 posiciones, aunque podría ser de mayor tamaño, en el cual cada vez que se utiliza un caracter, se marca su posición para no volverlo a usar, pero se deja disponible una vez se ha liberado el caracter de su uso:

// Permutaciones sin sustitución
    static boolean[] control = new boolean[100];
    public static void generarPermutacionNoSust(char[] elementos, String actual, int cantidad) {
        if(cantidad==0) {
            // Hacer con la secuencia generada
            System.out.println(actual);
        }
        else {
            for(int i=0; i<elementos.length; i  ) {
                if(control[i]==true) continue;
                control[i]=true;
                generarPermutacionNoSust(elementos, actual elementos[i],cantidad-1);
                control[i]=false;
            }
        }
    }


Para probar este método para generar todas las posibles subcadenas de dos caracteres sin sustitución formadas con los dígitos 1, 2 y 3, se puede utilizar este segmento de instrucciones:


String alfabeto = "123";
char[] elementos = alfabeto.toCharArray();
generarPermutacionNoSust(elementos, "", 2);


Con este código se generarían como salida las siguientes cadenas: 12, 13, 21, 23, 31 y 32

martes, octubre 12, 2010

Mejorando la generación de números vampiros

En la siguiente versión del método generarVampiros, se va a modificar la salida con tres parámetros booleanos que permitirán generar hasta 8 listas diferentes teniendo en cuenta si los factores que se multiplican para formar el número vampiro tienen el mismo número de dígitos (vMitad); si dichos factores son números primos o no (vPrimo); y si tanto los factores como el número generado no tienen dígitos repetidos (vUnico).

De esta manera, la ejecución del método generarVampiros(8, true, true, true) generará solamente números vampiros de 8 dígitos formados por la multiplicación de dos números de 4 dígitos que sean primos y que no contengan dígitos repetidos. En este caso, la respuesta del programa es la siguiente:

10.349.527 = 2.579 x 4.013
10.429.753 = 2.309 x 4.517
17.204.359 = 2.309 x 7.451
18.647.023 = 2.741 x 6.803
54.918.067 = 5.801 x 9.467
64.781.293 = 7.691 x 8.423



public static Vector<String> generarVampiros(int digitos, boolean vMitad, 
                                             boolean vPrimo, boolean vUnico) {
        // vMitad: true para factores del mismo tamaño
        // vPrimo: true para factores primos
        // vUnico: true para factores sin dígitos repetidos
        Vector<Integer> va, vb, vc;
        Vector<String>  respuesta = new Vector<String>();
        long numFinal = (long) Math.pow(10,digitos)-1;    // último vampiro posible
        long numBase  = (long) Math.pow(10,digitos-1);    // primer vampiro posible
        long numMin   = (long) Math.pow(10,digitos/2-1);  // menor factor tamaño n/2
        long numMax   = (long) Math.pow(10,digitos/2)-1;  // mayor factor tamaño n/2
        long factorInicialA=0;
        long factorFinalA=0;
        long factorInicialB=0;
        long factorFinalB=0;
        if(vMitad) {
            factorInicialA = numMin;
            factorFinalA   = numMax;
        }
        else {
            factorInicialA = 1;
            factorFinalA   = numFinal;
        }
        for(long a = factorInicialA; a<=factorFinalA; a++) {
            if(vPrimo && !Algoritmos.esPrimoV6(a)) continue;
            va = vectorDigitos(a);
            if(vMitad) {
                factorInicialB=Math.max(a+1,numBase/a);
                factorFinalB=numMax;
            }
            else {
                factorInicialB = Math.max(a+1,numBase/a);
                factorFinalB = numFinal;
            }
            for(long b = factorInicialB; b<=factorFinalB; b++) {
                if(vPrimo && !Algoritmos.esPrimoV6(b)) continue;
                long c = a*b;
                if(c>numFinal) { b=numFinal; continue; }
                if(c<numBase) continue;
                vb = vectorDigitos(b);
                vc = vectorDigitos(c);
                if(vUnico) {
                    Set<Integer> sa = new TreeSet<Integer>();
                    Set<Integer> sc = new TreeSet<Integer>();
                    sa.addAll(va);
                    sa.addAll(vb);
                    sc.addAll(vc);
                    if(sc.size()==digitos && sa.equals(sc)) {
                        respuesta.add(String.format("%,12d = %,6d x %,6d",c, a,b));
                    }
                }
                else {
                    for(int x: va) vb.add(x);
                    Collections.sort(vb);
                    Collections.sort(vc);
                    if(vb.equals(vc)) {
                        respuesta.add(String.format("%,12d = %,6d x %,6d",c, a,b));
                    }
                }
            }
        }
        Collections.sort(respuesta);
        return respuesta;
    }

domingo, octubre 10, 2010

Evaluador simple de funciones en java

Escribir un programa para evaluar una función que sea ingresada por el usuario como una cadena de caracteres es una labor que exige utilizar los pasos principales del proceso de compilación: análisis léxico, análisis sintáctico y análisis semántico.

En el programa en java que se transcribe a continuación, se define una clase llamada Expresion que puede ser incorporada fácilmente a cualquier otro programa, pues no requiere clases especiales diferentes a las ya existentes en la máquina virtual de java. Se requiere tan solo un uso reducido del paquete java.util.regex para el manejo de expresiones regulares, y del paquete java.lang.reflect para la invoación de métodos de la clase java.lang.Math como parte de la función ingresada por el usuario.

Los objetos de la clase Expresion se crean con una cadena que representa la función, la cual podría ser, por ejemplo "x^3-2*x^2+1", o incluso utilizar funciones matemáticas de la clase java.lang.Math que reciban un solo valor como parámetro, por lo que la función x*cos(x)^2 sería completamente válida.

import java.util.*;
import java.util.regex.*;
import java.lang.reflect.*;

public class Expresion {
    enum TipoToken  {   NUMERO, VARIABLE, FUNCION, ADD, SUB, MUL, DIV,
                        EXP, P_IZQ, P_DER, ERROR };
    class Token {
        TipoToken tipo;
        String    texto;
        Token(TipoToken ti, String te) { tipo=ti; texto=te;}
        Token(TipoToken ti) { tipo = ti; }
    }
    Queue<Token>    colaTokens;
    String          cadenaFuncion;
    double          variable;

    Expresion(String c) throws Exception {
        cadenaFuncion = c;
    }

    private void generarTokens() throws Exception {
        colaTokens = new LinkedList<Token>();
        StringBuffer entrada   = new StringBuffer(cadenaFuncion);
        Pattern pNumero = Pattern.compile("\\-?\\d+(\\.\\d+)?");
        Pattern pID     = Pattern.compile("\\p{Alpha}\\w+");
        while(entrada.length()>0) {
            Matcher      m  = pNumero.matcher(entrada);
            if(m.lookingAt()) {
                colaTokens.add(new Token(TipoToken.NUMERO,m.group()));
                entrada.delete(0, m.end());
                continue;
            }
            if(entrada.charAt(0) == 'x' || entrada.charAt(0) == 'X') {
                colaTokens.add(new Token(TipoToken.VARIABLE,"x"));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '+') {
                colaTokens.add(new Token(TipoToken.ADD));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '-') {
                colaTokens.add(new Token(TipoToken.SUB));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '*') {
                colaTokens.add(new Token(TipoToken.MUL));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '/') {
                colaTokens.add(new Token(TipoToken.DIV));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '(') {
                colaTokens.add(new Token(TipoToken.P_IZQ));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == ')') {
                colaTokens.add(new Token(TipoToken.P_DER));
                entrada.deleteCharAt(0);
                continue;
            }
            if(entrada.charAt(0) == '^') {
                colaTokens.add(new Token(TipoToken.EXP));
                entrada.deleteCharAt(0);
                continue;
            }
            m = pID.matcher(entrada);
            if(m.lookingAt()) {
                colaTokens.add(new Token(TipoToken.FUNCION, m.group()));
                entrada.delete(0, m.end());
                continue;
            }
            throw new Exception("Elemento no reconocido en la entrada: " 
                                 + entrada.charAt(0));
        }
    }

    private double evaluar(double x) throws Exception {
        generarTokens();
        variable = x;
        return expresion();
    }

    private double expresion() {
        double respuesta=termino();
        while(!colaTokens.isEmpty() ) {
            switch(colaTokens.element().tipo) {
                case ADD:   colaTokens.remove();
                            respuesta+=termino();
                            continue;
                case SUB:   colaTokens.remove();
                            respuesta-=termino();
                            continue;
            }
            break;
        }
        return respuesta;
    }

    private double termino() {
        double respuesta=factor();
        while(!colaTokens.isEmpty() ) {
            switch(colaTokens.element().tipo) {
                case MUL:   colaTokens.remove();
                            respuesta*=factor();
                            continue;
                case DIV:   colaTokens.remove();
                            respuesta/=factor();
                            continue;
                default:
            }
            break;
        }
        return respuesta;
    }

    private double factor() {
        double respuesta=valor();
        while(!colaTokens.isEmpty() ) {
            switch(colaTokens.element().tipo) {
                case EXP:   colaTokens.remove();
                            respuesta=Math.pow(respuesta,valor());
                            continue;
            }
            break;
        }
        return respuesta;
    }

    private double valor() {
        Token token;
        try {
            double respuesta = 0;
            token     = colaTokens.poll();
            switch(token.tipo) {
                case P_IZQ:     respuesta = expresion();
                                leaToken(TipoToken.P_DER);
                                return respuesta;
                case NUMERO:    return Double.parseDouble(token.texto);
                case VARIABLE:  return variable;
                case FUNCION:   leaToken(TipoToken.P_IZQ);
                                double argumento=expresion();
                                leaToken(TipoToken.P_DER);
                                Method m = java.lang.Math.class.
                                           getMethod(token.texto, Double.TYPE);
                                return (Double) m.invoke(null, argumento);
            }
            return respuesta;
        }
        catch(Exception ex) {
            System.err.println("Error: "  + ex.getMessage());
            System.exit(0);
        }
        return 0;
    }

    private boolean leaToken(TipoToken t) {
        Token token = colaTokens.poll();
        if(token.tipo.equals(t)) {
            return true;
        }
        else {
            System.err.println("Error: elemento no permitido "  + token.texto );
            return false;
        }
    }

    public static void main(String[] args) throws Exception {
        String funcion = "x*cos(x)^2";
        Expresion  exp = new Expresion(funcion);
        for(int x=0; x<=10; x++  ) {
            System.out.println(exp.evaluar(x));
        }
    }
}

El método main es una muestra del uso que se le puede dar a esta clase. Es importante tener en cuenta que sólo acepta funciones definidas con la variable 'x' y que las funciones matemáticas de la clase java.lang.Math aceptadas son las que reciben un solo parametro como argumento. Sin embargo, es válido utilizar por ejemplo la fución "sin(cos(x^2+1))", ya que cada una de las funciones está recibiendo como argumento una función o expresión evaluable de un solo argumento.

viernes, octubre 08, 2010

Los 5 lenguajes de programación más populares - Octubre 2010

De acuerdo con la información del portal tiobe.com los lenguajes de programación más populares entre la comunidad informática mundial para el mes de octubre de 2010 son los siguientes:

1. Java (18.17%)
2. C (17.18%)
3. C++ (9.80%)
4. PHP (8.32%)
5. VisualBasic (5.65%)

Es importante anotar que, a pesar de la inmensa cantidad de lenguajes de programación existentes, estos 5 concentran (y lo han hecho por mucho tiempo) aproximadamente el 60% del interés de la comunidad informática mundial.

En cuanto a la evolución histórica de preferencias de lenguajes de programación java se mantiene en el primer lugar, pero es muy importante tener en cuenta que el lenguaje C mantiene una vigencia constante desde el año 1985.

Por tipos de lenguajes de programación, los lenguajes orientados a objetos tienen el 55.9% de las preferencias y los lenguajes procedimentales el 38.9%, dejando sólo el 5.2% para los demás tipos de lenguajes de programación, lo que indica que si bien puede existir un interés de tipo académico o investigativo por otros paradigmas de programación, los nichos donde se pueden aplicar conocimientos en estos lenguajes son reducidos.



jueves, octubre 07, 2010

Ejemplo de antlr - Campeonato de fútbol

En el siguiente ejemplo en antlr se va a trabajar el problema de generar una tabla de puntuación para un torneo de fútbol. Se han utilizado solamente 4 equipos de fútbol, pero el ejemplo se puede modificar para permitir más equipos, bien sea determinados con anterioridad o no.

Tanto las reglas léxicas como sintácticas son relativamente sencillas, pues solo hay dos componentes léxicos principales: el equipo y el número de goles anotado; en el caso de las reglas sintácticas, también son dos: la que define el torneo como una secuencia de partidos, y la que define el partido como una combinación de dos equipos con dos números.

Las reglas semánticas implementadas en la gramática son tres: una para inicializar la tabla de resultados; la segunda para registrar en la tabla el resultado de un partido; la tercera para ordenar y mostrar la tabla de resultados al final del proceso.

En el ejemplo se muestra la forma de importar librerias de clase desde java y la definición de elementos del lenguaje: la clase Equipo con sus atributos y métodos, así como los métodos que implementan las acciones semánticas: crearTabla, registrarPartido y mostrarTabla.

grammar Campeonato;
// Codigo en lenguaje anfitrion
@header{
 import java.util.Vector;
 import java.util.Collections;
}
@members{
 class Equipo implements Comparable<Equipo> {
  String nombre;
  int  pj;
  int  pg;
  int  pe;
  int  pp;
  int  gf;
  int  gc;
  int  ptos;
  int dif() { return gf-gc; }
  Equipo(String n) { nombre = n;}
  public String toString() { 
   return String.format("\%-20s \%2d \%2d \%2d \%2d \%2d \%2d \%2d \%4d", 
                         nombre, pj, pg, pe, pp, gf, gc, dif(), ptos); 
  }
  public boolean equals(Object o) {
   Equipo tmp = (Equipo) o;
   if(this.nombre.equals(tmp.nombre)) return true;
   else return false;
  }
  public int compareTo(Equipo tmp) {
   if(this.ptos < tmp.ptos) return -1;
   else if(this.ptos > tmp.ptos) return 1;
   else if(this.dif() < tmp.dif()) return -1;
   else if(this.dif() > tmp.dif()) return 1;
   else if(this.pg < tmp.pg) return -1;
   else if(this.pg > tmp.pg) return 1;
   else return 0;
  }
 }
  
 Vector<Equipo> tabla = new Vector<Equipo>();
  
 void crearTabla() {
  tabla.add(new Equipo("Arsenal"));
  tabla.add(new Equipo("Chelsea"));
  tabla.add(new Equipo("Liverpool"));
  tabla.add(new Equipo("Manchester City"));
 }
  
 void registrarPartido(String ne1, String ge1, String ne2, String ge2) {
  int ng1 = Integer.parseInt(ge1);
  int ng2 = Integer.parseInt(ge2);
  Equipo e1 = new Equipo(ne1);
  Equipo e2 = new Equipo(ne2);
  e1=tabla.get(tabla.indexOf(e1));
  e2=tabla.get(tabla.indexOf(e2));
  e1.pj++;  e2.pj++  ;
  e1.gf+=ng1; e2.gf+=ng2;
  e1.gc+=ng2; e2.gc+=ng1;
  if(ng1>ng2)   { e1.pg++; e2.pp++; e1.ptos+=3; }
  else if(ng1<ng2) { e1.pp++; e2.pg++; e2.ptos+=3; }
  else     { e1.pe++; e2.pe++; e1.ptos++; e2.ptos++; }
 }
  
 void mostrarTabla() {
  Collections.sort(tabla);
  Collections.reverse(tabla);
  System.out.println("Equipo               PJ PG PE PP GF GC DG PTOS");
  System.out.println("-------------------- -- -- -- -- -- -- -- ----");
  for(Equipo e: tabla) System.out.println(e);
 }
}
 
// Componente lexicos
fragment DIGITO  : '0'..'9' ;
fragment LETRA   : 'A'..'Z'|'a'..'z';
NUMERO  : DIGITO DIGITO? ;
EQUIPO  : LETRA+ ((' ' LETRA) => ' ' LETRA+)*;
ESPACIO  : (' '|'\t'|'\n') { skip(); };
 
// Componentes sintacticos
torneo : { crearTabla(); } 
    partido+ 
    { mostrarTabla(); }
        ;
         
partido  : a=EQUIPO b=NUMERO c=EQUIPO d=NUMERO
          { registrarPartido($a.text, $b.text, $c.text, $d.text); }
        ;

Uso de reflexión para evaluar funciones matemáticas

Continuando con el uso del paquete java.lang.reflect, en este programa se muestra una forma fácil de invocar una función cualquiera de la clase java.lang.Math solicitada por el usuario en tiempo de ejecución.

El programa pregunta por pantalla la expresión matemática y, haciendo uso de la funcionalidad de expresiones regulares de java, verifica que la expresión esté bien escrita, que el método solicitado esté en la clase java.Math y que el argumento entre paréntesis sea un número.


import java.lang.reflect.*;
import static javax.swing.JOptionPane.*;


public class TestReflect {
    public static void main(String[] args) {
        ejecutarMetodoMatematico();
    }

    public static void ejecutarMetodoMatematico(){
        String cadena;
        String[] elem;
        boolean  valido=false;
        do {
            cadena = showInputDialog("Función matematica");
            if(cadena==null) break;
            if(!cadena.matches("\\w \\s*\\(\\s*\\-?\\d (\\.\\d )?\\s*\\)\\s*")){
                mostrarError("Cadena no permitida");
                continue;
            }
            elem   = cadena.split("\\(|\\)");
            elem[0] = elem[0].trim();
            elem[1] = elem[1].trim();
            if(elem.length!=2) {
                mostrarError("Cadena no valida");
                continue;
            }
            Class c = java.lang.Math.class;
            Method m;
            try {
                m = c.getMethod(elem[0], Double.TYPE);
            }
            catch(NoSuchMethodException x) {
                mostrarError("Metodo '" elem[0] "' no permitido");
                continue;
            }
            if(!elem[1].matches("\\-?\\d (\\.\\d*)?")) {
                mostrarError("Numero '" elem[1] "' no es valido");
                continue;
            }
            valido = true;
            double num = Double.parseDouble(elem[1]);
            try {
                Object respuesta = m.invoke(null, num);
                mostrarRespuesta(cadena " = "  respuesta);
            }
            catch(IllegalAccessException x) { x.printStackTrace(); }
            catch(InvocationTargetException x) { x.printStackTrace(); }
        } while(!valido);
    }

    public static void mostrarError(String msg) {
        showMessageDialog(null, msg, "Error", ERROR_MESSAGE);
    }

    public static void mostrarRespuesta(String msg) {
        showMessageDialog(null, msg, "Solución", PLAIN_MESSAGE);
    }
}

Ordenación por Residuos - Radix Sort

El método de ordenación por residuos, o RadixSort, utiliza una aproximación diferente a la de comparar los elementos del arreglo entre sí. En vez de esto, este algoritmo recorre el arreglo trasladando cada elemento a una cola determinada por el residuo, o dígito menos significativo del número. Cuando todos los elementos han sido trasladados a las colas, se recorren todas las colas en orden trasladando ahora los elementos al vector. El proceso se repite ahora para los demás dígitos de los elementos del vector.

Si bien se habla de digitos (unidades, decenas, centenas, etc), para un computador es más eficiente hacer las operaciones a nivel de bit, con desplazamientos, que las operaciones de división y residuo. Por tal motivo, la implementación que se presenta a continuación utiliza corrimientos de 4 bits, que se pueden representar como dígitos hexadecimales.


public static void ordenacionResiduos(int[] v) {
        int max    = 1;     // cantidad de repeticiones
        int nbytes = 4;     // numero de bytes a desplazar
        int nColas = (int) Math.pow(2,nbytes) ;
        // Creación e inicialización del arreglo de colas
        Queue<Integer>[] cola = new LinkedList[nColas];
        for(int i=0; i<nColas; i++) cola[i]=new LinkedList<Integer>();

        int     div     = 0;        // posición a comparar
        for(int i=0; i<max; i++) {
            // parte 1: recorrer el vector  para guardar cada elemento
            // en la cola correspondiente
            for(int numero: v) {
                // buscar el mayor número del vector
                if(i==0) if(numero>max) max=numero;
                // calcular en qué cola debe ir cada número
                int numCola = (numero>>div) & 0xf;
                cola[numCola].add(numero);
            }
            div = div+nbytes;

            // parte 2: recorrer las colas en orden para poner cada
            // elemento en el vector;
            int j=0;
            for(Queue<Integer> c: cola) {
                while(!c.isEmpty()) v[j++]=c.remove();
            }
            // la primera vez se actualiza el número de veces que se
            // debe ejecutar el proceso
            if(i==0) { max = (int) (Math.log(max)/Math.log(nColas)) + 1; }
        }
    }


La complejidad de este algoritmo es lineal, O(NxM), donde N es el número de elementos del arreglo y M es el número de dígitos del mayor elemento del vector.

miércoles, octubre 06, 2010

Uso del paquete java.lang.reflect

Utilizando las funcionalidades del paquete java.lang.reflect se pueden manipular, en tiempo de ejecución, los métodos y atributos de una clase. Por ejemplo, si se tienen todos los métodos de ordenación en una clase de nombre Algoritmos, se puede crear un método genérico que invoque a cualquiera de ellos sin utilizar un bloque condicional mediante la funcionalidad de "reflexión" de los métodos de la clase Algoritmos.

En el siguiente código, se asume que los métodos de ordenación publicados se encuentran en una clase de nombre "Algoritmos" y que se ha importado el paquete java.lang.reflect. El método ejecutarMetodo recibe como parámetro el nombre del método de la clase Algoritmos que implementa el algoritmo de ordenación requerido, así como el vector a ordenar, y devuelve el tiempo en segundos que tardó la ejecución del mismo.


public static double ejecutarMetodo(String nombreMetodo, int[] v) {
        try {
            Method m = Algoritmos.class.getMethod(nombreMetodo, v.getClass());
            double t1 = System.currentTimeMillis();
            m.invoke(null, v);
            double t2 = System.currentTimeMillis();
            return (t2-t1)/1000.0 ;
        }
        catch(Exception x) {
            System.out.println(x.getMessage());
            System.exit(0);
            return 0;
        }
    }


Para probar el funcionamiento de esta característica se puede crear una clase diferente, en este caso la clase TestReflect que se puede ejecutar desde la línea de comandos para recibir una lista de métodos de ordenación que se van a probar con tamaños de vector desde 1 en potencias de 2. A continuación se muestra el código de implementación de la clase TestReflect. Para efectos de prueba se incluyeron dos nombres de método por default, en caso de que la clase no se ejecute desde la línea de comandos:

public class TestReflection {
    public static void main(String[] args) {
        String[] tmp =  {"ordenacionInsercion", "ordenacionRapida"};
        if(args.length==0) args = tmp;
        int n=1;
        while(n<Integer.MAX_VALUE) {
            System.out.printf("%,12d ", n);
            for(String algoritmo: args) {
                int[] v = Algoritmos.crearVector(n);
                System.out.printf("%,12f ",Algoritmos.ejecutarMetodo(algoritmo, v));
            }
            System.out.println();
            n*=2;
        }
    }
}

En este caso en particular, los resultados para los dos algoritmos probados, con tamaños de vector por encima de 1,024 son los siguientes:

1.024     0,001000     0,000000 
       2.048     0,004000     0,000000 
       4.096     0,013000     0,001000 
       8.192     0,053000     0,000000 
      16.384     0,219000     0,002000 
      32.768     0,863000     0,005000 
      65.536     3,377000     0,010000 
     131.072    13,468000     0,019000 
     262.144    54,277000     0,041000 
     524.288   220,892000     0,085000 

Del análisis de estos datos se puede detectar fácilmente que el incremento en el tiempo requerido para ordenar un vector es aproximadamente cuatro veces mayor cuando el tamaño del vector aumenta al doble, mientras que para el de ordenación rápida, el incremento es ligeramente superior al doble. Ambas observaciones se corresponden con lo esperado según el análisis de su complejida.

martes, octubre 05, 2010

Números Vampiros

Los números vampiros son aquellos números con número par de dígitos que son resultado del producto de dos enteros de igual número de dígitos y que tienen como característica que están formados en su totalidad por los dígitos que conforman a sus dos factores.

Por ejemplo, para el caso de los números de 4 dígitos existen 7 números vampiros que se calculan así:

15 x 93 = 1.395
21 x 60 = 1.260
21 x 87 = 1.827
27 x 81 = 2.187
30 x 51 = 1.530
35 x 41 = 1.435
80 x 86 = 6.880

En este programa en JAVA se presenta una aproximación a la generación de números vampiros de 6 dígitos, pero que puede ser fácilmente configurable para generar números vampiros de cualquier tamaño. Para efectos de prueba el programa genera los números en un arreglo de cadenas, solamente por la facilidad de mostrar los factores que lo producen, pero también puede ser modificado para generar solamente los números vampiros en un arreglo o vector de números enteros o enteros grandes:


import java.util.*;

public class Vampiros {
    public static void main(String[] args) {
        Vector<String> respuesta = generarVampiros(6);
        System.out.println(respuesta.size());
        for(String x: respuesta) {
            System.out.println(x);
        }
    }
    public static Vector<String> generarVampiros(int digitos) {
        Vector<Integer> va, vb, vc;
        Vector<String>  respuesta = new Vector<String>();
        int numFinal = (int) Math.pow(10,digitos)-1;
        int numMin   = (int) Math.pow(10,digitos/2-1);
        int numMax   = (int) Math.pow(10,digitos/2)-1;
        for(int a = numMin; a<=numMax; a  ) {
            va = vectorDigitos(a);
            for(int b = a+1; b<=numMax; b  ) {
                int c = a*b;
                if(c>numFinal) { b=numFinal; continue; }
                vb = vectorDigitos(b);
                vc = vectorDigitos(c);
                for(int x: va) vb.add(x);
                Collections.sort(vb);
                Collections.sort(vc);
                if(vb.equals(vc)) {
                    respuesta.add(String.format("%,6d x %,6d = %,8d",a,b,c));
                }
            }
        }
        return respuesta;
    }

    public static Vector<Integer> vectorDigitos(int tmp) {
        int x=tmp;
        Vector<Integer> respuesta = new Vector<Integer>();
        while(x>=1) {
            respuesta.add(x % 10);
            x/=10;
        }
        return respuesta;
    }
}

lunes, octubre 04, 2010

Evaluador de expresiones aritméticas en AntLR

Esta gramática en ANTLR y escrita utilizando el paquete AntLRWorks.jar permite evaluar expresiones aritméticas que incluyan operaciones de suma, resta, multiplicación, división y exponenciación de número enteros y reales. Se permiten igualmente las expresiones anidadas entre paréntesis.

Desde el punto de vista léxico se define el componente NUMERO formado a partir del componente DIGITO para reconocer solamente números positivos enteros o reales; se ignoran los espacios con la regla ESPACIO, y los demás caracteres no permitidos generarán un error de ejecución con el componente RESTO ya que éste no aparece en ninguna regla gramatical.

Desde el punto de vista gramatical y semántico, se define una regla principal (s) que direcciona a una expresion y muestra al final el resultado de la misma. Las demás reglas se encargan de definir los diferentes componentes gramaticales: expresión, término, factor y valor. Las reglas semánticas se encargan de ir haciendo las operaciones a medida que se van traduciendo.


grammar evaluador1;

// Componentes léxicos
fragment DIGITO : '0'..'9' ;
NUMERO    : DIGITO+ '.'? DIGITO* ;
ESPACIO   : ( ' ' | '\t' ) {$channel=HIDDEN;}   ;
RESTO     : . ;

// Componentes sintácticos y semánticos
// s: componente principal
s        :  a=exp { System.out.println($a.vlr); }
        ;
// exp: expresion
exp returns[double vlr] : a=ter {$exp.vlr = $a.vlr; }
         ( '+' b=ter { $exp.vlr+=$b.vlr; }
         | '-' c=ter { $exp.vlr-=$c.vlr; }
         )*;
// ter: termino
ter returns[double vlr] : a=fac {$ter.vlr = $a.vlr; }
         ( '*' b=fac { $ter.vlr*=$b.vlr; }
         | '/' c=fac { $ter.vlr/=$c.vlr; }
         )*;
// fac: factor
fac returns[double vlr] : a=val { $fac.vlr = $a.vlr; }
         ( '^' b=val { $fac.vlr=Math.pow($fac.vlr,$b.vlr); }
         )*;
// valor
val returns[double vlr] : n=NUMERO { $val.vlr = Double.parseDouble($n.text); } 
        | '(' exp ')' 
        ;


Esta gramática queda grabada en el archivo "evaluador1.g". Para generar los programas en JAVA se puede utilizar la opción de generar código existente en la herramienta AntLRWorks o por línea de comandos utilizando la instrucción:

java org.antlr.Tool evaluador1.g

Si es necesario se debe incluir en el classpath la ruta donde está instalado antlr, o en su defecto el mismo archivo de AntLRWorks puede servir, en cuyo caso la instrucción quedaría así:

java -cp c:\algunaruta\antlrworks.jar org.antlr.Tool evaluador1.g

Cualquiera sea el método utilizado, se generarán dos archivos: evaluador1Lexer.java y evaluador1Parser.java, los cuales contienen respectivamente los analizadores léxicos y sintácticos generados a partir de la gramática especificada.

Para correr la gramática, se puede hacer desde un programa en java que cargue adecuadamente las librerías de antlr. Este ejemplo muestra un programa muy simple que lee por consola una expresión aritmética y devuelve el resultado:


import org.antlr.runtime.*;
import java.io.*;

public class TestEvaluador1 {
 public static void main(String args[]) throws Exception {
  Console consola = System.console();
  String  mensaje = "Escriba una expresion aritmetica"; 
  String pregunta = "";

  if(consola!=null) {
   consola.printf(mensaje);
   pregunta = consola.readLine();
  }
  else {
   pregunta = javax.swing.JOptionPane.showInputDialog(mensaje);
  }

  evaluador1Lexer      lex = new evaluador1Lexer(
        new ANTLRStringStream(pregunta));
  CommonTokenStream tokens = new CommonTokenStream(lex);
  evaluador1Parser    gram = new evaluador1Parser(tokens);

  gram.s();
 }
}

domingo, octubre 03, 2010

Ordenación Shaker

El algoritmo de ordenación por el método Shaker, también conocido como "Cocktail" o "Sacudida" es una mejora del método de la burbuja en la cual el proceso se realiza tanto desde la primera posición a la última del arreglo como en sentido inverso, evitando así que los elementos más pequeños tarden un mayor tiempo en "ascender" a las posiciones superiores.

La implementación de este algoritmo en lenguaje JAVA es la siguiente:

// Algoritmo de ordenacion Shaker Sort
    public static void ordenacionShaker(int[] v) {
        final int N = v.length;
        int limInferior = 0;
        int limSuperior = N-1;
        while(limInferior <= limSuperior) {
            for(int j=limInferior; j<limSuperior; j++) {
                if(v[j]>v[j 1]) {
                    int tmp = v[j];
                    v[j]    = v[j+1];
                    v[j+1]  = tmp;
                }
            }
            limSuperior--;
            for(int j=limSuperior;j>limInferior; j--) {
                if(v[j]<v[j-1]) {
                    int tmp = v[j];
                    v[j]    = v[j-1];
                    v[j-1]  = tmp;
                }
            }
            limInferior++;
        }
    }
La complejidad del algoritmo es cuadrática, puesto que si bien mejora un poco el rendimiento del método de la burbuja, no cambia el hecho de recorrer el arreglo una vez por cada cada elemento que se quiere dejar en su posición correcta. Se puede probar con la ecuación de recurrencias T(n) = k n + T(n-1) con la tecnología del motor de cálculo WolframAlpha.

Ordenación por Burbuja - Bubble Sort

El algoritmo de ordenación por el método de la burbuja, o Bubble Sort recorre todo el arreglo comparando cada uno de los elementos con el elemento siguiente e intercambiándolos de ser necesario. Al finalizar este proceso, el elemento mayor queda ubicado en la última posición de arreglo, mientras que todos los elementos menores han "ascendido" una posición. El proceso se continúa repitiendo nuevamente desde la posición inicial del arreglo hasta que cada elemento "caiga" a su posición correcta.

La implementación de este algoritmo en lenguaje JAVA es la siguiente:

// Algoritmo de ordenacion por Burbuja
    public static void ordenacionBurbuja(int[] v) {
        final int N = v.length;
        for(int i=N-1; i>0; i--) {
            for(int j=0; j<i; j++) {
                if(v[j]>v[j+1]) {
                    int tmp = v[j];
                    v[j]    = v[j+1];
                    v[j+1]  = tmp;
                }
            }
        }
    }

La complejidad del algoritmo es cuadrática, puesto que cada para lograr llevar un elemento a la última posición del arreglo se deben recorrer todos los elementos del mismo, y este proceso se repite para todos los demás elementos. Se puede probar con la ecuación de recurrencias T(n) = k n + T(n-1) con la tecnología del motor de cálculo WolframAlpha.

Ordenación por Inserción

El algoritmo de ordenación por inserción toma cada elemento a partir del segundo y recorre el vector en sentido inverso ubicando el elemento en su posición correcta haciendo los intercambios necesarios. Cuando termina de ubicar un elemento en su posición correcta, continúa con el siguiente elemento hasta hacer este proceso con todos los elementos del arreglo.

La implementación de este algoritmo en lenguaje JAVA es la siguiente:

// Algoritmo de ordenacion por insercion
    public static void ordenacionInsercion(int[] v) {
        final int N = v.length;
        for(int i=1; i<N; i++) {
            int j=i;
            while(j>0 && v[j]<v[j-1] ){
                int tmp = v[j];
                v[j]    = v[j-1];
                v[j-1]  = tmp;
                j--;
            }
        }
    }

La complejidad del algoritmo es cuadrática, puesto que cada para insertar el elemento en su posición correcta se deben recorrer los elementos anteriores a él. Sin embargo, este algoritmo presenta un mejor desempeño que otros algoritmos de complejidad cuadrática pues no es necesario recorrer para cada elemento la totalidad de los elementos anteriores, sino solamente hasta la posición correcta para un elemento en particular. Se puede probar con la ecuación de recurrencias T(n) = k n + T(n-1) con la tecnología del motor de cálculo WolframAlpha.

sábado, octubre 02, 2010

Ordenación por Selección

El algoritmo de ordenación por selección recorre todo el arreglo desde la primera posición buscando el menor elemento de todos. Cuando termina, lo reemplazar por el elemento de la primera posición y repite todo el proceso con el segundo elemento y así sucesivamente.

La implementación de este algoritmo en lenguaje JAVA es la siguiente:

// Algoritm de ordenacion por seleccion.
    public static void ordenacionSeleccion(int[] v) {
        final int N = v.length;
        for(int i=0; i<N; i++) {
            int posMenor = i;
            for(int j=i+1; j<N; j++) {
                if(v[j]<v[posMenor]) posMenor=j;
            }
            if(posMenor!=i) {
                int tmp     = v[i];
                v[i]        = v[posMenor];
                v[posMenor] = tmp;
            }
        }
    }

La complejidad del algoritmo es cuadrática, puesto que cada para identificar cuál elemento va en cada posición se debe comparar con los i-1 elementos posteriores a él. Se puede probar con la ecuación de recurrencias T(n) = k n + T(n-1) con la tecnología del motor de cálculo WolframAlpha.

Ordenación Clásica

El algoritmo de ordenación clásica es el primer algoritmo de ordenación que se enseña, normalmente dentro de un curso básico de algoritmos o de programación. Consiste básicamente en tomar el primer elemento del arreglo e irlo comparando con los demás y, en caso de encontrar un elemento menor que él, intercambiarlo inmediatamente. Una vez terminado de recorrer el vector, se tiene en la primera posición al menor elemento de todos. El proceso se repite ahora con el segundo elemento del arreglo y así para todos los elementos.

La implementación de este algoritmo en lenguaje JAVA es la siguiente:

// Algoritmo de ordenacion tradicional.
    public static void ordenacionTradicional(int[] v) {
        final int N = v.length;
        for(int i=0; i<N; i++) {
            for(int j=i+1; j<N; j++) {
                if(v[i]>v[j]) {
                    int tmp = v[i];
                    v[i] = v[j];
                    v[j] = tmp;
                }
            }
        }
    }

La complejidad del algoritmo es cuadrática, puesto que cada uno de los n elementos del arreglo se compara con los i-1 elementos posteriores a él. Se puede probar con la ecuación de recurrencias T(n) = k n + T(n-1) con la tecnología del motor de cálculo WolframAlpha.

viernes, octubre 01, 2010

Reversar MD5

Para encontrar la clave a partir de la cuál se generó el MD5 se utiliza un procedimiento que evalúa todas las posibles combinaciones de caracteres o letras de un tamaño determinado:

/**
* Construye recursivamente cadenas de un tamaño determinado para generarles
* su MD5 y compararlo con el MD5 objetivo.
* 
* @param alfabeto - Arreglo con los posibles caracteres que pueden formar claves
* @param objetivo - Cadena de caracteres con el MD5 conocido
* @param actual   - Subcadena de la posible clave previamente formada
* @param size     - Cantidad faltante de caracteres a completar en la posible clave
* @return Clave encontrada
*/
public static String buscarClave(char[] alfabeto, String objetivo, 
                                 String actual, int size) {
    // Cuando el tamaño es 0, la subcadena recibida es la clave candidata a evaluar
    if(size == 0 ) {
        String tmpOut = generarMD5(actual);
        if(tmpOut.equals(objetivo)) return actual;
        else return null;
    }
    // Si el tamaño no es 0, se le agrega a la subcadena candidata cada uno
    // de los caracteres del alfabeto y se llama recursivamente al mismo método.
    // Si se encontró la clave, se retorna, y si no, se evalúa el siguiente caracter.
    for(char caracter: alfabeto) {
        String clave = buscarClave(alfabeto, objetivo, actual+caracter, size-1);
        if(clave!=null) return clave;
    }
    // Si la clave no se pudo encontrar se retorna el valor nulo
    return null;
}


Para simplificar el proceso de búsqueda de claves de cualquier tamaño se crea un método similar al anterior que hace un ciclo para generar y evaluar cadenas de diferentes tamaños. En este método he involucrado código adicional para calcular el tiempo tardado en realizar la evaluación para cada uno de los tamaños:

public static String buscarClave(String alfabeto, String cadena) {
    char[] alfa = alfabeto.toCharArray();
    for(int i=1; i<20; i++) {
        System.out.printf("Evaluando claves de tamaño %2d -> ",i);
        long  t1 = System.currentTimeMillis();
        String clave = buscarClave(alfa, cadena, "", i);
        long  t2 = System.currentTimeMillis();
        double t = (t2-t1)/1000.0;
        System.out.printf("tiempo: %,10.3f segs %n", t);
        if(clave != null) return clave;
    }
    return null;
}

Generación MD5

Se puede generar el código MD5 para una cadena de caracteres utilizando las funcionalidades de java provistas por la clase MessageDigest del paquete java.security:

import java.security.*;
import java.math.BigInteger;

public class TestMD5 {
    public static String generarMD5(String cadena) {
        try {
            MessageDigest md = MessageDigest.getInstance("MD5");
            byte[]     bytes = md.digest(cadena.getBytes());
            BigInteger     x = new BigInteger(1,bytes);
            String respuesta = x.toString(16);
            while(respuesta.length()<16) respuesta="0"+respuesta;
            return respuesta;
        }
        catch(NoSuchAlgorithmException x) {
            return null;
        }
    }
}

El método generarMD5 recibe la cadena de caracteres para la cual se va a generar el código MD5 y retorna el código generado. En caso de que dicho código tenga menos de 16 caracteres se completa con ceros a la izquierda.

Multiprocesamiento recursivo en JAVA 7

Una de las estrategias de diseño de algoritmos más comunes es la de "divide y vencerás", en la cual, un problema de tamaño relativ...