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 a_n, a_n-1, a_n-2,..., a₁,a₀ e um número real x, compute o valor do polinômio

P_n(x) = a_n xⁿ +a_n-1 x^n-1 +a_n-2 x^n-2+…+ a₁ x+a₀

Hipótese de indução

Dados uma sequencia de números reais an−1, . . . , a1, a0, e um número real x, sabemos calcular o valor de

P_n-1(x) = a_n-1 x^n-1 +a_n-2 x^n-2+…+ a₁ x+a₀

Base de indução

P₀(x) = a₀ 

Passo de indução

P_n(x) = a_n xⁿ + P_n-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 an−1, . . . , a1, a0, e um número real x, sabemos calcular o valor de

P_n-1(x) = a_n-1 x^n-1 +a_n-2 x^n-2+…+ a₁ x+a_{0 e} x^n-1

Base de indução

P₀(x) = a₀ 

Passo de indução

P_n(x) = a_n*x*x^n-1 + P_n-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,an−1, . . . , a1, e um número real x, sabemos calcular o valor de

P'_n-1(x) = a_n x^n-1 +a_n-1 x^n-1+…+ a₂ x+a₁ 

Base de indução

P₀(x) =  a_n

Passo de indução

P_n(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]*x² + a[n-1]x + a[n-2]

p[3] = a[n]*x³ + a[n-1]x² + a[n-2]x + a[n-3]

...

p[n] = a[n]*xⁿ + a[n-1]x^n-1 + a[n-2]x^n-2 + ...+a[1]x+a[0]

O algoritmo também pode ser descrito também pela seguinte expressão:

a[n]*xⁿ + a[n-1]x^n-1 + a[n-2]x^n-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