Material didático para princípios de desenvolvimento de Algoritmos

Já o segundo diz respeito ao tempo para computar a resposta, é preciso que ele factível, quer dizer que ao obter a resposta, essa ainda seja útil. Por exemplo, em um grande aeroporto, em determinado período, deve-se obter a escala de decolagens e aterrissagens muito rapidamente, antes que acabe o combustível de alguma aeronave em sobrevoo.

Como discutido na seção sobre ponto flutuante, o problema de precisão numérica inicia-se na impossibilidade de representar valores irracionais e mesmo dizimas periódicas são trucadas. Mas existe outra questão que é a eficiência do algoritmo utilizado para o cômputo. Um exemplo simples é acumlar valores que cresce muito rapidamente (como exponenciais ou fatoriais) ou valores que aproximam-se se zero.

Como citado acima, um problema computacional é conseguir implementar funções que não podem ser escritas a partir de operações elementares de soma e multiplicação, com a função cosseno (que por isso é transcendental). Hoje, este não parece ser um problema, pois qualquer computador de bolso tem uma calculadora implementada capaz de devolver não apenas o valor de conssenos, mas de várias outras funções transcendentais. Verdade, mas isso só é possível por implementarem algum algoritmo eficiente (a partir de somas e multiplicações) para devolver o valor da função!

Existem problemas que sabidamente são intratáveis no sentido de sabermos matematicamente que não existe possibilidade de alguém encontrar um algoritmo que consegue resolvê-lo (como o problema da parada: não existe algoritmo que possa decidir se um algoritmo qualquer pára ou não após um tempo finito de execução).

Existem outros tipos de problemas que podem ser resolvidos computacionalmente, mas cuja solução conhecida é tremendamente ineficiente. Um bom exemplo é o problema da satisfatibilidade: encontrar um valores para variáveis booleanas que torna a expressão lógica verdadeira,como em f(b₁, b₂, b₃) = b₁ E (b₂ OU não b₃). Neste caso, por ser uma instância pequena do problema é fácil, senda a resposta sim, basta tomar b₁ e b₂ como verdadeiro (não importando o se b₃ seja verdadeiro ou falso).

Na seção seguinte examinaremos um particular problema, conseguir um valor aproximado para a função trigonométrica cosseno, exploranto tanto a questão da eficiência numérica (precisão) quanto a de tempo de execução (velocidade).

Um bom exemplo é o cômputo da função cosseno próximo do valor nulo, via truncamento de uma série de Taylor (ou mais geralmente de MacLaurin), ou seja, dada uma função f encontrar uma aproximação sua, em um ponto x próximo da origem, a partir de um polinômio aproximador p cuja propriedade é que as funções coincidam no ponto x (próximo da origem) e suas derivadas idem: f(x)=p(x), f'(x)=p'(x), f''(x)=p''(x),...

Em particular para a função cosseno, escrevendo o polinômio candidato p(y) = a₀ x⁰ + a₁ x¹ + a₂ x² +... e estabelecendo as identidades em x, obtemos o seguinte polinômio aproximador: cos(x) = 1 - x /2! + x /4! - x /6! + x /8! + ...

A partir da série de Taylor para o cosseno, percebe-se que pode-se elaborar um laço que a cada passo computa um dos termos da série, primeiro 1=x^0/0!, depois x^2/2! e assim por diante.

Desse modo uma primeira solução, seria implementar duas funçòes auxiliares, uma para computar a potência (pot) e uma para o fatorial (fat), a cada passo invocando as funções auxiliares.

while (alguma_condicao) {
     soma = soma + pot(-1, 2*i) * pot(x, 2*i) / fat(2*i);
     i += 2;
     sinal = -sinal;
     }

while (alguma_condicao) :
     soma = soma + pot(-1, 2*i) * pot(x, 2*i) / fat(2*i);
     i += 2;
     sinal = -sinal;
     
  return soma;

Ineficiência 2. Note que a mesma ineficiência do sinal ocorre com pot e fat, pois a cada passo ignora-se que uma potência e um fatorial parcial já foi computado e faz-se novamente todos os passos. Se ainda não está clara a ineficiência, vajamos um passo i=2: nele computa-se pot(x, 2*2)=pot(x, 4) e fat(2*2)=fat(4); e no passo seguinte, i=3 computa-se pot(x, 2*3)=pot(x, 6) e fat(2*3)=fat(6). Mas no passo anterior tinhamos os valores para 6, então, supondo a existência das variáveis pot1=pot(x, 6) e fat1=fat(6), bastaria fazer: pot1 = pot * x * x e fat1 = fat1 * 7 * 8, equivalendo respectivamente a pot * x * x = pot(x, 6) * x * x = pot(x, 8) e fat1 * 7 * 8 = fat(6) * 7 * 8 = fat(8).

Outro problema desta solução 1 é que potência e fatorial crescem muito rápido (se x > 1, então decai muito rápido). Isso também pode resultar ineficiência numérica.

Portanto, esta solução 1 é muito ineficaz, sendo assim bastante "ingênua". A discussão da razão de sua ineficácia já indica um caminho de melhoria, examinado a seguir.

Uma solução um pouco melhor, mas numericamente ainda ingênua, seria eliminar a grande ineficiência citada acima, a cada passo aproveitando a potência e o fatorial anterior. Usando como critério de parada que as diferenças entre o cômputo do termo da série seja menor que um dado limiar Lim, o código pode ficar como o mostrado abaixo. Suporemos a existëncia de uma função que devolve o módulo de um valor "flutuante", de nome valor_absoluto:

float cossInef (float x) {
  float pot = 1, soma = 0;
  float termo0 = 2, termo = 1;
  int fat = 1, i = 1, sinal = 1;
  while (valor_absoluto(termo0-termo)>Lim) {
     soma = soma + termo;
     pot *= x * x; // compute potencia 2i de x
     fat *= (i+1) * (i+2); // compute fatorial de 2i
     termo0 = termo;
     termo = sinal * pot / fat;
     i += 2;
     sinal = -sinal;
     }
  return soma;
  }

def cossInef (x) :
  pot = 1; soma = 0;
  termo0 = 2; termo = 1;
  fat = 1; i = 0; sinal = 1;
  while (valor_absoluto(termo0-termo)>Lim) :
     soma = soma + termo;
     pot *= x * x; # compute potencia 2i de x
     fat *= (i+1) * (i+2); # compute fatorial de 2i
     termo0 = termo;
     termo = sinal * pot / fat;
     i += 2;
     sinal = -sinal;
  return soma;

Rodando este algoritmo e comparando-o com a implementação interna das linguagens C e Python, mesmo para valores próximos de zero (como 0.1) nota-se uma diferença significativa de 0.01 (veja a tabela abaixo onde comparamos o algoritmo acima, sua versão mais eficiente e a implementação interna da linguagem). Isso indica que o método acima não é eficiente.

Analisando-se o algoritmo, percebe-se que o potencial problema é que a variável termo é resultado da divisão de 2 valores que tem tem potencial de crescimento enorme (as variáveis pot e fat - com valor x próximo de zero, pot na verdade aproxima-se muito rápido é do zero). Outra observação importante: a diferença entre 2 passos no laço para a variável termo é multiplicar por x * x / (i+1)*(i+2). Assim, poderia-se tentar a cada passo multiplicar diretamente por esta "diferença" e não acumular a potência e o fatorial!

Usando esta ideia produz-se o algoritmo seguinte que é bem mais eficiente. Nele aproveitamos para ilustrar o uso de medição de tempo de execução tanto em C quanto em Python,

// Leo^nidas O. Brandao - 2017/06/19
// cos(x) = 0! x^0 - x^2 /2! + x^4 /4! - x^6 /6! + x^8 /8! + ...
//        = 1 - x /2! + x /4! - x /6! + x /8! + ...
// gcc -lm -o introducao_eficiencia_algoritmos_cosseno introducao_eficiencia_algoritmos_cosseno.c

#include <stdio.h>
#include <math.h> // cos(x)
#include <time.h> // clock_t, clock()

#define Lim 0.001

float valor_absoluto (float x) {
  if (x>=0) return x;
  return -x;
  }

// Cosseno implementado de modo ineficiente
float cossInef (float x) { ... } // copiar aqui o codigo C do ineficiente acima

// Cosseno implementado de modo mais eficiente
float cossEfic (float x) {
  float pot = 1, soma = 0;
  float termo0 = 2, termo = 1;
  int i = 0, sinal = 1;
  while (valor_absoluto(termo0-termo)>Lim) {
     soma = soma + termo;
     termo0 = termo;
     termo *= -1 * x * x / ((i+1) * (i+2)); // compute potencia 2i de x e fatorial de 2i
     i += 2;
     }
  return soma;
  }

int main (void) {
  float x, cosx, auxcI, auxcE;
  int i;
  clock_t tempo_inicial = clock(); // "dispara o cronometro"...
  printf("    x | ineficiente | eficiente | math cos(x) | dist inef. | dist efic.\n");
  x = 0.0;
  for (i=0; i<10; i++) {
    cosx = cos(x);
    auxcI = cossInef(x);
    auxcE = cossEfic(x);
    printf(" %3.2f | %11.4f | %9.4f | %11.4f | %10.4f | %10.4f\n",
           x, auxcI, auxcE, cosx, valor_absoluto(auxcI-cosx), valor_absoluto(auxcE-cosx));
    x += 0.05;
    }
  clock_t tempo_final = clock();
  printf("Tempo em segundos: %f\n", (double)(tempo_final - tempo_inicial) / CLOCKS_PER_SEC);

  return 1;
  }

# Leo^nidas O. Brandao - 2017/06/19
# cos(x) = 0! x^0 - x^2 /2! + x^4 /4! - x^6 /6! + x^8 /8! + ...
#        = 1 - x /2! + x /4! - x /6! + x /8! + ...

# Invocar execucao com linha de comando: python introducao_eficiencia_algoritmos_cosseno.py

import math; # para cos(x)
import time; # para tempo 'time.time()'

Lim = 0.001

def valor_absoluto (x) :
  if (x>=0) : return x;
  return -x;

# Cosseno implementado de modo mais eficiente		
def cossInef (x) : # Copiar aqui a implementacao de cosseno ineficiente
  ...
		
# Cosseno implementado de modo mais eficiente
def cossEfic (x) :
  pot = 1; soma = 0;
  termo0 = 2; termo = 1;
  i = 0; sinal = 1;
  while (valor_absoluto(termo0-termo)>Lim) :
     soma = soma + termo;
     termo0 = termo;
     termo *= -1 * x * x / ((i+1) * (i+2)); # compute potencia 2i de x e fatorial de 2i
     i += 2;
  return soma;

def main () :
  tempo_inicial = time.time(); # "dispara o cronometro"...
  print("    x | ineficiente | eficiente | math cos(x) | dist inef. | dist efic.");
  x = 0.0;
  for i in range(0, 10) :
    cosx = math.cos(x);
    auxcI = cossInef(x);
    auxcE = cossEfic(x);
    print(" %3.2f | %11.4f | %9.4f | %11.4f | %10.4f | %10.4f" %
         ( x, auxcI, auxcE, cosx, valor_absoluto(auxcI-cosx), valor_absoluto(auxcE-cosx) ));
    x += 0.05;

  tempo_final = time.time();
  print("Tempo em segundos: %f\n" % (tempo_final - tempo_inicial));

main();

Experimente rodar em sua máquina o código acima (completanto com o código da função cossInef). Em minha máquina, tanto rodando C quanto Python produzem como resultado a tabela abaixo. Note que a medida que o x se afasta da origem, aparece mais erro, entretanto os erros são consistentemente maiores ao usar a implementação ingênua.

    x | ineficiente | eficiente | math cos(x) | dist inef. | dist efic.
 0.00 |      1.0000 |    1.0000 |      1.0000 |     0.0000 |     0.0000
 0.05 |      1.0012 |    0.9988 |      0.9988 |     0.0025 |     0.0000
 0.10 |      1.0050 |    0.9950 |      0.9950 |     0.0100 |     0.0000
 0.15 |      1.0112 |    0.9888 |      0.9888 |     0.0225 |     0.0000
 0.20 |      1.0199 |    0.9801 |      0.9801 |     0.0399 |     0.0000
 0.25 |      1.0311 |    0.9689 |      0.9689 |     0.0622 |     0.0000
 0.30 |      1.0447 |    0.9553 |      0.9553 |     0.0893 |     0.0000
 0.35 |      1.0606 |    0.9394 |      0.9394 |     0.1213 |     0.0000
 0.40 |      1.0789 |    0.9211 |      0.9211 |     0.1579 |     0.0000
 0.45 |      1.0996 |    0.9004 |      0.9004 |     0.1991 |     0.0000

Mas o tempo de execução é significativamente menor utilizando uma linguagem compilada com C. Na mesma máquina (um PC com 2 processadores AMD Phenom II rodando Linux/Debian 8.8), os resultados de tempo de execução para o executável (vindo de C) e interpretado Python foram respectivamente:

Tempo em segundos: 0.000079
Tempo em segundos: 0.000220

Leônidas de Oliveira Brandão
http://line.ime.usp.br