segunda-feira, 19 de março de 2012

Projeto de algoritmos usando indução

No artigo [1], o autor apresenta uma metodologia elegante para o projeto de algoritmos baseada na indução matemática. O coração dessa metodologia está assentada na analogia entre o processo de provar um teorema e o processo de construção de um algoritmo.

A indução é uma poderosa técnica de prova que permite estender soluções de subproblemas menores para subproblemas maiores. 

O benefício imediato dessa metodologia de construção de algoritmos é que a corretude do algoritmo é obtida diretamente.

Problema 1
Dada uma sequência de números reais an, an-1, an-2,..., a1,a0 e um número real x, compute o valor do polinômio
Pn(x) = an xn +an-1 xn-1 +an-2 xn-2+…+ a1 x+a0
Hipótese de indução
Dados uma sequencia de números reais an1, . . . , a1, a0, e um número real x, sabemos calcular o valor de
Pn-1(x) = an-1 xn-1 +an-2 xn-2+…+ a1 x+a0
Base de indução
P0(x) = a0 
Passo de indução
Pn(x) = an xn + Pn-1(x)
Algoritmo

p[0] = a[0];
for(i=1;i<=n;i++){
  xi = 1;
  for(j=1;j<=i;j++){
    xi = xi*x; 
  }
  p[i] = a[i]*xi + p[i-1];
}
printf("O resultado %lf\n",p[n]);

Este algoritmo realiza (n(n+1))/2 multiplicações e n adições. Vamos fortalecer a nossa hipótese de indução para reduzir o número de multiplicações realizadas.
Hipótese de indução
Dados uma sequencia de números reais an1, . . . , a1, a0, e um número real x, sabemos calcular o valor de
Pn-1(x) = an-1 xn-1 +an-2 xn-2+…+ a1 x+a0 e xn-1
Base de indução
P0(x) = a0 
Passo de indução
Pn(x) = an*x*xn-1 + Pn-1(x)
Algoritmo 
p[0] = a[0];
xi = 1;
for(i=1;i<=n;i++){
  xi = xi*x;
  p[i] = a[i]*xi + p[i-1];
}
printf("O resultado %lf\n",p[n]);
Este novo algoritmo realiza 2n multiplicações e n adições. Podemos alterar a nossa hipótese de indução para garantir um resultado ainda melhor.
Hipótese de indução
Dados uma sequencia de números reais an,an1, . . . , a1, e um número real x, sabemos calcular o valor de
P'n-1(x) = an xn-1 +an-1 xn-1+…+ a2 x+a
Base de indução
P0(x) =  an
Passo de indução
Pn(x) =  x*P'n-1(x) + a0
Algoritmo
p[0] = a[n];
for(i=1;i<=n;i++){
  p[i]=x*p[i-1]+a[n-i];
} 
O cálculo do valor do polinômio pode ser descrito da seguinte maneira: 
p[0] = a[n]
p[1] = a[n]*x  + a[n-1]
p[2] = a[n]*x2 + a[n-1]x + a[n-2]
p[3] = a[n]*x3 + a[n-1]x2 + a[n-2]x + a[n-3]
...
p[n] = a[n]*xn + a[n-1]xn-1 + a[n-2]xn-2 + ...+a[1]x+a[0]
O algoritmo também pode ser descrito também pela seguinte expressão:
a[n]*xn + a[n-1]xn-1 + a[n-2]xn-2 + ...+a[1]x+a[0]
=((((((a[n]*x + a[n-1])*x + a[n-2])x + a[n-3])...)x+a[1])x +a[0])
Este algoritmo é conhecido como regra de Horner.
Neste algoritmo consideramos a entrada da esquerda para a direita 
em vez do usual da direita para a esquerda. 
Este algoritmo realiza n multiplicações e n adições. 
Aplicações 


Converter uma string em um inteiro:
char buffer[20];
int r;
scanf("%s",buffer);
r=0;
for(i=0;i<strlen(buffer);i++)
  r = r*10 + buffer[i]-'0';
Referências:
[1] Udi Manber: Using Induction to Design Algorithms. Commun. ACM 31
Você gostará de ver:
Projeto de algoritmos por indução

Nenhum comentário: