terça-feira, outubro 29, 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]>
<![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]>
<![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]>.
<![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.
