Genetic Algorithm (explained in 4 minutes)

Desenvolvimento de Algoritmos

(1) Dado um problema, como encontramos um algoritmo eficiente para sua solução?

(2) Encontrado um algoritmo, como comparar este algoritmo com outros algoritmos que solucionam o mesmo problema?

(3) Como deveríamos julgar a qualidade de um algoritmo?

(4) Qual é o algoritmo de menor custo possível para resolver um problema particular?

Questões desta natureza são de interesse para programadores e cientistas da computação. Algoritmos podem ser avaliados por uma variedade de critérios. Na maioria das vezes estamos interessados na taxa de crescimento do tempo ou de espaço necessário para a solução de grandes problemas.

Uma maneira de comparar algortimos é por meio da notação O. Abaixo temos uma tabela com os comportamentos mais comuns relacionados ao tempo para execução de um algoritimo.

Tabela 1- Comportamentos comuns em consumo de tempo

Função	Significado ( tamanho da entrada = n)
1	tempo constante – o número de operações é o mesmo para qualquer tamanho da entrada
n	tempo linear – se n dobra, o número de operações também dobra
n2	tempo quadrático – se n dobra, o número de operações quadruplica
log n	tempo logarítmico – se n dobra, o número de operações aumenta de uma constante
nlog n	tempo n log n - se n dobra, o número de operações ultrapassa o dobro do tempo da entrada de tamanho n
2n	tempo exponencial - se n dobra, o número de operações é elevado ao quadrado

Algumas expressões de O são tão freqüentes que receberam denominações próprias:

Tabela 2- Algumas expressões de O

Expressão	Nome
O(1)	Constante
O(log n)	Logarítmica
O(log2n)	Log quadrado
O(n)	Linear
O(nlog n)	n log n
O(n2)	Quadrática
O(n3)	Cúbica
O(2n)	Exponencial

A Figura 1 mostra esse comportamento de maneira gráfica.

Figura 1 - Represetação gráfica da Tabela 1

MaiorNumeroPrimoTestCase

public class MaiorNumeroPrimoTestCase {

public static void main(String[] args) {

int i = 1;

while (i < 100) {

int k = 0;

for (int j = 1; j <= i; j++) {

if ((i % j) == 0) {

k++;

}

}

if (k == 2) {

System.out.println(i);

}

i++;

}

}

}

InputStream to String

private static String convertStreamToString(

InputStream is) throws IOException {
        /*
         * To convert the InputStream to String we use the Reader.read(char[]
         * buffer) method. We iterate until the Reader return -1 which means
         * there's no more data to read. We use the StringWriter class to
         * produce the string.
         */
        if (is != null) {
            Writer writer = new StringWriter();

            char[] buffer = new char[1024];
            try {
                Reader reader = new BufferedReader(new InputStreamReader(is,
                        "UTF-8"));
                int n;
                while ((n = reader.read(buffer)) != -1) {
                    writer.write(buffer, 0, n);
                }
            } finally {
                is.close();
            }
            return writer.toString();
        } else {
            return "";
        }
    }

Insertion Sort

import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class AlgorithmTestCase {

        protected Logger logger = LoggerFactory.getLogger(getClass());

        @Test
        public void insertionSortTest() {
                final int[] array = { -9, 9, 8, 7, 6, 5, 4, -8, 3, 2, 1, 0, 8945121 };

                int[] order = insertionAscSort(array);
                show(order);

                final int[] desc = insertionDescSort(array);
                show(desc);
        }

        private final int[] insertionAscSort(int[] array) {

                int i, j, elemento;

                for (i = 1; i < array.length; i++) {

                        elemento = array[i];

                        for (j = i - 1; j >= 0 && array[j] > elemento; j--) {
                                array[j + 1] = array[j];
                                array[j] = elemento;
                        }

                }

                return array;
        }

        private final int[] insertionDescSort(int[] array) {

                int i, j, elemento;

                for (i = 1; i < array.length; i++) {

                        elemento = array[i];

                        for (j = i - 1; j >= 0 && array[j] < elemento; j--) {
                                array[j + 1] = array[j];
                                array[j] = elemento;
                        }

                }

                return array;
        }

        private final void show(int[] array) {
                logger.info("Result");
                for (int i = 0; i < array.length; i++) {
                        logger.info("Array: " + array[i]);
                }
        }

}

Quick Sort By James Gosling

 /*
 * @(#)QSortAlgorithm.java    1.6f 95/01/31 James Gosling
 *
 * Copyright (c) 1994-1995 Sun Microsystems, Inc. All Rights Reserved.
 *
 * Permission to use, copy, modify, and distribute this software
 * and its documentation for NON-COMMERCIAL or COMMERCIAL purposes and
 * without fee is hereby granted.
 * Please refer to the file http://java.sun.com/copy_trademarks.html
 * for further important copyright and trademark information and to
 * http://java.sun.com/licensing.html for further important licensing
 * information for the Java (tm) Technology.
 *
 * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
 * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
 * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
 * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
 * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
 * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
 *
 * THIS SOFTWARE IS NOT DESIGNED OR INTENDED FOR USE OR RESALE AS ON-LINE
 * CONTROL EQUIPMENT IN HAZARDOUS ENVIRONMENTS REQUIRING FAIL-SAFE
 * PERFORMANCE, SUCH AS IN THE OPERATION OF NUCLEAR FACILITIES, AIRCRAFT
 * NAVIGATION OR COMMUNICATION SYSTEMS, AIR TRAFFIC CONTROL, DIRECT LIFE
 * SUPPORT MACHINES, OR WEAPONS SYSTEMS, IN WHICH THE FAILURE OF THE
 * SOFTWARE COULD LEAD DIRECTLY TO DEATH, PERSONAL INJURY, OR SEVERE
 * PHYSICAL OR ENVIRONMENTAL DAMAGE ("HIGH RISK ACTIVITIES").  SUN
 * SPECIFICALLY DISCLAIMS ANY EXPRESS OR IMPLIED WARRANTY OF FITNESS FOR
 * HIGH RISK ACTIVITIES.
 */

/**
 * A quick sort demonstration algorithm
 * SortAlgorithm.java, Thu Oct 27 10:32:35 1994
 *
 * @author James Gosling
 * @version     1.6f, 31 Jan 1995
 */
/**
 * 19 Feb 1996: Fixed to avoid infinite loop discoved by Paul Haeberli.
 *              Misbehaviour expressed when the pivot element was not unique.
 *              -Jason Harrison
 *
 * 21 Jun 1996: Modified code based on comments from Paul Haeberli, and
 *              Peter Schweizer (Peter.Schweizer@mni.fh-giessen.de).
 *              Used Daeron Meyer's (daeron@geom.umn.edu) code for the
 *              new pivoting code. - Jason Harrison
 *
 * 09 Jan 1998: Another set of bug fixes by Thomas Everth (everth@wave.co.nz)
 *              and John Brzustowski (jbrzusto@gpu.srv.ualberta.ca).
 */

class QSortAlgorithm extends SortAlgorithm {
    void sort(int a[], int lo0, int hi0) throws Exception {
    int lo = lo0;
    int hi = hi0;
    pause(lo, hi);
    if (lo >= hi) {
        return;
    }
        else if( lo == hi - 1 ) {
            /*
             *  sort a two element list by swapping if necessary
             */
            if (a[lo] > a[hi]) {
                int T = a[lo];
                a[lo] = a[hi];
                a[hi] = T;
            }
            return;
    }


        /*
         *  Pick a pivot and move it out of the way
         */
    int pivot = a[(lo + hi) / 2];
        a[(lo + hi) / 2] = a[hi];
        a[hi] = pivot;

        while( lo < hi ) {
            /*
             *  Search forward from a[lo] until an element is found that
             *  is greater than the pivot or lo >= hi
             */
            while (a[lo] <= pivot && lo < hi) {
        lo++;
        }

            /*
             *  Search backward from a[hi] until element is found that
             *  is less than the pivot, or lo >= hi
             */
        while (pivot <= a[hi] && lo < hi ) {
        hi--;
        }

            /*
             *  Swap elements a[lo] and a[hi]
             */
            if( lo < hi ) {
                int T = a[lo];
                a[lo] = a[hi];
                a[hi] = T;
                pause();
            }

        if (stopRequested) {
                return;
            }
    }

        /*
         *  Put the median in the "center" of the list
         */
        a[hi0] = a[hi];
        a[hi] = pivot;

        /*
         *  Recursive calls, elements a[lo0] to a[lo-1] are less than or
         *  equal to pivot, elements a[hi+1] to a[hi0] are greater than
         *  pivot.
         */
    sort(a, lo0, lo-1);
    sort(a, hi+1, hi0);
    }

    void sort(int a[]) throws Exception {
    sort(a, 0, a.length-1);
    }
}