Dica para os desenvolvedores de software: Onde encontrar algoritmos consagrados?

aLGORITMOS_cAPA

Introdução

Quem desenvolve programas para microprocessadores ou sistemas embarcados, especialmente os programas que envolvem a solução de problemas técnicos e científicos, muitas vezes se depara com o desafio de traduzir as regras e fórmulas da solução para algoritmos computacionais. Não tenho a menor dúvida de que qualquer programador experiente acabará encontrando um caminho, projetará os algoritmos e os fará funcionar corretamente. Muitas vezes, porém, esses algoritmos podem não ser muito eficientes e demandam muito tempo para executar as suas tarefas, ou então o código acaba ficando muito extenso. Em outras palavras, os algoritmos funcionam, mas são ineficientes. O tempo de execução ou o tamanho de um programa podem ser fatores determinantes para o sucesso (ou insucesso) de um projeto.

 

Alguns exemplos reais

Vou citar aqui alguns exemplos tirados de minha experiência profissional, para ilustrar como esse problema pode ser comum: Filtragem digital de arquivos de voz

Um dos projetos em que trabalhei tinha como requisito realizar uma filtragem digital offline de arquivos de voz, antes de embarcá-los no sistema eletrônico. Após testarmos várias configurações de filtros e criarmos involuntariamente efeitos especiais nos arquivos de voz (apelidamos esse trabalho de criação de “defeitos especiais”), finalmente encontramos uma configuração adequada à nossa necessidade. Mas tinha um problema… A operação para filtrar uns 10 minutos de arquivos de voz, demorava muitas e muitas horas para ser realizada. Filtrar todo o banco de frases então, levaria semanas!

Sistema leitor automático de placas de veículos

Meus colegas desenvolveram um sistema computacional para leitura e reconhecimento de placas de automóveis. O sistema capturava a imagem, iniciava o processamento digital dessa imagem e levava 15 minutos para reconhecê-la.

As soluções acima funcionaram perfeitamente, mas a demora na execução inviabilizava o projeto. As situações relatadas foram resolvidas com a utilização dos recursos de programação, que serão abordados a seguir.

 

Um pouco de história

O problema de se encontrar ou desenvolver algoritmos computacionais não é novo. Já atormentava os programadores de computadores desde as primeiras versões dessas máquinas. Para nossa sorte, nessas horas sempre aparece uma pessoa iluminada que facilita o nosso trabalho com o seu trabalho genial. Nesse caso estou falando de um sujeito chamado Donald Ervin Knuth. Ele nasceu em Milwaukee no ano de 1938 e lecionou na Universidade de Stanford  de 1968 até 1992, quando se aposentou. A seguir uma breve biografia desse gênio, extraída da Wikipedia:

Nascido no Wisconsin, graduou-se em 1960. Em 1963 obteve o doutorado no Instituto de Tecnologia da Califórnia (Caltech), onde tornou-se professor e começou a trabalhar no livro The Art of Computer Programming, originalmente planejado como uma série de sete livros. O primeiro volume foi publicado em 1968. Neste mesmo ano transferiu-se para a Universidade de Stanford. Em 1974 ganhou o Prêmio Turing.

Em 1976, após produzir o terceiro volume de sua série, ficou tão frustrado com o estado antiquado das ferramentas de publicação que dedicou seu tempo à criação de algo melhor. De seus esforços sugiram as ferramentas TEX e METAFONT.

Em reconhecimento às suas contribuições à ciência da computação ele foi agraciado em 1990 com o singular título de Professor of the Art of Computer Programming, que depois foi atualizado para Professor Emeritus of the Art of Computer Programming.

Em 1992 tornou-se um associado da Academia Francesa de Ciências. Neste mesmo ano aposentou-se da universidade para concluir The Art of Computer Programming. Em 2003 foi eleito como Fellow da Royal Society. Em 2004 os primeiros três volumes de seu livro foram re-editados. Atualmente Knuth está trabalhando no quarto volume e trechos são liberados periodicamente em seu site pessoal.

Como você já percebeu, a obra desse gênio são as publicações The Art of Computer Programming. São livros de leitura obrigatória ou pelo menos para se ter de cabeceira para consulta, quando necessário. O incrível é que não é fácil comprar esses livros no Brasil. Eles são importados.

Para conhecer melhor o conteúdo desses livros, “clicke” nas figuras ou nos links abaixo.

 Knuth_vol_01a  Knuth_vol_02a  Knuth_vol_03a  Knuth_vol_04aa

.

Esses livros são muito técnicos. São feitas análises matemáticas detalhadas sobre os diversos problemas a serem solucionados e mostrados os algoritmos mais adequados para isso. Nos primeiros volumes, alguns exemplos de código para os algoritmos estão escritos em linguagem assembly. Não é uma leitura fácil. Por outro lado, a maioria dos algoritmos desenvolvidos nesses livros são considerados referências e continuam atuais.

Outra obra de referência obrigatória é a obra que será apresentada a seguir. Nela são apresentados os algoritmos de forma simples e direta e de quebra são fornecidos, em CD-ROM ou em formato digital para baixar direto da internet, os códigos fonte da implementação desses algoritmos em diversas linguagens de programação.

.

 NUMERICAL RECIPIES

Numerical Recipies  –  The Art of Scientific Computing é uma publicação da Universidade de Cambridge. A primeira edição data de 1985. São coletâneas de algoritmos consagrados com as implementações em diversas linguagens:  PASCAL, FORTRAN, C/C++, BASIC, LISP, MODULA 2, etc. As edições anteriores do  livro estão disponíveis para consulta online gratuita. “Clicke na figura abaixo para acessá-las.

Numerical_1

.

Essa publicação encontra-se na terceira edição: Numerical Recipes 3rd Edition (2007). Se acaso você resolver comprar essa obra, não se esqueça de comprar também os códigos em CD (ou em formato digital para baixar direto da internet), que são vendidos separadamente. Essa obra também é difícil de ser encontrada no Brasil.

  NumericalBook

 .

Exemplos de algoritmos

Uma necessidade muito comum em programação é a de se ordenar números em sequências crescentes ou decrescentes. Um algoritmo bastante simples e interativo, que aprendi na faculdade, é o algoritmo conhecido como Bubble Algorithm, ou “algoritmo da bolha”Na Figura 1 pode-se ver um exemplo desse algoritmo. Utilizei esse algoritmo para ordenar os números sorteados no meu programa infalível para acertar os números da Mega Sena. Obviamente esse programa ainda não funciona direito…

==================================================

// Algorítmo da bolha - Coloca 6 números em ordem crescente

bTrocou = true;

while (bTrocou == true)
{
  bTrocou = false;

  for (int nIndice = 0; nIndice < 5; nIndice++)
  {
     // Verifica se na ordem correta

     if (nMatrizAuxiliar[nIndice] > nMatrizAuxiliar[nIndice + 1])
     {
        // Troca de posição

        nVarAux = nMatrizAuxiliar[nIndice];
        nMatrizAuxiliar[nIndice] = nMatrizAuxiliar[nIndice + 1];
        nMatrizAuxiliar[nIndice + 1] = nVarAux;
        bTrocou = true;
     }
   }
}
=======================================================================

 Figura 1: Exemplo da implementação do “algoritmo da bolha”

Quando fui pesquisar o “algoritmo da bolha” no livro Numerical Recipies para escrever esse artigo, deparei, para minha surpresa, com a opinião negativa dos autores do livro a respeito desse algoritmo. Segundo eles, o algoritmo acima é apontado como um dos mais ineficientes que existem. Na opinião dos autores:

If you know what bubble sort is, wipe it from your mind; if you don’t know, make a point of never finding out!

Numa tradução livre, as frases acima dizem o seguinte: “Se você sabe o que é uma ordenação do tipo bolha, apague isso de sua mente. Se você não sabe, faça questão de nunca descobrir!”

Bem… tudo depende da aplicação. Nesse capítulo do livro é mostrado que o uso de recursos computacionais cresce exponencialmente na potência de 2, conforme cresce o número N de itens a serem ordenados. Na Figura 2,  pode-se ver um exemplo do algoritmo de ordenação crescente chamado de algoritmo de inserção direta (Straight Insertion), tirado do livro, que pode ser utilizado para N < 20.

=======================================================================
#include "nr.h"

void NR::piksrt(Vec_IO_DP &arr)
{
	int i,j;
	DP a;

	int n=arr.size();
	for (j=1;j<n;j++) {
		a=arr[j];
		i=j;
		while (i > 0 && arr[i-1] > a) {
			arr[i]=arr[i-1];
			i--;
		}
		arr[i]=a;
	}
}
=========================================================================

Figura 2: Algoritmo Straight Insertion

Para outras aplicações específicas, você encontrará outras referências importantes. Quando o assunto é processamento digital de sinais, por exemplo, uma referência essencial é o livro:

  • DFT/FFT and Convolution Algorithms – Theory and Implementation – C.S. Burrus and T.W. Parks (1984)

.

Esses livros e recursos deveriam estar nas prateleiras de todos os desenvolvedores de software. Você conhece mais alguma referência interessante? Deixe aqui o seu comentário.

==============

Henrique

consulte sempre um engenheiro eletrônico

 

Licença Creative Commons Esta obra, “Dica para os desenvolvedores de software: Onde encontrar algoritmos consagrados?“, de Henrique Frank W. Puhlmann, foi licenciada sob uma Licença Creative Commons Atribuição-NãoComercial-CompartilhaIgual 3.0 Não Adaptada.

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google

Você está comentando utilizando sua conta Google. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s