terça-feira, 29 de outubro de 2013

Cálculo de Sequências de Polinômios

Resumo

O problema "Palácio dos Espelhos" deseja encontrar uma solução algorítmica para calcular as possibilidades de caminhos que um raio de luz pode percorrer de acordo com um número variado de k reflexões em n placas de vidros. O estudo realizou diversas simulações e apresenta uma abordagem que utiliza o cálculo de seqüências de polinômios.

Introdução

O problema "Palácio dos Espelhos" deseja encontrar uma solução a qual se origina em uma situação física. Se colocarmos várias placas de vidro umas sobre as outras, conforme exibição na Figura 1 (que contém 3 placas de vidro), os raios de luz terão múltiplos caminhos, originados pelas reflexões entre as placas. Os raios poderão ter um número variado de reflexões, entre zero e ∞. Na figura 1 são ilustrados alguns desses caminhos.
Figura 1 – Simulação de algumas reflexões usando 3 placas de vidro.

O objetivo deste trabalho é apresentar uma proposta de solução algorítmica para determinar de quantas formas um raio de luz poderá sofrer k reflexões em uma pilha de n placas de vidro. O estudo realizou simulações para reconhecer um padrão e em seguida apresentou os valores para 1, 2 e 3 placas, após generalizou a solução para  combinações de n números de placas e k reflexões. Apresentando o resultado no final deste trabalho para uma simulação feita com 16 placas de vidros e 16 reflexões.

O trabalho apresenta os padrões encontrados, o método de solução proposto e o algoritmo proposto para solução do problema na seção de solução e os resultados encontrados e a conclusão na parte final deste trabalho.

Solução
Reflexões em apenas uma placa terão apenas uma possibilidade, por isso o estudo procurou uma relação de recorrência a partir de duas placas. Após a simulação, foi encontrado o resultado apresentado na Tabela 1.

N Placas
2
2
2
2
2
2
K Reflexões
0
1
2
3
4
5
Possibilidades K
1
2
3
5
8
13
Tabela 1 – Simulação de Reflexões em 2 Placas de Vidro.

Teorema 1 - As possibilidades para k reflexões em duas placas de vidro demonstraram uma cadeia de equações de polinômios, onde o seu crescimento pode ser dado pela seguinte relação de recorrência: Pk = Pk-1 + Pk-2 para todo k maior que 2.

Prova 1 – A possibilidade de 3 reflexões, por exemplo, poderia ser dada pelo seguinte cálculo: se Pk-1 = 3 e PK-2 = 2 então PK = 5, pois 5=3+2, assim sucessivamente para todas as possibilidades de K reflexões, conforme exibição (em negrito) da Tabela 2.

Para todo N = 2 e K menor ou igual a 2, ou ainda um k números de reflexões maior que 2 temos a seguinte relação de recorrência:

CalculeDuasPlacas(k)=<![if !msEquation]><![endif]>

Após encontrar a relação de recorrência, foi desenvolvido o algoritmo para resolver o problema usando duas placas de vidro:

Inteiro CalculeDuasPlacas(int placa, int reflexao)

Se reflexao <= 2 Então
                Retorne  reflexao + 1
Senão 
                Retorne  CalculeDuasPlacas (k-1) + CalculeDuasPlacas (k-2)
Listagem 1 – Algoritmo Desenvolvido para Solução de duas Placas.

O estudo avançou na investigação de uma nova relação de recorrência para 3 placas  e os seus resultados são apresentados na Tabela 2.

N Placas
3
3
3
3
3
3
K Reflexões
0
1
2
3
4
5
Possibilidades K
1
3
6
14
31
70
Tabela 2 – Simulação de Reflexões em 3 Placas de Vidro.

Teorema 2 - As possibilidades para k reflexões em três placas de vidro demonstraram uma nova relação de recorrência, onde o seu crescimento pode ser dado por: Pk = 2 * Pk-1 + Pk-2 – PK-3 para todo k maior que 2.

Prova 2 – Para 3 reflexões, por exemplo, poderia ser feito o seguinte cálculo: se Pk-1 = 6, PK-2 = 3 e PK-1 = 1 então PK = 14, pois 14 = 2*6+3-1, assim sucessivamente para todo cálculo de possibilidades de K, conforme exibição (em negrito) da Tabela 3.

Assim, para todo N = 3 e K reflexões que seja menor ou igual a 2, ou ainda que tenhamos um k maior que 2 existem as seguintes possibilidades:

CalculePlacas(n,k)=<![if !msEquation]><![endif]>
                                                        
Após encontrar a relação de recorrência foi construído o algoritmo para resolver o problema usando 3 placas de vidro:

Inteiro CalculePlacas(int placa, int reflexao)
int k0 = 1 ;            int K1 = n ;            int K2 = 2 * n ;     int possibilidades = 0;

Se (reflexao = 0)
                Retorne 1

Se (reflexao >=1 e reflexao <=2)
                Retorne reflexao * placa
Senão
Para i=3 onde i <= reflexão Faça
                               possibilidades = 2 * k2 + K1 – K0
                               K0 = K1
                               K1 = K2
                               K2 = possibilidades            
                              
                Retorne Numero
Listagem 2 – Algoritmo Desenvolvido para Resolver o Problema com 3 Placas.

Generalização do algoritmo

A partir do padrão encontrado no cálculo das 3 placas de vidro, foi feita uma tentativa de generalização do caso para n placas e k reflexões, porém os valores estavam incorretos de acordo com os casos de teste. Assim, foi necessário realizar uma nova simulação para encontrar um novo padrão de recorrência. Após a simulação, foi percebido que existe uma relação de recorrência diferente, onde uma seqüência de polinômios demonstra uma forma de solução para cada número de placa, conforme exibição da Tabela 3.

Polinômios
Placa
N-1 * K-1
N-2 * K-2
N-2 * K-3


3
N-2 * K-1
N-1 * K-2
N-3 * K-3
N-3 * K-4

4
N-2 * K-1
N-2 * K-2
N-1 * K-3
N-4 * K-4
N-4 * K-5
5
Tabela 3 – Exemplo de Seqüências de polinômios.

Uma nova simulação buscou o número de possibilidades de k reflexões em 4 placas, conforme demonstração apresentada na Tabela 4.

N Placas
4
4
4
4
4
4
K Reflexões
0
1
2
3
4
5
Possibilidades K
1
4
8
27
73
215
                                   Tabela 4 – Simulação de Valores para 4 Placas.

Teorema 3 - A fórmula encontrada para cálculo é uma seqüência de polinômios: (N-2 * Pk-1) + (N-1 * PK-2) – (N-3 * Pk-3) – (N-3 * PK-4). Onde: N-2 = 2; N-1 = 3; K = 3; Pk-1 = 19; Pk-2 = 8; Pk-3 = 4; Pk-4 = 1;.

Prova 3 – Substituindo os valores contidos na Tabela 5, é possível realizar o cálculo com mais facilidade: (2 * 19) + (3 * 8) – (1 * 4) – (1 * 1) = 57.

O caso de generalização buscou uma aproximação com cálculos de seqüências de polinômios, onde a partir de uma configuração de n placas e k reflexões, é encontrada uma relação de recorrência em uma seqüência a ser utilizada para calcular as possibilidades. Para facilitar o entendimento, o algoritmo foi divido em 3 partes: (I) geração da seqüências de placas, (II) geração da seqüência de termos e cada operando dos polinômios e (III) algoritmo principal.

A geração das seqüências de placas encontrou uma padronização de crescimento (Tabela 5), onde existia uma diferença para os números de placas pares e ímpares (vermelho), a forma de crescimento dos elementos à direita (amarelo), à esquerda (azul) e o elemento central que sempre se repete (verde).

N-1
N-2
N-2





3
N-2
N-1
N-3
N-3




4
N-2
N-2
N-1
N-4
N-4



5
N-3
N-2
N-2
N-1
N-5
N-5


6
N-3
N-3
N-2
N-2
N-1
N-6
N-6

7
N-4
N-3
N-3
N-2
N-2
N-1
N-7
N-7
8
Tabela 5 - Padrão de Formação Encontrado no Crescimento das Placas de Vidro.

De posse dessa padronização, foi desenvolvido o algoritmo para resolver o padrão de crescimento das placas:

inteiro[] geraSequenciaPlacas(int n){
                int[n] placa;
                int i=-1;
               
                se (n>2){   
                    se ((n>3) e (n%2==0)) {se par em vermelho}{
                                placa[++i] = n/2;
                                
                                se ((n>5) e (count >0)){
                                    incrementaPar++;
                                }
                    }
                    Senão ((n>3) e (n%2!=0)) {se impar em vermelho}{
                               placa[++i] = (n-1)/2;
                               placa[++i] = (n-1)/2;
                    }
                   
                    se(count>0) {parte em azul} {
   
                               enquanto (posicao < count){
                               arrayAux[posicao] = incrementaPar;
                               posicao++;
                               }
                              
                               count=0;
                              
                               j= posicao-1
                              
                               enquanto j>=0 decremente j-1 {
                                  se arrayAux[j] <> 0 {
                                               placa[++i]=arrayAux[j];
                                   }
                               }             
                    }
                   
                    placa[++i] = n-(n-1) {parte em verde};
                    placa[++i] = n-1 {parte em amarelo};
                    placa[++i] = n-1 {parte em amarelo};
                   
                    para j=0 se j<n incremente j+1 faça{
                               se (placa[j]==0){
                                   count++;
                               }
                    }
                   
                    se (count>0){
                               retorne geraSequenciaPlacas(n);
                    }
                }
                retorne placa;
    }
Listagem 3 - Algoritmo Desenvolvido para Geração das Seqüências de Placas.

A próxima geração de seqüência é apresentada na Tabela 6, onde é demonstrado o padrão de crescimento para os valores das possibilidades de k reflexões de placas de vidro. Uma explicação sobre como serão feitos os cálculos usando essa padronização será demonstrada adiante.

+K-1
+K-2
-K-3





3
+K-1
+K-2
-K-3
-K-4




4
+K-1
+K-2
-K-3
-K-4
+K-5



5
+K-1
+K-2
-K-3
-K-4
+K-5
+K-6


6
+K-1
+K-2
-K-3
-K-4
+K-5
+K-6
-K-7

7
+K-1
+K-2
-K-3
-K-4
+K-5
+K-6
-k-7
-k-8
8
Tabela 6 - Padrão de Formação das Possibilidades de k Reflexões por Número de Placas.

Conforme a geração dos termos dos polinômios foi encontrada uma nova seqüência de padronização para adição e subtração dos seus termos (Tabela 7).

+
+
-





3
+
+
-
-




4
+
+
-
-
+



5
+
+
-
-
+
+


6
+
+
-
-
+
+
-

7
+
+
-
-
+
+
-
-
8
Tabela 7 - Padrão de Formação das Operações por Número de Placas.

Com base nessa informação e simulação de casos de testes, foi possível desenvolver um algoritmo para resolver o padrão de crescimento das possibilidades de k reflexões e padrão de formação das operações por número de placas:

inteiro[] geraSequenciaTermos(int n){
            int[n] termos;
            string[n]operandos;
            int incrementaPares=1;
            String sinal="+";
           
            se (n>3){

                para i de 0 até n-1 {

                        termos[i] = n/2+i+1-n/2;

                        se (incrementaPares==3){
                           
                            if (sinal == "+")
                                   sinal="-";
                            else
                                   sinal="+";
                                      
                            incrementaPares=1;
                        }
                        operandos[i] = sinal;
                        incrementaPares++;
                }
            }
            retorne termos;
    }
Listagem 4 – Algoritmo para de termos do polinômio e seu operando.

De posse das informações contidas nas Tabelas 5, 6 e 7, cada linha dessas tabelas serão iteradas conjuntamente, buscando a formação de uma seqüência de polinômios, de acordo com a demonstração apresentada no Teorema 3 e Prova 3.

N-1 *
N-2 *
N-2 *
Tabela 5

K-1
K-2
K-3
Tabela 6


+
-
Tabela 7

N-1*K-1
+ N-2*K-2
-N-2 *k-3
Seqüência
N=3
3-1*6
+3-2*3
-3-2*1
Resultado
K=3
Tabela 8 - Cálculo dos Termos dos Polinômios.

O algoritmo inicia o cálculo para k reflexões com atribuição de valores para todo k < 3 da mesma forma que apresentada na solução anterior para 3 placas de vidro, pois não houve mudança nesse padrão. Quando o valor de k >= 3 é realizado o cálculo de cada termo do polinômio, que depende da quantidade de placas e reflexões. O resultado de cada termo é acumulado e realizado o cálculo repetidamente até findar o cálculo de todos os termos da seqüência. Essa iteração é demonstrada nas Tabelas 8 e 9, onde k possibilidades são calculadas utilizando uma seqüência de polinômios gerada automaticamente pelo algoritmo, dada a configuração inicial de 3 placas e 3 reflexões.


N-1*K-1
+ N-2*K-2
-N-2 *k-3
Seqüência
N=3

3-1*31
+3-2*14
-3-2*6

k=6

S= 62
S =S + 14 = 76
S = S -6 = 70
Resultado

Possibilidades K
1
3
6
14
31
70

Tabela 9 – Simulação do Algoritmo para 3 Placas.


N-2*k-1
+N-1*K-2
-N-3*K-3
-N-3*k-4
N=4

4-2*73
+4-1*27
-4-3*8
-4-3*4
k=6

S= 146
S=S+ 81 = 227
S= S -8 = 219
S=S -4 = 215

Possibilidades K
1
4
8
27
73
215



N-2*k-1
+N-2*K-2
-N-1*K-3
-N-4*k-4
+N-4 *K-5
N=5

5-2*132
+5-2*41
-5-1*10
-5-4*5
+5-4*1
k=3

S= 396
S=S+123= 519
S=S -40 = 479
S=S-5 = 474
S=S-1= 475

Possibilidades K
1
5
10
41
132
475




Após a averiguação dos resultados com base nos casos de testes, foi possível desenvolver o algoritmo final para calcular as possibilidades de n de placas e k reflexões:

Inteiro CalculePlacas(int p, int r)
Int k = 0;
long soma = 0;
int[] placa;
int[] termo;
String[] operando;
long[] possibilidades;

Se (r = 0)
            Retorne 1
Se (r >=1 e r <=2)
            Retorne r * p
Senão
     placa = geraSequenciaPlacas(p);
     termo = geraSequenciaTermos(p);

      possibilidades[k] = 1
      possibilidades[k++] = p
      possibilidades[k++] = 2* p

       Para i=3 to reflexões faça
            Para j=0 até j < termo.lenght – (termo.lenght-k) Faça
               Se (operando[j+1]=="+")
       soma = soma + p-placa[j] * possibilidades[k-termo[j]]
  Senão
                  soma = soma - p-placa[j] * possibilidades[k-termo[j]]
               Fim- Para

            Se (p>i) {
                 possibilidades[k++] = soma;
                    soma = 0;
}
     Fim – Para
Retorne Numero
Listagem 5 – Algoritmo para Calcular as Possibilidades de Placas maiores que 2.

Assim, é exibida a combinação dos algoritmos desenvolvidos neste trabalho para solução de qualquer configuração de n placas e k reflexões:

Inteiro CalculaCombinacoes(int placa, int reflexao)
Se placa = 1 Então
Retorne 1
Se placa = 2 Então
Retorne CalculeDuasPlacas(placa, reflexao)
Se placa > 2 Então
                Retorne CalculePlacas(placa, reflexao)
Listagem 6 – Algoritmo Proposto para Solução do Problema.

Complexidade

De posse da solução algorítmica foi possível realizar o cálculo da sua complexidade, que será apresentado brevemente. A complexidade do algoritmo desenvolvido para calcular duas placas de vidro pode ser dada pela análise de sua recorrência, onde Θ(log n), conforme demonstração exibida na listagem 7.

T(n) = T(k-1) + T(K-2)
T(n) = 2T(K-3)

2 (2T(k-2)+K-4) = 4T(K-2)+K-4
4(2T(K-4)+K-8) = 8T(K-4)+K-8
8(2T(K-6)+K-16) =16T(K-6)+K-16

<![if !msEquation]><![endif]>T(K-<![if !msEquation]><![endif]>)+<![if !msEquation]><![endif]>
T(n) = <![if !msEquation]><![endif]> + T(K-<![if !msEquation]><![endif]>+<![if !msEquation]><![endif]>
T(n) = log n + T(K-log n) + K-log n
T(n) = log n

Θ(g(n)) = {f(n): 0 ≤ 1 ≤ f(n) ≤ log n}
Listagem 7 – Complexidade do Algoritmo para Cálculo de 2 Placas.

A complexidade total do algoritmo para solução do problema proposto é O(<![if !msEquation]><![endif]>) ou quadrática, pois o trecho de maior complexidade é o cálculo de 3 placas ou mais, onde existem duas iterações para o cálculo do termos das seqüências de polinômios. O cálculo realizado nas iterações pode ser dado pelos seguintes somatórios <![if !msEquation]><![endif]>.

Resultados

Os resultados (Tabela 10) foram obtidos com base em diversas configurações até o limite proposto no estudo (16) para que pudesse ser feita uma comparação de resultados com outros trabalhos.

Configuração
Possibilidades
2 placas e 2 reflexões
3.0

3 placas e 3 reflexões
14.0

4 placas e 4 reflexões
73.0

5 placas e 5 reflexões
475.0

6 placas e 6 reflexões
2595.0

7 placas e 7 reflexões
32559.0

8 placas e 8 reflexões
228846.0

9 placas e 9 reflexões
3990398.0

10 placas e 10 reflexões
3.2507383E7

11 placas e 11 reflexões
7.4364286E8

12 placas e 12 reflexões
6.871305104E9

13 placas e 13 reflexões
1.96500637364E11

14 placas e 14 reflexões
2.026070737423E12

15 placas e 15 reflexões
7.0003023618478E13

16 placas e 16 reflexões
7.95674567041916E14

Tabela 10 – Resultados.
Conclusão

O problema proposto buscava determinar de quantas formas um raio de luz poderia sofrer k reflexões em uma pilha de n placas de vidro. O estudo realizou simulações para reconhecer um padrão de recorrência e em seguida apresentou soluções com teoremas e provas para 2 e 3 placas. Após a verificação dos casos de testes, foi descoberto um padrão de crescimento em relação ao aumento das placas de vidro. Assim, generalizando a solução para atender o padrão, tornou-se possível realizar o cálculo de k possibilidades. A aproximação utilizada foi a geração de polinômios, dada uma configuração inicial (placa e reflexões), onde foi gerada automaticamente uma seqüência de solução para a recorrência encontrada de acordo com a quantidade de placas de vidro. Após a construção e execução do algoritmo, os resultados foram apresentados em uma simulação com base em diversas configurações de n placas e k reflexões até o limite de 16 placas e 16 reflexões (Tabela 10).

Este estudo utilizou uma junção de diversas técnicas de análise de algoritmos, como: reconhecimento de padrões, sistemas lineares e programação dinâmica, entretanto, podem existir outras soluções para o mesmo problema originadas de uma forma mais simples a partir da análise das recorrências. Um dos objetivos principais do autor ao evidenciar a aplicação conjunta de tais técnicas, foi aprimorar os estudos das técnicas de análise de algoritmos e se preparar para resolver problemas computacionais com nível de complexidade igual ou ainda maior que o problema proposto neste trabalho.

Inscreva-se

Creative Commons 3.0. Tecnologia do Blogger.

Teste a Velocidade da Internet

Siga-me

Curta